【BZOJ4384】[POI2015]Trzy wieże
Description
给定一个长度为n的仅包含'B'、'C'、'S'三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。
Input
第一行包含一个正整数n(1<=n<=1000000)，表示字符串的长度。
第二行一个长度为n的字符串。
Output
包含一行一个正整数，即最长的满足条件的子串的长度。
Sample Input
9
CBBSSBCSC
CBBSSBCSC
Sample Output
6
HINT
选择BSSBCS这个子串。
题解：挺吓人的一道题~
只有一种颜色的情况直接处理，下面只说多种颜色的情况。
我们对于每个颜色维护前缀和xi,yi,zi，然后将子串和变成前缀相减。一段区间中没有两种颜色颜色相同，即这两端点的xi-yi,yi-zi,xi-zi都不相同。于是这就变成了一个类似三维偏序的问题。
先按x排序干掉一维，然后用两个以y为下标的树状数组干掉一维，最后一维怎么办呢？我们对于树状数组的每个节点维护位置的最小值，最小值的z值，以及位置的次小值，要求最小值和次小值的z不能相同。还有最大值。然后查询时用最小值或次小值更新答案，就没了、、、
最后还卡了一发常数才过~
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000010;
int n,ans,sum;
char str[maxn];
struct node
{
int x,y,z,v;
}p[maxn];
bool cmp(const node &a,const node &b)
{
return a.x<b.x;
}
int a1[maxn<<1],a2[maxn<<1],b1[maxn<<1],b2[maxn<<1],c1[maxn<<1],c2[maxn<<1],d1[maxn<<1],d2[maxn<<1];
inline int max(int a,int b) {return a>b?a:b;}
inline void updata(int x)
{
register int i,z=p[x].z,v=p[x].v;
for(i=p[x].y;i<=2*n+1;i+=i&-i)
{
if(v>p[a1[i]].v)
{
if(z!=p[a1[i]].z) a2[i]=a1[i];
a1[i]=x;
}
else if(z!=p[a1[i]].z&&v>p[a2[i]].v) a2[i]=x;
if(v<p[c1[i]].v)
{
if(z!=p[c1[i]].z) c2[i]=c1[i];
c1[i]=x;
}
else if(z!=p[c1[i]].z&&v<p[c2[i]].v) c2[i]=x;
}
for(i=p[x].y;i;i-=i&-i)
{
if(v>p[b1[i]].v)
{
if(z!=p[b1[i]].z) b2[i]=b1[i];
b1[i]=x;
}
else if(z!=p[b1[i]].z&&v>p[b2[i]].v) b2[i]=x;
if(v<p[d1[i]].v)
{
if(z!=p[d1[i]].z) d2[i]=d1[i];
d1[i]=x;
}
else if(z!=p[d1[i]].z&&v<p[d2[i]].v) d2[i]=x;
}
}
inline void query(int x)
{
register int i,z=p[x].z,v=p[x].v;
for(i=p[x].y-1;i;i-=i&-i)
{
if(z==p[a1[i]].z) ans=max(ans,p[a2[i]].v-v);
else ans=max(ans,p[a1[i]].v-v);
if(z==p[c1[i]].z) ans=max(ans,v-p[c2[i]].v);
else ans=max(ans,v-p[c1[i]].v);
}
for(i=p[x].y+1;i<=2*n+1;i+=i&-i)
{
if(z==p[b1[i]].z) ans=max(ans,p[b2[i]].v-v);
else ans=max(ans,p[b1[i]].v-v);
if(z==p[d1[i]].z) ans=max(ans,v-p[d2[i]].v);
else ans=max(ans,v-p[d1[i]].v);
}
}
int main()
{
scanf("%d%s",&n,str+1);
register int i,j;
int a=0,b=0,c=0;
for(i=1;i<=n;i++)
{
a+=(str[i]=='B'),b+=(str[i]=='C'),c+=(str[i]=='S');
p[i].x=b-a,p[i].y=c-b+n+1,p[i].z=c-a,p[i].v=i;
if(str[i]==str[i-1]) sum++;
else sum=1;
ans=max(ans,sum);
}
p[0].y=n+1;
sort(p,p+n+1,cmp);
for(i=1;i<=2*n+1;i++) a1[i]=a2[i]=b1[i]=b2[i]=n+1,c1[i]=d1[i]=c2[i]=d2[i]=n+2;
p[n+1].v=-1,p[n+2].v=n+2;
for(i=0;i<=n;i=j+1)
{
for(j=i,query(j);j<n&&p[j+1].x==p[j].x;query(++j));
for(j=i,updata(j);j<n&&p[j+1].x==p[j].x;updata(++j));
}
printf("%d",ans);
return 0;
}