HDU_3474
我们可以把C看成1，J看成-1，那么原问题就转化成了对于任意一种情况，如果序列从左往右加或者从右往左加，存在其一使得在加的过程中中间结果始终不为负数，那么这种断开的情况就是符合要求的。
我们不妨把环处理成两个相同的序列，并计算出其前缀和A[i]，那么对于任意一种左端点为i，右端点为j的情况，如果min{A[k]}-A[i-1]>=0或者A[j]-max{A[k]}>=0，那么这种情况就是符合要求的，其中i-1<=k<=j，于是两个单调队列分别维护A[k]的最小值及最大值即可。
#include<stdio.h>
#include<string.h>
#define MAXD 2000010
char b[MAXD];
int A[MAXD], N, q1[MAXD], q2[MAXD], d1[MAXD], d2[MAXD], hash[MAXD];
void init()
{
int i, j;
scanf("%s", b);
for(i = 0; b[i]; i ++)
{
if(b[i] == 'C')
A[i] = 1;
else
A[i] = -1;
}
N = i;
for(j = 0; j < N; j ++)
A[j + N] = A[j];
for(i = 1; i < 2 * N; i ++)
A[i] += A[i - 1];
}
void solve()
{
int i, j, h1, h2, r1, r2, res;
h1 = h2 = r1 = r2 = 0;
for(i = 0; i < N; i ++)
{
while(h1 < r1 && q1[r1 - 1] >= A[i])
r1 --;
q1[r1] = A[i];
d1[r1] = i;
r1 ++;
while(h2 < r2 && q2[r2 - 1] <= A[i])
r2 --;
q2[r2] = A[i];
d2[r2] = i;
r2 ++;
}
memset(hash, 0, sizeof(hash));
for(i = N; i < 2 * N; i ++)
{
while(h1 < r1 && d1[h1] < i - N)
h1 ++;
while(h1 < r1 && q1[r1 - 1] >= A[i])
r1 --;
q1[r1] = A[i];
d1[r1] = i;
r1 ++;
if(q1[h1] - A[i - N] < 0)
hash[i - N] ++;
while(h2 < r2 && d2[h2] < i - N)
h2 ++;
while(h2 < r2 && q2[r2 - 1] <= A[i])
r2 --;
q2[r2] = A[i];
d2[r2] = i;
r2 ++;
if(A[i] - q2[h2] < 0)
hash[i - N] ++;
}
res = 0;
for(i = 0; i < N; i ++)
if(hash[i] < 2)
res ++;
printf("%d\n", res);
}
int main()
{
int t, tt;
scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
{
printf("Case %d: ", tt + 1);
init();
solve();
}
return 0;
}