「BalkanOI 2018 Day1」Election

记C为1，T为-1，\(sum[i]\)为\(i\)点的前缀和。

对于询问\([l,r]\)，分两步计算答案。

1. 要求所有点的\(sum[i]-sum[l-1] \geq 0\)，那么就把一些点拔高，需要删去的点数为\(max(sum[l-1]-sum[i])\)，最终得到\(sum^{'}[i]\)，记需要删去的点个数为\(ans_1\)。

2. 要求所有点\(sum^{'}[r]-sum^{'}[i] \geq 0\)，那么就把一些点降低，需要删去的点数为\(max(sum^{'}[i]-sum^{'}[r])\)，而\(sum^{'}[r]=sum[r]+ans_1\)，\(sum^{'}[i]=sum[l-1] + sum[i]-min(sum[k])(k \in [l-1,i])\)，\(max(sum^{'}[])=max(sum[i]-sum[j] +sum[l-1]) (l-1\leq j<i \leq r)\)。

实际上，上面的所有东西都可以用ST表来维护。

#include<bits/stdc++.h>

#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)

#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)

#define mem(a,b) memset(a,b,sizeof a )

#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl

using namespace std;

void in(int &r){

	static char c;

	r=0;

	while(c=getchar(),c<48);

	do r=(r<<1)+(r<<3)+(c^48);

	while(c=getchar(),c>47);

}

const int mn=500005;

char as[mn];

int maxv[19][mn],val[19][mn],minv[19][mn];

int sum[mn],lg[mn],n;

void init(){

	int *a=maxv[0],*b=minv[0],*c,*d,*e,*f;

	rep(q,1,n)sum[q]=as[q]+sum[q-1],a[q]=sum[q],b[q]=sum[q];

	rep(q,2,n)lg[q]=lg[q>>1]+1;

	rep(q,1,lg[n]){

		a=maxv[q],b=maxv[q-1];

		c=minv[q],d=minv[q-1];

		e=val[q],f=val[q-1];

		int v=1<<q-1;

		rep(w,1,n-(1<<q)+1){

			a[w]=max(b[w],b[w+v]);

			c[w]=min(d[w],d[w+v]);

			e[w]=max(max(f[w],f[w+v]),b[w+v]-d[w]);

		}

	}

}

int bin[mn];

int main(){

	freopen("elections.in","r",stdin);

	freopen("elections.out","w",stdout);

	in(n);

	scanf("%s",as+1);

	rep(q,1,n)as[q]=as[q]=='C'?1:-1;

	init();

	rep(q,0,lg[n])bin[1<<q]=q;

	int Q,a,b;

	in(Q);

	rep(q,1,Q){

		in(a),in(b);

		int Min=sum[a-1],d=b-a+1,vl=0,now=a;

		while(d){

			int w=bin[d&-d];

			vl=max(vl,max(val[w][now],maxv[w][now]-Min));

			Min=min(Min,minv[w][now]);

			now+=1<<w,d&=d-1;

		}

		printf("%d\n",vl-(sum[b]-sum[a-1]));

	}

	return 0;

}