admin管理员组文章数量:1584180
(有任何问题欢迎留言或私聊
题意:传送门
翻译过来大概是,给你一个区间,区间内应该有一些数的异或和等于k,求异或和等于k的方案数。
flag[i]保存的是区间内异或和为 i 的方案数
我们已知区间[L,R]的情况,从区间[L,R]可以O(1)得到[L+1,R],[L-1,R],[L,R-1],[L,R+1]的情况
ans数组保存的是每次询问的答案
然后处理出异或前缀和数组ar[N]
[L,R]区间的异或和就是ar[R]^ar[L-1]
初始化
flag[0]=1;因为区间内什么都不选,异或值就是0这是一种方案。
已知区间:int L,R;
重点:将询问的区间排个序,然后玄学使得总时间复杂度降低。O(n^1.5);
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1<<20;
int belong[N];
LL flag[N],ans[N],ar[N];
int n,m,k;
int L=1,R=0;
LL Ans=0;
struct lp{
int l,r,id;
}cw[N];
bool cmp(const lp &a,const lp &b){
if(belong[a.l]==belong[b.l]){
return a.r<b.r;
}
return belong[a.l]<belong[b.l];
}
void add(int x){
Ans+=flag[ar[x]^k];
flag[ar[x]]++;
}
void del(int x){
flag[ar[x]]--;
Ans-=flag[ar[x]^k];
}
int main(int argc, char const *argv[]){
while(~scanf("%d%d%d",&n,&m,&k)){
ar[0]=0,L=1,R=0,Ans=0;
memset(flag,0,sizeof(flag));
int sz=sqrt(n);
for(int i=1;i<=n;++i){
scanf("%lld",&ar[i]);
ar[i]=ar[i]^ar[i-1];
belong[i]=i/sz;
}
for(int i=0;i<m;++i){
scanf("%d%d",&cw[i].l,&cw[i].r);
cw[i].id=i;
}
sort(cw,cw+m,cmp);
flag[0]=1;
for(int i=0;i<m;++i){
while(L<cw[i].l){
del(L-1);
L++;
}
while(L>cw[i].l){
L--;
add(L-1);
}
while(R<cw[i].r){
add(++R);
}
while(R>cw[i].r){
del(R--);
}
ans[cw[i].id]=Ans;
}
for(int i=0;i<m;++i){
printf("%lld\n",ans[i]);
}
}
本文标签: 算法模板xorCodeforces617ENumber
版权声明:本文标题:Codeforces617E-XOR and Favorite Number-莫队算法模板 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1727933075a1138623.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论