二次离线莫队

恶补知识点。

能 $\Theta(sn\sqrt n)\to \Theta(ns+n\sqrt n)$ ，其中 $s$ 是移动端点复杂度。

设 $f(x,[l,r])$ 是 $x$ 对 $[l,r]$ 区间的贡献。

使用条件是 $f(x,[l,r])=f(x,[1,r])-f(x,[1,l-1])$ ，并且能快速查。

如果有这些性质，你发现所有对贡献的询问都是前缀询问，于是可以扫描线查询， $n\sqrt n$ 次查询 $n$ 次扫描，所以扫描复杂度可以高一点，上面说的快速查其实就是查询的快速查。

但是空间复杂度太大了，然后你发现我们查的只有 $f(x,[x+1,r])$ 和 $f(x,[l,x-1])$ ，以后一种为例，所有差分出来的 $f(x,[1,x-1])$ 只有 $n$ 种可以预处理，而端点大跨步 $R:x\to y$ 中间的那些询问其实是连续的，问的是 $f(x,[1,l]),x\in$ 一个区间，那我们可以把这个区间挂在 $l$ 上，这样直接枚举区间，省下了空间复杂度和时间常数。

注意范围，我们需要正着倒着扫描线两遍。

注意我们实质上求出的是答案的差分，最后要做一遍前缀和。

P4887 【模板】莫队二次离线（第十四分块(前体)）

珂朵莉给了你一个序列 $a$ ，每次查询给一个区间 $[l,r]$ ，查询 $l \leq i< j \leq r$ ，且 $a_i \oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。 $\oplus$ 是指按位异或。

$1 \leq n, m \leq 100000$ ， $0 \leq a_i, k < 16384$ 。

套板子，复杂度 $\binom{14}{7}n+n\sqrt n+n\sqrt m$ 。

F(i,1,n) {
    sR[i]=bn[a[i]];
    for(int x:P) bn[a[i]^x]++;
}
memset(bn,0,sizeof bn);
UF(i,n,1) {
    sL[i]=bn[a[i]];
    for(int x:P) bn[a[i]^x]++;
}
F(i,1,m) l[i]=read(),r[i]=read(),p[i]=i;
sort(p+1,p+m+1,[](int x,int y){return id(l[x])==id(l[y])?r[x]<r[y]:l[x]<l[y];});
int L=1,R=0;
F(j,1,m) {int i=p[j];
    if(R<r[i]) Rz[L]+=X{R,i};
    while(R<r[i]) ans[i]+=sR[++R];
    if(L>l[i]) Lz[R]+=X{L,i};
    while(L>l[i]) ans[i]+=sL[--L];
    if(R>r[i]) Rz[L]+=X{R,i};
    while(R>r[i]) ans[i]-=sR[R--];
    if(L<l[i]) Lz[R]+=X{L,i};
    while(L<l[i]) ans[i]-=sL[L++];
} 
memset(bn,0,sizeof bn);
F(j,1,n) {
    for(auto[R,i]:Rz[j]) {
        while(R<r[i]) ans[i]-=bn[a[++R]];
        while(R>r[i]) ans[i]+=bn[a[R--]];
    }
    for(int x:P) bn[a[j]^x]++;
}
memset(bn,0,sizeof bn);
UF(j,n,1) {
    for(auto[L,i]:Lz[j]) {
        while(L>l[i]) ans[i]-=bn[a[--L]];
        while(L<l[i]) ans[i]+=bn[a[L++]];
    }
    for(int x:P) bn[a[j]^x]++;
}
F(i,1,m) ans[p[i]]+=ans[p[i-1]];

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

区间逆序对。

$n\le10^5,250\text{ ms,31.25 MB}$ 。

只有 $n$ 次修改，搞一个根号修 $\mathcal O(1)$ 查。