题解 P1494 【[国家集训队]小Z的袜子 /【模板】莫队】

· · 题解

这里介绍一个zyb爷爷给我讲的在线做法，复杂度是和莫队相同的 O(n\sqrt n)。

我们考虑一下答案该怎么计算，令 ans 表示有多少对 (i,j), i\not=j 满足 C_i=C_j。

之后显而易见的，答案就是 ans \div \text A_{r-l+1}^2。

于是我们只需要考虑怎么快速计算出 ans。

首先对序列分块，之后我们将所有的 (i,j) 分成三类：

对于第一类的 (i,j)，我们有一个十分经典的套路，只需令 f(a,b) 表示从 a 到 b 这 b-a+1 个块的答案即可。之后可以很暴力的从 f(a,b-1) 计算出 f(a,b) 的值，这一部分的复杂度是 O(n\sqrt n)。

虽然应该没有人不会这个暴力计算的方式，但是还是提一下。

我们维护当前所有颜色的出现次数，用 cnt_i 来表示当前 i 颜色出现了几次。

从块 b 的开头暴力扫到块 b 的结尾，当扫描到一个颜色 C 时，我们发现答案中颜色 C 的贡献会从 \text A_{cnt_C}^2 变成 \text A_{cnt_C+1}^2。简单推一下式子就会发现只需令答案加上 2\times cnt_C 即可。

对于第二类的 (i,j)，考虑到散点个数不会超过 2\sqrt n，我们直接按照类似于第一类 (i,j) 计算时方法计算出这 2\sqrt n 个数的贡献加到答案里。

对于第三类的 (i,j)，我们依然尝试枚举散点中的每一个颜色，当我们枚举到一个颜色 C 时，容易发现这个颜色会对答案产生 2\times \text{整块中颜色C的出现次数} 的贡献。

显然，直接维护从块 a 到块 b 中颜色 i 的出现次数会导致空间复杂度达到 O(n^2)。但是我们发现出现次数这种信息是可减的，于是维护 g(a,i) 表示前 a 个块中颜色 i 的出现次数，然后就可以 O(1) 计算出颜色 C 对答案的贡献了。

至此，我们得到了一个需要 O(n\sqrt n) 的时间复杂度进行预处理，需要 O(m\sqrt n) 的时间复杂度来处理所有询问的在线算法。

我分块写的不多，代码很丑qwq

#include<bits/stdc++.h>

using namespace std;
typedef long long int_t;

#ifdef ONLINE_JUDGE
    #define getchar getch 
#endif

char getch(){
    static char B[100000], *s, *t;
    return (s == t) && (t = (s = B) + fread(B, 1, 100000, stdin)), s == t ? EOF : *s++;
}

int_t read(){
    int_t x=0, w=1; char C=0;
    while(!isdigit(C)) {C = getchar(); if(C == '-') w = -1;}
    while(isdigit(C)) x = x * 10 + C - '0', C = getchar();
    return x * w;
}

int_t gcd(int_t a,int_t b){return b?gcd(b,a%b):a;}

int_t C[50010], lp[300], rp[300], bel[50010], ans[300][300], tmp[50010], cnt[300][50010];

int main() {
    int_t n = read(), m = read(), siz = sqrt(n), ks = 0;
    for(int_t i=1;i<=n;i++) C[i] = read(), bel[i] = (i-1) / siz + 1, rp[bel[i]] = max(rp[bel[i]], i), ks = bel[i];
    for(int_t i=1;i<=ks;i++) lp[i] = rp[i-1] + 1;
    for(int_t i=1;i<=ks;i++) {
        for(int_t j=i,tans=0;j<=ks;j++) {
            for(int_t k=lp[j];k<=rp[j];k++) tans += 2 * (++tmp[C[k]]) - 2;
            ans[i][j] = tans;
        }
        for(int_t j=1;j<=n;j++) cnt[i][j] = cnt[i-1][j], tmp[j] = 0;
        for(int_t j=lp[i];j<=rp[i];j++) cnt[i][C[j]] ++;
    }
    while(m--) {
        int_t l = read(), r = read(), zkl = bel[l] + (l != lp[bel[l]]), zkr = bel[r] - (r != rp[bel[r]]), sdl = lp[zkl] - 1, sdr = rp[zkr] + 1, tans = ans[zkl][zkr];
        if(l == r) {puts("0/1"); continue;}
        if(bel[l] >= bel[r] - 1) {
            tans = 0;
            for(int_t i=l;i<=r;i++) tans += 2 * (++tmp[C[i]]) - 2;
            for(int_t i=l;i<=r;i++) tmp[C[i]] = 0;
        } else {
            for(int_t i=l;i<=sdl;i++) tans += 2 * (++tmp[C[i]] + cnt[zkr][C[i]] - cnt[zkl - 1][C[i]]) - 2;
            for(int_t i=sdr;i<=r;i++) tans += 2 * (++tmp[C[i]] + cnt[zkr][C[i]] - cnt[zkl - 1][C[i]]) - 2;
            for(int_t i=l;i<=sdl;i++) tmp[C[i]] = 0;
            for(int_t i=sdr;i<=r;i++) tmp[C[i]] = 0;
        }
        int_t fm = (r - l + 1) * (r - l), d = gcd(tans, fm);
        printf("%lld/%lld\n", tans / d, fm / d);
    }
}