【BZOJ4384】[POI2015]Trzy wieże

Description

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

Input

第一行包含一个正整数n(1<=n<=1000000)，表示字符串的长度。
第二行一个长度为n的字符串。

Output

包含一行一个正整数，即最长的满足条件的子串的长度。

Sample Input

9
CBBSSBCSC

Sample Output

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;

}

巴特西

【BZOJ4384】[POI2015]Trzy wieże 树状数组