BZOJ 2906: 颜色

分治无法快速维护，考虑分块
\(f_{i,j,k}\) 表示第 \(i\) 块到第 \(j\) 块之间权值为 \(1\) 到 \(k\) 的答案，\(c_{i,j,k}\) 表示第 \(i\) 块到第 \(j\) 块之间权值为 \(k\) 的个数
预处理及回答询问时，新加入一个颜色为 \(k\) 的点对答案的贡献为 \(2 * cnt_k + 1\)，由 \(cnt_k ^ 2 \to (cnt_k + 1)^2\)
这样就可以拓展得到答案
设块大小为 \(B\)
预处理复杂度为 \(O(n(\dfrac{n}{B})^2)\)，询问复杂度为 \(O(nB)\)，\(B\) 取 \(n^{\frac{2}{3}}\) 时即可

#include <bits/stdc++.h>
#define uint unsigned

inline int read() {
  int x = 0, f = 1; char ch = getchar();
  while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
  return x * f;
}

const int N = 5e4 + 7, M = 2e4 + 7;
int B, n, m, q, color[N];
uint f[40][40][M], c[40][40][M], sum[N], cnt[N];

void build() {
    B = pow(n, 0.6666666667);
    int num = n / B;
    for (int i = 1; i <= num; i++) {
        for (int j = i; j <= num; j++) {
            for (int k = (j - 1) * B + 1; k <= j * B; k++)
                sum[color[k]] += cnt[color[k]] * 2 + 1, cnt[color[k]]++;
            for (int k = 1; k <= m; k++) 
                c[i][j][k] = cnt[k], f[i][j][k] = f[i][j][k - 1] + sum[k];
        }
        for (int j = 1; j <= m; j++)
            sum[j] = cnt[j] = 0;
    }
}

int main() {
    n = read(), m = read(), q = read();
    for (int i = 1; i <= n; i++)
        color[i] = read();
    build();
    uint ans = 0;
    for (int l, r, a, b; q--; ) {
        l = read(), r = read(), a = read(), b = read();
        l ^= ans, r ^= ans, a ^= ans, b ^= ans;
        int x = (l - 1) / B + 1, y = (r - 1) / B + 1;
        ans = f[x + 1][y - 1][b] - f[x + 1][y - 1][a - 1];
        if (x == y) {
            for (int i = l; i <= r; i++) 
                if (color[i] >= a && color[i] <= b) 
                    ans += cnt[color[i]] * 2 + 1, cnt[color[i]]++;
            for (int i = l; i <= r; i++) 
                if (color[i] >= a && color[i] <= b) 
                    cnt[color[i]]--;
        } else {
            for (int i = l; i <= x * B; i++)
                if (color[i] >= a && color[i] <= b) 
                    ans += (c[x + 1][y - 1][color[i]] + cnt[color[i]]) * 2 + 1, cnt[color[i]]++;
            for (int i = r; i > (y - 1) * B; i--)
                if (color[i] >= a && color[i] <= b) 
                    ans += (c[x + 1][y - 1][color[i]] + cnt[color[i]]) * 2 + 1, cnt[color[i]]++;
            for (int i = l; i <= x * B; i++)
                if (color[i] >= a && color[i] <= b) 
                    cnt[color[i]]--;
            for (int i = r; i > (y - 1) * B; i--)
                if (color[i] >= a && color[i] <= b) 
                    cnt[color[i]]--;
        }
        printf("%u\n", ans);
    }
    return 0;
}

BZOJ 2906: 颜色

原文：https://www.cnblogs.com/Mrzdtz220/p/12325839.html