[KMOI R1]五五五五 （Hard）题解

· · 题解

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

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

\mathbf{Method1}

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

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

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

--- 对于操作 $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$，就是一个普通线段树的区间求和（~~看这出题人多良心~~）。 标程： ```cpp #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 不想再写字了，那么就留给大家去思考。