Yazid的新生舞会

题目描述

Yazid 有一个长度为 \(n\) 的序列 \(A\)，下标从 \(1\) 至 \(n\)。显然地，这个序列共有 \(\frac{n\left( n+1\right)}{2}\) 个子区间。

对于任意一个子区间 \([l,r]\)，如果该子区间内的众数在该子区间的出现次数严格大于 \(\frac{r-l+1}{2}\)（即该子区间长度的一半），那么 Yazid 就说这个子区间是“新生舞会的”。

所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。

现在，Yazid 想知道，共有多少个子区间是“新生舞会的”。

思路:

  如果一个数是当前区间的众数,那一定会满足\(cnt_r - cnt_l > r - l - \left(cnt_r - cnt_l\right)\)移相后可转化为\(2cnt_r - r > 2cnt_l - l\)这样子就将原问题转化成了对每个\(r\)有多少个\(l \in \left[0, r - 1\right]\)满足\(2cnt_r - r > 2cnt_l - l\),可以直接用树状数组来维护,但是直接做的时间复杂度是\(O\left(n ^ 2 \log n\right)\),所以需要进一步去优化.
  令\(P_i = 2cnt_i - i\),可以发现\(P_i\)在上一次出现所选众数\(x\)的位置和下一次出现\(x\)的位置之间,是一个公差为\(-1\)的等差数列,那么每出现一次\(x\)就相当于给后面的区间加上一个公差为\(1\)的等差数列.那么用\(c_i\)来存储权值,用\(T_i = \sum\limits_{j = 1}^{i}c_j\)来表示\(c_i\)的前缀和,每一个\(P_i\),它对区间的贡献就是\(T_{P_i - 1}\).那么对区间\(\left[l, r\right]\)的贡献就是\(\sum\limits_{i = l - 1}^{r - 1}T_i\)，记\(G_i = \sum\limits_{j = 1}^{i} T_j\)来表示\(T_i\)的前缀和,所以总共的贡献就是\(G_{r - 1} - G_{l - 1}\)。这样就转化为了一个区间加和二维前缀和的操作。
  \(\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\end{aligned}\)
  就将二维前缀和转化成了差分数组\(d_k\)的三维前缀和，因为\(\sum\limits_{i = 1}^{x}\sum\limits_{j = 1}^{i}\sum\limits_{k = 1}^{j} d_k\)这个式子太过于繁琐要推导出一个能够用树状数组直接计算的式子.
  \(\begin{aligned}\sum\limits_{i = 1}^{x}\sum\limits_{j = 1}^{i}\sum\limits_{k = 1}^{j} d_k &= \sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i}\left(i - k + 1\right)d_k \\ &= \sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i} i×d_k - \sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i}\left(k - 1\right)d_k\end{aligned}\)
  对于\(\sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i}i×a_k\)展开为\(1×\left(a_1\right) + 2×\left(a_1 + a_2\right) + \dots \left(x - 1\right)\left(a_1 + a_2 + \dots a_{x - 1}\right) + x×\left(a_1 + a_2 + \dots + a_{x - 1} + a_x\right)\)再合并一下同类项,\(\left(1 + 2 + \dots + x\right)a_1 + \left(2 + 3 + \dots + x - 1 + x\right)a_2 + \dots + a_x\)，\(a_i\)前的系数是一个等差数列,可以求和再次化简, \(\left(\frac{\left(1 + x\right)x}{2}a_1 + \dots \frac{\left(k + x\right)\left(x - k + 1\right)}{2} + \dots + a_x\right)\)，最终转化为\(\sum\limits_{k = 1}^{x} \frac{\left(k + x\right)\left(x - k + 1\right)}{2}d_k\)
  对于\(\sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i}\left(k - 1\right)d_k\)展开为\(0×a_1 + (2 - 1)(x - 1)×a_2 + (3 - 1)(x - 2)a_3 + \dots + (k - 1)(x - k + 1)a_k + \dots + \left(x - 1\right)\left(x - x + 1\right)a_x\),合并为\(\sum\limits_{k = 1}^{x} \left(k - 1\right)\left(x - k + 1\right) d_k\)
  \(\begin{aligned}\sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i} i×d_k - \sum\limits_{i = 1}^{x}\sum\limits_{k = 1}^{i}\left(k - 1\right)d_k &= \sum\limits_{k = 1}^{x} \frac{\left(k + x\right)\left(x - k + 1\right)}{2}d_k - \sum\limits_{k = 1}^{x} \left(k - 1\right)\left(x - k + 1\right) d_k \\ &= \sum\limits_{k = 1}^{x} \frac{\left(x + 2 - k\right)\left(x + 1 - k\right)}{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 * k + \frac{1}{2}\sum\limits_{k = 1}^{x}d_k * k ^ 2\end{aligned}\)
  只需要用树状数组分别维护\(d_k, kd_k, k ^ 2 d_k\)就行了。

    int n;
    i64 c1[N * 2], c2[N * 2], c3[N * 2];

    void add(int x, i64 v) {
        for (int i = x; i <= n * 2 + 1; i += i & -i) {
            c1[i] += v;
            c2[i] += 1ll * v * x;
            c3[i] += 1ll * v * x * x;
        }
    }

    i64 query(int x) {
        i64 ans = 0;
        for (int i = x; i; i -= i & -i) {
            ans += c1[i] * (x + 2) * (x + 1) - c2[i] * (2ll * x + 3) + c3[i];
        }
        return ans / 2;
    }

    int a[N];
    std::vector<int> b[N];

    signed main() {
        int op; 
        scanf("%d%d", &n, &op);
        for (register int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            b[a[i]].push_back(i);
        }

        i64 ans = 0;
        for (register int i = 0; i < n; i++) {
            int last = 0;
            b[i].push_back(n + 1);
            for (int j = 0; j < int(b[i].size()); j++) {
                int r = n + 1 + 2 * j - last, l = n + 1 + 2 * j - (b[i][j] - 1);
                ans += query(r - 1) - (l >= 3 ? query(l - 2) : 0);
                add(l, 1);
                add(r + 1, -1);
                last = b[i][j];
            }

            last = 0;
            for (register int j = 0; j < int(b[i].size()); j++) {
                int l = n + 1 + 2 * j - (b[i][j] - 1), r = n + 1 + 2 * j - last;
                add(l, -1), add(r + 1, 1);
                last = b[i][j];
            }
        }

        printf("%lld\n", ans);

        return 0 ^ 0;
    }