题目链接：http://codeforces.com/contest/558/problem/E
题意: 给定一个字符串, m次操作, 每次操作一个区间, 0表示让这个区间降序, 1 表示升序, 问最后字符串的样子。
字符集只有26个，所以线段树维护区间内每个字母的数量，对于排序操作就直接暴力进行区间覆盖。
#include<bits/stdc++.h> #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) #define ls (o<<1) #define rs (o<<1|1) #define mid (l+r>>1) #define ll long long using namespace std; const int N = 1e5+100; int i,n,m,h,t; char s[N]; struct node{ int v[30],lz,len; }T[4*N]; void up(int o) { rep(i, 0, 25) T[o].v[i] = T[ls].v[i]+T[rs].v[i]; } void build(int o,int l,int r) { T[o].len = r-l+1; T[o].lz = -1; if(l==r) { T[o].v[s[l]-'a']++; return; } build(ls,l,mid); build(rs,mid+1,r); up(o); } void down(int o) { rep(i, 0, 25) { T[ls].v[i] = 0; T[rs].v[i] = 0; } int lz = T[o].lz; T[ls].v[lz] = T[ls].len; T[rs].v[lz] = T[rs].len; T[ls].lz = T[rs].lz = lz; T[o].lz = -1; } void add(int o,int l,int r,int h,int t,int x) { if(l>=h&&r<=t){ rep(i, 0, 25) T[o].v[i] = 0; T[o].v[x] = T[o].len; T[o].lz = x; return ; } if(T[o].lz!=-1) down(o); if(mid>=h) add(ls,l,mid,h,t,x); if(mid<t) add(rs,mid+1,r,h,t,x); up(o); } int query(int o,int l,int r,int h,int t,int x) { if(l>=h&&r<=t) return T[o].v[x]; if(T[o].lz!=-1) down(o); int ans = 0; if(mid>=h) ans += query(ls,l,mid,h,t,x); if(mid<t) ans += query(rs,mid+1,r,h,t,x); return ans; } int cnt[30]; int main() { // freopen("a.txt","r",stdin); ios::sync_with_stdio(0); cin>>n>>m; cin>>s+1; build(1,1,n); rep(i, 1, m) { int l,r,oper; cin>>l>>r>>oper; rep(j, 0, 25) cnt[j] = query(1,1,n,l,r,j); if(oper) { int now = l; rep(j, 0, 25) { if(cnt[j]==0) continue; add(1,1,n,now,now+cnt[j]-1,j); now += cnt[j]; } } else { int now = l; per(j, 25, 0) { if(cnt[j]==0) continue; add(1,1,n,now,now+cnt[j]-1,j); now += cnt[j]; } } } rep(i, 1, n) rep(j, 0, 25) if(query(1,1,n,i,i,j)) cout<<char(j+'a'); return 0; }
