题解-CF617E XOR and Favorite Number

题面

CF617E XOR and Favorite Number

给定 \(n,m,k\) 和 \(n\) 个数的序列 \(a_i\)，\(m\) 次求区间 \([l,r]\) 中异或值为 \(k\) 的子序列个数。

数据范围：\(1\le n,m\le 10^5\)，\(0\le k,a_i\le 10^6\)。

蒟蒻语

这题的莫队做法太一眼，谁都会是吧（

那么蒟蒻就来写一个过不了这题（会 MLE、TLE）但是可以在线且很有趣的做法：分块。

说不定谁去开大限制卡个离线蒟蒻解就成正解了。

蒟蒻解

设 \(f(l,r)\) 表示区间 \([l,r]\) 的异或值为 \(k\) 的子区间数。

设 \(cross(l,r)\) 表示区间左端点在 \([1,l]\) 右端点在 \([r,n]\) 的异或值为 \(k\) 的区间数。

先容斥一下（\(cross(l-1,r+1)\) 为了抵消掉 \(f(1,n)\) 中多余的部分）：

\[ans=f(l,r)=f(1,r)+f(l,n)-f(1,n)+cross(l-1,r+1)
\]

这东西前 \(3\) 项可以时空 \(\Theta(n)\) 求出，只是最后一项太恶心了，蒟蒻的方法是分块时空 \(\Theta(n\sqrt{n})\)（巨佬如果有更优做法一定要指教蒟蒻）。

设有 \(b_n\) 个块，每个块为 \([l_i,r_i]\)。

先预处理 \(i<j:cro_{i,j}=cross(r_i,l_j)\)，做法同莫队，前缀和加 unordered_map。

再记 \(lc_{i,c}\) 表示 \([1,r_i]\) 中前缀和为 \(c\) 的个数，\(rc_{i,c}\) 表示 \([l_i,n]\) 中前缀和为 \(c\) 的个数。

求 \(cross(l,r)\) 时，设 \(lb=\max_{i=1}^{b_n} r_i\le l\)，\(rb=\min_{i=1}^{b_n} l_i\ge r\)。

结果就是 \(cro_{lb,rb}\) 再加上

左端点在 \([r_{lb}+1,l]\) 右端点在 \([l_{rb},n]\) 的答案（用 \(rc\) 数组求）

和左端点在 \([1,r_{lb}]\) 右端点在 \([r,l_{rb}-1]\) 的答案（用 \(lc\) 数组求）

和左端点在 \([r_{lb}+1,l]\) 右端点在 \([r,l_{rb}-1]\) 的答案（用前缀和加 unordered_map）。

然后这题就做完了，别忘了这个做法过不了。

代码

#include <bits/stdc++.h>

using namespace std;

//Start

typedef long long ll;

typedef double db;

#define mp(a,b) make_pair(a,b)

#define x first

#define y second

#define be(a) a.begin()

#define en(a) a.end()

#define sz(a) int((a).size())

#define pb(a) push_back(a)

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

//Data

const int N=1e5;

int n,m,k,sm[N+2];

int a[N+1]; ll la[N+2],ra[N+2];

unordered_map<int,int> cnt;

//Block

const int B=320;

int sz,b[N+1];

ll cro[B+2][B+2];

unordered_map<int,int> lc[B+2],rc[B+2];

void build(){

    sz=sqrt(n);

    for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1;

    for(int i=1;i<=b[n];i++)

        for(int j=1;j<=min(sz*i,n);j++) lc[i][sm[j-1]]++;

    for(int i=1;i<=b[n];i++)

        for(int j=n;j>=sz*(i-1)+1;j--) rc[i][sm[j]]++;

    for(int i=1;i<=b[n];i++){

        for(int t=b[n];t>i;t--){

            for(int j=sz*(t-1)+1;j<=min(sz*t,n);j++)

                cro[i][t]+=lc[i][sm[j]^k];

            cro[i][t]+=cro[i][t+1];

        }

    }

}

ll cross(int l,int r){

    if(l<0||r>n) return 0;

    int lb=b[l+1]-1,rb=b[r-1]+1;

    ll res=cro[lb][rb];

    cnt.clear();

    for(int i=lb*sz+1;i<=l;i++) cnt[sm[i-1]]++;

    for(int i=r;i<=min((rb-1)*sz,n);i++) res+=cnt[sm[i]^k];

    for(int i=lb*sz+1;i<=l;i++) res+=rc[rb][sm[i-1]^k];

    for(int i=r;i<=min((rb-1)*sz,n);i++) res+=lc[lb][sm[i]^k];

    return res;

}

//Main

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0),cout.tie(0);

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) sm[i]=sm[i-1]^a[i];

    cnt.clear(),cnt[sm[0]]++;

    for(int i=1;i<=n;i++) la[i]=la[i-1]+cnt[sm[i]^k],cnt[sm[i]]++;

    cnt.clear(),cnt[sm[n]]++;

    for(int i=n;i>=1;i--) ra[i]=ra[i+1]+cnt[sm[i-1]^k],cnt[sm[i-1]]++;

    assert(la[n]==ra[1]);

    // for(int i=1;i<=n;i++) cout<<la[i]<<' ';cout<<'\n';

    // for(int i=1;i<=n;i++) cout<<ra[i]<<' ';cout<<'\n';

    build();

    for(int i=0;i<m;i++){

        int l,r; cin>>l>>r;

        cout<<ra[l]+la[r]-la[n]+cross(l-1,r+1)<<'\n';

    }

    return 0;

}

祝大家学习愉快！

巴特西

题解-CF617E XOR and Favorite Number

题面

蒟蒻语

蒟蒻解

代码

最新文章

热门文章