莫队板子 用于复习
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <map>
- #define Sqr(x) ((x)*(x))
- using namespace std;
- const int N = 1e5 + 5;
- struct Q{
- int x, y, id;
- }q[N];
- int n, m, k, res;
- int cnt[N <<1], sum[N], a[N], ans[N];
- int bl[N], blsize;
- bool rule(Q x, Q y){return bl[x.x] == bl[y.x] ? x.y < y.y : x.x < y.x;}
- inline void ins(int x){
- res += cnt[k ^ sum[x]];
- ++cnt[sum[x]];
- }
- inline void del(int x){
- --cnt[sum[x]];
- res -= cnt[k ^ sum[x]];
- }
- int main() {
- scanf("%d%d%d", &n, &m, &k);
- blsize = sqrt(n);
- bl[0] = 1;
- for(int i = 1; i <= n; ++i){
- scanf("%d", &a[i]);
- sum[i] = sum[i - 1] ^ a[i];
- bl[i] = i / blsize + 1;
- }
- for(int i = 1; i <= m; ++i)
- scanf("%d%d", &q[i].x, &q[i].y), --q[i].x, q[i].id = i;
- sort(q + 1, q + m + 1, rule);
- int l = 1, r = 0;
- for(int i = 1; i <= m; ++i){
- while(l> q[i].x) ins(--l);
- while(l <q[i].x) del(l++);
- while(r> q[i].y) del(r--);
- while(r < q[i].y) ins(++r);
- ans[q[i].id] = res;
- }
- for(int i = 1; i <= m; ++i)
- printf("%d\n", ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3011897.html