CF 558E 线段树

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <string>
  5 #include <string.h>
  6 #include <stdio.h>
  7 #include <math.h>
  8 #include <stdlib.h>
  9 #include <queue>
 10 #include <stack>
 11 #include <map>
 12 #include <set>
 13 #include <ctime>
 14 #include <numeric>
 15 #include <cassert>
 16 
 17 using namespace std;
 18 
 19 const int N=1e5+100;
 20 
 21 char s[N];
 22 
 23 struct SegmentTree {
 24     #define M N*4
 25     int val[M];
 26     int flag[M];
 27     void up(int rt) {
 28         val[rt]=val[rt<<1]+val[rt<<1|1];
 29     }
 30     void build(int l,int r,int rt) {
 31         if (l==r) {
 32             val[rt]=0;
 33             flag[rt]=-1;
 34             return;
 35         }
 36         int m=(l+r)>>1;
 37         build(l,m,rt<<1);
 38         build(m+1,r,rt<<1|1);
 39         up(rt);
 40     }
 41     void down(int rt,int m=0) {
 42         if (flag[rt]!=-1) {
 43             flag[rt<<1]=flag[rt];
 44             flag[rt<<1|1]=flag[rt];
 45             if (flag[rt]==1){
 46                 val[rt<<1]=m-(m>>1);
 47                 val[rt<<1|1]=(m>>1);
 48             }
 49             else {
 50                 val[rt<<1]=0;
 51                 val[rt<<1|1]=0;
 52             }
 53             flag[rt]=-1;
 54         }
 55     }
 56     void update(int p,int c,int l,int r,int rt) {
 57         if (l==r) {
 58             val[rt]=c;
 59             return;
 60         }
 61         down(rt,r-l+1);
 62         int m=(l+r)>>1;
 63         if (p<=m)
 64             update(p,c,l,m,rt<<1);
 65         else
 66             update(p,c,m+1,r,rt<<1|1);
 67         up(rt);
 68     }
 69     void update(int L,int R,bool c,int l,int r,int rt) {
 70         if (L<=l&&r<=R) {
 71             val[rt]=c?(r-l+1):0;
 72             flag[rt]=c;
 73             return;
 74         }
 75         down(rt,r-l+1);
 76         int m=(l+r)>>1;
 77         if (L<=m) update(L,R,c,l,m,rt<<1);
 78         if (R>m) update(L,R,c,m+1,r,rt<<1|1);
 79         up(rt);
 80     }
 81     int query(int p,int l,int r,int rt) {
 82         if (l==r) {
 83             return val[rt];
 84         }
 85         down(rt,r-l+1);
 86         int m=(l+r>>1);
 87         if (p<=m) return query(p,l,m,rt<<1);
 88         else return query(p,m+1,r,rt<<1|1);
 89     }
 90     int query(int L,int R,int l,int r,int rt) {
 91         if (L<=l&&r<=R) {
 92             return val[rt];
 93         }
 94         down(rt,r-l+1);
 95         int m=(l+r)>>1;
 96         int ret=0;
 97         if (L<=m) ret+=query(L,R,l,m,rt<<1);
 98         if (R>m) ret+=query(L,R,m+1,r,rt<<1|1);
 99         return ret;
100     }
101     #undef M
102 }seg[26];
103 
104 int main() {
105     int n,q;
106     scanf("%d %d",&n,&q);
107     scanf("%s",s+1);
108     for (int i=0;i<26;i++)
109         seg[i].build(1,n,1);
110     for (int i=1;i<=n;i++) {
111         int p=s[i]-‘a‘;
112         seg[p].update(i,1,1,n,1);
113         //cout<<p<<" xxx"<<endl;
114     }
115     while (q--) {
116         int l,r,t;
117         scanf("%d %d %d",&l,&r,&t);
118         int cnt[26];
119         for (int i=0;i<26;i++) {
120             cnt[i]=seg[i].query(l,r,1,n,1);
121             if (cnt[i]>0){
122                 seg[i].update(l,r,0,1,n,1);
123             }
124         }
125         if (t==1) {
126             for (int i=0;i<26;l+=cnt[i++]){
127                 if (cnt[i]==0) continue;
128                 seg[i].update(l,l+cnt[i]-1,1,1,n,1);
129             }
130         }
131         else {
132             for (int i=25;i>=0;l+=cnt[i--]){
133                 if (cnt[i]==0) continue;
134                 seg[i].update(l,l+cnt[i]-1,1,1,n,1);
135             }
136         }
137     }
138     for (int i=1;i<=n;i++) {
139         for (int j=0;j<26;j++){
140             if (seg[j].query(i,1,n,1)) {
141                 s[i]=‘a‘+j;
142                 break;
143             }
144         }
145     }
146     s[n+1]=0;
147     printf("%s\n",s+1);
148     return 0;
149 }