Problem solution [LuoguP5607][Ynoi2013] unable to return to the sky NOI2017

Problem solving is unable to return to the sky NOI2017

Title Link

Ask maximum xor ⁡ \operatorname{xor} xor and, support modification, think of the linear basis of the line segment tree set.

But I can't do it again: I can't tag. Why can't I hit tag? Because tag can only record one number, and the segment tree maintains a linear base rather than an exclusive or sum. If marked, it needs to be marked with many numbers.

Therefore, it can only be modified at a single point.

Consider using the segment tree to maintain the difference array, and then what to do with operation 2?

Set the difference score group as b b b. If we want to inquire [ a l , a r ] [a_l,a_r] The linear basis of [al, ar] (let it be linear basis I) can be queried a l , [ b l + 1 , b r ] a_l,[b_{l+1},b_r] al, linear basis of [bl+1, br] (let it be linear basis 2).

Next, it is proved that the bilinear basis is equivalent:

If selected in linear basis 2 b k b_k bk, which can be selected from linear basis 1 a k − 1 , a k a_{k-1},a_k ak−1​,ak​; If there is a choice on the linear basis a k a_k ak, if k = l k=l k=l, selected from linear basis 2 a l a_l al, if k ≠ l k≠l k  = l, optional a l , [ b l + 1 , b k ] a_l,[b_{l+1},b_k] al​,[bl+1​,bk​]. Perceptual understanding.

So we use segment tree maintenance b b b array. But there's another one a l a_l How to de al with it? Think about what we'll do a a a array: interval repair, single point query. Therefore, both line segment tree and tree array can be used for maintenance. If the tree array is used for maintenance, the differential array needs to be maintained.

Note: the difference array should be calculated from the back to the front.

Note: when a single point of the line segment tree is modified to a leaf node, the linear basis needs to be reconstructed. At this time, the lower difference group can be maintained, such as k k k-bit XOR a k = a k xor ⁡ v a_k=a_k \operatorname{xor} v ak = ak ﹐ xorv, and then insert this number into the linear base.

So now there are: a a a the array maintains the difference, the tree array maintains the prefix sum of the difference, that is, the original number, and the line segment tree maintains the linear basis. The problem is solved!

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
int n, m, a[N], bit[N];

struct node{
	int p[32], l, r;
	void ins(int k){
		for(int i = 31; i >= 0; -- i){
			if(!(k&(1<<i))) continue;
			if(!p[i]){ p[i] = k; break; }
			k ^= p[i];
	void ins(node &k){
		for(int i = 31; i >= 0; -- i) ins(k.p[i]);
	int mx(int v){
		for(int i = 31; i >= 0; -- i) v = max(v, v ^ p[i]);
		return v;
} T[N<<2], res;
struct SegTree{
	void buildtree(int p, int l, int r){
		T[p].l = l, T[p].r = r;
		if(l == r) T[p].ins(a[l]);
			int mid = l + r >> 1;
			buildtree(p<<1, l, mid);
			buildtree(p<<1|1, mid+1, r);
			T[p].ins(T[p<<1]); T[p].ins(T[p<<1|1]);
	void modify(int p, int x, int v){
		if(T[p].l == T[p].r){
			memset(T[p].p, 0, sizeof(T[p].p));
			T[p].ins(a[T[p].l] ^ v);
			a[T[p].l] ^= v;
		} else {
			int mid = T[p].l + T[p].r >> 1;
			if(x <= mid) modify(p<<1, x, v);
			else modify(p<<1|1, x, v);
			memset(T[p].p, 0, sizeof(T[p].p));
			T[p].ins(T[p<<1]); T[p].ins(T[p<<1|1]);
	void query(int p, int l, int r){
		if(l <= T[p].l && T[p].r <= r) res.ins(T[p]);
		else {
			int mid = T[p].l + T[p].r >> 1;
			if(l <= mid) query(p<<1, l, r);
			if(mid < r) query(p<<1|1, l, r);
} ST;
struct BIT{
	int lb(int x){ return x & -x; }
	void add(int p, int v){
		while(p <= n) bit[p] ^= v, p += lb(p);
	int pre(int r){
		int ans = 0;
		while(r) ans ^= bit[r], r -= lb(r);
		return ans;
} BIT;
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
	for(int i = n; i; -- i) a[i] ^= a[i-1];
	for(int i = 1; i <= n; ++ i) BIT.add(i, a[i]);
	ST.buildtree(1, 1, n);
	for(int i = 1, op, l, r, v; i <= m; ++ i){
		scanf("%d%d%d%d", &op, &l, &r, &v);
		if(op == 1){
			ST.modify(1, l, v), BIT.add(l, v);
			if(r < n) ST.modify(1, r+1, v), BIT.add(r+1, v);
		} else {
			memset(res.p, 0, sizeof(res.p));
			res.ins(BIT.pre(l)); ST.query(1, l+1, r);
	return 0;

How to say, at least it is also a Ynoi. Although the thinking difficulty may be a little simpler than other Ynoi, there are a lot of details.

Tags: C++ Algorithm data structure

Posted by poisa on Sun, 15 May 2022 00:36:35 +0300