[DS记录]P4786 [BalkanOI2018]Election

**题意** ： 一个长度为 $n$ 的字符串 $S[1:n]$，它仅由 `C` 和 `T` 两种字母组成。 每次询问给出 $l$ 和 $r$ ，求至少在 $S[l:r]$ 中删除多少个字符，才能保证：对于其每一个**前缀和后缀**，其 `C` 的数量都不小于 `T` 的数量。 $n,q\leq 5\times 10^5$ ，时限$\texttt{1s}$。 ------------ > 感谢 @热言热语 的指导。 考虑如何回答单组询问。 将 `C` 的权值赋为 $1$ ，`T` 的权值赋为 $-1$ ，合法等价于使得前后缀和均非负。 不难发现，我们会删除 `T`。 从前往后考虑，若前缀和为负，则删除当前字符 （一定为 `T`）。 再从后往前考虑，若后缀和为负，则删除当前字符 （一定为 `T`）。 不难发现，第一次扫描中删除了合法的尽量靠后的 `T` ，最有利于第二次扫描，这个贪心是正确的。 考虑如何刻画我们删除的 `T`。 记 $pre_i$ 为前缀和， $suf_i$ 为后缀和。 第一次扫描中删除的 `T` 即为 $pre$ 第一次为 $-1,-2,-3...$ 的位置，删除的总个数即为 $\min_i pre_i$。 记 $suf'_i$ 为第一次扫描（删除）后的后缀和。 第而次扫描中删除的 `T` 即为 $suf'$ 第一次为 $-1,-2,-3...$ 的位置，删除的总个数即为 $-\min_i suf_i'$。 考虑如何表示 $suf_i'$。 对于 $i$ ，其前面在第一轮中遭到的删除次数为 $-\min_{j<i}pre_i$ ，则后面（含）遭到的删除次数为 $\min_{j<i}pre_i-\min_ipre_i$ 于是 $suf_i'=suf_i+\min_{j<i}pre_j-\min_jpre_j$ 综上 ： $$ \begin{aligned} {\rm Ans}&=-\min_i pre_i-\min_i\Big\{suf_i+\min_{j\leq i}pre_j-\min_jpre_j\Big\}\\ &=-\min_i\Big\{suf_i+\min_{j\leq i}pre_j\Big\}\\ &=-\min_{j<i}pre_i+suf_i\\ \end{aligned} $$ 这相当于找出两个不交的前缀后缀，使得和最小。取补集，也相当于找出一个区间使得和最大。 线段树维护区间最大子段和即可。复杂度 $O(n+q\log n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 500500 using namespace std; struct Node{int s,ls,rs,ms;}a[1<<21|500]; inline void up(Node &u,Node &l,Node &r){ u.s=l.s+r.s; u.ls=max(l.ls,l.s+r.ls); u.rs=max(r.rs,r.s+l.rs); u.ms=max(max(l.ms,r.ms),l.rs+r.ls); } char s[MaxN]; void build(int l,int r,int u) { if (l==r){ int x=(s[l]=='T' ? -1 : 1); a[u].s=x;a[u].ls=a[u].rs=a[u].ms=max(x,0); return ; }int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(a[u],a[u<<1],a[u<<1|1]); } int wfl,wfr,trs,tms,ts; void qry(int l,int r,int u) { if (wfl<=l&&r<=wfr){ ts+=a[u].s; tms=max(max(tms,a[u].ms),trs+a[u].ls); trs=max(a[u].rs,trs+a[u].s); return ; }int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int n,m; int main() { scanf("%d%s",&n,s+1); build(1,n,1); scanf("%d",&m); for (int i=1;i<=m;i++){ scanf("%d%d",&wfl,&wfr); ts=trs=tms=0; qry(1,n,1); printf("%d\n",-(ts-tms)); }return 0; } ```