自动搬运

查看原文

来自洛谷，原作者为

	追梦之鲸 哼~

搬运于2025-08-24 23:10:59，当前版本为作者最后更新于2025-03-13 15:47:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这里提供一种 $\mathcal O(n \sqrt n)$ 的做法。

我们考虑开 $2^d$ 个桶，范围为 $[0, 2^d-1]$，每个桶用一个 vector 维护。考虑把每一个元素的二进制分两部分处理，把二进制下位数小于 $d$ 的部分（下文简称为低位）放到一个桶里统一处理，二进制下位数大于 $d$ 的部分（下文简称为高位）单独预处理

操作 0

在桶中找到 $v_x$ 的低位并删除，然后再异或掉 $v_x$ 的高位。然后再加入 $p$ 即可。

由于有操作 2，所以我们需要记录一个 $cnt$ 表示当前已经进行操作 2 的次数，$bs_i$ 表示第 $i$ 个元素的低位上次被修改时操作 2 的次数，然后就可以得到 $v_x$ 实际的低位。

由于用的是 vector 维护的桶，所以该操作时间复杂度为 $\mathcal O(n)$，瓶颈在于 vector 的插入和删除，但是由于 vector 极其优秀的常数导致很难跑满（而且出题人貌似没想到卡

操作 1

只需要把每个桶维护的 vector 传给下一个桶即可，若 $2^d$ 的桶里面有 vector，那么把里面的数的高位加一并把这个 vector 塞到 $0$ 号桶里即可。

时间复杂度均摊为 $\mathcal O(2^d + n / 2^d)$。

操作 2

遍历每个桶并异或，然后再加上之前高位的预处理即可。

时间复杂度为 $\mathcal O(2^d)$。

显然当 $d=\log(n) / 2$ 时时间复杂度为 $\mathcal O(n \sqrt n)$。，但我调的 $d = 10$ 时最慢的点才跑了 73ms（

CODE

#include<bits/stdc++.h>
namespace whaleL{
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
#define ull unsigned long long
#define ll long long
#define db double
#define re return
#define con continue
#define brk break
#define emp emplace
#define emb emplace_back
#define mpr make_pair
#define lwb lower_bound
#define upb upper_bound
#define all(x) x.begin(), x.end()
#define mms(a, b) memset(a, b, sizeof(a))
#define sml(a,b)(a=min(a,b))
#define big(a,b)(a=max(a,b))
#define fo(i,j,n)for(int i=(j);i<=(n);i++)
#define of(i,j,n)for(int i=(j);i>=(n);i--)
#define f(i,n)fo(i,1,n)
#define fr(i,n)of(i,n,1)
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#elif __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define isd(c)((c)>47&&(c)<58)
#define iss(c)((c)<33)
#define il inline
#define tln template<typename m>
#define tls template<typename m,typename...ms>
#define getc(c) for(c=getchar();iss(c);c=getchar());
il void sf(){}il void ot(){}il void ut(){putchar('\n');}
tln il void sf(m&x){char f=1,c=getchar();x=0;for(;!isd(c);c=getchar())(c=='-')?f=-1:0;for(;isd(c);c=getchar())x=x*10+c-48;x*=f;}
tln il void ot(m x){x<0?x=-x,putchar('-'):0;static short s[51],t(0);do s[++t]=x%10;while(x/=10);for(;t;)putchar(s[t--]|48);}
il void sf(char&x){getc(x);}
il void ot(char x){putchar(x);}
il void sf(char*x){char c;getc(c);for(;!iss(c);c=getchar())*x++=c;*x=0;}
tln il void ot(m*x){while(*x)putchar(*x++);}
il void sf(string&x){x.clear();char c;getc(c);for(;!iss(c);c=getchar())x=x+c;}
il void ot(string x){printf("%s", x.c_str());}
il void sf(db&x){scanf("%lf", &x);}
il void ot(db x){printf("%lf", x);}
il void sf(long db&x){scanf("%Lf", &x);}
il void ot(long db x){printf("%Lf", x);}
tls il void sf(m&x,ms&...y){sf(x);sf(y...);}
tls il void ot(m x,ms...y){ot(x);ot(y...);}
tls il void ut(m x,ms...y){ot(x);putchar(' ');ut(y...);}
tln il void PC(m*a, m*b){for(;a!=b;cout<<*a++<<' ');ut();}
#ifndef ONLINE_JUDGE
#define err()cout<<"err "<<__LINE__,exit(0)
#define p(x...)(cout<<setw(18)<<#x,ot(" Line ",__LINE__," : "),ut(x))
#define pa(a, x...)(cout<<setw(18)<<#a,ot(" Line ",__LINE__," : "),ut(x))
#define po(x,y)(cout<<setw(18)<<#x,ot(" Line ",__LINE__," : "),PC(x,y))
#define g(x...) do{x;}while(0);
#else
#define err()1
#define p(x...)1
#define pa(x...)1
#define po(x...)1
#define g(x)
#endif
#ifndef DISFILE
#define file(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#else
#define file(x)
#endif
const ull MOD = 1e9 + 7;
#define mo(x)((1ULL*x)%MOD)
#define ma(x,y)(x=mo(y+(x)))
};using namespace whaleL;
const int N = 2e5 + 233;
const int d = 1023;
const int D = 262143 - 1023;
#define d(x) ((x) & d)
#define D(x) ((x) & D)

vector<int> e[N]; int en;
int a[N], p[N], bs[N];
int n, q, ans, cnt;

void add(int i) {
	int u = d(a[i]);
	if (!p[u]) p[u] = ++ en;
	e[p[u]].insert(upb(all(e[p[u]]), i), i);
	ans ^= D(a[i]);
}

signed main() {
	sf(n, q);
	f(i, n) 
		sf(a[i]), add(i);
	int op, i, v, u, res;
	f(awa, q) {
		sf(op);
		if (op == 0) {
			sf(i, v);
			ans ^= D(a[i]);
			u = p[d(a[i] + cnt - bs[i])];
			e[u].erase(lwb(all(e[u]), i));
			a[i] = v;
			add(i);
			bs[i] = cnt;
		}
		else if (op == 1) {
			cnt ++;
			fr(j, d + 1) //倒序
				p[j] = p[j - 1], p[j - 1] = 0;
			if (p[d + 1]) {
				for (int j : e[p[d + 1]]) {
					ans ^= D(a[j]);
					a[j] |= d, a[j] ++;
					ans ^= D(a[j]);
					bs[j] = cnt;
				}
				p[0] = p[d + 1];
			}
		}
		else if (op == 2) {
			res = 0;
			f(j, d) 
				if (e[p[j]].size() & 1) 
					res ^= j;
			ut(ans ^ res);
		}
	}
}