P4786 [BalkanOI2018] Election 题解

题意

给定一个长度为 \(n\) 的字符串 \(s\)，有 \(m\) 个询问，每次询问最少需要删掉多少个字符才能使 \(l\) 到 \(r\) 组成的字符串当中的每一个前缀和后缀都满足 C 的数量不小于 T 的数量。

思路

因为要满足 C 的数量不小于 T 的数量，我们不妨设字符 C 的位置的值为 \(1\)，字符 S 的位置的值为 -1。

考虑每一组询问 \(l\) 和 \(r\)，设 \(pre_{i}\) 表示区间中 \(l\) 到 \(i\) 的和，\(suf_{i}\) 表示区间中 \(i\) 到 \(r\) 的和，即前缀和和后缀和。首先考虑暴力，可以先正序枚举一遍，取 \(pre\) 的最小值的相反数。并且在 \(pre\) 的每个分界点（值从 \(k\) 变成 \(k-1\) 并且 \(k-1\) 是之前最小的）标记一下表示删除，相当于是每当前缀和为 \(-1\) 的时候就删除当前数并且将前缀和变为 \(0\)。然后再倒序枚举一遍，之前删除过了的就不用管了，记修改后的后缀和为 \(suf1\)，再取 \(suf1\) 中的最小值的相反数，最后把两个数加起来就可以了，时间复杂度 \(O(n^{2})\)。

贪心正确性证明：因为在前缀操作的时候删除的都是分界点，所以位置一定尽量靠后，这样删除后的后缀和一定比删除更靠前的数的后缀和更大，所以这样删除对于后缀也是最优的。

但是暴力的时间复杂度肯定是不优的，于是考虑优化。我们考虑操作前缀前的 \(suf_{i}\) 和操作前缀后的 \(suf1_{i}\) 有什么区别。其实相比于 \(suf\)，\(suf1\) 加上了考虑前缀时在 \(i\) 到 \(r\) 中删除的点的数量，即：\(suf1_{i}=suf_{i}+(\min_{l \le j<i} pre_{j}-pre_{mn})\)，那么后缀的最终的答案是 \(-suf1_{mn}\)。其中 \(pre_{mn}\) 和 \(suf1_{mn}\) 表示区间 \(l\) 到 \(r\) 中 \(pre\) 和 \(suf1\) 的最小值。

最后的答案是 \(ans=-(pre_{mn}+suf1_{mn})\)，暴力表示为:

\(ans=-(pre_{mn}+\min(suf1_{l},\min(pre_{l})+suf_{l+1},\min(pre_{l},\dots,pre_{r-1})suf_{r})-pre_{mn})\)

化简得 \(ans=\min_{l\le i<j\le r}(pre_{i}+suf_{j})\)。

发现这个式子的意义为不相交的前缀和和后缀和的和的最小值，等价于区间和减去区间最大子段和。这两个东西用线段树维护即可，时间复杂度 \(O(n \log n)\)。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 5e5 + 10;
int n,m,a[MAXN],op,l,r;
char c[MAXN];
struct SegmentTree{int l,r,sum,lmx,rmx,mx;}tree[MAXN << 2];
inline void Pushup(int id)
{
	tree[id].sum = tree[ls].sum + tree[rs].sum;
	tree[id].lmx = max(tree[ls].lmx,tree[ls].sum + tree[rs].lmx);
	tree[id].rmx = max(tree[rs].rmx,tree[rs].sum + tree[ls].rmx);
	tree[id].mx = max(max(tree[ls].mx,tree[rs].mx),tree[ls].rmx + tree[rs].lmx);
}
inline void Build(int id,int l,int r)
{
	tree[id].l = l,tree[id].r = r;
	if(l == r){tree[id].sum = tree[id].lmx = tree[id].rmx = a[l];tree[id].mx = max(0ll,a[l]);return;}
	int mid = (l + r) >> 1;
	Build(ls,l,mid),Build(rs,mid + 1,r);
	Pushup(id);
}
inline SegmentTree Query(int id,int l,int r,int a,int b)
{
	if(a <= l && b >= r) return tree[id];
	int mid = (l + r) >> 1;SegmentTree res;
	if(a > mid) return res = Query(rs,mid + 1,r,a,b);
	if(b <= mid) return res = Query(ls,l,mid,a,b);
	else
	{
		SegmentTree x = Query(ls,l,mid,a,b),y = Query(rs,mid + 1,r,a,b);
		res.sum = x.sum + y.sum;
		res.lmx = max(x.lmx,x.sum + y.lmx);
		res.rmx = max(y.rmx,y.sum + x.rmx);
		res.mx = max(max(x.mx,y.mx),x.rmx + y.lmx);
		return res;
	}
}
signed main()
{
	cin >> n >> (c + 1) >> m;
	for(int i = 1;i <= n;i++) a[i] = (c[i] == 'C' ? 1 : -1);
	Build(1,1,n);
	for(int i = 1;i <= m;i++)
	{
		cin >> l >> r;
		SegmentTree ans = Query(1,1,n,l,r);
		cout << ans.mx - ans.sum << endl;
	}
	return 0;
}