CodeForces - 558E A Simple Task——线段树 + 计数排序

CodeForces - 558E A Simple Task——线段树 + 计数排序

题意：给定一个字符序列，每次可以把一个区间变成升序或者降序，求最终的字符序列

思路：

sort的复杂度为nlog（n），总共是n^2 log（n），超时

计数排序的复杂度为n，总共是n^2,还是会超时

所以要用到线段树优化计数排序中数字的统计，优化到26 * log（n），这样总复杂度是n * 26 log(n)，不会超时

那么如何优化呢？现在我们需要对于给出的区间马上算出其中a，b，c。。。z的总数，可以用26棵线段树维护26个字符在每个区间的数量（叶节点存0或1,0代表没有字符，1代表有字符），这样一来循环26次就可以求出a到z的总数。

那么如何更新线段树呢？假设当前区间为【L, R】，要更新为升序，而且现在已经知道了26个字母在这个区间的数量。

第一步26棵线段树的【L, R】更新为0；

第二步设一个变量pos，初始为L；

第三步，从a到z循环26次（降序的话从z到a），对于每一个字符，如果它的数量不为0，就把区间【pos，pos + 当前字符的数量】更新为1；

第四步pos += 当前字符的数量

这样的话就能实现更新了（慵懒标记、下推什么的按照平时的线段树写就行）

输出看代码最后就行了，不是很难懂，不做介绍了

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;char str[maxn];int n, q, segTree[26][maxn<<2], lazy[26][maxn<<2];void init() { for (int i = 0; i < 26; i++) { for (int j = 0; j <= n * 4; j++) { lazy[i][j] = -1; } }}void pushup(int root, int flag) { segTree[flag][root] = segTree[flag][root<<1] + segTree[flag][root<<1|1];}void pushdown(int root, int flag, int cntL, int cntR) { if (lazy[flag][root] != -1) { lazy[flag][root<<1] = lazy[flag][root<<1|1] = lazy[flag][root]; segTree[flag][root<<1] = lazy[flag][root] * cntL; segTree[flag][root<<1|1] = lazy[flag][root] * cntR; lazy[flag][root] = -1; }}void build(int L, int R, int root, int flag) { if (L == R) { if (str[L - 1] == 'a' + flag) segTree[flag][root] = 1; else segTree[flag][root] = 0; return; } int mid = (L + R)>>1; build(L, mid, root<<1, flag); build(mid + 1, R, root<<1|1, flag); pushup(root, flag);}void update_interval(int L, int R, int root, int uL, int uR, int val, int flag) { if (uL <= L && R <= uR) { segTree[flag][root] = (R - L + 1) * val; lazy[flag][root] = val; return; } int mid = (L + R)>>1; pushdown(root, flag, mid - L + 1, R - mid); if (uL <= mid) { update_interval(L, mid, root<<1, uL, uR, val, flag); } if (uR > mid) { update_interval(mid + 1, R, root<<1|1, uL, uR, val, flag); } pushup(root, flag);}int query(int L, int R, int root, int qL, int qR, int flag) { if (qL <= L && R <= qR) { return segTree[flag][root]; } int mid = (L + R)>>1; pushdown(root, flag, mid - L + 1, R - mid); int temp = 0; if (qL <= mid) { temp += query(L, mid, root<<1, qL, qR, flag); } if (qR > mid) { temp += query(mid + 1, R, root<<1|1, qL, qR, flag); } return temp;}int main(){ scanf("%d %d", &n, &q); scanf("%s", str); init(); for (int i = 0; i < 26; i++) { build(1, n, 1, i); } while (q--) { int x, y, z; scanf("%d %d %d", &x, &y, &z); if (x > y) swap(x, y); int cnt[26] = {0}; for (int i = 0; i < 26; i++) { cnt[i] = query(1, n, 1, x, y, i); update_interval(1, n, 1, x, y, 0, i); } int pos = x; if (z == 0) { for (int i = 25; i >= 0; i--) { if (cnt[i]) { update_interval(1, n ,1, pos, pos + cnt[i] - 1, 1, i); } pos += cnt[i]; } } else { for (int i = 0; i < 26; i++) { if (cnt[i]) { update_interval(1, n, 1, pos, pos + cnt[i] - 1, 1, i); } pos += cnt[i]; } } } for (int i = 1; i <= n; i++) { for (int j = 0; j < 26; j++) { if (query(1, n, 1, i, i, j)) { printf("%c", j + 'a'); break; } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。