Codeforces 703D Mishka and Interesting sum（离线 + 树状数组）

题目链接 Mishka and Interesting sum

题意给定一个数列和$q$个询问，每次询问区间$[l, r]$中出现次数为偶数的所有数的异或和。

设区间$[l, r]$的异或和为$s(l, r)$，区间$[l, r]$中所有出现过的数的异或和为$c(l, r)$

那么每个询问的答案为$s(l, r)$ $xor$ $c(l, r)$。

对于$s(l, r)$的求解维护一个前缀和即可。

对于$c(l, r)$，把所有的询问离线并按照左端点升序排序（右端点无所谓，但是我程序里还是考虑了）

然后把数列中所有第一个出现的数加到树状数组里。

每个询问处理下来，要保证当前询问的$l$之前的$l - 1$个数已经在树状数组中被删除。

所谓被删除就是当前位置$x$上的元素被移去。

同时考虑位置$y$，满足$a_{x}=a_{y}， y > x$且$y$最小。（在$a_{x}$第一个和$a_{x}$值相同的元素的位置）

在位置$y$上把$a_{y}$加入树状数组，这样就可以离线求$c(l, r)$了。

时间复杂度$O(nlogn)$。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 1e6 + 10;

struct node{

	int l, r, id;

	friend bool operator < (const node &a, const node &b){

		return a.l == b.l ? a.r < b.r : a.l < b.l;

	}

} q[N];

int a[N], c[N], nxt[N];

int n, m;

int ans[N], s[N];

int l;

unordered_map <int, int> mp;

int update(int x, int val){

	for (; x <= n; x += x & -x) c[x] ^= val;

}

int query(int x){

	int ret = 0;

	for (; x; x -= x & -x) ret ^= c[x];

	return ret;

}

int undo(int x){

	update(x, a[x]);

	if (nxt[x]) update(nxt[x], a[nxt[x]]);

}

int main(){

	scanf("%d", &n);

	rep(i, 1, n) scanf("%d", a + i);

	rep(i, 1, n) s[i] = s[i - 1] ^ a[i];

	rep(i, 1, n){

		if (mp.count(a[i])) continue;

		else{

			mp[a[i]] = 1;

			update(i, a[i]);

		}

	}

	mp.clear();

	dec(i, n, 1){

		nxt[i] = (mp.count(a[i])) ? mp[a[i]] : 0;

		mp[a[i]]  = i;

	}

	scanf("%d", &m);

	rep(i, 1, m){

		scanf("%d%d", &q[i].l, &q[i].r);

		q[i].id = i;

	}

	sort(q + 1, q + m + 1);

	l = 1;

	rep(i, 1, m){

		while (l < q[i].l){

			undo(l);

			++l;

		}

		ans[q[i].id] = query(q[i].r) ^ s[q[i].r] ^ s[q[i].l - 1];

	}

	rep(i, 1, m) printf("%d\n", ans[i]);

	return 0;

}

巴特西

Codeforces 703D Mishka and Interesting sum（离线 + 树状数组）

最新文章

热门文章