[CQOI2018]异或序列
[CQOI2018]异或序列题目描述已知一个长度为n的整数数列(a_1,a_2,...,a_n)给定查询参数l、r,问在(a_l,a_{l+1},a_r)?区间内,有多少子序列满足异或和等于k。也就是说,对于所有的x,y (I ≤ x ≤ y ≤ r),能够满足(a_x bigoplus a_{x+1} bigoplus ... bigoplus a_y = k)的x,y有多少组。 输入输出格式输入格式: 输入文件第一行,为3个整数n,m,k。 第二行为空格分开的n个整数,即(a_1,..a_n)?。 接下来m行,每行两个整数(l_j,r_j)?,表示一次查询。 输出格式: 输出文件共m行,对应每个查询的计算结果。 输入输出样例输入样例#1: 复制 4 5 1 输出样例#1: 复制 4 说明对于30%的数据,(1 ≤ n,m ≤ 1000) 对于100%的数据,(1 ≤ n,m ≤ 10^5,0 ≤ k,a_i ≤ 10^5,1 ≤ l_j ≤ r_j ≤ n) 题解首先我们明确一点。那就是异或的性质。 代码#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int cnt[500001],val[500001],k,n,tmp,sum,ans[500001],ch[500001]; struct node{ int l,r,id; }t[500001]; int read() { int x=0,w=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*w; } bool cmp(node a,node b) { if(a.l/tmp==b.l/tmp)return a.r<b.r; return a.l<b.l; } void init() { n=read();m=read();k=read();tmp=sqrt(n); for(int i=1;i<=n;i++)val[i]=read(),val[i]^=val[i-1];//cout<<val[i]; for(int i=1;i<=m;i++) { t[i].l=read();t[i].r=read(); t[i].id=i; } sort(t+1,t+m+1,cmp); } void delet(int x) { //cout<<"delet "<<x<<endl; cnt[val[x]]--; sum-=cnt[val[x]^k]; } void add(int x) { // cout<<"add "<<x<<endl; sum+=cnt[val[x]^k]; cnt[val[x]]++; } void solve() { cnt[0]=1; int left=1,right=0; for(int i=1;i<=m;i++) { while(right<t[i].r)add(++right); while(right>t[i].r)delet(right--); while(left<t[i].l){delet(left-1);left++;} while(left>t[i].l){left--;add(left-1);} ans[t[i].id]=sum; } for(int i=1;i<=m;i++) printf("%dn",ans[i]); } int main() { init(); solve(); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- 【读书小结】—— Kaspersky anti-virus engine technology
- [Delphi] Unit 'SimpleTimer' implicitly impor
- 在vs中集成lua开发环境
- Learning English with EnglishClass101.com---10 Habits o
- 在groovy多行字符串中删除缩进
- delphi – 为什么有条件的断点使我的程序减少了很多?
- Delphi 常用属性说明
- Perl学习笔记 之 [ 函数, 参数, @_, $_, $_[0], shift ]
- Lua打印table升级版
- 关于Delphi XE2的FMX的一点点研究之消息篇