自动搬运

查看原文

来自洛谷，原作者为

	AutumnKite **

搬运于2025-08-24 22:08:26，当前版本为作者最后更新于2019-10-30 21:13:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看起来楼上那个代码有点(?)长...尝试补一个，顺便加点社区贡献，给 CSP2019 攒点 RP。

倍长以后直接用线段树维护 $B$，发现每次修改只会修改最多四个 $B_i$，可以直接单点修改。

对于询问，显然可以二分答案 $md$，那么显然需要满足 $[x+md-1,n+x-md+1]$ 这段区间中存在被大于 $0$ 的数包围的全 $0$ 子段。

也就是说，我们需要求区间中被大于 $0$ 的数包围的子段数量。

基础线段树练习题。

注意特判答案为 $0$ 的情况，即 $A_x=0$ 且 $[x+1,n+x-1]$ 中没有符合条件的子段。然后 $md$ 就可以在 $[1,n/2]$ 的范围内二分了。

而答案为 $-1$ 的情况就是 $md$ 在这个范围内取任意值都不合法。当然你想特判也行。

时间复杂度 $O(q\log^2n)$。

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
int read(){
	register int x = 0;
	register char f = 1, ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
	for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	return f ? x : -x;
}
void print(int x, char ch = '\n'){
	if (x == 0) return putchar('0'), putchar(ch), void(0);
	int cnt = 0, num[25];
	for (x < 0 ? putchar('-'), x = -x : 0; x; x /= 10) num[++cnt] = x % 10;
	while (cnt) putchar(num[cnt] ^ '0'), --cnt;
	putchar(ch);
}
const int N = 200005;
char s[5];
int n, q, a[N], c[N];
namespace segt{
	struct node{
		int c, l, r, s; // c 是区间中 >0 的数量，l,r表示区间左右的数，s表示满足条件的全 0 子段数量
		void init(int v){
			s = 0;
			if (v) c = l = r = 1;
			else c = l = r = 0;
		}
	}a[N << 2];
	node operator + (const node &a, const node &b){
		node c;
		c.c = a.c + b.c, c.l = a.l, c.r = b.r;
		c.s = a.s + b.s;
		if (a.c && b.c && (!a.r || !b.l)) ++c.s;
		return c;
	}
	void modify(int u, int l, int r, int x, int v){
		if (l == r) return a[u].init(v), void(0);
		int md = (l + r) >> 1;
		if (x <= md) modify(u << 1, l, md, x, v);
		else modify(u << 1 | 1, md + 1, r, x, v);
		a[u] = a[u << 1] + a[u << 1 | 1];
	}
	node query(int u, int l, int r, int L, int R){
		if (L <= l && r <= R) return a[u];
		int md = (l + r) >> 1;
		if (R <= md) return query(u << 1, l, md, L, R);
		else if (L > md) return query(u << 1 | 1, md + 1, r, L, R);
		else return query(u << 1, l, md, L, R) + query(u << 1 | 1, md + 1, r, L, R);
	}
}
int calc(int i){ return c[i] ? a[i] * a[i - 1] % 10 : (a[i] + a[i - 1]) % 10; } // 计算 B 的值
int main(){
	n = read(), q = read();
	for (register int i = 1; i <= n; ++i){
		a[i] = read(), scanf("%s", s), c[i] = s[0] == '*';
		a[n + i] = a[i], c[n + i] = c[i];
	}
	for (register int i = 2; i <= (n << 1); ++i)
		segt :: modify(1, 1, n << 1, i, calc(i));
	while (q--){
		int op = read(), x = read() + 1;
		if (op == 1){
			a[x] = read(), scanf("%s", s), c[x] = s[0] == '*';
			a[n + x] = a[x], c[n + x] = c[x];
			if (x > 1) segt :: modify(1, 1, n << 1, x, calc(x));
			segt :: modify(1, 1, n << 1, x + 1, calc(x + 1));
			segt :: modify(1, 1, n << 1, n + x, calc(n + x));
			if (x < n) segt :: modify(1, 1, n << 1, n + x + 1, calc(n + x + 1));
			// 修改四个点的 B[i]
		}
		else{
			if (!a[x] && segt :: query(1, 1, n << 1, x + 1, n + x - 1).s == 0){ puts("0"); continue; } // 特判答案为 0 的情况
			segt :: modify(1, 1, n << 1, x, a[x]);
			segt :: modify(1, 1, n << 1, n + x, a[x]);
			// 特别处理端点的 B[i]
			int l = 0, r = n >> 1, md, ans = -2;
			while (l <= r)
				if (md = (l + r) >> 1, segt :: query(1, 1, n << 1, x + md, n + x - md).s) ans = md, l = md + 1;
				else r = md - 1;
			++ans; // 二分的其实是全 0 段两边的数到端点的距离，所以加 1
			print(ans);
			if (x > 1) segt :: modify(1, 1, n << 1, x, calc(x));
			segt :: modify(1, 1, n << 1, n + x, calc(n + x));
		}
	}
}