Codeforces 558E A Simple Task（计数排序+线段树优化）

http://codeforces.com/problemset/problem/558/E

Examples

input 1

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

output 1

cbcaaaabdd

input 2

10 1
agjucbvdfk
1 10 1

output 2

abcdfgjkuv

题意：
给出一个字母的序列（只包含小写字母），每次对它的一个区间进行排序（递增或递减），问最后的字母序列。

自闭题，身为蒟蒻的我读完题后单纯的觉得这题如名字一一样一个简单的任务（完全没有意识到问题的严重性），直接sort走起，结果。。。该题数据规模很大排序是关键，要想到计数排序

看了题解，真好，26颗线段树，人否？

题解：
采用计数排序的复杂度是O(n∗q)，无法通过，但有所启示。
可以看出计数就是区间求和，排序就是区间更新，可以用线段树维护。
做法是建立26棵线段树，第i棵树维护第i个字母的位置信息。
计数时，在26棵线段树内对[L,R]分别做一次查询，统计区间[L,R]中每个字母的个数，排序时根据递增还是递减，在相应的区间内按照字母的顺序（升序或降序）依次重新填进区间内。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <string>
  5 #include <math.h>
  6 #include <algorithm>
  7 #include <queue>
  8 #include <set>
  9 #include <math.h>
 10 const int INF=0x3f3f3f3f;
 11 typedef long long LL;
 12 const int mod=1e9+7;
 13 const double PI=acos(-1);
 14 const int maxn=1e5+10;
 15 using namespace std;
 16 
 17 int n,q;
 18 char str[maxn];
 19 
 20 struct Tree
 21 {
 22     int sum;
 23     int l;
 24     int r;
 25     int lazy;
 26 };
 27 
 28 struct SegmentTree
 29 {
 30     Tree tree[maxn<<2];
 31     void PushUp(int rt)
 32     {
 33         tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
 34     }
 35     void PushDown(int rt)
 36     {
 37         int lazy=tree[rt].lazy;
 38         if(lazy!=-1)
 39         {
 40             tree[rt<<1].lazy=tree[rt<<1|1].lazy=lazy;
 41             tree[rt<<1].sum=(tree[rt<<1].r-tree[rt<<1].l+1)*lazy;
 42             tree[rt<<1|1].sum=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*lazy;
 43             tree[rt].lazy=-1;
 44         }
 45     }
 46     void Build(int rt,int l,int r,int id)//建树 
 47     {
 48         tree[rt].l=l;
 49         tree[rt].r=r;
 50         tree[rt].lazy=-1;
 51         if(l==r)
 52         {
 53             if(str[l]-'a'==id) tree[rt].sum=1;
 54             else tree[rt].sum=0;
 55             return ;
 56         }
 57         int m=(l+r)>>1;
 58         Build(rt<<1,l,m,id);
 59         Build(rt<<1|1,m+1,r,id);
 60         PushUp(rt);
 61     }
 62     void Update(int rt,int L,int R,int v)//区间更新 
 63     {
 64         int l=tree[rt].l;
 65         int r=tree[rt].r;
 66         if(L<=l&&R>=r)
 67         {
 68             tree[rt].sum=(r-l+1)*v;
 69             tree[rt].lazy=v;
 70             return ;
 71         }
 72         PushDown(rt);
 73         int m=(l+r)>>1;
 74         if(L<=m&&R>=l)
 75             Update(rt<<1,L,R,v);
 76         if(R>m&&L<=r)
 77             Update(rt<<1|1,L,R,v);
 78         PushUp(rt);
 79     }
 80     int Query(int rt,int L,int R)//区间查询 
 81     {
 82         int l=tree[rt].l;
 83         int r=tree[rt].r;
 84         if(L<=l&&R>=r)
 85             return tree[rt].sum;
 86         PushDown(rt);
 87         int m=(l+r)>>1;
 88         int sum=0;
 89         if(L<=m&&R>=l)
 90             sum+=Query(rt<<1,L,R);
 91         if(R>m&&L<=r)
 92             sum+=Query(rt<<1|1,L,R);
 93         return sum;
 94     }
 95 }SegTree[26];
 96 
 97 
 98 int main()
 99 {
100     scanf("%d %d",&n,&q);
101     scanf("%s",str+1);
102     for(int i=0;i<26;i++)//建立26个线段树 
103     {
104         SegTree[i].Build(1,1,n,i);
105     }
106     while(q--)
107     {
108         int a,b,c;
109         scanf("%d %d %d",&a,&b,&c);
110         int num[26];//记录区间内每个字母的个数 
111         for(int i=0;i<26;i++)
112         {
113             num[i]=SegTree[i].Query(1,a,b);
114             SegTree[i].Update(1,a,b,0);//将该区间内的字母消去 
115         }
116         int l=a;//l指向要填入区间的头 
117         if(c)//升序填入 
118         {
119             for(int i=0;i<26;i++)
120             {
121                 SegTree[i].Update(1,l,l+num[i]-1,1);
122                 l+=num[i];
123             }
124         }
125         else//降序填入 
126         {
127             for(int i=25;i>=0;i--)
128             {
129                 SegTree[i].Update(1,l,l+num[i]-1,1);
130                 l+=num[i];
131             }
132         }
133     }
134     for(int i=1;i<=n;i++)
135     {
136         for(int j=0;j<26;j++)
137         {
138             if(SegTree[j].Query(1,i,i))
139             {
140                 printf("%c",j+'a');
141             }
142         }
143     }
144     printf("
");
145     return 0;
146 }