string [线段树优化桶排]

题意大概是给你一个字符串，1e5次修改，每次给一个区间升序排列或降序排列，最后输出这个字符串;

其实是个挺裸的线段树优化题;但是我没有意识去结合桶排，扑该.....

首先 1.40分算法

O(NMlogN)

 1 inline void update(int k){
 2     for(int i=1;i<=26;++i){
 3         tmp[k].tong[i]=tmp[ls].tong[i]+tmp[rs].tong[i];
 4     }
 5 }
 6 
 7 void ud(int k,int l,int r,int L,int R){
 8     if(L<=l&&r<=R)return void();
 9     if(L<=mid)ud(ls,l,mid,L,R);
10     if(R>mid)ud(rs,mid+1,r,L,R);
11     update(k);
12

直接sort

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define val(x) (x-'a'+1)
 4 int s[100050],N,M;
 5 char S[100050];
 6 bool cmp1(int a,int b){return a<b;}
 7 bool cmp0(int a,int b){return a>b;}
 8 int main()
 9 {
10     //freopen("da.in","r",stdin);
11    // freopen("ac.out","w",stdout);
12     scanf("%d%d",&N,&M);
13     scanf("%s",S+1);
14     for(int i=1;i<=N;++i)s[i]=val(S[i]);
15     for(int i=1,l,r,opt;i<=M;++i){
16         scanf("%d%d%d",&l,&r,&opt);
17         if(!opt)sort(s+l,s+r+1,cmp0);
18         else sort(s+l,s+r+1,cmp1);
19        // if(clock()>999900)break;
20     }
21     char c;
22     for(int i=1;i<=N;++i){
23         c=s[i]+'a'-1;
24         printf("%c",c);
25     }
26     printf("
");
27 }

其次 2.仍是40分算法：

其实也是出题人没良心，我们可以直接桶排，复杂度O(NM);起码降下了一个log，但还是40分;

代码就不提供了;

最后 3.100分算法：

思路：结合2.中的桶排思想，我们发现修改排序一次可以只有O(N)的复杂度，而N,M<=1e5，自然想到线段树优化桶排;

而这样想的裸想法的复杂度是O（MNlogN）氧化钙！跟暴力一样！

但是可以发现你的数值N的值域是你的字母，那N就只有26啦;

最后O(MlogN*26)

分析一下 M是询问; logN是线段树上的查询（合并桶而需查询你所修改的区域的桶来合成一个新的桶）; 26是每次桶合并所需复杂度;

好，接下来，我们每次修改一个区间进行排序，就是把对应区间的桶合并成一个新桶，然后用这个新桶进行区间修改，但是注意，这个区间修改一定不要去真的O(N)区间赋值

那就成为了真正的O（NMlogN）了;

那怎么办？

我们可以打懒标记啊！别说你像我一样不会打标记......

那我们就可以标记哪个区间被修改了然后访问到再down一下，最后一遍dfs来一次全down统计答案对吧;

注意，这里down很长很长

 1 void down(int k){
 2     if(!tmp[k].lazy)return ;
 3     register int sz=len(ls),pl=0,pr=0;
 4     memset(tmp[ls].tong,0,sizeof(tmp[ls].tong));
 5     memset(tmp[rs].tong,0,sizeof(tmp[rs].tong));
 6     if(tmp[k].opt){
 7         for(int i=1;i<=26;++i){
 8             if(tmp[k].tong[i]<=sz)
 9             {
10                 tmp[ls].tong[i]=tmp[k].tong[i],sz-=tmp[k].tong[i];
11             }
12             else {
13                 tmp[ls].tong[i]=sz;sz=i;break;
14             }
15         }
16         tmp[rs].tong[sz]=tmp[k].tong[sz]-tmp[ls].tong[sz];
17         if(len(rs)==1&&tmp[rs].tong[sz]==1){pr=sz;}
18         register int zs=len(rs)-tmp[rs].tong[sz];
19         for(int i=sz+1;i<=26;++i){
20             tmp[rs].tong[i]=tmp[k].tong[i];
21             zs-=tmp[k].tong[i];
22             if(!zs)break;
23         }
24     }
25     else {
26         for(int i=26;i>=1;--i){
27             if(tmp[k].tong[i]<=sz)
28             {
29                 tmp[ls].tong[i]=tmp[k].tong[i],sz-=tmp[k].tong[i];
30             }
31             else {
32                 tmp[ls].tong[i]=sz;sz=i;break;
33             }
34         }
35         tmp[rs].tong[sz]=tmp[k].tong[sz]-tmp[ls].tong[sz];
36         register int zs=len(rs)-tmp[rs].tong[sz];
37         for(int i=sz-1;i>=1;--i){
38             tmp[rs].tong[i]=tmp[k].tong[i];
39             zs-=tmp[k].tong[i];
40             if(!zs)break;
41         }
42     }
43     if(tmp[ls].l!=tmp[ls].r)tmp[ls].lazy=1;
44     else tmp[ls].lz=pl;tmp[ls].opt=tmp[k].opt;
45     if(tmp[rs].l!=tmp[rs].r)tmp[rs].lazy=1;
46     else tmp[rs].lz=pr;tmp[rs].opt=tmp[k].opt;
47     tmp[k].lazy=0;tmp[k].opt=0;
48 }

当然我不像Deepin某一样缩行;

其实这里的down就是把你线段树上这个节点的两个儿子所对应区间的桶重新赋值的过程，当然赋值一次需要O（52）;

Tip：

还有一点特别容易错的就是

记住每次把你对应修改的区间的桶合并后要立即修改对应区间的桶（区间修改）：（这里lg这个vector存放的是你修改的区间的在线段树上的节点编号）

 1 void exch(int opt){
 2     sort(lg.begin(),lg.end(),cmp);
 3     for(int i=0,sz,tt=1,ts=26;i<lg.size();++i){
 4         sz=len(lg[i]);
 5         memset(tmp[lg[i]].tong,0,sizeof(tmp[lg[i]].tong));
 6         if(opt){
 7             for(;tt<=26;++tt){
 8             if(sz>=ans[tt]){
 9                 sz-=ans[tt];
10                 tmp[lg[i]].tong[tt]=ans[tt];
11             }
12             else {
13                 tmp[lg[i]].tong[tt]=sz;
14                 ans[tt]-=sz;break;
15             }
16             }
17         }
18         else {
19             for(;ts>=1;--ts){
20                         if(sz>=ans[ts]){
21                             sz-=ans[ts];
22                             tmp[lg[i]].tong[ts]=ans[ts];
23                         }
24                         else {
25                             tmp[lg[i]].tong[ts]=sz;
26                             ans[ts]-=sz;break;
27                         }
28             }
29         }
30     }
31 }

区间修改

然后修改完后要立即把你这些修改的区间到根update一遍，毕竟你的懒标记只能维护儿子而不能维护父亲;

 1 inline void update(int k){
 2     for(int i=1;i<=26;++i){
 3         tmp[k].tong[i]=tmp[ls].tong[i]+tmp[rs].tong[i];
 4     }
 5 }
 6 
 7 
 8 void ud(int k,int l,int r,int L,int R){
 9     if(L<=l&&r<=R)return void();
10     if(L<=mid)ud(ls,l,mid,L,R);
11     if(R>mid)ud(rs,mid+1,r,L,R);
12     update(k);
13 }

update

然后附上代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define val(x) (x-'a'+1)
  4 #define mid (l+r>>1)
  5 #define ls (k<<1)
  6 #define rs (k<<1|1)
  7 #define len(x) (tmp[x].r-tmp[x].l+1)
  8 int s[100050],N,M;
  9 char S[100050];
 10 struct node{
 11    int l;int r;
 12    int tong[30];
 13    int lazy,lz,opt;
 14 }tmp[100050<<3];
 15 int ans[30];
 16 vector<int>lg;
 17 
 18 inline void update(int k){
 19     for(int i=1;i<=26;++i){
 20         tmp[k].tong[i]=tmp[ls].tong[i]+tmp[rs].tong[i];
 21     }
 22 }
 23 
 24 void down(int k){
 25     if(!tmp[k].lazy)return ;
 26     register int sz=len(ls),pl=0,pr=0;
 27     memset(tmp[ls].tong,0,sizeof(tmp[ls].tong));
 28     memset(tmp[rs].tong,0,sizeof(tmp[rs].tong));
 29     if(tmp[k].opt){
 30         for(int i=1;i<=26;++i){
 31             if(tmp[k].tong[i]<=sz)
 32             {
 33                 tmp[ls].tong[i]=tmp[k].tong[i],sz-=tmp[k].tong[i];
 34            //     if(len(ls)==1&&tmp[ls].tong[i]){pl=i;break;}
 35             }
 36             else {
 37                 tmp[ls].tong[i]=sz;sz=i;break;
 38             }
 39         }
 40         //for(int i=1;i<=sz-1;++i)tmp[rs].tong[i]=0;
 41         //for(int i=sz+1;i<=26;++i)tmp[ls].tong[i]=0;
 42         tmp[rs].tong[sz]=tmp[k].tong[sz]-tmp[ls].tong[sz];
 43         if(len(rs)==1&&tmp[rs].tong[sz]==1){pr=sz;}
 44         register int zs=len(rs)-tmp[rs].tong[sz];
 45         for(int i=sz+1;i<=26;++i){
 46             tmp[rs].tong[i]=tmp[k].tong[i];
 47             zs-=tmp[k].tong[i];
 48             if(!zs)break;
 49         //    if(len(rs)==1&&tmp[rs].tong[i]&&!pr)pr=i;
 50         }
 51     }
 52     else {
 53         for(int i=26;i>=1;--i){
 54             if(tmp[k].tong[i]<=sz)
 55             {
 56                 tmp[ls].tong[i]=tmp[k].tong[i],sz-=tmp[k].tong[i];
 57                // if(len(ls)==1&&tmp[ls].tong[i]){pl=i;break;}
 58             }
 59             else {
 60                 tmp[ls].tong[i]=sz;sz=i;break;
 61             }
 62         }
 63         //for(int i=26;i>=sz+1;--i)tmp[rs].tong[i]=0;
 64         //for(int i=1;i<=sz-1;++i)tmp[ls].tong[i]=0;
 65         tmp[rs].tong[sz]=tmp[k].tong[sz]-tmp[ls].tong[sz];
 66         //if(len(rs)==1&&tmp[rs].tong[sz]==1){pr=sz;}
 67         register int zs=len(rs)-tmp[rs].tong[sz];
 68         for(int i=sz-1;i>=1;--i){
 69             tmp[rs].tong[i]=tmp[k].tong[i];
 70             zs-=tmp[k].tong[i];
 71             if(!zs)break;
 72           //  if(len(rs)==1&&tmp[rs].tong[i]&&!pr)pr=i;
 73         }
 74     }
 75     if(tmp[ls].l!=tmp[ls].r)tmp[ls].lazy=1;
 76     else tmp[ls].lz=pl;tmp[ls].opt=tmp[k].opt;
 77     if(tmp[rs].l!=tmp[rs].r)tmp[rs].lazy=1;
 78     else tmp[rs].lz=pr;tmp[rs].opt=tmp[k].opt;
 79     tmp[k].lazy=0;tmp[k].opt=0;
 80 }
 81 
 82 inline void merge(int u,int opt){
 83     down(u);
 84     for(register int i=1;i<=26;++i){
 85         ans[i]+=tmp[u].tong[i];
 86     }
 87     if(len(u)>1)tmp[u].lazy=1;lg.push_back(u);
 88     tmp[u].opt=opt;
 89 }
 90 
 91 inline int zip(int k){
 92     //cout<<"laidao!"<<endl;
 93     for(int i=1;i<=26;++i)if(tmp[k].tong[i])return i;
 94 }
 95 
 96 void find(int k,int l,int r){
 97     if(l==r)return s[l]=zip(k),void();
 98     down(k);
 99     find(ls,l,mid);
100     find(rs,mid+1,r);
101 }
102 
103 void query(int k,int l,int r,int L,int R,int opt){
104     if(L<=l&&r<=R)return merge(k,opt),void();
105     down(k);
106     if(L<=mid)query(ls,l,mid,L,R,opt);
107     if(R>mid)query(rs,mid+1,r,L,R,opt);
108 }
109 
110 void ud(int k,int l,int r,int L,int R){
111     if(L<=l&&r<=R)return void();
112     if(L<=mid)ud(ls,l,mid,L,R);
113     if(R>mid)ud(rs,mid+1,r,L,R);
114     update(k);
115 }
116 
117 void building(int k,int l,int r){
118     tmp[k].l=l;tmp[k].r=r;
119     if(l==r)return  tmp[k].l=tmp[k].r=l,tmp[k].tong[s[l]]=1,tmp[k].lazy=tmp[k].opt=0,void();
120     building(ls,l,mid);building(rs,mid+1,r);
121     update(k);
122 }
123 
124 bool cmp(int u,int v){return tmp[u].l<tmp[v].l;}
125 
126 void exch(int opt){
127     sort(lg.begin(),lg.end(),cmp);
128     for(int i=0,sz,tt=1,ts=26;i<lg.size();++i){
129         sz=len(lg[i]);
130         memset(tmp[lg[i]].tong,0,sizeof(tmp[lg[i]].tong));
131         if(opt){
132             for(;tt<=26;++tt){
133             if(sz>=ans[tt]){
134                 sz-=ans[tt];
135                 tmp[lg[i]].tong[tt]=ans[tt];
136             }
137             else {
138                 tmp[lg[i]].tong[tt]=sz;
139                 ans[tt]-=sz;break;
140             }
141             }
142         }
143         else {
144             for(;ts>=1;--ts){
145                         if(sz>=ans[ts]){
146                             sz-=ans[ts];
147                             tmp[lg[i]].tong[ts]=ans[ts];
148                         }
149                         else {
150                             tmp[lg[i]].tong[ts]=sz;
151                             ans[ts]-=sz;break;
152                         }
153             }
154         }
155     }
156 }
157 int main()
158 {
159     //freopen("da.in","r",stdin);
160     //freopen("te.out","w",stdout);
161     scanf("%d%d",&N,&M);
162     scanf("%s",S+1);
163     for(int i=1;i<=N;++i)s[i]=val(S[i]);
164     building(1,1,N);
165     for(int i=1,l,r,opt;i<=M;++i){
166         scanf("%d%d%d",&l,&r,&opt);
167         memset(ans,0,sizeof(ans));lg.clear();
168         query(1,1,N,l,r,opt);
169         exch(opt);
170         ud(1,1,N,l,r);
171     }
172     find(1,1,N);
173     char c;
174     for(int i=1;i<=N;++i){
175         c=s[i]+'a'-1;
176         printf("%c",c);
177     }
178     printf("
");
179     //int ppx='P'-'a'+1;
180     //cout<<"ppx="<<ppx<<endl;
181 }