@ysner
2018-04-24T20:19:08.000000Z
字数 1776
阅读 1926
莫队
给你一个大小为的序列,然后给你一个数字,再给出组询问,询问给出一个区间,问这个区间里面有多少个区间的异或结果为.
莫队裸题。
于是我交了份傻逼代码。(于是RE成30分)
struct line
{
int l,r,pos;
bool operator < (const line &o) const {return (l/len)==(o.l/len)?(r<o.r):(l<o.l);}
}a[N];
il void add(re int x,re int f,re int ysn)
{
re int tot=0;
if(!f)
fp(i,x,R)
{
tot^=p[i];
if(tot==k) now+=ysn;
}
else
fq(i,x,L)
{
tot^=p[i];
if(tot==k) now+=ysn;
}
}
int main()
{
n=gi();m=gi();k=gi();len=sqrt(n);
fp(i,1,n) p[i]=gi();
fp(i,1,m) a[i].l=gi(),a[i].r=gi(),a[i].pos=i;
sort(a+1,a+1+m);
L=1,R=0;
fp(i,1,m)
{
re int l=a[i].l,r=a[i].r;
while(L>l) add(--L,0,1);
while(R<r) add(++R,1,1);
while(L<l) add(L++,0,-1);
while(R>r) add(R--,1,-1);
ans[a[i].pos]=now;
}
fp(i,1,m) printf("%d\n",ans[i]);
return 0;
}
喂喂喂,极限复杂度是呢。。。
于是用下脑子,发现可以存一下当前统计答案的区间中每种值的数目,每加上或减去时,相应统计的贡献即可。
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,k,p[N],len,ans[N],now,L,R,num[N];
struct line
{
int l,r,pos;
bool operator < (const line &o) const {return (l/len)==(o.l/len)?(r<o.r):(l<o.l);}
}a[N];
il int gi()
{
re char ch=getchar();
re int x=0,t=1;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void add(re int x){now+=num[k^p[x]];++num[p[x]];}
il void del(re int x){--num[p[x]];now-=num[k^p[x]];}
int main()
{
n=gi();m=gi();k=gi();len=sqrt(n);
fp(i,1,n) p[i]=gi()^p[i-1];
fp(i,1,m) a[i].l=gi()-1,a[i].r=gi(),a[i].pos=i;
sort(a+1,a+1+m);
L=0,R=-1;
fp(i,1,m)
{
re int l=a[i].l,r=a[i].r;
while(L>l) add(--L);
while(R<r) add(++R);
while(L<l) del(L++);
while(R>r) del(R--);
ans[a[i].pos]=now;
}
fp(i,1,m) printf("%d\n",ans[i]);
return 0;
}