题解：P6627 [省选联考 2020 B 卷] 幸运数字

注意到答案一定是 $0,A,A-1,A+1,B,B-1,B+1,L,L-1,L+1,R,R-1,R+1$ 这 $\mathcal O(n)$ 个数中的某个。所以我们只需要快速计算这些数的价值。

不难发现这三种奖励条件都可以化归成一个或多个区间。区间型条件当然就是 $[L, R]$，相等型条件是 $[A, A]$，不等型条件是 $(-\infty, B-1]$ 和 $[B+1,\infty)$。我们把这些区间预处理好后，问题变成了：

- $\mathcal O(n)$ 次询问。给定一个数 $x$。求满足 $l_i \le x \le r_i$ 的区间的 $w_i$ 的异或和。

正难则反。上面这个条件不满足，等价于 $x < l_i$ 或 $x > r_i$。而这个东西是很好用 **树状数组** 维护的。注意值域很大需要离散化。

复杂度一只 $\log$。

代码很烂。仅供参考吧。

```cpp
// #define tests
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int n, cnt;
vector<int> nums;

struct Node {
	int l, r, w;
}a[N];

void add(int x) {
	if (x >= -1e18 && x <= 1e18) {
		nums.push_back(x);
	}
}

void add(int l, int r, int w) {
	a[ ++ cnt] = {l, r, w};
	add(l), add(r), add(l - 1), add(r - 1), add(l + 1), add(r + 1);
}

struct Tree1 {
	int tr[N];
	
	void modify(int x, int d) {
		x = N - x - 1;
		for (int i = x; i < N; i += i & -i) tr[i] ^= d;
	}
	
	int query(int x) {
		x = N - x - 1;
		int res = 0;
		for (int i = x; i; i -= i & -i) res ^= tr[i];
		return res;
	}
}T1;

struct Tree2 {
	int tr[N];
	
	void modify(int x, int d) {
		for (int i = x; i < N; i += i & -i) tr[i] ^= d;
	}
	
	int query(int x) {
		int res = 0;
		for (int i = x; i; i -= i & -i) res ^= tr[i];
		return res;
	}
}T2;

void solve() {
	cin >> n;
	
	add(0);
	
	for (int i = 1; i <= n; ++ i ) {
		int op, l, r, x, w;
		cin >> op;
		if (op == 1) {
			cin >> l >> r >> w;
			add(l, r, w);
		} else if (op == 2) {
			cin >> x >> w;
			add(x, x, w);
		} else if (op == 3) {
			cin >> x >> w;
			add(-1e18, x - 1, w);
			add(x + 1, 1e18, w);
		}
	}

sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	
	int mx = -1e18, res_mx = -1e18, res_mn = 1e18;
	
	sort(a + 1, a + cnt + 1,
		[&](Node a, Node b) {
			return a.r == b.r ? a.l < b.l : a.r < b.r;
		});
	
	vector<int> cur = nums;
	for (int i = 1; i <= cnt; ++ i ) {
		cur.push_back(a[i].l);
		cur.push_back(a[i].r);
	}
	
	sort(cur.begin(), cur.end());
	cur.erase(unique(cur.begin(), cur.end()), cur.end());
	
	for (int &v : nums) {
		v = lower_bound(cur.begin(), cur.end(), v) - cur.begin() + 1;
	}
	for (int i = 1; i <= cnt; ++ i ) {
		a[i].l = lower_bound(cur.begin(), cur.end(), a[i].l) - cur.begin() + 1;
		a[i].r = lower_bound(cur.begin(), cur.end(), a[i].r) - cur.begin() + 1;
	}
	
	int sum = 0;
	for (int i = 1; i <= cnt; ++ i ) {
		sum ^= a[i].w;
		T1.modify(a[i].l, a[i].w);
		T2.modify(a[i].r, a[i].w);
	}
	
	int j = 0;
	for (int v : nums) {
		int res = sum ^ T1.query(v + 1) ^ T2.query(v - 1);
		
		if (res > mx) {
			mx = res;
			if (cur[v - 1] < 0) res_mx = cur[v - 1], res_mn = 1e18;
			else res_mn = cur[v - 1], res_mx = -1e18;
		} else if (res == mx) {
			if (cur[v - 1] < 0) res_mx = max(res_mx, cur[v - 1]);
			else res_mn = min(res_mn, cur[v - 1]);
		}
	}
	
	cout << mx << ' ';
	if (abs(res_mx) < abs(res_mn)) cout << res_mx;
	else cout << res_mn;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
#ifdef tests
	cin >> T;
#endif
	while (T -- ) solve();
	return 0;
}
```

正在渲染内容...