CF703D Mishka and Interesting sum

题意：给定一个1e6长度的值域1e9的数组。每次给定询问，询问区间内出现偶数次的数的异或和。

题解：首先很显然，每一次询问的答案，等于这个区间所有不同元素异或和异或上区间异或和。（因为出现偶数次的对区间异或和贡献为0，此时剩下的是出现奇数次的数，在取个补集即为答案）

区间异或和前缀和就好了，那问题转化为求区间不同元素异或和。由于这个东西区间合并很困难，所以在线算法是比较不优雅的。那我们考虑离线算法。我们按询问的右端点为第一关键字排序，然后处理到目前这个右端点位置的last数组，last数组定义为每个数最后出现的位置，然后给每个值对应的last附上它的值，这样我们一个区间求异或和可以得到区间不同元素异或和。树状数组一发就好了。

 #include<bits/stdc++.h>

 using namespace std;

 #define N 1000000

 #define LL long long

 #define lowbit(x) ((x) & -(x))

 inline LL read() {

     LL x = , f = ; char a = getchar();

     while(a < '' || a > '') { if(a == '-') f = -; a = getchar(); }

     while(a >= '' && a <= '') x = x *  + a - '', a = getchar();

     return x * f;

 }

 int n, a[N + ], ans[N + ], sum[N + ], Q;

 int fen[N + ];

 map<int, int> last;

 struct query {

     int id, l, r;

     bool operator < (const query & w) const {

         return r < w.r;

     }

 } q[N + ];

 inline void add(int pos, int val) { if(!pos) return; for(int i = pos; i <= n; i += lowbit(i)) fen[i] ^= val; }

 inline int querysum(int l, int r) {

     int ret = ;

     for(int i = r; i; i -= lowbit(i)) ret ^= fen[i];

     for(int i = l - ; i; i -= lowbit(i)) ret ^= fen[i];

     return ret;

 }

 int main() {

     n = read();

     for(int i = ; i <= n; i++) a[i] = read();

     for(int i = ; i <= n; i++) sum[i] = sum[i - ] ^ a[i];

     Q = read();

     for(int i = ; i <= Q; i++) q[i].id = i, q[i].l = read(), q[i].r = read();

     sort(q + , q +  + Q);

     for(int pos = , i = ; i <= Q; i++) {

         for(; pos <= q[i].r; pos++) {

             add(last[a[pos]], a[pos]);

             last[a[pos]] = pos;

             add(pos, a[pos]);

         }

         ans[q[i].id] = querysum(q[i].l, q[i].r) ^ sum[q[i].l-] ^ sum[q[i].r];

     }

     for(int i = ; i <= Q; i++) printf("%d\n", ans[i]);

     return ;

 }

巴特西

CF703D Mishka and Interesting sum

最新文章

热门文章