洛谷 P5607 [Ynoi2013] 无力回天 NOI2017

人生第一道Ynoi，开心

Description

https://www.luogu.com.cn/problem/P5607

Solution

拿到这个题，看了一下，发现询问要求最大异或和，怎么办？

没办法，我只学过线性基，就顺着这个思路硬上吧。

我们开一颗线段树，里面的节点存线性基，那么空间复杂度是\(O(n \log v)\)的

先不管修改操作，那么我们容易分析得到单次查询的复杂度是\(O(\log n \log^2 v)\)

这个复杂度一看就是正解，接着想修改

区间\(\text{xor}\)还得维护线性基？？？什么鬼？？？

我们想，区间\(\text{xor}\)在线段树上难以办到，但是单点\(\text{xor}\)很简单

怎么办？

差分啊！！！

但我们怎么差分才能保证正确性呢？

熟知，对于一个数列\(a_n\)

如果我们把它差分，使得\(b_1 = a_1, b_i = a_i \text{xor} a_{i-1} (i>1)\)

那么由线性代数基础知识，数列\(b_n\)的线性基和原数列的线性基是一样的

这启发我们线段树维护差分的线性基，然后再单独维护\(a\)，询问时将\(a\)插入线段树查询得到的线性基、

这个\(a\)就很好维护了，直接上线段树或者树状数组维护差分即可

这样，单次修改复杂度为\(O(\log n \log v)\)

Code

#include <cstdio>

#include <iostream>

using namespace std;

const int N = 50010;

int n, m, a[N], b[N], opt, l, r, v;

inline int read() {

	int res = 0, flag = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = 1;

	for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);

	if(flag) res = ~res + 1;

	return res;

}

struct LineBase{

	int a[31];

	inline void clear() {for(int i = 0; i < 31; ++i) a[i] = 0;}

	inline void insert(int x) {

		for(int i = 30; i + 1; --i)

			if(x & (1 << i))

				if(!a[i]) {a[i] = x; break;}

				else x ^= a[i];

	}

}O;

inline LineBase merge(LineBase x, LineBase y) {

	for(int i = 30; i + 1; --i) if(y.a[i]) x.insert(y.a[i]);

	return x;

}

struct SegmentTree{

	#define lc (k << 1)

	#define rc (lc | 1)

	#define mid (l + r >> 1)

	LineBase tr[N << 2];

	inline void update(int k) {tr[k] = merge(tr[lc], tr[rc]);}

	inline void build(int k, int l, int r) {

		if(l == r) {tr[k].insert(b[l]); return;}

		build(lc, l, mid), build(rc, mid + 1, r), update(k);

	}

	inline void modify(int k, int l, int r, int loc) {

		if(l > loc || r < loc) return ;

		if(l == r) {tr[k].clear(), tr[k].insert(b[l]); return;}

		modify(lc, l, mid, loc), modify(rc, mid + 1, r, loc), update(k);

	}

	inline LineBase query(int k, int l, int r, int L, int R) {

		if(l > R || r < L) return O;

		if(L <= l && r <= R) return tr[k];

		return merge(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));

	}

}s;

struct BIT{

	#define lowbit(x) (x & -x)

	int tr[N];

	inline void insert(int x, int v) {for(; x <= n; x += lowbit(x)) tr[x] ^= v;}

	inline int query(int x) {int res = 0; for(; x; x -= lowbit(x)) res = res ^ tr[x]; return res;}

}bit;

inline void out(int x) {

	int flag = 0;

	for(int i = 30; i + 1; --i)

		if(flag) printf("%d",((x & (1 << i)) > 0));

		else if(x & (1 << i)) printf("1"), flag = 1;

	if(!flag) printf("0");

}

int main() {

	n = read(), m = read();

	for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i] ^ a[i - 1], bit.insert(i, b[i]); b[n + 1] = a[n];

	s.build(1, 1, n + 1);

	for(int i = 1; i <= m; ++i) {

		opt = read(), l = read(), r = read(), v = read();

		if(opt == 1) {

			b[l] ^= v, b[r + 1] ^= v;

			bit.insert(l, v), bit.insert(r + 1, v);

			s.modify(1, 1, n + 1, l), s.modify(1, 1, n + 1, r + 1);

		}

		else {

			LineBase ans = s.query(1, 1, n + 1, l + 1, r);

			ans.insert(bit.query(l));

			for(int j = 30; j + 1; --j) if((ans.a[j] ^ v) > v) v ^= ans.a[j];

			printf("%d\n",v);

		}

	}

	return 0;

}

巴特西

洛谷 P5607 [Ynoi2013] 无力回天 NOI2017

Description

Solution

Code

最新文章

热门文章