并不对劲的复健训练-bzoj5301:loj2534:p4462 [CQOI2018]异或序列

题目大意

给出一个序列\(a_1,...,a_n\)(\(a,n\leq 10^5\))，一个数\(k\)(\(k\leq 10^5\))，\(m\)(\(m\leq10^5\))次询问，每次询问给\(l,r\)，求\([l,r]\)有多少个子区间\([x,y]\)满足\(a_x \bigoplus ...\bigoplus a_y=k\)

题解

求前缀异或和\(s_1,...,s_n\)，询问变成对于每个\(x\in [l,r]\)，总共有多少\(y\in[l-1,x)\)满足\(a_x\bigoplus a_y=k\)，即询问有多少个\(y\in[l-1,x)\)满足\(a_x\bigoplus k=a_y\)

这样就会有一个暴力的想法：从\(l\)到\(r\)枚举\(x\)，维护\(a_{l-1},...,a_{x-1}\)中每个值的出现次数。

发现\(k\)不变，没有修改或强制在线，就可以考虑离线。

假设当前考虑的区间是\([l_0,r_0]\)，把区间变成\([l_0-1,r_0]\)时要考虑\(a_{l_0-2}\)与\(a_{l_0-1},...,a_{r_0}\)的贡献。把区间变成\([l_0+1,r_0]\)时同理。

假设当前考虑的区间是\([l_0,r_0]\)，把区间变成\([l_0,r_0+1]\)时要考虑\(a_{r_0+1}\)与\(a_{l_0-1},...,a_{r_0}\)的贡献。把区间变成\([l_0,r_0-1]\)时同理。

代码

#include<algorithm>

#include<bitset>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];k!=-1;k=nxt[k])

#define maxn 100007

#define maxk ((1<<17)+1)

#define LL long long

using namespace std;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)&&ch!='-')ch=getchar();

	if(ch=='-')f=-1,ch=getchar();

	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x*f;

}

void write(LL x)

{

	if(x==0){putchar('0'),putchar('\n');return;}

	int f=0;char ch[20];

	if(x<0)putchar('-'),x=-x;

	while(x)ch[++f]=x%10+'0',x/=10;

	while(f)putchar(ch[f--]);

	putchar('\n');

	return;

}

int blo=300,num[maxk],num2[maxk],a[maxn],n,m,k;

LL ans[maxn],nowans;

struct quest{int l,r,id;}q[maxn];

bool cmp(quest x,quest y){return (x.l/blo==y.l/blo)?(x.r<y.r):(x.l<y.l);}

void addl(int id,int f)

{

	if(f==1)num2[a[id]]++;

	nowans+=(LL)f*num2[a[id-1]^k];

	if(f==-1)num2[a[id]]--;

	num[a[id-1]]+=f;

}

void addr(int id,int f)

{

	if(f==1)num[a[id-1]]++;

	nowans+=(LL)f*num[a[id]^k];

	if(f==-1)num[a[id-1]]--;

	num2[a[id]]+=f;

}

int main()

{

	n=read(),m=read(),k=read();

	rep(i,1,n)a[i]=a[i-1]^read();

	rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;//cout<<"ookk"<<endl;

	sort(q+1,q+m+1,cmp);

	int nowl=1,nowr=1;num[0]++,num2[a[1]]++,nowans+=(k==a[1])?1:0;

	rep(i,1,m)

	{

		while(nowl>q[i].l)nowl--,addl(nowl,1);

		while(nowr<q[i].r)nowr++,addr(nowr,1);

		while(nowl<q[i].l)addl(nowl,-1),nowl++;

		while(nowr>q[i].r)addr(nowr,-1),nowr--;

		ans[q[i].id]=nowans;

	}

	//rep(i,1,n)cout<<a[i]<<" ";cout<<endl;

	//rep(i,1,n)cout<<b[i]<<" ";cout<<endl;

	rep(i,1,m)write(ans[i]);

	return 0;

}

一些感想

想玩飞天虫棍！！！