题意：

给定一个长度为n的仅包含'B'、'C'、'S'三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。

题解：

恶心的树状数组题。首先先求出只有一种字符的最长字串。然后预处理出前缀和。题目要求满足

cnt[1][i]-cnt[1][j]!=cnt[2][i]-cnt[2][j] cnt[2][i]-cnt[2][j]!=cnt[3][i]-cnt[3][j] cnt[1][i]-cnt[1][j]!=cnt[3][i]-cnt[3][j]

化简得到cnt[1][i]-cnt[2][i]!=cnt[1][j]-cnt[2][j] cnt[2][i]-cnt[3][i]!=cnt[2][j]-cnt[3][j] cnt[1][i]-cnt[3][i]!=cnt[1][j]-cnt[3][j]

把cnt[1][i]-cnt[2][i],cnt[2][i]-cnt[3][i],cnt[1][i]-cnt[3][i]分别当成xi,yi,zi，题目就转化成对每个i，求一个j使它们的xyz不同且i与j相差最大。首先以x为关键字排序，接着以y（离散化除掉负数，用链表法，如果用排序法会T）为下标建树状数组，树状数组维护6个值：之前处理过的位置的最大最小值、最大最小值对应的z，与最大最小值的z不同的最大最小值。为什么要维护最小值呢？因为按x排序后位置先后顺序会不一样，可能会出现位置靠后的比位置靠前先处理的情况。使x不同的具体方法，就是对于x相同的一组位置，先对它们一起分别查询更新答案，更新答案完后再一起分别插入树状数组。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define maxn 1000010 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define lb(x) x&-x 7 #define INF 0x3fffffff 8 using namespace std; 9 10 struct nd{
   int id,cnt[3];}; nd nds[maxn]; struct e{
   int v,n;}; int ess,g[maxn<<1]; e es[maxn];11 void pe(int a,int b){es[++ess]=(e){a,g[b]}; g[b]=ess;}12 int ans,n,tot; char s[maxn];13 struct bit{
   int mn1,mnz,mn2,mx1,mxz,mx2;}; bit bits1[maxn],bits2[maxn];14 bool cmp1(nd a,nd b){
   return a.cnt[0]
        
         bits1[b].mx1){48             if(a.cnt[2]!=bits1[b].mxz)49                 bits1[b].mxz=a.cnt[2],bits1[b].mx2=bits1[b].mx1,bits1[b].mx1=a.id;50             else bits1[b].mx1=a.id;51         }else if(a.cnt[2]!=bits1[b].mxz&&a.id>bits1[b].mx2)bits1[b].mx2=a.id;52         b+=lb(b);53     }54 }55 void update2(nd a){56     int b=a.cnt[1];57     while(b){58         if(a.id
         
          bits2[b].mx1){64             if(a.cnt[2]!=bits2[b].mxz)65                 bits2[b].mxz=a.cnt[2],bits2[b].mx2=bits2[b].mx1,bits2[b].mx1=a.id;66             else bits2[b].mx1=a.id;67         }else if(a.cnt[2]!=bits2[b].mxz&&a.id>bits2[b].mx2)bits2[b].mx2=a.id;68         b-=lb(b);69     }70 }71 int main(){72     scanf("%d",&n); scanf("%s",s+1); int cnt[3]={
   0,0,0};73     int l=1,r=1; while(r<=n){
   while(r<=n&&s[l]==s[r])ans=max(ans,r-l+1),r++; l++;}74     nds[0]=(nd){
   0,{
   0,0,0}};75     inc(i,1,n){76         if(s[i]=='B')cnt[0]++; if(s[i]=='C')cnt[1]++; if(s[i]=='S')cnt[2]++;77         nds[i]=(nd){i,{cnt[0]-cnt[1],cnt[0]-cnt[2],cnt[1]-cnt[2]}};78     }79     ess=0; inc(i,0,n)pe(i,nds[i].cnt[1]+n+1); tot=0;80     inc(i,0,n*2+1)if(g[i]){81         tot++; int x=g[i]; while(x)nds[es[x].v].cnt[1]=tot,x=es[x].n;82     }83     inc(i,1,tot)bits1[i]=bits2[i]=(bit){INF,0,INF,0,0,0}; sort(nds,nds+n+1,cmp1); int i=0;84     while(i<=n){85         int j=i; while(j<=n&&nds[j].cnt[0]==nds[i].cnt[0])j++;86         if(i)inc(k,i,j-1){query1(nds[k]); query2(nds[k]);}87         inc(k,i,j-1){update1(nds[k]); update2(nds[k]);}88         i=j;89     }90     printf("%d",ans); return 0;91 }
         
        
       
      
     

 

20160627