蒟蒻君的刷题日记Day5（线段树专题T2）：CF703D Mishka and Interesting sum

蒟蒻君的刷题日记Day5（线段树专题T2）：CF703D Mishka and Interesting sum

文章目录

解题思路：树状数组代码实现

解题思路：树状数组

题目中要求的是出现偶数次数的异或和。可知，两个相同的数异或为 0 0 0，则 答案 = l − r l-r l−r所有数的异或和 ⊕ oplus ⊕ 出现过数的异或和，这样出现奇数次的就 无 啦~这些异或和需要用树状数组维护一下。总结一下，这道题考察了树状数组的应用，作为紫题较水。

因为本题求得是出现次数为偶数次数的异或和，我们可以知道，两个相同的数异或和为0，那么区间l-r之间的异或和即为出现次数为奇数个数数的异或和，这样我们再求一下区间l-r中不同数的异或和（树状数组老套路），用着两个异或和既可以求出答案。

代码实现

#include 
using namespace std;
const int N = 1000005;
int a[N], b[N], c[N];
struct edge {
    int l, r, id;
    bool operator < (edge &Edge) const {
        return r < Edge.r;
    }
} e[N];
inline int lowbit(int x) {
    return x & -x;
}
int n, m;
void update(int i, int x) {
    for (; i <= n; i += lowbit(i)) {
        c[i] ^= x;
    }
}
int query(int i) {
    int res = 0;
    for (; i; i -= lowbit(i)) {
        res ^= c[i];
    }
    return res;
}
int s[N], pos[N], res[N];
int main() {
	ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i];
        s[i] = s[i - 1] ^ a[i];
    }
    sort(b + 1, b + n + 1);
    int k = unique(b + 1, b + n + 1) - (b + 1);
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].l >> e[i].r;
        e[i].id = i;
    }
    sort(e + 1, e + m + 1);
    int pre = 1;
    for (int i = 1; i <= n; ++i) {
        int idx = lower_bound(b + 1	, b + k + 1, a[i]) - b;
        if (pos[idx]) {
        	update(pos[idx], a[i]);
		}
		update(i, a[i]);
        pos[idx] = i;
        while (e[pre].r == i) {
            res[e[pre].id] = query(e[pre].r) ^ query(e[pre].l - 1) ^ s[e[pre].r] ^ s[e[pre].l - 1]; 
            ++pre;
        }
    }
    for (int i = 1; i <= m; ++i) {
        cout << res[i] << 'n';
    }
    return 0;
}

Good Good 贺题， Day Day Up！！