CodeForces - 558E.A Simple Task字符串区间排序（计数排序+26棵线段树的维护）

Time limit ：5000 ms
Memory limit ： 524288 kB

This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k?=?1 or in non-increasing order if k?=?0.

Output the final string after applying the queries.

Input

The first line will contain two integers n,?q (1?≤?n?≤?105, 0?≤?q?≤?50?000), the length of the string and the number of queries respectively.

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i,?j,?k (1?≤?i?≤?j?≤?n, ).(0<=k<=1)

Output

Output one line, the string S after applying the queries.

Examples

Input

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

Output

cbcaaaabdd

Input

10 1
agjucbvdfk
1 10 1

Output

abcdfgjkuv

Note

First sample test explanation:

abacdabcda->abacdadcba
abacdadcba->abacacddba
abacacddba->cbaaacddba
cbaaacddba->cbcaaaddba
cbcaaaddba->cbcaaaabdd

题目大意：给你一个字符串，编号从1到n，给q次操作，每次操作为x,y,id，如果id为0就将区间[x,y]降序排序，否则按升序排序。

我们可以先STL大法暴力一波，可以跑到test 9,is_sorted是个好东西：

#include?using?namespace?std;const?int?mac=1e5+10;char?s[mac];int?a[mac];bool?cmpde(int?x,int?y){return?x>y;}bool?cmpin(int?x,int?y){return?x<y;}int?main(){
????int?n,q;
????scanf?("%d%d",&n,&q);
????scanf?("%s",s+1);
????for?(int?i=1;?i<=n;?i++)?a[i]=s[i]-‘a‘;
????while?(q--){
????????int?l,r,id;
????????scanf?("%d%d%d",&l,&r,&id);
????????if?(id==0)?{
????????????bool?yes?=?is_sorted(a?+?l,?a?+?1?+?r,?cmpde);
????????????if?(!yes)?sort(a+l,a+1+r,cmpde);
????????}
????????else?{
????????????bool?yes=is_sorted(a+l,a+1+r,cmpin);
????????????if?(!yes)?sort(a+l,a+1+r,cmpin);
????????}
????}
????for?(int?i=1;?i<=n;?i++)
????????????printf?("%c",a[i]+‘a‘);
????printf?("\n");
????return?0;}

然后想一想，我们可以用O（n）的计数排序，由于这里的所需要的空间非常小（将26个字母-‘a’只有26个数）我们只需要26个空间就够了，但如果也暴力求的话显然也跑不过去，那么我们可以用线段树维护每一个字母的空间位置。每颗线段树维护一个字母，询问和修改的时候就从0到25每个走一遍。最后的复杂度就是O(26 * q * logn)。为了方便写，我们可以将线段树的操作和线段树放到结构体里面封装。

以下是AC代码：

#include?using?namespace?std;#define?lson?l,mid,rt<<1#define?rson?mid+1,r,rt<<1|1#define?ls?rt<<1#define?rs?rt<<1|1#define?debug?printf?("**")const?int?mac=1e5+10;char?s[mac];int?a[mac];struct?Tree{
????int?sum,f;};struct?node{
????Tree?tree[mac<<2];

????void?build(int?l,int?r,int?rt,int?val)
????{
????????tree[rt].f=-1;
????????if?(l==r){
????????????if?(a[l]==val)?tree[rt].sum=1;
????????????else?tree[rt].sum=0;
????????????return;
????????}
????????int?mid=(l+r)>>1;
????????build(lson,val);build(rson,val);
????????tree[rt].sum=tree[ls].sum+tree[rs].sum;
????}

????void?pushdown(int?l,int?r,int?rt)
????{
????????int?mid=(l+r)>>1;
????????tree[ls].f=tree[rs].f=tree[rt].f;
????????tree[ls].sum=(mid-l+1)*tree[rt].f;
????????tree[rs].sum=(r-mid)*tree[rt].f;
????????tree[rt].f=-1;
????}

????void?update(int?l,int?r,int?rt,int?L,int?R,int?val)
????{
????????if?(l>=L?&&?r<=R)?{
????????????tree[rt].sum=(r-l+1)*val;
????????????tree[rt].f=val;
????????????return;
????????}
????????int?mid=(l+r)>>1;
????????if?(tree[rt].f!=-1)?pushdown(l,r,rt);
????????if?(mid>=L)?update(lson,L,R,val);
????????if?(mid<R)?update(rson,L,R,val);
????????tree[rt].sum=tree[ls].sum+tree[rs].sum;
????}

????int?query(int?l,int?r,int?rt,int?L,int?R)
????{
????????int?sum=0;
????????if?(l>=L?&&?r<=R)?return?tree[rt].sum;
????????int?mid=(l+r)>>1;
????????if?(tree[rt].f!=-1)?pushdown(l,r,rt);
????????if?(mid>=L)?sum+=query(lson,L,R);
????????if?(mid<R)?sum+=query(rson,L,R);
????????return?sum;
????}}sgtree[30];int?num[30];int?main(){
????int?n,q;
????scanf?("%d%d",&n,&q);
????scanf?("%s",s+1);
????for?(int?i=1;?i<=n;?i++)?a[i]=s[i]-‘a‘;
????for?(int?i=0;?i<26;?i++)?sgtree[i].build(1,n,1,i);
????while?(q--){
????????int?l,r,id;
????????scanf("%d%d%d",&l,&r,&id);
????????memset(num,0,sizeof?num);
????????for?(int?i=0;?i<26;?i++)?{
????????????num[i]?=?sgtree[i].query(1,?n,?1,?l,?r);//有多少个在区间里面
????????????sgtree[i].update(1,?n,?1,?l,?r,?0);//第i课线段树清空区间[l,r]
????????}
????????if?(id){//升序排序
????????????for?(int?i=0;?i<26;?i++){
????????????????if?(!num[i])?continue;
????????????????sgtree[i].update(1,n,1,l,l+num[i]-1,1);
????????????????l+=num[i];//对左端点的控制实现排序
????????????}
????????}
????????else?{//降序排序
????????????for?(int?i=25;?i>=0;?i--){
????????????????if?(!num[i])?continue;
????????????????sgtree[i].update(1,n,1,l,l+num[i]-1,1);
????????????????l+=num[i];
????????????}
????????}
????}
????for?(int?i=1;?i<=n;?i++){
????????for?(int?j=0;?j<26;?j++){//对每棵树询问i位置是否存在数
????????????if?(sgtree[j].query(1,n,1,i,i))?{
????????????????printf?("%c",j+‘a‘);
????????????????break;
????????????}
????????}
????}
????printf?("\n");
????return?0;}

? ? ? ? ? ? ? ?

CodeForces - 558E.A Simple Task字符串区间排序（计数排序+26棵线段树的维护）

原文：https://blog.51cto.com/u_15249461/2856320