noip11 string
这道题改题时我打了个玄学复杂度的暴力，然后我成功的造了一组数据hack掉了自己的代码。。。。
通过观察，我们可以很容易的发现在操作几次后，整个序列就会变成一块一块相同的字母。
于是我们可以对我们的暴力做一些优化：在将字母塞进桶中时，不是一个一个往里塞，而是将一段连续的区间O（1）塞进桶中。
实现也很简单：在每次操作后，存下每个块的左右端点，塞进去的时候注意把包含l,r的块断开，即可愉快的AC并且代码跑的快的飞起。
但是有一个问题：处理l,r所在块的边界时，需要暴力找到这两个块的边界，如果块特别大，那么每次寻找都是O（n）的，然后就愉快的T了（反正我自己造的100000个a跑了6s）
附超快AC代码：
1 #include<cstdio> 2 char s[100001],bx[100001];int br[100001],b[127],n,m; 3 main(){ 4 scanf("%d%d%s",&n,&m,s+1);br[n+1]=n+1; 5 for(int i=1;i<=n;++i)br[i]=i,bx[i]=s[i]; 6 for(int i=1,l,r,x;i<=m;++i){ 7 scanf("%d%d%d",&l,&r,&x); 8 int j;for(j=l;!br[j];--j); 9 int k=br[j]+1;if(j!=l)b[bx[j]]+=br[j]-l+1,br[j]=l-1;else k=j; 10 while(br[k]<=r){ 11 b[bx[k]]+=br[k]-k+1; 12 int lst=k;k=br[k]+1;br[lst]=0; 13 } 14 if(k<=r)b[bx[k]]+=r-k+1,br[r+1]=br[k],bx[r+1]=bx[k],br[k]=0; 15 if(x)for(char ch='a';ch<='z';++ch)if(b[ch])br[l]=l+b[ch]-1,bx[l]=ch,l=br[l]+1,b[ch]=0; 16 if(!x)for(char ch='z';ch>='a';--ch)if(b[ch])br[l]=l+b[ch]-1,bx[l]=ch,l=br[l]+1,b[ch]=0; 17 } 18 for(int i=1;i<=n;i=br[i]+1)for(int j=i;j<=br[i];++j)putchar(bx[i]); 19 }