string
【题目描述】
给定一个由小写字母组成的字符串 s。有 m 次操作,每次操作给
定 3 个参数 l,r,x。如果 x=1,将 s[l]~s[r]升序排序;如果 x=0,将 s[l]~s[r]
降序排序。你需要求出最终序列。
【输入数据】
第一行两个整数 n,m。第二行一个字符串 s。接下来 m 行每行三
个整数 x,l,r。
【输出数据】
一行一个字符串表示答案。
【样例输入】
5 2
cabcd
1 3 1
3 5 0
【样例输出】
abdcc
【数据范围】
对于 40%的数据,n,m<=1000。
对于 100%的数据,n,m<=100000。
题解：
正解不明，但可以写出nlogn*26*26的线段树（然而只比暴力多10分）。
看到一共只有26个字母，考虑枚举每个字母，统计在区间内部的个数，那么对于每种字母，显然如果按顺序排序，那么显然是从a~z，一个一个区间覆盖，区间清空。
线段树实现，当然lz打的是区间覆盖的标记，只要当前这个节点的元素值是什么，那么其他儿子节点的元素值就什么，就实现了区间清空和区间加法。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 110000
#define RG register
using namespace std;
struct node{
int lz,l,r,sum[];
}a[MAXN*];
int n,q;
char ch[MAXN];
int chuan[MAXN],tot[]; inline void pushup(int xv){
for(int i=;i<=;i++) a[xv].sum[i]=a[xv*].sum[i]+a[xv*+].sum[i];
} inline void pushdown(int xv,int x,int y){
if(a[xv].lz){
a[xv].lz=;
for(int i=;i<=;i++){
if(a[xv].sum[i]==) a[xv*].sum[i]=a[xv*+].sum[i]=;
else a[xv*].sum[i]=x,a[xv*+].sum[i]=y;
}
a[xv*].lz=a[xv*+].lz=;
}
} inline void build(int xv,int l,int r){
if(l==r){
a[xv].l=l,a[xv].r=r,a[xv].lz=;
memset(a[xv].sum,,sizeof(a[xv].sum));
a[xv].sum[chuan[l]]=;
return;
}
a[xv].l=l,a[xv].r=r;
int mid=(l+r)/;
build(xv*,l,mid),build(xv*+,mid+,r);
pushup(xv);
} inline int query(int xv,int l,int r,int k){
RG int L=a[xv].l,R=a[xv].r,mid=(L+R)/;
if(L==l&&R==r){
return a[xv].sum[k];
}
pushdown(xv,mid-L+,R-mid);
if(r<=mid) return query(xv*,l,r,k);
else if(l>mid) return query(xv*+,l,r,k);
else return query(xv*,l,mid,k)+query(xv*+,mid+,r,k);
} inline void update(int xv,int l,int r,int k){
RG int L=a[xv].l,R=a[xv].r,mid=(L+R)/;
if(l==L&&R==r){
memset(a[xv].sum,,sizeof(a[xv].sum));
a[xv].sum[k]=r-l+;
a[xv].lz=;
return;
}
pushdown(xv,mid-L+,R-mid);
if(r<=mid) update(xv*,l,r,k);
else if(l>mid) update(xv*+,l,r,k);
else update(xv*,l,mid,k),update(xv*+,mid+,r,k);
pushup(xv);
} inline int query2(int xv,int ps){
RG int L=a[xv].l,R=a[xv].r,mid=(L+R)/;
if(L==R){
for(int i=;i<=;i++)
if(a[xv].sum[i]) return i;
}
pushdown(xv,mid-L+,R-mid);
if(ps<=mid) return query2(xv*,ps);
else return query2(xv*+,ps);
} int main()
{
scanf("%d%d",&n,&q);
scanf("%s",ch+);
for(int i=;i<=n;i++) chuan[i]=ch[i]-'a';
build(,,n);
while(q--){
int l,r,x;scanf("%d%d%d",&l,&r,&x);
if(l>r) swap(l,r);
memset(tot,,sizeof(tot));
for(int i=;i<=;i++) tot[i]+=query(,l,r,i);
if(x==){
int ll=l,rr=l-;
for(int i=;i<=;i++){
if(tot[i]!=){
rr+=tot[i];
update(,ll,rr,i);
ll=rr+;
}
}
}
else{
int ll=l,rr=l-;
for(int i=;i>=;i--){
if(tot[i]!=){
rr+=tot[i];
update(,ll,rr,i);
ll=rr+;
}
}
}
}
for(int i=;i<=n;i++){
printf("%c",query2(,i)+'a');
}
return ;
}