CF558E A Simple Task

开一颗珂朵莉树，对于每个新的查询，先把l-1,l之间和r,r+1之间split开，然后对于剩下的部份用桶排序并暴力合并即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set> 
using namespace std;
const int N=100005;

struct Data{
	int l;int r;char id;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};
int n,q;
char ch[N];
std::set<Data> st;
inline void split(std::set<Data>::iterator it, int X){
	int l=it->l,r=it->r;char id=it->id;
	if(X<l||X>=r){
		return;
	}
	st.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});
}
int bckt[30];
inline void clr(){
	for(int i=0;i<26;++i){
		bckt[i]=0;
	}
}
inline void uni(int l,int r,int op){
	std::set<Data>::iterator itx,ity;
	itx=st.lower_bound((Data){0,l-1,0});
	split(itx,l-1);
	ity=st.lower_bound((Data){0,r,0});
	split(ity,r);
	itx=st.lower_bound((Data){0,l,0});
	ity=st.lower_bound((Data){0,r,0});
	++ity;
	for(std::set<Data>::iterator it=itx;it!=ity;++it){
		bckt[(it->id)-'a']+=(it->r)-(it->l)+1;
	}
	st.erase(itx,ity);
	int loc,nl=l;
	for(int i=0;i<26;++i){
		loc=op?i:(26-i-1);
		if(bckt[loc]<=0){
			continue;
		}
		st.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});
		nl+=bckt[loc];
	}
	clr();
}
inline void prnt(){
	for(std::set<Data>::iterator it=st.begin();it!=st.end();++it){
		for(int j=it->l;j<=it->r;++j){
			putchar(it->id);
		}
	}
	puts("");
}
inline void init(){
	scanf("%d%d",&n,&q);
	std::cin>>ch+1;
	for(int i=1;i<=n;++i){
		st.insert((Data){i,i,ch[i]});
	}
	int l,r,op;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&l,&r,&op);
		uni(l,r,op);
//		prnt();
	}
	prnt();
}

int main(){
	init();
	return 0;
}