自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:15:51，当前版本为作者最后更新于2025-06-09 22:27:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $a_1\sim a_{2^n}$，满足 $a_i\in[0,2^n)$，定义 $f(l,r)$ 表示 $\max_x\mathrm{mex}(a_l\oplus x,a_{l+1}\oplus x,\dots,a_r\oplus x)$。

支持 $q$ 次询问一个区间的 $f$ 值，或者所有子区间的 $f$ 值之和。

数据范围：$n\le 18,q\le 10^6$。

思路分析

首先刻画 $f$，把所有元素建 Trie，计算每个子树的 $f_p$，如果有一个子树是满的，则 $f_p=f_{ls}+f_{rs}$，否则 $f_p=\max (f_{ls},f_{rs})$。

但这个做法不能很好的刻画 $f(l,r)$。

注意到 $f$ 的本质就是选择 Trie 树上的一个点，然后把他到根的链删掉，剩余的满子树大小之和。

那么如果 $a$ 是一个排列，我们就可以扫描线，在每个子树被填满的时候更新他的兄弟子树内每个叶子的权值。

注意到每个叶子的权值都是一个 $n$ 段的分段函数，因此总的更新次数是 $\mathcal O(n^22^n)$ 的，再用一个线段树维护即可。

进一步你把每个叶子的分段函数先归并起来，这样的更新次数是 $\mathcal O(n2^n)$ 的。

接下来回到原问题，此时每个子树会被多次填满，我们就不能每次暴力更新兄弟子树的分段函数。

考虑一个比较方便的维护分段函数的方法，对每个子树建一棵刚才的 Trie 树，并且维护最大出现位置最小的一个，然后把这个元素删掉，重复此过程，每次取出 $f_{rt}$ 即可。

然后当一个子树填满的时候，设此前子树内最大出现位置最小的元素时刻为 $t'$，而现在被更新为 $t$，那么我们只关心其兄弟子树在 $[t',t]$ 范围内的分段函数。

那么我们对每个子树建 Trie 树维护 dp，然后我们不断弹出兄弟子树最小时刻在 $[t',t]$ 范围内的元素，就能得到这个范围的分段函数。

很显然得到的总段数不超过每个 Trie 树上插入操作的次数，那么操作次数就是 $\mathcal O(n2^n)$ 级别的。

由于 $f$ 具有单调性，那么区间 chkmax 相当于区间赋值，用线段树支持区间赋值区间历史和即可。

时间复杂度 $\mathcal O(n^22^n+nq)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=(1<<18)+5,inf=1e9;
int ty,n,m,q;
struct Trie {
	int N,lo,*f,*s;
	array <int,2> *mn;
	void psu(int p) {
		mn[p]=min(mn[p<<1],mn[p<<1|1]),f[p]=max(f[p<<1],f[p<<1|1]);
		if(f[p]==s[p]/2) f[p]=f[p<<1]+f[p<<1|1];
	}
	void init(int l,int r) {
		N=r-l+1,lo=l,f=new int[2*N],s=new int[2*N],mn=new array<int,2>[2*N];
		for(int i=N;i<2*N;++i) s[i]=1,f[i]=0,mn[i]={inf,i};
		for(int i=N-1;i;--i) psu(i),s[i]=s[i<<1]+s[i<<1|1];
	}
	void upd(int p,int t) {
		p=p-lo+N,f[p]=1,mn[p]={t,p};
		for(p>>=1;p;p>>=1) psu(p);
	}
	void pop() {
		int p=mn[1][1]; f[p]=0,mn[p]={inf,p};
		for(p>>=1;p;p>>=1) psu(p);
	}
}	tr[MAXN*2];
struct SegmentTree {
	int mn[MAXN*2],mx[MAXN*2],tg[MAXN*2],len[MAXN*2],ct[MAXN*2];
	ll su[MAXN*2],hs[MAXN*2],ht[MAXN*2];
	//ct -> tg -> ht
	void adt(int p,int k) { hs[p]+=1ll*k*su[p],(~tg[p]?ht[p]+=1ll*tg[p]*k:ct[p]+=k); }
	void cov(int p,int k) { mn[p]=mx[p]=tg[p]=k,su[p]=1ll*len[p]*k; }
	void adh(int p,ll h) { hs[p]+=h*len[p],ht[p]+=h; }
	void psd(int p) {
		if(ct[p]) adt(p<<1,ct[p]),adt(p<<1|1,ct[p]),ct[p]=0;
		if(~tg[p]) cov(p<<1,tg[p]),cov(p<<1|1,tg[p]),tg[p]=-1;
		if(ht[p]) adh(p<<1,ht[p]),adh(p<<1|1,ht[p]),ht[p]=0;
	}
	void psu(int p) {
		su[p]=su[p<<1]+su[p<<1|1],hs[p]=hs[p<<1]+hs[p<<1|1];
		mn[p]=min(mn[p<<1],mn[p<<1|1]),mx[p]=max(mx[p<<1],mx[p<<1|1]);
	}
	void init(int l=0,int r=n-1,int p=1) {
		tg[p]=-1,len[p]=r-l+1,tr[p].init(l,r);
		if(l==r) return ;
		int mid=(l+r)>>1;
		init(l,mid,p<<1),init(mid+1,r,p<<1|1);
	}
	void upd(int ul,int ur,int v,int l=0,int r=n-1,int p=1) {
		if(mn[p]>=v) return ;
		if(ul<=l&&r<=ur&&mx[p]<=v) return cov(p,v);
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) upd(ul,ur,v,l,mid,p<<1);
		if(mid<ur) upd(ul,ur,v,mid+1,r,p<<1|1);
		psu(p);
	}
	ll qhs(int ul,int ur,int l=0,int r=n-1,int p=1) {
		if(ul<=l&&r<=ur) return hs[p];
		int mid=(l+r)>>1; ll s=0; psd(p);
		if(ul<=mid) s+=qhs(ul,ur,l,mid,p<<1);
		if(mid<ur) s+=qhs(ul,ur,mid+1,r,p<<1|1);
		return s;
	}
	int qv(int u,int l=0,int r=n-1,int p=1) {
		if(l==r) return su[p];
		int mid=(l+r)>>1; psd(p);
		return u<=mid?qv(u,l,mid,p<<1):qv(u,mid+1,r,p<<1|1);
	}
}	T;
int a[MAXN],mn[MAXN*2];
ll ans[MAXN*4];
vector <array<int,2>> qy[MAXN];
struct info {
	int d,w,t,o;
};
void upd(int x,int t) {
	vector <info> op;
	op.push_back({0,1,t,0});
	for(int d=0;d<m;++d) {
		int p=(x+n)>>d,lst=mn[p];
		tr[p].upd(x,t),mn[p]=(d?min(mn[p<<1],mn[p<<1|1]):t);
		if(mn[p^1]>=0) op.push_back({d+1,1<<d,mn[p^1],1});
		if(mn[p]==lst) continue;
		for(;tr[p^1].mn[1][0]<=mn[p];tr[p^1].pop()) {
			op.push_back({d+1,tr[p^1].f[1]+(1<<d),tr[p^1].mn[1][0],0});
		}
		if(tr[p^1].mn[1][0]<=t) op.push_back({d+1,tr[p^1].f[1]+(1<<d),mn[p],0});
	}
	sort(op.begin(),op.end(),[&](auto i,auto j){ return i.t>j.t; });
	static int f[20],w[20];
	memset(f,0,sizeof(f)),memset(w,0,sizeof(w));
	for(auto e:op) {
		if(e.o) for(int i=0;i<e.d;++i) w[i]+=e.w;
		else f[e.d]=max(f[e.d],e.w);
		int z=0;
		for(int i=0;i<=m;++i) z=max(z,f[i]+w[i]);
		T.upd(0,e.t,z);
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>m>>q>>ty,n=1<<m,T.init();
	for(int i=0;i<n;++i) cin>>a[i];
	for(int i=1,l,r;i<=q;++i) cin>>l>>r,qy[r-1].push_back({l-1,i});
	memset(mn,-0x3f,sizeof(mn));
	for(int i=0;i<n;++i) {
		upd(a[i],i),T.adt(1,1);
		for(auto o:qy[i]) ans[o[1]]=(ty==1?T.qv(o[0]):T.qhs(o[0],i));
	}
	for(int i=1;i<=q;++i) cout<<ans[i]<<"\n";
	return 0;
}