自动搬运

查看原文

来自洛谷，原作者为

	Akiyama_mzk 交わる 線と線 着飾る 大好きな アレコレソレ そう いつだって 譲れないアイデンティティ

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

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

以下是正文

戳

题意

给定一个值域为 $[1,30]$ 的序列，合并操作定义是使用两个相同的元素（设为 $x$）合并出一个值为 $x+1$ 的元素，代价为 $2^{x+1}$，维护以下四种操作。

• 操作 $1$：求出区间 $[l,r]$ 内的元素通过合并能得到的最大元素。

• 操作 $2$：将区间 $[l,r]$ 之间的元素合并，直至任意元素互不相同，然后再加入一个值为 $k$ 的元素，继续合并直至任意元素互不相同，求出加新元素后所有合并的代价之和。

• 操作 $3$：将第 $x$ 个数的值改为 $val$。

• 操作 $4$：回到第 $t$ 次操作。

算法

注意到 $[1,30]$ 的值域，想到使用二进制维护合并，合并操作就像二进制加法内的进位，少了两个相同的元素，多出另一个元素。

因此，区间合并后的最大的元素就是区间和的最大二进制位，其他操作也可以照样用二进制维护。

对于操作 $4$ 的回退和操作 $3$ 的修改操作，我们使用可持久化线段树来维护。

但什么是可持久化？

下面内容请会可持久化线段树的大佬跳过。

我们需要先了解 P3919 【模板】可持久化线段树 1（可持久化数组）。

题面为在某个历史版本上修改某一个位置上的值，并访问某个历史版本上的某一位置的值。

可持久化线段树的基本思想就是只对进行修改的结点进行复制，以减少空间的消耗，让我们不必复制每个版本所有节点。

易得，每次添加的节点数为 $\log(n)$ 个，可持久化线段树有很多根，对于每一个根都可以构成一棵完整的线段树。

所以我们知道，可持久化线段树只会对部分节点进行复制，我们每一次想询问一个版本的线段树，就可以在那个版本的根构成的线段树中询问。

我们直接开一块内存池存新节点。编号为此时总节点数个数 $+1$。开结构体存节点编号。根要另外开个数组存。

注意，可持久化线段树不能用 $x\times 2$，$x\times 2+1$ 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。

代码如下。

int n,m,dfn;
int root[1000001],a[1000001];
struct president_tree{
	struct node{
		int lson,rson,val;
	}t[25000001];
	void build(int &x,int l,int r){
		x=++dfn;
		if(l==r){
			t[x].val=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(t[x].lson,l,mid);
		build(t[x].rson,mid+1,r);
	}
	void update(int idx,int &id,int l,int r,int x,int d){
		id=++dfn;
		t[id]=t[idx];
		if(l==r){
			t[id].val=d;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			update(t[idx].lson,t[id].lson,l,mid,x,d);	
		}
		else{
			update(t[idx].rson,t[id].rson,mid+1,r,x,d);
		}
	}
	int query(int x,int l,int r,int pos){
		if(l==r){
			return t[x].val;
		}
		int mid=(l+r)>>1;
		if(pos<=mid){
			return query(t[x].lson,l,mid,pos);
		}
		else{
			return query(t[x].rson,mid+1,r,pos);
		}
	}
}tree;

代码与评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long 
inline long long read(){
	long long x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(long long x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
int n,m,dfn,a,p,q;
int root[4000001],cost[4000001];
struct president_tree{
	struct node{
		int lson,rson,val;
	}t[64000001];
	#define lson(x) t[x].lson
	#define rson(x) t[x].rson
	void push_up(int x){
		t[x].val=t[lson(x)].val+t[rson(x)].val;
	} 
	void build(int &x,int l,int r){
		x=++dfn;
		if(l==r){
			t[x].val=cost[l];
			return;
		}
		int mid=(l+r)>>1;
		build(t[x].lson,l,mid);
		build(t[x].rson,mid+1,r);
		push_up(x);
		return;
	}
	void update(int idx,int &id,int l,int r,int x,int d){
		id=++dfn;
		t[id]=t[idx];
		if(l==r){
			t[id].val=d;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			update(t[idx].lson,t[id].lson,l,mid,x,d);	
		}
		else{
			update(t[idx].rson,t[id].rson,mid+1,r,x,d);
		}
		push_up(id);
	}
	int query(int x,int l,int r,int ll,int rr){
		if(ll<=l&&r<=rr){
			return t[x].val;
		}
		int mid=(l+r)>>1;
		int res=0;
		if(ll<=mid){
			res+=query(t[x].lson,l,mid,ll,rr);
		}
		if(rr>=mid+1){
			res+=query(t[x].rson,mid+1,r,ll,rr);
		}
		return res;
	}
}tree;
const int mod=1e9+7;
int cal(){
	a=(7ll*a+13)%19260817;
	return (a+19260817)%19260817;
}
signed main(){
	n=read();
	m=read();
	a=read();
	p=read();
	q=read();
	for(int i=1;i<=n;i++){
		cost[i]=cal()%q+1;
		cost[i]=(1ll<<cost[i]);
	}
	tree.build(root[0],1,n);
	for(int i=1;i<=m;i++){
		root[i]=root[i-1];
		int op=cal()%p+1;
		if(op==1){
			int l=cal()%n+1;
			int r=cal()%n+1;
			if(r<l){
				swap(l,r);
			}
			long long ans=tree.query(root[i],1,n,l,r);
			write(__lg(ans));
			printf("\n");
		}
		if(op==2){
			int l=cal()%n+1;
			int r=cal()%n+1;
			if(r<l){
				swap(l,r);
			}
			int k=cal()%q+1;
			int res=tree.query(root[i],1,n,l,r);
			int ans=0;
			for(int j=0;res;j++){
				if(j>=k){
					if(res&1){
						ans+=(1ll<<(j+1))%mod;
						ans%=mod;
					}
					else{
						break;
					}
				}
				res>>=1;
			}
			write(ans);
			printf("\n");
		}
		if(op==3){
			int pos=cal()%n+1;
			int k=cal()%q+1;
			k=1ll<<k;
			tree.update(root[i-1],root[i],1,n,pos,k);
		}
		if(op==4){
			int loc=cal()%i;
			root[i]=root[loc];
		}
	}
	return 0;
}

record