[BalkanOI2018] Election

题目描述

有一个长度为 $N$ 的字符串 $S[1\dots N]$ ，它仅由 C 和 T 两种字母组成。
现在有 $Q$ 个查询，每个查询包含两个整数 $L$ 和 $R$ ，表示：设新字符串 $S'=S[L\dots R]$ ，至少在 $S'$ 中要删除多少个字符，才能保证：对于 $S'$ 的每一个前缀和后缀，其 C 的数量都不小于 T 的数量。

$N\leq5\times10^5$ 。

题解

线段树维护最大子段和。

代码

const int N = 1e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int sum[N];
	char s[N];
	struct SegmentTree {
		struct tree {
			int l, r, lmx, rmx, sum, ans;
		}t[N << 2];
#define lson (p << 1)
#define rson (p << 1 | 1)
		tree friend operator + (tree a, tree b) {
			return (tree){a.l, b.r,
			max({0, a.lmx, a.sum + b.lmx}),
			max({0, b.rmx, b.sum + a.rmx}),
			a.sum + b.sum,
			max({a.ans + b.sum, a.sum + b.ans, a.lmx + b.rmx})};
		}
//		void pushup (int p) {
//			t[p].lmx = max({0, t[lson].lmx, t[lson].sum + t[rson].lmx});
//			t[p].rmx = max({0, t[rson].rmx, t[rson].sum + t[lson].rmx});
//			t[p].sum = t[lson].sum + t[rson].sum;
//			t[p].ans = max({t[lson].ans + t[rson].sum, t[lson].sum + t[rson].ans, t[lson].lmx + t[rson].rmx});
//		}
		void build (int p, int l, int r) {
			t[p].l = l, t[p].r = r;
			if (t[p].l == t[p].r) { 
				t[p].lmx = s[l] == 'T';
				t[p].rmx = s[l] == 'T';
				t[p].sum = (s[l] == 'T'? 1: -1);
				t[p].ans = s[l] == 'T';
				return;
			}
			int mid = (t[p].l + t[p].r) >> 1;
			build (lson, l, mid);
			build (rson, mid + 1, r);
			t[p] = t[lson] + t[rson];
		}
		tree query (int p, int l, int r) {
			if (l <= t[p].l && t[p].r <= r) return t[p];
			int mid = (t[p].l + t[p].r) >> 1;
			if (l <= mid && r > mid) return query (lson, l, r) + query (rson, l, r);
			if (l <= mid) return query (lson, l, r);
			else return query (rson, l, r);
		}
	} sgt;
	int main () {
		n = Read();
		scanf ("%s", s + 1);
		for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == 'C');
		sgt.build(1, 1, n);
		int ans = 0;
		for (m = Read(); m--; ) {
			int l = Read(), r = Read();
			//ans ^= sgt.query (1, l, r).ans + (sum[r] - sum[l - 1] == 0);
			printf ("%d\n", sgt.query(1, l, r).ans);
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}