自动搬运

查看原文

来自洛谷，原作者为

	Fire_flame 乐观乐观再乐观

搬运于2025-08-24 22:51:04，当前版本为作者最后更新于2023-06-12 23:36:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前置知识：T4 五五五五 （Easy） 正解（必须），线段树或者平衡树。

可以发现上一道题其实提示了这个题目的方法呢。

$\mathbf{Method1}$

本方法考虑线段树维护，定义 $g_i$ 表示数组 $\overline{a_1a_2\dots a_i}$ 末尾连续 $5$ 的个数。

首先预处理 $g$ 数组和初始答案 $ans$。

不难发现，在进行操作 $1$ 的过程中，仅仅维护 $g$ 数组是不够的，我们需要预处理一个镜像数组 $g'$，一个镜像答案 $ans'$。

$g'_i$ 表示 $\overline{a_ia_{(i-1)}\dots a_1}$ 末尾连续 $5$ 的个数。接下来，我们用线段树维护 $g,g'$ 即可。

对于操作 $1$，我们得分类讨论：

• 如果是把一个 $5$ 改成其他的数，那么 $g_{g'_{x}} \sim g_{x-1}$ 全部减 $g_x$，$g_x$ 清零。

  并且 $g'_{g_{x}} \sim g'_{x-1}$ 全部减 $g'_x$，$g'_x$ 清零。

• 把其他的数改成 $5$ 也同理，这里不再赘述。

记得每一次操作完 $ans,ans'$ 都要相应的改变。

对于操作 $2$，我们使用一个变量 $now$ 表示经过翻转了奇数次还是偶数次，$now=1$ 表示翻转了奇数次，$now=0$ 表示翻转了偶数次。

操作 $2$ 时直接异或一下 $now$ 即可。

对于操作 $3$，如果 $now=0$ 输出 $ans$，否则输出 $ans'$。

对于操作 $4$，就是一个普通线段树的区间求和（看这出题人多良心）。

标程：

#include <ctime>//By wzy2021   (Orz Orz)
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

struct node {
	int l, r, sz, sum;
	int l5, r5, s5; ll sf, sg; 
};
int n, m; ll f[N], g[N];

void init (int n) {
	for (int i = 1; i <= n; ++i) f[i] = (f[i - 1] + i) % mod, g[i] = (g[i - 1] + i * (i + 1) / 2) % mod;
}

int get (int x, int y) {
	return (1ll * f[x] * y % mod + g[x]) % mod;
}

struct Tree {
	node t[N << 2];
	void pushup (int x) {
		t[x].sum = t[x << 1].sum + t[x << 1 | 1].sum;
		t[x].l5 = t[x << 1].l5; if (t[x << 1].l5 == t[x << 1].sz) t[x].l5 += t[x << 1 | 1].l5;
		t[x].r5 = t[x << 1 | 1].r5; if (t[x << 1 | 1].r5 == t[x << 1 | 1].sz) t[x].r5 += t[x << 1].r5;
		t[x].s5 = ((t[x << 1].s5 + t[x << 1 | 1].s5 - f[t[x << 1].r5] - f[t[x << 1 | 1].l5] + f[t[x << 1].r5 + t[x << 1 | 1].l5]) % mod + mod) % mod;
		t[x].sf = (t[x << 1].sf + t[x << 1 | 1].sf + 1ll * t[x << 1].sz * t[x << 1 | 1].s5 % mod) % mod;
		t[x].sf -= get (t[x << 1].r5, t[x << 1].sz - t[x << 1].r5) + get (t[x << 1 | 1].l5, t[x << 1].sz);
		t[x].sf += get (t[x << 1].r5 + t[x << 1 | 1].l5, t[x << 1].sz - t[x << 1].r5);
		t[x].sf = (t[x].sf % mod + mod) % mod;
	}
	void build (int x, int l, int r) {
		t[x].l5 = t[x].r5 = t[x].s5 = t[x].sf = t[x].sg = 0;
		t[x].l = l; t[x].r = r; t[x].sz = r - l + 1; t[x].sum = 0;
		if (l == r) return ;
		int mid = (l + r) >> 1;
		build (x << 1, l, mid); build (x << 1 | 1, mid + 1, r);
	}
	void update (int x, int k, int v) {
		if (t[x].l == t[x].r) {
			t[x].sum = v; t[x].l5 = t[x].r5 = t[x].s5 = t[x].sf = t[x].sg = (v == 5);
			return ;
		}
		int mid = (t[x].l + t[x].r) >> 1;
		if (k <= mid) update (x << 1, k, v);
		else update (x << 1 | 1, k, v);
		pushup(x);
	}
	int query (int x, int l, int r) {
		if (l <= t[x].l && t[x].r <= r) return t[x].sum;
		int mid = (t[x].l + t[x].r) >> 1, ans = 0;
		if (l <= mid) ans = (ans + query (x << 1, l, r)) % mod;
		if (r > mid) ans = (ans + query (x << 1 | 1, l, r)) % mod;
		return ans;
	}
} T[2]; 

int main() {
	init(N - 5);
	int n, m; scanf ("%d%d", &n, &m);
	T[0].build (1, 1, n); T[1].build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		int x; scanf ("%d", &x); T[0].update (1, i, x); T[1].update (1, n - i + 1, x); 
	} int flag = 0;
	while (m--) {
		int opt; scanf ("%d", &opt);
		if (opt == 1) {
			int x, y; scanf ("%d%d", &x, &y);
			T[flag].update(1, x, y); T[flag ^ 1].update(1, n - x + 1, y);
		} else if (opt == 2) {
			flag ^= 1;
		} else if (opt == 3) {
			printf ("%lld\n", T[flag].t[1].sf % mod);
		} else {
			int l, r; scanf ("%d%d", &l, &r);
			printf ("%d\n", T[flag].query (1, l, r));
		}
	}
	return 0;
}

$\mathbf{Method2}$

这个题目也可以用平衡树解决。

因为 FF 不想再写字了，那么就留给大家去思考。