string

题目描述

给定一个由小写字母组成的字符串s。有m次操作，每次操作给定3个参数l,r,x 。如果x=1，将 s[l]~s[r]升序排序；如果x=0，将s[l]~s[r]降序排序。你需要求出最终序列。

输入格式

第一行两个整数n,m，表示字符串长度为n，有m次操作。
第二行一个字符串。
接下来行每行三个整数l,r,x。

输出格式

一行一个字符串表示答案。

样例

样例输入

5 2
cabcd
1 3 1
3 5 0

样例输出

abdcc

数据范围与提示

对于100%的数据， n,m<=100000

思路：首先想到的是用sort水，不过sort是nlogn，所以只能谁40分。

　　　正解：线段树，用线段树维护一段区间内字母的个数，这时tree[maxn]数组记录的不是区间和而是如果tree[rt]统治的区间内符号相同，则tree[rt]为此符号的值类似于lazy标记（这样做为了优化一下时间效率）

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=100000+10;
 4 char s[maxn];
 5 int tree[maxn<<2],f[maxn],n;
 6 void Build(int rt,int l,int r){
 7     if(l==r){
 8         tree[rt]=s[l]-'a'+1;//注意要加1,不然若这个字符为a的话，tree为0,区分不出有没有字符标记
 9         return ;
10     }
11     int mid=(l+r)>>1;
12     Build(rt<<1,l,mid);
13     Build(rt<<1|1,mid+1,r);
14     if(tree[rt<<1]==tree[rt<<1|1]) tree[rt]=tree[rt<<1];//若左右子树相等，更新根节点
15 }
16 void pushdown(int rt,int l,int r){
17     if(tree[rt]){
18         tree[rt<<1]=tree[rt];
19         tree[rt<<1|1]=tree[rt];
20         tree[rt]=0;
21     }
22 }
23 void query(int rt,int l,int r,int s,int t){
24     if(s<=l&&t>=r&&tree[rt]){//若tree有值，再return
25         f[tree[rt]]+=(r-l+1);
26         return ;
27     }
28     pushdown(rt,l,r);
29     int mid=(l+r)>>1;
30     if(s<=mid) query(rt<<1,l,mid,s,t);
31     if(t>mid) query(rt<<1|1,mid+1,r,s,t);
32 }
33 void Modify(int rt,int l,int r,int s,int t,int w){
34     if(s<=l&&t>=r||tree[rt]==w){//写tree[rt]==w，会快一点
35         tree[rt]=w;
36         return;
37     }
38     pushdown(rt,l,r);
39     int mid=(l+r)>>1;
40     if(s<=mid) Modify(rt<<1,l,mid,s,t,w);
41     if(t>mid) Modify(rt<<1|1,mid+1,r,s,t,w);
42     if(tree[rt<<1]==tree[rt<<1|1]) tree[rt]=tree[rt<<1];
43 }
44 void solve(int l,int r,int x){
45     memset(f,0,sizeof(f));//记得初始化
46     query(1,1,n,l,r);//查询每个字母的数量
47     if(x==1){
48         int sum=l;
49         for(int i=1;i<=26;i++){
50             if(f[i]){
51                 Modify(1,1,n,sum,sum+f[i]-1,i);
52                 sum+=f[i];
53             }
54         }
55     }//正序，正着枚举
56     else{
57         int sum=l;
58         for(int i=26;i>=1;i--){
59             if(f[i]){
60                 Modify(1,1,n,sum,sum+f[i]-1,i);
61                 sum+=f[i];
62             }
63         }
64     }//倒序，倒着枚举
65 }
66 void print(int rt,int l,int r){
67     if(tree[rt]){
68         for(int i=l;i<=r;i++){
69             printf("%c",tree[rt]+'a'-1);
70         }
71         return;
72     }
73     int mid=(l+r)>>1;
74     print(rt<<1,l,mid);
75     print(rt<<1|1,mid+1,r);
76 }
77 int main(){
78     int m;
79     scanf("%d%d",&n,&m);
80     scanf("%s",s+1);
81     Build(1,1,n);
82     for(int i=1;i<=m;i++){
83         int l,r,x;
84         scanf("%d%d%d",&l,&r,&x);
85         solve(l,r,x);
86     }
87     print(1,1,n);
88     printf("
");
89     return 0;
90 }

View Code