[关闭]
@ysner 2018-04-24T20:19:08.000000Z 字数 1776 阅读 1905

LuoguP4462 [CQOI2018]异或序列

莫队


题面

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

解析

莫队裸题。
于是我交了份傻逼代码。(于是RE成30分)

  1. struct line
  2. {
  3. int l,r,pos;
  4. bool operator < (const line &o) const {return (l/len)==(o.l/len)?(r<o.r):(l<o.l);}
  5. }a[N];
  6. il void add(re int x,re int f,re int ysn)
  7. {
  8. re int tot=0;
  9. if(!f)
  10. fp(i,x,R)
  11. {
  12. tot^=p[i];
  13. if(tot==k) now+=ysn;
  14. }
  15. else
  16. fq(i,x,L)
  17. {
  18. tot^=p[i];
  19. if(tot==k) now+=ysn;
  20. }
  21. }
  22. int main()
  23. {
  24. n=gi();m=gi();k=gi();len=sqrt(n);
  25. fp(i,1,n) p[i]=gi();
  26. fp(i,1,m) a[i].l=gi(),a[i].r=gi(),a[i].pos=i;
  27. sort(a+1,a+1+m);
  28. L=1,R=0;
  29. fp(i,1,m)
  30. {
  31. re int l=a[i].l,r=a[i].r;
  32. while(L>l) add(--L,0,1);
  33. while(R<r) add(++R,1,1);
  34. while(L<l) add(L++,0,-1);
  35. while(R>r) add(R--,1,-1);
  36. ans[a[i].pos]=now;
  37. }
  38. fp(i,1,m) printf("%d\n",ans[i]);
  39. return 0;
  40. }

喂喂喂,极限复杂度是呢。。。
于是用下脑子,发现可以存一下当前统计答案的区间中每种值的数目,每加上或减去时,相应统计的贡献即可。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<cmath>
  7. #include<algorithm>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=5e5+100;
  15. int n,m,k,p[N],len,ans[N],now,L,R,num[N];
  16. struct line
  17. {
  18. int l,r,pos;
  19. bool operator < (const line &o) const {return (l/len)==(o.l/len)?(r<o.r):(l<o.l);}
  20. }a[N];
  21. il int gi()
  22. {
  23. re char ch=getchar();
  24. re int x=0,t=1;
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. il void add(re int x){now+=num[k^p[x]];++num[p[x]];}
  31. il void del(re int x){--num[p[x]];now-=num[k^p[x]];}
  32. int main()
  33. {
  34. n=gi();m=gi();k=gi();len=sqrt(n);
  35. fp(i,1,n) p[i]=gi()^p[i-1];
  36. fp(i,1,m) a[i].l=gi()-1,a[i].r=gi(),a[i].pos=i;
  37. sort(a+1,a+1+m);
  38. L=0,R=-1;
  39. fp(i,1,m)
  40. {
  41. re int l=a[i].l,r=a[i].r;
  42. while(L>l) add(--L);
  43. while(R<r) add(++R);
  44. while(L<l) del(L++);
  45. while(R>r) del(R--);
  46. ans[a[i].pos]=now;
  47. }
  48. fp(i,1,m) printf("%d\n",ans[i]);
  49. return 0;
  50. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注