题目链接:Topcoder----洛谷
题目大意:
给定一个长为n的由a到z组成的字符串,有m次操作,每次操作将[l,r]这些位置的字符进行重排,得到字典序最小的回文字符串,如果无法操作就不进行。
思路:
用26颗线段树分别统计在每个位置上是否有对应的字母
每次操作:
1.有出现次数为奇数的字母:
大于1,不可能回文,无法操作。
等于1,放到中间
2.全是偶数次数:
分别放两端
1 # include<bits/stdc++.h> 2 using namespace std; 3 #define endl "\n" 4 # define int long long 5 # define ls u<<1 6 # define rs u<<1|1 7 const int N = 1e5 + 10; 8 char a[N], p; 9 int n, m; 10 struct segtree { 11 int sum[4 * N], lazy[4 * N]; 12 void pushup(int u) { 13 sum[u] = (sum[ls] + sum[rs]); 14 } 15 16 void build(int tr, int u, int l, int r) { 17 lazy[u] = -1; 18 if (l == r) { 19 sum[u] = ((a[l] - 'a' ) == tr); 20 return; 21 } 22 int mid = l + r >> 1; 23 build(tr, ls, l, mid); 24 build(tr, rs, mid + 1, r); 25 pushup(u); 26 } 27 28 void pushdown(int u, int l, int r) { 29 int mid = l + r >> 1; 30 if (lazy[u] != -1) { 31 sum[ls] = (mid - l + 1) * lazy[u]; 32 sum[rs] = (r - mid) * lazy[u]; 33 34 lazy[ls] = lazy[u]; 35 lazy[rs] = lazy[u]; 36 lazy[u] = -1; 37 } 38 39 } 40 41 void modify(int u, int l, int r, int L, int R, int c) { 42 if (l > r || l > R || r < L) return; 43 if (L <= l && r <= R) { 44 sum[u] = (r - l + 1) * c; 45 lazy[u] = c; 46 return; 47 } 48 int mid = l + r >> 1; 49 pushdown(u, l, r); 50 if (L <= mid) modify(ls, l, mid, L, R, c); 51 if (mid + 1 <= R) modify(rs, mid + 1, r, L, R, c); 52 pushup(u); 53 } 54 55 int query(int u, int l, int r, int L, int R) { 56 if (l > r || l > R || r < L) return 0; 57 if (l >= L && r <= R) { 58 return sum[u]; 59 } 60 pushdown(u, l, r); 61 int mid = l + r >> 1; 62 int ans = 0; 63 if (L <= mid) ans += query(ls, l, mid, L, R); 64 if (R > mid) ans += query(rs, mid + 1, r, L, R); 65 return ans; 66 } 67 } tr[26]; 68 69 signed main() { 70 ios::sync_with_stdio(false); 71 cin.tie(0); 72 cout.tie(0); 73 freopen("input.txt", "r", stdin); 74 freopen("output.txt", "w", stdout); 75 cin >> n >> m; 76 string s; 77 cin >> s; 78 for (int i = 1; i <= n; ++i) a[i] = s[i - 1]; 79 for (int i = 0; i < 26; ++i) tr[i].build(i, 1, 1, n); 80 for (int t = 1; t <= m; ++t) { 81 int l, r; 82 cin >> l >> r; 83 int odd = 0; 84 int tmp[26] = {0}, key; 85 for (int i = 0; i < 26; ++i) tmp[i] = tr[i].query(1, 1, n, l, r);//记录在区间[l,r]中每个字母出现的次数 86 for (int i = 0; i < 26; ++i) if (tmp[i] & 1) odd++, key = i; 87 if (odd > 1) continue; 88 for (int i = 0; i < 26; ++i) tr[i].modify(1, 1, n, l, r, 0); 89 if (odd) { 90 --tmp[key]; 91 tr[key].modify(1, 1, n, (l + r) / 2, (l + r) / 2, 1);//奇数置中 92 } 93 int nl = l, nr = r; 94 for (int i = 0; i < 26; ++i) {//偶数分两边放 95 if (tmp[i]) { 96 tr[i].modify(1, 1, n, nl, nl + tmp[i] / 2 - 1, 1); 97 nl += tmp[i] / 2; 98 tr[i].modify(1, 1, n, nr - tmp[i] / 2 + 1, nr, 1); 99 nr -= tmp[i] / 2; 100 } 101 } 102 } 103 for (int i = 1; i <= n; ++i) { 104 for (int j = 0; j < 26; ++j) { 105 if (tr[j].query(1, 1, n, i, i)) { 106 cout << (char)(j + 'a'); 107 } 108 } 109 } 110 return 0; 111 }
标签:tmp,CF240F,26,int,线段,tr,lazy,mid From: https://www.cnblogs.com/empty-y/p/16796213.html