JZOJ P5829 A. string
题面：https://www.cnblogs.com/Juve/articles/11286476.html
考场上想起了排序这道题：https://www.cnblogs.com/Juve/p/11269638.html
n遍二分？
亲测TLE，0分
你暴力sort都有40分
当然这题不用这样
我们借鉴排序的思路
我们用线段树来完成操作，那么我们想线段树存什么，懒标记是什么
借鉴刚才那道题，我们将节点信息和懒标记合二为一
设tr[k].val，如果k管辖的区间里的字母都是同一个字母，则tr[k].val就是那个字母，否则tr[k].val=0，
这样十分方便维护：
down：
if(!tr[k].val) return ;
tr[k<<1].val=tr[k<<1|1].val=tr[k].val;
up：
if(tr[k<<1].val==tr[k<<1|1].val)
tr[k].val=tr[k<<1].val;
我们每次对于一次排序[L,R]，查询[L,R]，中26个字母出现的次数cnt[i]，
实现：
if(opl<=l&&r<=opr&&tr[k].val){
cnt[tr[k].val]+=(r-l+1);
return ;
}
如果升序，就把[L,R]中前cnt[a]修改成a，接下来cnt[b]修改成b，。。。。。。
降序就反过来
最后输出也是一遍线段树dfs，然后。。。其实没什么了
来代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define MAXN 100005
#define re register
using namespace std;
int n,m,a[MAXN],cnt[28];
char ch[MAXN]
struct Segtree{
int l,r,val;
}tr[MAXN<<2];
void down(int k,int data){
if(!tr[k].val) return ;
tr[k<<1].val=tr[k<<1|1].val=tr[k].val;
tr[k].val=data;
}
void build(int k,int l,int r){
tr[k].l=l,tr[k].r=r;
if(l==r){
tr[k].val=a[l];
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
if(tr[k<<1].val==tr[k<<1|1].val)
tr[k].val=tr[k<<1].val;
}
void get_cnt(int k,int opl,int opr){
int l=tr[k].l,r=tr[k].r;
if(opl<=l&&r<=opr&&tr[k].val){
cnt[tr[k].val]+=(r-l+1);
return ;
}
down(k,tr[k].val);
int mid=(l+r)>>1;
if(opl<=mid) get_cnt(k<<1,opl,opr);
if(opr>mid) get_cnt(k<<1|1,opl,opr);
}
void change(int k,int opl,int opr,int data){
if(tr[k].val==data) return ;
int l=tr[k].l,r=tr[k].r;
if(opl<=l&&r<=opr){
tr[k].val=data;
return ;
}
down(k,0);
int mid=(l+r)>>1;
if(opl<=mid) change(k<<1,opl,opr,data);
if(opr>mid) change(k<<1|1,opl,opr,data);
if(tr[k<<1].val==tr[k<<1|1].val)
tr[k].val=tr[k<<1].val;
}
void print(int k){
if(tr[k].val){
int l=tr[k].l,r=tr[k].r;
for(int i=l;i<=r;i++)
putchar(tr[k].val-1+'a');
return ;
}
print(k<<1),print(k<<1|1);
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",ch+1);
for(re int i=1;i<=n;i++)
a[i]=ch[i]-'a'+1;
build(1,1,n);
for(re int i=1,x,l,r;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
memset(cnt,0,sizeof(cnt));
get_cnt(1,l,r);
if(x==0){
for(re int j=26;j>=1;j--){
change(1,l,l+cnt[j]-1,j);
l+=cnt[j];
}
}else{
for(re int j=1;j<=26;j++){
change(1,l,l+cnt[j]-1,j);
l+=cnt[j];
}
}
}
print(1);
puts("");
return 0;
}