Codeforces 617E:XOR and Favorite Number(莫队算法)
2024-08-31 23:52:03
http://codeforces.com/problemset/problem/617/E
题意:给出n个数,q个询问区间,问这个区间里面有多少个区间[i,j]可以使得ai^ai+1^...^aj = k。
思路:根据xor的性质,可以处理出前缀异或和sum[],那么要使结果等于k,就是sum[i-1]^sum[j] == k,即sum[j]^k == sum[i-1],那么用一个数组cnt[]存储对于每一个sum[]的数量。然后用莫队算法做。莫队算法是一种离线处理区间问题的算法,在我看来是将询问通过分块排序成一个可以暴力处理的序列,让暴力的复杂度尽量的低。只有O(n*sqrt(n))的复杂度。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
#define N 100010
#define INF 0x3f3f3f3f
struct node {
int l, r, id;
LL ans;
} q[N*];
int sum[N], kuai, k;
LL cnt[N*]; bool cmp1(const node &a, const node &b) {
if(a.l / kuai != b.l / kuai) return a.l / kuai < b.l / kuai; // 根据块的编号排序
return a.r < b.r; // 块内按照r值排序
} bool cmp2(const node &a, const node &b) {
return a.id < b.id;
} int main()
{
int n, m, num, L, R;
LL s = ;
scanf("%d%d%d", &n, &m, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &num); sum[i] = sum[i-] ^ num;
}
for(int i = ; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i; q[i].l--;
}
kuai = sqrt(n);
sort(q + , q + + m, cmp1);
L = ; R = ;
for(int i = ; i <= m; i++) {
int l = q[i].l, r = q[i].r;
while(L < l) {
cnt[sum[L]]--;
s -= cnt[sum[L]^k];
L++;
}
while(L > l) {
L--;
s += cnt[sum[L]^k];
cnt[sum[L]]++;
}
while(R < r) {
R++;
s += cnt[sum[R]^k];
cnt[sum[R]]++;
}
while(R > r) {
cnt[sum[R]]--;
s -= cnt[sum[R]^k];
R--;
}
q[i].ans = s;
}
sort(q + , q + + m, cmp2);
for(int i = ; i <= m; i++) printf("%lld\n", q[i].ans);
return ;
}
最新文章
- js创建,获取,检测cookie
- 使用.NET读取exchange邮件
- 用CRT connect MongoDB 使用Backspace无效
- 【转】Android Studio简单设置
- js循环array,json,map
- 静态变量符 static
- ReactiveSwift日常运用<;一>;
- IDEA_教你十分钟下载并破解IntelliJ IDEA(2017)(转)
- 当进行服务端渲染的时间,某些npm包可能会调用document,window这些对象而导致报错
- awk、sed、grep三大shell文本处理工具之sed的应用
- centos下安装python3.6.2
- IIS7配置伪静态把后缀名映射为html方案
- 对网络助手的NABCD分析心得
- jQuery基本筛选器-表单筛选器-关系筛选器
- Yii 中Criteria常用方法
- Ubbeditor的使用
- jQuery基础---Ajax基础
- mac --snip 滚动截屏
- <;Android 基础(五)>; MVVM
- [课堂总结]C++课堂总结(二)