LuoguP4462 [CQOI2018]异或序列

https://zybuluo.com/ysner/note/1124952

题面

给你一个大小为\(n\)的序列，然后给你一个数字\(k\)，再给出\(m\)组询问，询问给出一个区间，问这个区间里面有多少个区间的异或结果为\(k\).

\(n,m\leq10^5\)

解析

莫队裸题。

于是我交了份傻逼代码。（于是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;

}

喂喂喂，极限复杂度是\(O(n^2)\)呢。。。

于是用下脑子，发现可以存一下当前统计答案的区间中每种值的数目，每加上或减去\(x\)时,相应统计\(num[k\bigoplus x]\)的贡献即可。

// 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;

}

巴特西

LuoguP4462 [CQOI2018]异或序列

https://zybuluo.com/ysner/note/1124952

题面

解析

最新文章

热门文章