题解 P4062 【[Code+#1]Yazid 的新生舞会】 最后更新于 2025-05-01 18:39:23

写一个比较自然的题解，不需要利用什么性质。分别给出了用树状数组、线段树实现的方法，时间复杂度皆为 $O(n\log n)$。 由数据范围 $0\le A_i\le n-1$，我们想到枚举每个种类的数，分别计算贡献。 对当前选中的数 $w$，设 $S_i$ 为前 $i$ 个数中 $w$ 的个数 ，那么对于一段区间 $[l+1,r]$ ，$w$ 能成为绝对众数（数量严格超过一半的众数）的条件是 $S_r-S_l>r-l-(S_r-S_l)$。 移项得到 $2S_r-r>2S_l-l$，那问题就变成了对每个 $r$ ，统计 $l\in[0,r-1]$ 的范围内有多少满足 $2S_r-r>2S_l-l$。（可以发现， $2S_i-i$ 其中就是前缀里 $w$ 的个数减去非 $w$ 的个数）如果用树状数组来维护每个 $2S_i-i$ 的个数，时间复杂度度 $O(n^2log(n))$ ，只能骗部分分。当然有些细节要注意，比如 $2S_i-i$ 的值域范围是 $[-n,n]$ ，你需要加个 $n+1$ 的偏移量才能用数据结构维护。 为了方便叙述，记 $P_i=2S_i-i$。 然后观察对某个选中的数 $w$，其 $P_i$ 的变化情况。可以发现如果有 $k$ 个 $w$，那么可以分成 $k+1$ 个区间（以 $0$ 位置及每个 $w$ 为开头到下个 $w$ 之前的数为止），每个区间内部的 $P_i$ 值都是公差为 $-1$ 的等差数列。 举个例子：  这样如果我们能用某种方法把每段里的数**同时处理**，那么总共需要处理的段数就是 $O(n)$ 的了。 具体来说，假设当前这段的等差数列是 $y,y-1,y-2,\dots ,x$ ，用数据结构来维护权值 $c_i$，那么也就是对区间 $[x,y]$ 加 $1$。 并且可以发现同一段是不会有任何贡献的（因为是递减的），只需查询前面所有段的 $P_i$ 值带来的影响，所以在更新操作之前，我们应该先做查询， 记 $T_i$ 表示权值的前缀和，即 $T_i=\sum\limits_{j=1}^{i}c_j$。对段内每个位置的 $P_i$ ，我们得到的贡献是 $T_{P_i-1}$。也就是说，对整个段内 $[x,y]$ 这些数，总贡献是 $\sum\limits_{i=x-1}^{y-1}T_i$。记 $G_i$ 表示权值的前缀和的前缀和，即 $G_i=\sum\limits_{j=1}^{i}T_j$，那么总贡献可以表示为 $G_{y-1}-G_{x-1}$。 现在问题简化为区间加一个数和求二阶前缀和，下面分别用树状数组和线段树解决这个问题： --- ### 树状数组 想必你用树状数组做过 “区间加一个数，区间求和”的问题，本质单点更新，是求二阶前缀和。 事实上，使用 $n$ 个树状数组，可以实现单点更新，查询 $n$ 阶前缀和： 比如 $n=3$ 时， 设 $c$ 是 $b$ 的前缀和， $b$ 是 $a$ 的前缀和，$a$ 是 $d$ 的前缀和，即 $c$ 是 $d$ 的三阶前缀和，那么有 $$ \begin{aligned} &c_x=\sum\limits_{i=1}^{x} b_i\\ &=\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i} a_j\\ &=\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{j}d_k\\ &=\sum\limits_{k=1}^{x}\frac{(x+2-k)(x+1-k)}{2}d_k\\ &=\frac{(x+2)(x+1)}{2}\sum\limits_{k=1}^{x}d_k-\frac{2x+3}{2}\sum\limits_{k=1}^{x}d_k\cdot k+\frac{1}{2}\sum\limits_{k=1}^{x}d_k\cdot k^2 \end{aligned} $$ 对这题而言，现在区间更新可以转换为差分数组 $d$ 的两个单点更新，原数组的二阶前缀和变为差分数组 $d$ 的三阶前缀和。 那么只要用三个树状数组维护 $d_i,d_i\times i,d_i\times i^2$ 即可，完整代码如下： ```c++ #include <bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const LL mod = 1e9 + 7; const int N = 500005; // 修改差分 来维护前缀和的前缀和 // c1 为差分d c2为d*i c3 为d*i*i LL c1[N * 2], c2[N * 2], c3[N * 2]; LL sum(int x) { LL res = 0; for (int i = x; i > 0; i -= i & -i) { res += c1[i] * (x + 2) * (x + 1) - c2[i] * (2 * x + 3) + c3[i]; } return res / 2; } void add(int x, LL d, int n) { for (int i = x; i <= n; i += i & -i) { c1[i] += d; c2[i] += d * x; c3[i] += d * x * x; } } int a[N]; vector<int> b[N]; int main() { int n; scanf("%d%*d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[a[i]].push_back(i); } const int wc = n + 1; // 偏移量，把[-n,n] 平移到 [1,2n+1] LL ans = 0; for (int i = 0; i < n; i++) { b[i].push_back(n + 1); int last = 0; for (int j = 0; j < b[i].size(); j++) { int y = 2 * j - last + wc, x = 2 * j - (b[i][j] - 1) + wc; // 查询 sum([1,t-1] 的权值和), 其中t在[x,y]范围内， ans += sum(y - 1) - (x >= 3 ? sum(x - 2) : 0); // [x,y] 这些数的权值+1 add(x, 1, 2 * n + 1); add(y + 1, -1, 2 * n + 1); last = b[i][j]; } last = 0; for (int j = 0; j < b[i].size(); j++) { int y = 2 * j - last + wc, x = 2 * j - (b[i][j] - 1) + wc; add(x, -1, 2 * n + 1); add(y + 1, 1, 2 * n + 1); last = b[i][j]; } } printf("%lld\n", ans); return 0; } ``` --- ### 线段树 其实也可以用两棵线段树来求二阶前缀和，但这就没有意思了，和树状数组维护三阶前缀和没区别。 我的方法是用线段树维护权值的前缀和 $T_i$ ，这样在 $[x,y]$ 上的区间加 $1$ 就变成了：在 $[x,y]$ 上加等差数列 $1,2,3,\ldots,y-x+1$，在 $[y+1,2n+1]$ 上加上 $y-x+1$。后者也可看成是公差为 $0$ 的等差数列。 那么线段树怎么维护等差数列呢？ 我们可以发现任意个等差数列的和都是等差数列，只是公差和首项发生了变化。 那么只要把公差和首项作为延迟标记，来维护区间和就好了，具体实现见代码。 因为维护的是 $T_i$ ，查询也只是简单的区间查询了，注意一些边界问题就OK了。 完整代码如下： ```c++ #include <bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const LL mod = 1e9 + 7; const int N = 500005; // sx,gc 表示首项和公差 LL val[N << 3], sx[N << 3], gc[N << 3]; inline void push_up(int u) { val[u] = val[u << 1] + val[u << 1 | 1]; } inline void gx(int u, LL v, LL d, int len) { val[u] += (v + v + (len - 1) * d) * len / 2; sx[u] += v; gc[u] += d; } inline void push_down(int u, int len1, int len2) { if (sx[u] || gc[u]) { gx(u << 1, sx[u], gc[u], len1); gx(u << 1 | 1, sx[u] + gc[u] * len1, gc[u], len2); sx[u] = gc[u] = 0; } } void update(int u, int l, int r, int x, int y, int v, int d) { if (x <= l && r <= y) { gx(u, v + (l - x) * d, d, r - l + 1); return; } int mid = l + r >> 1; push_down(u, mid - l + 1, r - mid); if (x <= mid) update(u << 1, l, mid, x, y, v, d); if (y > mid) update(u << 1 | 1, mid + 1, r, x, y, v, d); push_up(u); } LL query(int u, int l, int r, int x, int y) { if (x <= l && r <= y) { return val[u]; } int mid = l + r >> 1; push_down(u, mid - l + 1, r - mid); LL res = 0; if (x <= mid) res += query(u << 1, l, mid, x, y); if (y > mid) res += query(u << 1 | 1, mid + 1, r, x, y); return res; } int a[N]; vector<int> b[N]; int main() { int n; scanf("%d%*d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[a[i]].push_back(i); } const int wc = n + 1; // 偏移量，把[-n,n] 平移到 [1,2n+1] LL ans = 0; for (int i = 0; i < n; i++) { b[i].push_back(n + 1); int last = 0; for (int j = 0; j < b[i].size(); j++) { int y = 2 * j - last + wc, x = 2 * j - (b[i][j] - 1) + wc; // 查询 sum([1,t-1] 的权值和), 其中t在[x,y]范围内 ans += query(1, 1, 2 * n + 1, max(x - 1, 1), y - 1); // [x,y] 这些数的权值+1，真正要维护的是它们的前缀和， // 在[x,y] 上是加上一段等差数列 1,2,3,...,y-x+1，[y+1,2n+1] 上每个数+y-x+1 update(1, 1, 2 * n + 1, x, y, 1, 1); if (x + 1 <= 2 * n + 1) update(1, 1, 2 * n + 1, y + 1, 2 * n + 1, y - x + 1, 0); last = b[i][j]; } last = 0; for (int j = 0; j < b[i].size(); j++) { int y = 2 * j - last + wc, x = 2 * j - (b[i][j] - 1) + wc; update(1, 1, 2 * n + 1, x, y, -1, -1); if (x + 1 <= 2 * n + 1) update(1, 1, 2 * n + 1, y + 1, 2 * n + 1, -(y - x + 1), 0); last = b[i][j]; } } printf("%lld\n", ans); return 0; } ``` 最后，同样时间复杂度是 $O(n\log n)$，但是线段树跑的时间是树状数组的三倍。