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

· · 题解

这道题就是一个经（du）典（liu）的莫队二次离线。

不卡常，不需要其他的数据结构。

我们先来讲一下莫队二次离线是什么神仙。

Solution

首先，我们会发现某些莫队在转移的过程中时间复杂度比较大。

我们先把问题给差分化。

设 (l, r) 区间内的数异或 k 的满足条件的数的个数为 f(l, r, k)。

比如说在这道题里，r 指针每向右移动一位，对答案的贡献为：

f(l, r-1, a[r])

我们把它用前缀和的形式表示：

f(1, r-1, a[r]) - f(1, l, a[r])

很显然，前面的那个 f(1, r-1, a[r]) 是可以预处理出来的。

考虑后面的 f(1, l, a[r]) 怎么算。

我们可以用一个 vector 数组。

对于每一个 f(1, l, a[r])，把 vec[l].push_back(a[r])。

然后跑一篇 for(int i=1;i<=n;i++) 即可。

但是，我们会神奇的发现这样由于有 N \sqrt N 次移动。

空间复杂度是 O(N \sqrt N)，原地爆炸。

所以我们能想到每次的移动是连续的。

普通的莫队是这样移动的：

while (r<q[i].r) r++;

所以我们只需要把移动的区间 (r+1, q[i].r) 存下来就行了。

这样空间复杂度便降到了 O(N + M)。

想练练手的，左转 P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

这道题加了一个数据结构叫值域分块，其实就是把分块当一个桶来使。

Code

看一下代码，感性理解一下，应该是能懂的。

温馨提示

%:include"bits/stdc++.h"
using namespace std;
#define N (int)(1e5+10)
int n,m,a[N],c[N],tot=0,siz,belong[N],l=1,r=0,K;
int t[N];
long long ans[N],b[N],d[N]; //不开 long long 见祖宗
struct query {
    int l,r,id;
}q[N];
struct node {
    int l,r,p,id;
};
vector<node>vec1[N],vec2[N];
static char buf[100000],*p1=buf,*p2=buf;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
int read() {
    int res=0;
    char c=gc;
    while (!isdigit(c)) c=gc;
    while (isdigit(c)) res=(res<<1)+(res<<3)+(c^48),c=gc;
    return res;
}
void write(long long x) {
    static int sta[50],top=0;
    do {
        sta[top++]=x%10,x/=10;
    }while (x);
    while (top) putchar(sta[--top]+48);
    putchar('\n');
}
inline bool cmp(query a,query b) {
    return (belong[a.l]^belong[b.l]? belong[a.l]<belong[b.l]:(belong[a.l]&1? a.r<b.r:a.r>b.r));
}
inline int lowbit(int x) {
    return x&(-x);
}
inline int one(int x) {
    int ans=0;
    while (x>0) {
        ans++; x-=lowbit(x);
    }
    return ans;
}
signed main() {
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++) cin>>a[i];
    if (K>14) {
        for(int i=1;i<=m;i++) cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<=16384;i++) if (one(i)==K) c[++tot]=i; //k 可能为 0
    siz=sqrt(n); for(int i=1;i<=n;i++) belong[i]=(i-1)/siz+1;
    for(int i=1;i<=m;i++) {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;i++) {
        if (r<q[i].r) vec1[l].push_back((node){r+1,q[i].r,1,q[i].id});
        if (r>q[i].r) vec1[l].push_back((node){q[i].r+1,r,-1,q[i].id});
        r=q[i].r;
        if (l<q[i].l) vec2[r].push_back((node){l,q[i].l-1,-1,q[i].id});
        if (l>q[i].l) vec2[r].push_back((node){q[i].l,l-1,1,q[i].id});
        l=q[i].l;
    }
    for(int i=1;i<=n;i++) {
        b[i]=1ll*t[a[i]]; // 异或具有交换性，a[i]^a[j]=c[k]，则 a[i]^c[j]=a[j]
        for(int j=1;j<=tot;j++) t[a[i]^c[j]]++;
    }
    memset(t,0,sizeof(t));
    for(int i=n;i>=1;i--) {
        d[i]=1ll*t[a[i]];
        for(int j=1;j<=tot;j++) t[a[i]^c[j]]++;
    }
    memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++) {
        for(int j=0;j<vec1[i].size();j++) {
            for(int k=vec1[i][j].l;k<=vec1[i][j].r;k++) {
                ans[vec1[i][j].id]+=1ll*vec1[i][j].p*(b[k]-1ll*t[a[k]]);
            }
        }
        for(int j=1;j<=tot;j++) t[a[i]^c[j]]++;
    }
    memset(t,0,sizeof(t));
    for(int i=n;i>=1;i--) {
        for(int j=0;j<vec2[i].size();j++) {
            for(int k=vec2[i][j].l;k<=vec2[i][j].r;k++) {
                ans[vec2[i][j].id]+=1ll*vec2[i][j].p*(d[k]-1ll*t[a[k]]);
            }
        }
        for(int j=1;j<=tot;j++) t[a[i]^c[j]]++;
    }
    for(int i=2;i<=m;i++) ans[q[i].id]+=ans[q[i-1].id]; //记得把差分还原
    for(int i=1;i<=m;i++) write(ans[i]);
    return 0;
}

完结撒花！ ^.^