题面

定义一个好的 $01$ 串 $\mathcal{S}$ 满足以下条件：

• $\mathcal{S}$ 非空。

• $\mathcal{S}$ 的任意一个前缀 $\mathcal {S}[1\dots p](p\in [1,|$ $\mathcal S$ $|])$ 中， $0$ 的数量都不多于 $1$ 的数量。

• $\mathcal{S}$ 的任意一个后缀 $\mathcal S[p\dots |$ $\mathcal{S}$ $|](p\in [1,|$ $\mathcal S$ $|])$ 中， $0$ 的数量都不多于 $1$ 的数量。

现在你得到了一个长度为 $n$ 的 $01$ 串 $\mathcal{T}$ ，有 $q$ 次询问，每次询问给定一对 $l,r$ ，求最少在 $\mathcal{T}[l\dots r]$ 中插入多少个 $1$ 使得它变成好串。

$n\leq10^6$ 。

题解

相比较插入 $1$ ，删除 $0$ 更好处理，发现两个问题很好转化。可以证明插入删除不同当且仅当 $\mathcal{T}$ 中只有 $0$ 。

于是题目变成了 [BalkanOI2018] Election。

代码

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] == '0';
				t[p].rmx = s[l] == '0';
				t[p].sum = (s[l] == '0'? 1: -1);
				t[p].ans = s[l] == '0';
				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(), m = Read();
		scanf ("%s", s + 1);
		for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '1');
		sgt.build(1, 1, n);
		int ans = 0;
		for (; m--; ) {
			int l = Read(), r = Read();
			ans ^= sgt.query (1, l, r).ans + (sum[r] - sum[l - 1] == 0);
		}
		printf ("%d\n", ans);
		return 0;
	}
}

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