题目大意就是给一个字符串，然后多个操作，每次操作可以把每一段区间的字符进行升序或者降序排序，问最终的字符串是怎样的。
做法的话就是用线段树维护区间和
一开始只考虑字符串中字符’a’的情况，假设操作区间[L,R]中有x个’a’,那么一次操作后，这x个’a’要么去最左(升序)，要么去最右(降序),我们可以建立一颗线段树来维护这样的操作，字符’a’出现的位置值为1，否则为0，那么q次操作后，最后值为1的地方填的就是’a’了。
然后，在考虑字符’a’和’b’的情况，，操作的情况和上面类似，字符’a’和’b’出现的位置值为1，否则为0，q次操作后，如果一个位置的值为1，并且该位置没有填写’a’，那么这个位置就填写’b’。
接下来的情况以此类推，考虑abc，abcd，……，abcd…z。
时间复杂度O(26*(n+q)logn)。
#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;struct Tree{int l,r,sum;}tree[int(4e5)];void create(int l,int r,int k){tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int m=l+r>>1;create(l,m,k<<1);create(m+1,r,k<<1|1);}void lazy(int k){if(tree[k].l!=tree[k].r&&tree[k].sum!=tree[k<<1].sum+tree[k<<1|1].sum){if(tree[k].sum==0)tree[k<<1].sum=tree[k<<1|1].sum=0;else{tree[k<<1].sum=tree[k<<1].r-tree[k<<1].l+1;tree[k<<1|1].sum=tree[k<<1|1].r-tree[k<<1|1].l+1;}}}void update(int l,int r,bool flag,int k){lazy(k);if(l==tree[k].l&&r==tree[k].r){tree[k].sum=flag?r-l+1:0;return;}int m=tree[k].l+tree[k].r>>1;if(r<=m)update(l,r,flag,k<<1);else if(l>m)update(l,r,flag,k<<1|1);else{update(l,m,flag,k<<1);update(m+1,r,flag,k<<1|1);}tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;}int seek(int l,int r,int k){lazy(k);if(l==tree[k].l&&r==tree[k].r)return tree[k].sum;int m=tree[k].l+tree[k].r>>1;if(r<=m)return seek(l,r,k<<1);if(l>m)return seek(l,r,k<<1|1);return seek(l,m,k<<1)+seek(m+1,r,k<<1|1);}void update(int l,int r,bool flag){int t=seek(l,r,1);if(flag){if(l<=l+t-1)update(l,l+t-1,1,1);if(l+t<=r)update(l+t,r,0,1);}else{if(r-t+1<=r)update(r-t+1,r,1,1);if(l<=r-t)update(l,r-t,0,1);}}struct Box{int l,r;bool flag;}box[int(1e5)+10];int ans[int(1e5)+10];int main(){int n,q;cin>>n>>q;create(1,n,1);string s;cin>>s;for(int i=0;i<q;i++)cin>>box[i].l>>box[i].r>>box[i].flag;for(int i=0;i<26;i++){update(1,n,0,1);for(int j=0;j<n;j++)if(s[j]<=i+'a')update(j+1,j+1,1,1);for(int j=0;j<q;j++)update(box[j].l,box[j].r,box[j].flag);for(int j=0;j<n;j++)if(ans[j]==0&&seek(j+1,j+1,1)==1)ans[j]=i+'a';}for(int i=0;i<n;i++)putchar(ans[i]);}
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
This task is very simple. Given a stringSof lengthnandqqueries each query is on the formatijkwhich means sort the substring consisting of the characters fromitojin non-decreasing order ifk=1or in non-increasing order ifk=0.
Output the final string after applying the queries.
Input
The first line will contain two integersn,q(1≤n≤105,0≤q≤50000), the length of the string and the number of queries respectively.
Next line contains a stringSitself. It contains only lowercase English letters.
Nextqlines will contain three integers eachi,j,k(1≤i≤j≤n,).
Output
Output one line, the stringSafter applying the queries.
Sample test(s)
input
10 5abacdabcda7 10 05 8 11 4 03 6 07 10 1
output
cbcaaaabdd
input
10 1agjucbvdfk1 10 1
output
abcdfgjkuv
Note
First sample test explanation:
版权声明：本文为博主原创文章，未经博主允许不得转载。
学习会使你永远立于不败之地。
