| 1234567 |
- #include <array>
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- struct Node{array<int,26> count{};int lazy=-1;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;string s;cin>>n>>q>>s;vector<Node>tr(4*n);auto pull=[&](int u){for(int c=0;c<26;++c)tr[u].count[c]=tr[u*2].count[c]+tr[u*2+1].count[c];};auto apply=[&](int u,int l,int r,int c){tr[u].count.fill(0);tr[u].count[c]=r-l+1;tr[u].lazy=c;};auto push=[&](int u,int l,int r){if(tr[u].lazy<0||l==r)return;int m=(l+r)/2;apply(u*2,l,m,tr[u].lazy);apply(u*2+1,m+1,r,tr[u].lazy);tr[u].lazy=-1;};auto build=[&](auto&&self,int u,int l,int r)->void{if(l==r){tr[u].count[s[l]-'a']=1;return;}int m=(l+r)/2;self(self,u*2,l,m);self(self,u*2+1,m+1,r);pull(u);};auto assign=[&](auto&&self,int u,int l,int r,int ql,int qr,int c)->void{if(qr<l||r<ql)return;if(ql<=l&&r<=qr){apply(u,l,r,c);return;}push(u,l,r);int m=(l+r)/2;self(self,u*2,l,m,ql,qr,c);self(self,u*2+1,m+1,r,ql,qr,c);pull(u);};auto ask=[&](auto&&self,int u,int l,int r,int ql,int qr)->array<int,26>{if(ql<=l&&r<=qr)return tr[u].count;push(u,l,r);int m=(l+r)/2;array<int,26>z{};if(ql<=m){auto a=self(self,u*2,l,m,ql,qr);for(int c=0;c<26;++c)z[c]+=a[c];}if(qr>m){auto a=self(self,u*2+1,m+1,r,ql,qr);for(int c=0;c<26;++c)z[c]+=a[c];}return z;};build(build,1,0,n-1);while(q--){int l,r,k;cin>>l>>r>>k;--l;--r;auto cnt=ask(ask,1,0,n-1,l,r);int pos=l;if(k==1){for(int c=0;c<26;++c)if(cnt[c])assign(assign,1,0,n-1,pos,pos+cnt[c]-1,c),pos+=cnt[c];}else{for(int c=25;c>=0;--c)if(cnt[c])assign(assign,1,0,n-1,pos,pos+cnt[c]-1,c),pos+=cnt[c];}}for(int i=0;i<n;++i){auto x=ask(ask,1,0,n-1,i,i);for(int c=0;c<26;++c)if(x[c])cout<<char('a'+c);}cout<<'\n';}
|
