自动搬运

查看原文

来自洛谷，原作者为

	OMG_wc 幻想家协会会长

搬运于2025-08-24 21:56:04，当前版本为作者最后更新于2020-08-13 15:39:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

写一个比较自然的题解，不需要利用什么性质。分别给出了用树状数组、线段树实现的方法，时间复杂度皆为 $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$ 即可，完整代码如下：

#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了。

完整代码如下：

#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)$，但是线段树跑的时间是树状数组的三倍。