LOJ#517. 「LibreOJ β Round #2」计算几何瞎暴力

[题目链接](https://loj.ac/problem/517)

题解：发现只需要分两段维护就可以了。
上一次排过序的前缀部分用字典树维护，并且对每一位记录$now_xor$表示按照当前的顺序，第$i$位是否被翻转。后面的部分用一个前缀和维护。

这样的话，异或的时候维护偏移值，每一次排序我们就把后面的部分全部插入字典树，并且更新$now\_xor$。

```
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 2e5 + 5;

namespace Trie {
	int trie[maxn * 30][2], sz[maxn * 30], cnt, root;
	int bits_1[maxn * 30][30], now_xor[30], out_xor[30], oxor;
	void push_up(int rt) {
		sz[rt] = sz[trie[rt][0]] + sz[trie[rt][1]];
		int tl = trie[rt][0], tr = trie[rt][1];
		for(register int i = 0; i < 30; ++i) {
			bits_1[rt][i] = bits_1[tl][i] + bits_1[tr][i];
		}
	}
	void insert(int x, int b, int &rt) {
		if(!rt) rt = ++cnt;
		if(b == -1) {
			++sz[rt];
			for(register int i = 0; i < 30; ++i)
				if(((1 << i) & x)) ++bits_1[rt][i];
			return ;
		}
		insert(x, b - 1, trie[rt][(bool) ((1 << b) & x)]);
		push_up(rt);
	}
	void query(int p, int rt, int b, int ans[30]) {
		if(b == -1) {
			if(p) {
				for(register int i = 0; i < 30; ++i)
					if(bits_1[rt][i]) ans[i] += p;
			}
			return ;
		}
		int tl = trie[rt][now_xor[b]], tr = trie[rt][now_xor[b] ^ 1];
		if(sz[tl] >= p) query(p, tl, b - 1, ans);
		else {
			for(register int i = 0; i < 30; ++i)
				ans[i] += bits_1[tl][i];
			query(p - sz[tl], tr, b - 1, ans);
		}
	}
	int tmp1[30], tmp2[30];
	void Ins(int x) {
		insert(x, 29, root);
	}
	LL Q(int l, int r) {
		LL ans = 0;
		memset(tmp2, 0, sizeof(tmp2));
		memset(tmp1, 0, sizeof(tmp1));
		query(l - 1, 1, 29, tmp1);
		for(register int i = 0; i < 30; ++i)
			if(out_xor[i]) tmp1[i] = l - 1 - tmp1[i];
		query(r, 1, 29, tmp2);
		for(register int i = 0; i < 30; ++i)
			if(out_xor[i]) tmp2[i] = r - tmp2[i];
		for(register int i = 0; i < 30; ++i) {
			ans += 1ll * (1 << i) * (tmp2[i] - tmp1[i]);
			//else ans += 1ll * (1 << i) * (r - l + 1 - (tmp2[i] - tmp1[i]));
		}
		return ans;
	}
}

int ob[maxn][30], num[maxn], ncnt, pos;

void Ins(int x) {
	using namespace Trie;
	num[++ncnt] = x ^ oxor;
	for(register int i = 0; i < 30; ++i)
		ob[ncnt][i] = (((bool)(x & (1 << i))) ^ out_xor[i]) + ob[ncnt - 1][i];
}

void Sort() {
	using namespace Trie;
	for(register int i = 0; i < 30; ++i)
		now_xor[i] = out_xor[i];
	pos += ncnt;
	for(register int i = 1; i <= ncnt; ++i)
		Trie::Ins(num[i]);
	ncnt = 0;
}

LL query(int l, int r) {
	using namespace Trie;
	LL ans = 0;
	for(register int i = 0; i < 30; ++i) {
		if(!out_xor[i]) ans += 1ll * (1 << i) * (ob[r][i] - ob[l - 1][i]);
		else ans += 1ll * (1 << i) * (r - l + 1 - (ob[r][i] - ob[l - 1][i]));
	}
	return ans;
}

void All_Xor(int x) {
	using namespace Trie;
	oxor ^= x;
	for(register int i = 0; i < 30; ++i) {
		out_xor[i] ^= (bool) (x & (1 << i));
	}
}

LL Q(int l, int r) {
	if(r <= pos) 
		return Trie::Q(l, r);
	else if(l > pos) 
		return query(l - pos, r - pos);
	else return Trie::Q(l, pos) + query(1, r - pos);
}

int main() {
	int n, m, op, a, b;
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &a), Ins(a);
	scanf("%d", &m);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d", &op);
		if(op == 1) scanf("%d", &a), Ins(a);
		else if(op == 2) scanf("%d%d", &a, &b), printf("%lld\n", Q(a, b));
		else if(op == 3) scanf("%d", &a), All_Xor(a);
		else Sort();
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链