题解 P4062 【[Code+#1]Yazid 的新生舞会】

写一个比较自然的题解，不需要利用什么性质。分别给出了用树状数组、线段树实现的方法，时间复杂度皆为 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)，但是线段树跑的时间是树状数组的三倍。