题目描述：

Description

This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.

Output the final string after applying the queries.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input

The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively.

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, ).

Output

Output one line, the string S after applying the queries.

Sample Input

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

 

10 1
agjucbvdfk
1 10 1

Sample Output

cbcaaaabdd

abcdfgjkuv

思路:

题目的意思是，给定一个字符串，有q个询问，要把区间[l,r]的字符根据k的值升序(k=1)，或降序(k=0)改变。

因为字母集有26个字母，就可以建立27棵线段树分别维护区间上每个字母出现的次数，一般地，第i棵线段树维护字母i-1+'a'的数目。

维护字母在区间上出现的次数有什么用？想想我们要做的事情，就是把区间[l,r]上的排一个序，字母集有限，想到计数排序，用一个27大小(0不存)的cnt数组，cnt[i]记录字母i出现的次数

如果k是1，则下标从1开始，如果对应那一项不为0，说明区间这个位置要被覆盖成i，就直接覆盖掉原来的线段树对应区间[l,r]上记录的字母i出现的次数，注意这里是直接覆盖，而不是累加，所以要修改线段树模板的区间和的upgrade函数的sum[a][r]+=改为sum[a][r]=，（a表示字母a对应的线段树）对应的懒标记也改为=。

一开始由于循环写的有点长（值代码长度），把计数的变量写叉了，有因为上面没有注意是最直接覆盖，一直出现out of bound错误，一开始还莫名其妙，搞了一个上午一直到晚上才知道写错了(╯‵□′)╯︵┻━┻，bug真好写，改是真难。

一开始写得麻烦了，比如把区间修改成字母a，然后我还在后面有把在这个区间上的，原来的对应的字母对应的线段树，一个位置一个位置的修改，然后提交，超时。。。

咋办嘞？原来只要在开始输入l,r那会统计每个字母在这个区间上出现次数后，紧接着立马删掉原来的数据（区间上的数据全置0），这么一改，好家伙，连样例都过不了了-_-||

找了半天，然后联想到这题的直接覆盖的不同寻常之处，也就是不同于区间和，才发现懒标记我标的有问题，没有懒标记我标0，懒标记为0（区间清零要用的）的还是0，那我在pushdown的时候怎么区分这两种情况呢？

咋办？标奇偶！神奇，覆盖的标记是1，清零的标记是2，没有标记的是0，这样就可以区分，那我咋使用呢？lz%2就行，1就是1,2就是0，可以正常使用了。

这题思路清晰，就是要注意细节，果然还是我太菜了。。

知识点：线段树的覆盖（自编题目）

代码：（开了氧气上瘾了）（注释依稀可见我超时的地方）

  1 #include <iostream>
  2 #include <cstring>
  3 #include <memory.h>
  4 #define max_n 100005
  5 using namespace std;
  6 char s[max_n];
  7 int sum[27][max_n<<2];
  8 int lz[27][max_n<<2];
  9 int cnt[27];
 10 int n;
 11 int q;
 12 int k;
 13 void pushup(int a,int r)
 14 {
 15     sum[a][r] = sum[a][r<<1]+sum[a][r<<1|1];
 16 }
 17 void build(int a,int r,int lc,int rc)
 18 {
 19     if(lc==rc)
 20     {
 21         if(a==s[lc]-'a'+1)
 22         sum[a][r] = 1;
 23         lz[a][r] = 0;
 24         return;
 25     }
 26     int mid = (lc+rc)>>1;
 27     build(a,r<<1,lc,mid);
 28     build(a,r<<1|1,mid+1,rc);
 29     pushup(a,r);
 30 }
 31 void pushdown(int a,int r,int ln,int rn)
 32 {
 33     if(lz[a][r])
 34     {
 35         //cout << "r" << r << endl;
 36         sum[a][r<<1] = ln*(lz[a][r]%2);//注意这里的改变
 37         sum[a][r<<1|1] = rn*(lz[a][r]%2);//还有这里
 38         lz[a][r<<1] = lz[a][r];
 39         lz[a][r<<1|1] = lz[a][r];
 40         lz[a][r] = 0;
 41     }
 42 }
 43 void upgrade(int a,int r,int L,int R,int lc,int rc,int val)
 44 {
 45     if(L<=lc&&rc<=R)
 46     {
 47         sum[a][r] = (rc-lc+1)*(val%2);//这里，这里！
 48         lz[a][r] = val;//直接覆盖就是等于哦
 49         return;
 50     }
 51     int mid = (lc+rc)>>1;
 52     pushdown(a,r,mid-lc+1,rc-mid);
 53     if(L<=mid) upgrade(a,r<<1,L,R,lc,mid,val);
 54     if(mid<R) upgrade(a,r<<1|1,L,R,mid+1,rc,val);
 55     pushup(a,r);
 56 }
 57 int query(int a,int r,int L,int R,int lc,int rc)
 58 {
 59     if(L<=lc&&rc<=R)
 60     {
 61         return sum[a][r];
 62     }
 63     int mid = (lc+rc)>>1;
 64     pushdown(a,r,mid-lc+1,rc-mid);
 65     int res = 0;
 66     if(L<=mid) res += query(a,r<<1,L,R,lc,mid);
 67     if(mid<R) res += query(a,r<<1|1,L,R,mid+1,rc);
 68     return res;
 69 }
 70 #pragma optimize(2)
 71 int main()
 72 {
 73     cin >> n >> q;
 74     for(int i = 1;i<=n;i++)
 75     {
 76         cin >> s[i];
 77     }
 78     for(int i = 1;i<=26;i++)
 79     {
 80         build(i,1,1,n);
 81     }
 82     int l,r,k;
 83     for(int i=0;i<q;i++)
 84     {
 85         cin >> l >> r >> k;
 86         for(int j = 1;j<=26;j++)
 87         {
 88             cnt[j] = query(j,1,l,r,1,n);
 89             upgrade(j,1,l,r,1,n,2);//直接清零
 90         }
 91         if(k==1)
 92         {
 93             int lp = l;
 94             for(int p = 1; p<=26; p++)
 95             {
 96                 if(cnt[p])
 97                 {
 98                     char ch =p+'a'-1;
 99                     //cout << ch << ":" << cnt[p] << endl;
100                     upgrade(p,1,lp,lp+cnt[p]-1,1,n,1);
101                     lp = lp+cnt[p];
102                     /*for(int j = 0; j<cnt[p];j++)
103                     {
104                         upgrade(s[lp]-'a'+1,1,lp,lp,1,n,-1);
105                         s[lp]=p+'a'-1;
106                         lp++;
107                     }*/
108                 }
109             }
110             /*for(int i = 1; i<=n; i++)
111             {
112                 cout << s[i];
113             }
114             cout << endl;*/
115         }
116         else
117         {
118             int lp = l;
119             for(int p = 26; p>=1; p--)
120             {
121                 if(cnt[p])
122                 {
123                     char ch = p+'a'-1;
124                     //cout << ch << ":" << cnt[p] << endl;
125                     upgrade(p,1,lp,lp+cnt[p]-1,1,n,1);
126                     lp = lp+cnt[p];
127                     /*for(int j = 0; j<cnt[p];j++)
128                     {
129                         upgrade(s[lp]-'a'+1,1,lp,lp,1,n,-1);
130                         s[lp] = p+'a'-1;
131                         lp++;
132                     }*/
133 
134                 }
135             }
136             /*for(int i = 1; i<=n; i++)
137             {
138                 cout << s[i];
139             }
140             cout << endl;*/
141         }
142     }
143     for(int i = 1;i<=n;i++)
144     {
145         for(int j = 1;j<27;j++)
146         {
147             cnt[j] = query(j,1,i,i,1,n);
148             if(cnt[j])
149             {
150                 char ch = j-1+'a';
151                 cout << ch;
152             }
153         }
154     }
155     cout << endl;
156     return 0;
157 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄