CF617E 题解

E1_de5truct0r · 2023-02-18 17:26:43 · 题解

莫队题，但是可以分块。

下文中假设值域为 W=10^6，块长为 B，符号 \oplus 表示按位异或运算。

思路

首先我们要求出前缀异或数组 s，并且先把序列分成若干块。

然后定义两个数组：

求解 g_{i,j} 很简单，可以枚举 i 然后每次在 g_{i-1,j} 的基础上添加。复杂度 O\left(\dfrac{nW}{B}\right)。

求解 f_{i,j}，可以枚举 i 和 j，然后每次对于 f_{i,j} 我们可以从 f_{i,j-1} 转移过来，并且开一个桶 mp 记录一下出现过的值的数量，每次对于 s_p 的贡献就是 mp_{s_p \oplus k}。复杂度 O\left(\dfrac{nB^2}{B}\right)=O(nB)。

然后考虑每次怎么计算答案。假设一次询问 l,r，l 所在的块右端点为 rig_l，r 所在的块左端点为 lef_r。如果我们用 (i,j) 表示一个满足条件的子序列 a_i,a_{i+1},\dots,a_j，那么答案分成三部分：

因此我们的时间复杂度是 O\left(\dfrac{nW}{B}+nB+qB\right)，空间是 O\left(\dfrac{nW}{B}\right)。这个时候你可以去把异或序列这题写了。

不过这道题显然这个复杂度时间空间都无法接受。

一些小优化

因此我们考虑对值域离散化。因为有用的异或值实际只有 s_i 和 s_i\oplus k 所以有效的 W 只有 2n=2 \times 10^5 个。

所以加一个离散化之后复杂度可以降到 O\left(\dfrac{n^2}{B}+nB+qB\right)。显然这个时候 B=\sqrt{n} 最优，复杂度 O(n\sqrt{n}+q\sqrt{n})。

另外，记得开 long long。不过这个 long long 很难调，容易发现只有 f 数组需要 long long，切忌直接无脑改，否则你会因为空间不够调大块长，然后你会发现调大之后直接 TLE 了。

于是你得到了一个 3.96s 极限 AC 分块代码。

代码

卡常内容很多，极其恶心只能说。

不保证每次能过，因为我这个是压着时限过的（

#include <bits/stdc++.h>

// 缺省源↓

#define _cst const
#define _IfD long long
#define _siz 20
char buf[1<<_siz],buffer[1<<_siz],*p1=buf,*p2=buf,chhhhh=' ';
int op1=-1; _cst int op2=(1<<_siz)-1;
inline char gc(){return (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<_siz,stdin)),p1==p2?EOF:*p1++);}
inline void flush(){fwrite(buffer,1,op1+1,stdout),op1=-1;}
inline void pc(_cst char &x){if(op1==op2)flush();buffer[++op1]=x;}
template<typename T>void read(T &w){
    w=0;bool f=1;char ch=gc();
    for(;ch<=32;ch=gc()); if(ch=='-')f=0;
    for(;'0'<=ch && ch<='9';ch=gc()) w=(w<<1)+(w<<3)+(ch^48);
    w=f?w:-w;
}template<typename T,typename ...Arg>void read(T &w,Arg &...arg){
    read(w); read(arg...);
}template<typename T>void wrt(T x){
    if(x<0) pc('-'),x=-x;
    if(x>9) wrt(x/10);
    pc(x%10|48);
}template<typename T>void write(T x){
    wrt(x); pc(chhhhh);
}template<typename T,typename ...Arg>void write(T x,Arg ...arg){
    write(x); write(arg...);
}inline _IfD pow_10(_IfD x){
    _IfD base=10,ans=1;
    while(x) ans*=((x&1)?base:1),base*=base,x>>=1;
    return ans;
}template<typename T>void readd(T &w){
    w=0; _IfD x=0,cnt=0; bool f=1; char ch=gc();
    for(;ch<=32;ch=gc()); if(ch=='-')f=0;
    for(;'0'<=ch && ch<='9';ch=gc()) x=(x<<1)+(x<<3)+(ch^48);
    w=(T)(f?x:-x);
    if(ch!='.') return; x=0,ch=gc();
    for(;'0'<=ch && ch<='9';ch=gc(),++cnt) x=(x<<1)+(x<<3)+(ch^48);
    T tmp=(T)(x/(T)pow_10(cnt));
    w=w+(T)(f?tmp:-tmp);
}template<typename T,typename ...Arg>void readd(T &w,Arg &...arg){
    readd(w); readd(arg...);
    readd(w); readd(arg...);
}
template<typename T>inline T qmax(_cst T &a,_cst T &b){return a>b?a:b;}
template<typename T,typename ...Arg>inline T qmax(_cst T &a,_cst T &b,_cst Arg &...arg){return qmax(a,qmax(b,arg...));}
template<typename T>inline T qmin(_cst T &a,_cst T &b){return a<b?a:b;}
template<typename T,typename ...Arg>inline T qmin(_cst T &a,_cst T &b,_cst Arg &...arg){return qmin(a,qmin(b,arg...));}
template<typename T>inline void qswap(T &a,T &b){a+=b,b=a-b,a-=b;}

// 缺省源↑

using namespace std;

const int MAXN=100005;

int n,q,k,len,tot;
int a[MAXN],s[MAXN];

int c[MAXN<<1],fk,lsh[1048580];

int bel[MAXN],g[305][MAXN<<1];
long long f[305][305],mp[MAXN<<1];

inline long long get(int L,int R,int x){
    if(L>R) return 0;
    return g[R][x]-g[L-1][x];
}

long long solve(int l,int r){
    if(bel[l]==bel[r]){
        int ans=0; vector<int> vec;
        ++mp[lsh[s[l-1]]]; vec.push_back(lsh[s[l-1]]);
        for(register int i=l;i<=r;++i){
            ans+=mp[lsh[s[i]^k]],++mp[lsh[s[i]]];
            vec.push_back(lsh[s[i]]);
        }
        for(register int u:vec) mp[u]=0;
        return ans;
    }

    long long tmp; 

    long long ans=0; vector<int> vec; tmp=ans;
    ++mp[lsh[s[l-1]]]; vec.push_back(lsh[s[l-1]]);
    ans+=get(bel[l]+1,bel[r]-1,lsh[s[l-1]^k]);
    for(register int i=l;i<=bel[l]*len;++i){
        ans+=mp[lsh[s[i]^k]];
        if(i!=bel[l]*len) ans+=get(bel[l]+1,bel[r]-1,lsh[s[i]^k]);
        ++mp[lsh[s[i]]],vec.push_back(lsh[s[i]]);
    }
    for(register int u:vec) mp[u]=0; vec.clear();

    ++mp[lsh[s[bel[l]*len]]],vec.push_back(lsh[s[bel[l]*len]]);
    for(register int i=(bel[r]-1)*len+1;i<=r;++i){
        ans+=mp[lsh[s[i]^k]]+get(bel[l]+1,bel[r]-1,lsh[s[i]^k]);
        ++mp[lsh[s[i]]],vec.push_back(lsh[s[i]]);
    }

    for(register int u:vec) mp[u]=0; vec.clear();

    ++mp[lsh[s[l-1]]]; vec.push_back(lsh[s[l-1]]);
    for(register int i=l;i<bel[l]*len;++i){
        ++mp[lsh[s[i]]];
        vec.push_back(lsh[s[i]]);
    }
    for(register int i=(bel[r]-1)*len+1;i<=r;++i) ans+=mp[lsh[s[i]^k]];

    for(register int u:vec) mp[u]=0; vec.clear();

    return ans+f[bel[l]+1][bel[r]-1];
}

signed main(){
//  freopen("tst.in","r",stdin);
//  freopen("my.out","w",stdout);
    read(n,q,k);
    for(register int i=1;i<=n;++i) read(a[i]),s[i]=s[i-1]^a[i];

    for(register int i=1;i<=n;++i) c[++fk]=s[i],c[++fk]=s[i]^k;
    sort(c+1,c+1+fk); int M=unique(c+1,c+1+fk)-c-1;
    for(register int i=1;i<=M;++i) lsh[c[i]]=i;

    len=340;

    for(register int i=1;i<=n;++i){
        if(i%len==1) ++tot;
        bel[i]=tot;
    }

    g[0][0]=1;
    for(register int i=1;i<=tot;++i){
        memset(mp,0,sizeof(mp));
        for(register int j=1;j<=200000;++j) g[i][j]=g[i-1][j];
        for(register int j=(i-1)*len+1;j<=qmin(n,i*len);++j) g[i][lsh[s[j]]]++;
        mp[lsh[s[(i-1)*len]]]++;
        for(register int j=i;j<=tot;++j){
            f[i][j]=f[i][j-1];
            for(register int p=(j-1)*len+1;p<=qmin(n,j*len);p++) f[i][j]+=mp[lsh[s[p]^k]],mp[lsh[s[p]]]++;
        }
    }

//  cout<<f[2][2]<<'\n';

    memset(mp,0,sizeof(mp));

    int Q=0;
    while(q--){
        int l,r; read(l,r);
        wrt(solve(l,r)),pc(10);
    }

    return flush(),0;
}