【2025广东省队集训day5】修理 做题记录

对于一个正整数序列 $b$，你需要不断进行以下两种操作将 $b$ 变成全 $0$：

• 将变量 $x$ 增加 $1$（刚开始 $x=0$）；
• 将某个 $b_i$ 变成 $b_i\oplus x$（$\oplus$ 表示按位异或操作）；

求最小的操作次数。

这个问题太简单了，所以给定一个长 $n$ 的正整数序列 $a$ 和 $q$ 次询问，每次你要求出 $b=a_{[l,r]}$ 的答案，强制在线。

$1\le n,q\le 2\times 10^5,1\le a_i<2^{60}$。

问题显然相当于 $r-l+1+\min\limits_{x\ge 2^k}\{x+|\{a_i|a_i>x,i\in[l,r]\}|\}$，其中 $k$ 是最大的满足 $\exist i\in[l,r],a_i\ge 2^k$ 的整数（即 higbit）。

注意到这个东西只和 $a_i\in[2^k,2^{k+1}-1]$ 有关，所以按 higbit 分类后可以去掉 $x$ 的下界，即变成求 $\min\limits_{x\ge 0}\{x+|\{a_i|a_i>x,i\in[l,r]\}|\}$，继续转化为 $r-l+1-\max\limits_{x\ge 0}\{|\{a_i|a_i\le x,i\in[l,r]\}|-x\}$。

注意到这很像 Hall 定理。具体的，Hall 定理（的拓展）指出，对于一个左部点集为 $V$ 的二分图，其最大匹配大小为：

$|V|-\max\limits_{S\subseteq V}\{|S|-|N(S)|\}$

其中 $N(S)$ 表示点集 $S$ 的邻域（通过一条边能从 $S$ 中点到达的点集）的大小。

那么注意到 $r-l+1-\max\limits_{x\ge 0}\{|\{a_i|a_i\le x,i\in[l,r]\}|-x\}$ 中 $x$ 显然是 $\le r-l+1$ 的，故可以只考虑 $\le n$ 的 $a_i$。

那么就可以这样构造一个二分图，使得其最大匹配大小恰好就是我们要求的东西（还要加上区间中 $>n$ 的 $a_i$ 的个数）：

• 左部点集为 $\{i|i\in [l,r],a_i\le n\}$，右部点集为 $\{1,2,3,\dots,n\}$；
• 左部点 $i$ 和右部点 $j$ 之间有边当且仅当 $a_i\ge j$；

这个二分图性质很好，具体的，最大匹配可以这样求：

• 以任意顺序加入左部点，维护哪些右部点被占用了；
• 加入点 $i$ 时找到最大的 $\le a_i$ 且未被占用的右部点 $j$，让 $i$ 和 $j$ 匹配；

那么考虑扫描线，对于一个 $r$，求出倒序加入 $[1,r]$ 中的 $a_i$ 后哪些左部点在匹配中（记为集合 $S$），则区间 $[l,r]$ 的答案就相当于 $|[l,r]\cap S|$。

考虑 $r$ 从 $r-1$ 变过来时 $S$ 的变化，显然要强制 $a_r$ 在匹配中。依旧考虑 Hall 定理，对于一个匹配 $S$，设 $w_x=|i|i\in S,a_i\le x|-x$，则 $S$ 合法当且仅当 $\forall 0\le x\le n,w_x\ge 0$。故考虑找到加入 $a_r$ 后第一个 $w_i<0$ 的位置 $i$，然后找到最小的 $id\in S,a_{id}\le i$ 删去即可。

$S$ 用主席树维护，$w$ 用线段树维护，时间复杂度 $O((n+q)\log n)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

const int S=200005,TS=20000005,BS=65;
const int inf=1e8;

int n,q,t;
ll a[S];
int cnt,ls[TS],rs[TS],sm[TS];
vector<int> vec[BS];
int rt[BS][S];

inline int higbit(ll x){for(int i=BS-3;i>=0;i--) if(x>>i&1) return i;}

inline void upda(int u)
{
	sm[u]=0;
	if(ls[u]!=0) sm[u]+=sm[ls[u]];
	if(rs[u]!=0) sm[u]+=sm[rs[u]];
}
void addp(int &u,int lst,int l,int r,int p,int x)
{
	u=++cnt;
	ls[u]=ls[lst],rs[u]=rs[lst],sm[u]=sm[lst];
	if(l==r) return sm[u]+=x,void();
	int mid=l+r>>1;
	if(p<=mid) addp(ls[u],ls[lst],l,mid,p,x);
	else addp(rs[u],rs[lst],mid+1,r,p,x);
	upda(u);
}
int quelr(int u,int l,int r,int L,int R)
{
	if(l>R||r<L||u==0) return 0;
	if(l>=L&&r<=R) return sm[u];
	int mid=l+r>>1,res=0;
	if(L<=mid) res+=quelr(ls[u],l,mid,L,R);
	if(R>=mid+1) res+=quelr(rs[u],mid+1,r,L,R);
	return res;
}

namespace sega
{
	set<int> st[S];
	int mn[S<<2],mnp[S<<2],tag[S<<2],mnid[S<<2];
	inline void upda(int u)
	{
		int ls=u<<1,rs=u<<1|1;
		mn[u]=min(mn[ls],mn[rs]);
		if(mn[u]==mn[ls]) mnp[u]=mnp[ls];
		else mnp[u]=mnp[rs];
		mnid[u]=min(mnid[ls],mnid[rs]);
	}
	inline void addtag(int u,int x)
	{
		mn[u]+=x;
		tag[u]+=x;
	}
	inline void dwntag(int u)
	{
		if(tag[u]==0) return;
		addtag(u<<1,tag[u]),addtag(u<<1|1,tag[u]);
		tag[u]=0;
	}
	void build(int u,int l,int r)
	{
		tag[u]=0;
		if(l==r) return mn[u]=mnp[u]=l,mnid[u]=inf,void();
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		upda(u);
	}
	void addlr(int u,int l,int r,int L,int R,int x)
	{
		if(l>R||r<L) return;
		if(l>=L&&r<=R) return addtag(u,x),void();
		dwntag(u);
		int mid=l+r>>1;
		if(L<=mid) addlr(u<<1,l,mid,L,R,x);
		if(R>=mid+1) addlr(u<<1|1,mid+1,r,L,R,x);
		upda(u);
	}
	void updp(int u,int l,int r,int p)
	{
		if(l==r) return mnid[u]=st[p].empty()?inf:*st[p].begin(),void();
		dwntag(u);
		int mid=l+r>>1;
		if(p<=mid) updp(u<<1,l,mid,p);
		else updp(u<<1|1,mid+1,r,p);
		upda(u);
	}
	int quelr(int u,int l,int r,int L,int R)
	{
		if(l>R||r<L) return inf;
		if(l>=L&&r<=R) return mnid[u];
		dwntag(u);
		int mid=l+r>>1,res=inf;
		if(L<=mid) res=min(res,quelr(u<<1,l,mid,L,R));
		if(R>=mid+1) res=min(res,quelr(u<<1|1,mid+1,r,L,R));
		return res;
	}
}

inline void doit(int id)
{
	ll de=1ll<<id;
	for(int i=0;i<=n;i++) sega::st[i].clear();
	sega::build(1,0,n);
	for(int i=0;i<vec[id].size();i++)
	{
		rt[id][i]=i==0?0:rt[id][i-1];
		ll x=a[vec[id][i]]-de;
		if(x>n)
		{
			addp(rt[id][i],rt[id][i],0,n,i,1);
			continue;
		}
		sega::addlr(1,0,n,x,n,-1);
		sega::st[x].insert(i);
		sega::updp(1,0,n,x);
		addp(rt[id][i],rt[id][i],0,n,i,1);
		if(sega::mn[1]<0)
		{
			int j=sega::quelr(1,0,n,0,sega::mnp[1]);
			int y=a[vec[id][j]]-de;
			sega::addlr(1,0,n,y,n,1);
			sega::st[y].erase(j);
			sega::updp(1,0,n,y);
			addp(rt[id][i],rt[id][i],0,n,j,-1);
		}
	}
}

int main()
{
	freopen("repair.in","r",stdin);
	freopen("repair.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q>>t;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) vec[higbit(a[i])].push_back(i);
	for(int i=0;i<=BS-3;i++) doit(i);
	sega::build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		sega::st[i].insert(-higbit(a[i]));
		sega::updp(1,1,n,i);
	}
	ll lstans=0;
	while(q-->0)
	{
		ll l,r;
		cin>>l>>r;
		if(t==2) l^=lstans,r^=lstans;
		if(l>r) swap(l,r);
		int id=-sega::quelr(1,1,n,l,r);
		ll add=(1ll<<id)+r-l+1;
		int lb=lower_bound(vec[id].begin(),vec[id].end(),l)-vec[id].begin();
		int rb=upper_bound(vec[id].begin(),vec[id].end(),r)-vec[id].begin()-1;
		// cout<<"cp: "<<quelr(rt[id][rb],0,n,lb,rb)<<'\n';
		cout<<(lstans=quelr(rt[id][rb],0,n,lb,rb)+add)<<'\n';
	}
	return 0;
}