Codeforces Round #340 (Div. 2) E. XOR and Favorite Number 莫队算法
E. XOR and Favorite Number
题目连接:
http://www.codeforces.com/contest/617/problem/E
Descriptionww.co
Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k.
Input
The first line of the input contains integers n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000) — the length of the array, the number of queries and Bob's favorite number respectively.
The second line contains n integers ai (0 ≤ ai ≤ 1 000 000) — Bob's array.
Then m lines follow. The i-th line contains integers li and ri (1 ≤ li ≤ ri ≤ n) — the parameters of the i-th query.
Output
Print m lines, answer the queries in the order they appear in the input.
Sample Input
6 2 3
1 2 1 1 0 3
1 6
3 5
Sample Output
7
0
Hint
题意
给你n个数,然后M次询问,问你l,r区间内有多少对数,使得a[i]^a[j] = k
题解:
无修改,而且可以知道[l,r]可以O(1)就出[l-1,r],[l,r+1],[l+1,r],[l,r-1]的数据的
所有很显然的莫队算法搞一搞就好了
直接大暴力,注意不能再带log,所以直接开数组存就好了
注意,数组得开大一点哦
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 120010;
int a[maxn],pos[maxn];
long long ans,flag[5000000];
long long Ans[maxn];
int k;
struct query
{
int l,r,id;
}Q[maxn];
bool cmp(query a,query b)
{
if(pos[a.l]==pos[b.l])
return a.r<b.r;
return pos[a.l]<pos[b.l];
}
void Updata(int x)
{
ans+=flag[a[x]^k];
flag[a[x]]++;
}
void Delete(int x)
{
flag[a[x]]--;
ans-=flag[a[x]^k];
}
int main()
{
int n,m;
scanf("%d%d%d",&n,&m,&k);
int sz =ceil(sqrt(1.0*n));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=(i-1)/sz;
}
for(int i=1;i<=n;i++)
a[i]^=a[i-1];
for(int i=1;i<=m;i++)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].id = i;
}
sort(Q+1,Q+1+m,cmp);
int l = 1,r = 0;
ans=0;
flag[0]=1;
for(int i=1;i<=m;i++)
{
int id = Q[i].id;
while(r<Q[i].r)
{
r++;
Updata(r);
}
while(l>Q[i].l)
{
l--;
Updata(l-1);
}
while(r>Q[i].r)
{
Delete(r);
r--;
}
while(l<Q[i].l)
{
Delete(l-1);
l++;
}
Ans[id]=ans;
}
for(int i=1;i<=m;i++)
printf("%lld\n",Ans[i]);
}
最新文章
- bzoj3037--贪心
- jquery仿搜狐投票动画代码
- 【转】mysql忘记密码(未初始化)
- A Popup Progress Window
- Unity开发 资源准备
- [转]Dynamics AX and Generic collections of .Net
- Javascript实现摩斯码加密解密
- qsort 排序功能 总结
- 锅巴H264播放器地址和说明
- @Controller注解
- 利用java反射机制实现读取excel表格中的数据
- jQuery 源码学习 - 01 - 简洁的 $(&#39;...&#39;)
- [Swift]LeetCode1000. 合并石头的最低成本 | Minimum Cost to Merge Stones
- 使用IntelliJ IDEA新建Java Web后端resfulAPI模板
- 树莓派(centos7)安装mysql
- HTML-Ronoob-基础教程:HTML 字符实体
- windows 远程连接
- linux中sftp默认登录的端口号是多少? sftp通过指定的端口号连接?sftp默认端口号
- Tomcat不自动解压问题
- 20155214 2016-2017-2 《Java程序设计》第4周学习总结
热门文章
- ZOJ 2599 Graduated Lexicographical Ordering (数位DP)
- Asp.net MVC4 使用EF实现数据库的增删改查
- 标准IO
- bzoj 3594 [Scoi2014]方伯伯的玉米田(DP+二维BIT)
- DzzOffice1.0 Beta2 全新安装图文教程及界面简单了解
- python 使用 setup.py 方式安装及包的卸载
- 关于网站编码显示问题 效果是 访问 带有中文注释的sass文件出现编码报错。
- Operation not applicable
- DataTrigger的几个用法
- MYSQL数据库性能调优之三:explain分析慢查询