Codeforces Round #312 (Div. 2) E. A Simple Task T12 D43

[传送门]( Problem - 558E - Codeforces )

思路

建26棵线段树，线段树节点表示每一个字母再这段区间的数量。

k=0时，字典序倒叙遍历线段树，对于每一个字母，查找这段区间的数量，再把这颗线段树[l,r]覆盖为零，再将[be,be+cnt-1]这段区间覆盖为1； be为上一个字母覆盖的末尾

k=1,字典序遍历，同上。

最后遍历26棵线段树填字符串即可。

参考代码

#include<bits/stdc++.h>
#define pb push_back
#define ll  long long
#define fi first
#define se second
#define ull unsigned long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (t[i][p].l+t[i][p].r)/2
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const int qs=2e5+17;
const int inf = 0x3f3f3f3f;
struct Tree{
	int l,r,add,val;
	#define l(i,x) t[i][x].l
	#define r(i,x) t[i][x].r
	#define add(i,x) t[i][x].add
	#define val(i,x) t[i][x].val
}t[30][qs<<2];
int n,q;
string s;

void build(int i,int p,int l,int r){
	l(i,p)=l,r(i,p)=r;
	add(i,p)=-1;
	if(l==r){
		int fp=s[l-1]-'a';
		if(fp==i) val(i,p)=1;
		else val(i,p)=0;
		return;
	}
	build(i,ls,l,mid);
	build(i,rs,mid+1,r);
	val(i,p)=val(i,ls)+val(i,rs);
}

void down(int i,int p){
	if(add(i,p)==-1) return;
	val(i,ls)=(r(i,ls)-l(i,ls)+1)*add(i,p);
	val(i,rs)=(r(i,rs)-l(i,rs)+1)*add(i,p);
	add(i,ls)=add(i,rs)=add(i,p);
	add(i,p)=-1;
}

int ask(int i,int p,int l,int r){
	if(l<=l(i,p)&&r>=r(i,p)){
		return val(i,p);
	}
	down(i,p);
	int val=0;
	if(l<=mid) val+=ask(i,ls,l,r);
	if(r>mid) val+=ask(i,rs,l,r);
	return val;
}

void modify(int i,int p,int l,int r,int k){
	if(l<=l(i,p)&&r>=r(i,p)){
		val(i,p)=(r(i,p)-l(i,p)+1)*k;
		add(i,p)=k;
		return;
	}
	down(i,p);
	if(l<=mid) modify(i,ls,l,r,k);
	if(r>mid) modify(i,rs,l,r,k);
	val(i,p)=val(i,ls)+val(i,rs);
}

void forans(int i,int p){
	if(l(i,p)==r(i,p)){
		if(val(i,p)==1) s[l(i,p)-1]=('a'+i);
		return;
	}
	down(i,p);
	if(val(i,ls)) forans(i,ls);
	if(val(i,rs)) forans(i,rs);
}

int main(){
	n=read(),q=read();
	cin>>s;
	for(int i=0;i<26;++i){
		build(i,1,1,n);
	}
    
    while(q--){
    	int l,r,k,e,f,x,be;
    	l=read(),r=read(),k=read();
    	if(k==0) f=25,e=-1,x=-1;
    	else f=0,e=26,x=1;
    	be=l;
    	for(int i=f;i!=e;i+=x){
    		int cnt=ask(i,1,l,r);
    		if(cnt==0) continue;
    		modify(i,1,l,r,0);
        	modify(i,1,be,be+cnt-1,1);

    		be=be+cnt;
		}	
	}
	for(int i=0;i<26;++i){
			forans(i,1);	
	}
    cout<<s<<"\n";
    return 0;
}