自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

搬运于2025-08-24 23:09:49，当前版本为作者最后更新于2025-02-18 16:33:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

考虑 P11620 的 trick，原序列显然可以转化为异或差分后的序列；因为原序列显然可以通过其异或差分异或出来，故所表示的基是相同的。

转化为异或差分序列后，操作相当于单点异或，还有区间赋值为 $0$；注意到总共有 $n + q$ 级别的单点修改，故对于合法的区间推平操作显然也是 $O(n + q)$ 次的。

现在我们只需要支持单点异或一个数，全局查询最大值；即需要维护一个支持删除的线性基。

离线后维护一个删除时间即可，使用 bitset 维护，时间复杂度为 $O(\frac{n^3}{w})$。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define bset bitset<N>
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 2020;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int n, m, q, op, l, r;
int pre[N];
bool f[N];
vector<pair<bset, int>> V[N];
bset x;
bset a[N], d[N];
pair<bset, int> p[N];
inline void insert(pair<bset, int> v){
	for(int i = m - 1; i >= 0; --i){
		if(!v.fi[i])
		  continue;
		if(p[i].se == -1){
			p[i] = v;
			break;
		}
		if(p[i].se < v.se)
		  swap(v, p[i]);
		v.fi ^= p[i].fi;
	}
}
inline bset ask(){
	bset ans;
	for(int i = m - 1; i >= 0; --i)
	  if(!ans[i] && p[i].se != -1)
	    ans ^= p[i].fi;
	return ans;
}
inline void print(bset ans){
	for(int i = m - 1; i >= 0; --i)
	  putchar(ans[i] + '0');
	putchar('\n');
}
bool End;
int main(){
	n = read(), m = read(), q = read();
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		d[i] = a[i - 1] ^ a[i];
	}
	for(int i = 1; i <= q; ++i){
		op = read();
		if(op == 1){
			l = read(), r = read();
			cin >> x;
			for(int j = l; j <= r; ++j)
			  a[j] ^= x;
		}
		else if(op == 2){
			l = read(), r = read();
			cin >> x;
			for(int j = l; j <= r; ++j)
			  a[j] = x;
		}
		else
		  f[i] = 1;
		if(op <= 2){
			for(int j = l; j <= min(r + 1, n); ++j){
				bset t = a[j] ^ a[j - 1];
				if(d[j] != t){
					if(d[j].count())
					  V[pre[j]].push_back({d[j], i});
					d[j] = t;
					pre[j] = i;
				}
			}
		}
	}
	for(int i = 1; i <= n; ++i)
	  if(d[i].count())
	    V[pre[i]].push_back({d[i], q + 1});
	for(int j = 0; j < m; ++j)
	  p[j].se = -1;
	for(int i = 0; i <= q; ++i){
		for(int j = 0; j < m; ++j)
		  if(p[j].se == i)
		    p[j].se = -1;
		for(auto t : V[i])
		  insert(t);
		if(f[i])
		  print(ask());
	}
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}