「2017 山东一轮集训 Day1」Sim 题解

注意：1 操作的 $S$ 中的元素是不同的。

思路

首先看到 5 操作可以想到莫队，并且题目中有修改操作，所以我们可以使用带修莫队。

对于 1 操作，设 $s1,s2,s3$ 分别表示一个集合中选 1，2，3 个元素的总和（$s3$ 即为集合的答案）。

现在的主要难点是维护数组的下标，3、4操作会对数组进行添加和删除操作，打乱数组下标。

考虑平衡树，使用平衡树动态维护下标，最后再把下标映射回去。3 操作可以直接把当前位置的元素置为 0，对答案没有贡献，4 操作直接插入即可。

最后跑带修莫队即可。

一些细节

注意平衡树除了维护当前子树大小，还要维护当前子树内有多少未被删除的点，因为删去点后此点是不算入下标内的。

平衡树每个节点都要储存哪些修改修改了这个点，便于操作完后将正确修改的位置映射回修改操作。

时间复杂度 $O(n^{\frac{5}{3}})$。

细节较多，详见代码。

代码

#include<bits/stdc++.h>
#define lc(p) tr[p].ls // 获取左儿子
#define rc(p) tr[p].rs // 获取右儿子
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,a[200010],rt,b[200010]; // n:初始长度, a:初始数组, rt:Treap根节点, b:最终的静态数组
mt19937 rd(999983); // 随机数生成器，用于生成Treap的优先级
struct N{
	int ls,rs,rd,vz,vs,sz; // ls,rs:左右儿子, rd:随机优先级, vz:是否有效(1有效0删除), vs:子树有效节点数, sz:子树总节点数
	vector<int> qi; // 记录询问或修改该节点时对应的操作编号
}tr[200010];
int id; // Treap节点总数
int nd(int qi){ // 新建Treap节点
	tr[++id]={0,0,rd(),1,1,1,{qi}};
	return id;
}
void pushup(int p){ // 上传信息，更新子树大小和有效节点数
	tr[p].sz=tr[lc(p)].sz+tr[rc(p)].sz+1;
	tr[p].vs=tr[lc(p)].vs+tr[rc(p)].vs+tr[p].vz;
}
void split(int p,int k,int &x,int &y){ // 按总节点数k分裂Treap
	if(!p){
		x=y=0;
		return ;
	}
	if(tr[lc(p)].sz<k){
		x=p;
		split(rc(p),k-tr[lc(p)].sz-1,rc(p),y);
	}
	else{
		y=p;
		split(lc(p),k,x,lc(p));
	}
	pushup(p);
}
int merge(int x,int y){ // 合并两棵Treap
	if(!x||!y)return x+y;
	if(tr[x].rd<tr[y].rd){
		rc(x)=merge(rc(x),y);
		pushup(x);
		return x;		
	}
	else{
		lc(y)=merge(x,lc(y));
		pushup(y);
		return y;
	}
}
int fdrk(int k){ // 查找第k个【有效】元素在Treap中的绝对位置(只包含未删除节点的排名)
	if(!k)return 0; 
	int p=rt,ans=0;
	while(1){
		if(tr[lc(p)].vs+tr[p].vz==k&&tr[p].vz)return ans+tr[lc(p)].sz+1;
		if(tr[lc(p)].vs>=k)p=lc(p);
		else k-=tr[lc(p)].vs+tr[p].vz,ans+=tr[lc(p)].sz+1,p=rc(p);
	}
}
void ins(int k,int v,int qi){ // 在下标为k的有效元素之后插入新元素
	k=fdrk(k);
	int x,y,z;
	split(rt,k,x,y);
	split(x,k-1,x,z);
	tr[x].qi.push_back(qi); // 将操作编号记录在左半部分的末尾节点上
	rt=merge(merge(merge(x,z),nd(qi)),y); // 合并：左半部分 + 原第k个元素 + 新节点 + 右半部分
}
void del(int k,int qi){ // 删除下标为k的有效元素
	k=fdrk(k);
	int x,y,z;
	split(rt,k,x,y);
	split(x,k-1,x,z);
	tr[z].vz=tr[z].vs=0;tr[z].qi.push_back(qi); // 标记为无效，但不从树中删除以维持相对位置
	rt=merge(merge(x,z),y);
}
void change(int k,int v,int qi){ // 修改下标为k的有效元素
	k=fdrk(k);
	int x,y,z;
	split(rt,k,x,y);
	split(x,k-1,x,z);
	tr[z].qi.push_back(qi); // 记录修改操作的编号
	rt=merge(merge(x,z),y);
}
void tg(int k,int qi){ // 获取下标为k的有效元素的当前绝对位置，用于处理查询的左右端点
	k=fdrk(k);
	int x,y,z;
	split(rt,k,x,y);
	split(x,k-1,x,z);
	tr[z].qi.push_back(qi);
	rt=merge(merge(x,z),y);
}
int aid,pi[500010]; // aid:静态数组最终大小, pi[i]:操作i对应的静态数组下标
void dfs(int p){ // 中序遍历Treap，将有效节点按顺序映射到静态数组，并确定各操作对应的最终下标
	if(!p)return ;
	dfs(lc(p));
	aid++;
	for(int i:tr[p].qi)if(i)pi[i]=aid; // 将记录在该节点上的操作，其对应的下标都设为aid
	dfs(rc(p));
}
int B; // 莫队分块大小
struct QU{
	int op,l,r,ri,id; // op:询问类型, l,r:左右端点, ri:该询问前的修改数, id:询问编号
}q[100010];
bool cmp(QU a,QU b){ // 带修改莫队的排序规则 (3D莫队)
	if(a.l/B!=b.l/B)return a.l<b.l;
	if(a.r/B!=b.r/B)return a.r<b.r;
	return (a.l/B&1)?a.ri>b.ri:a.ri<b.ri; // 奇偶优化，减少时间指针tp的移动
}
struct R{
	int x,v; // x:修改的位置, v:修改后的值(离散化后)
}rr[100010];
ll ans[100010];
ll s1,s2,s3,s; // s:不同元素个数, s1:sum(v), s2:sum(v_i*v_j), s3:sum(v_i*v_j*v_k)
ll lsh[200010],ln; // 离散化数组及有效元素个数
int cnt[200010]; // 记录每个值在当前区间内的出现次数
void add(ll v){ // 莫队加入元素
	if(!v)return ; // 忽略无效位置(v=0对应被删除或尚未插入的空位)
	cnt[v]++;
	if(cnt[v]==1){ // 第一次出现该值，更新组合数答案
		s++;
		v=lsh[v]; // 还原为真实值
		s3=(s3+s2*v%mod)%mod;
		s2=(s2+s1*v)%mod;
		s1=(s1+v)%mod;
	}
}
void delv(ll v){ // 莫队删除元素
	if(!v)return ;
	cnt[v]--;
	if(!cnt[v]){ // 该值在区间内不再出现，更新组合数答案
		s--;
		v=lsh[v];
		s1=(s1-v+mod)%mod;
		s2=(s2-s1*v%mod+mod)%mod;
		s3=(s3-s2*v%mod+mod)%mod;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int Q; 
	cin>>n>>Q;
	int ti=0; // 全局时间戳/节点编号
	for(int i=1;i<=n;i++){ // 初始化Treap，读入初始数组
		cin>>a[i];lsh[++ln]=a[i];
		rt=merge(rt,nd(++ti));
	}
	int qi=0,ri=0,lln=n; // qi:询问总数, ri:修改总数, lln:初始元素总数
	for(int i=1;i<=Q;i++){ // 离线处理所有操作，将动态下标转化为静态下标
		int op;
		cin>>op;
		if(op==1){ // 询问1
			int l,r;
			cin>>l>>r;
			ti++;tg(l,ti); // 获取左端点对应的节点，并记录操作编号
			l=ti;
			ti++;tg(r,ti); // 获取右端点对应的节点，并记录操作编号
			r=ti;qi++;
			q[qi]={1,l,r,ri,qi};
		}
		if(op==2){ // 修改操作
			int x,v;
			cin>>x>>v;lsh[++ln]=v;
			ti++;
			change(x,v,ti);
			rr[++ri]={ti,v};
		}
		if(op==3){ // 删除操作
			int x;
			cin>>x;
			ti++;
			del(x,ti);
			rr[++ri]={ti,0}; // v=0表示删除
		}
		if(op==4){n++; // 插入操作
			int x,v;
			cin>>x>>v;lsh[++ln]=v;
			ti++;
			ins(x,v,ti);
			rr[++ri]={ti,v};
		}
		if(op==5){ // 询问5
			int l,r;
			cin>>l>>r;
			ti++;tg(l,ti);
			l=ti;
			ti++;tg(r,ti);
			r=ti;qi++;
			q[qi]={2,l,r,ri,qi};
		}
	}
	dfs(rt); // 中序遍历Treap，确定所有操作对应的最终静态下标
	sort(lsh+1,lsh+ln+1); // 离散化
	ln=unique(lsh+1,lsh+1+ln)-lsh-1;
	for(int i=1;i<=lln;i++){ // 构建初始的静态数组b
		b[pi[i]]=lower_bound(lsh+1,lsh+1+ln,a[i])-lsh;
	}
	for(int i=1;i<=qi;i++)q[i].l=pi[q[i].l],q[i].r=pi[q[i].r]; // 将询问端点替换为最终静态下标
	for(int i=1;i<=ri;i++){ // 将修改位置替换为最终静态下标
		rr[i].x=pi[rr[i].x];if(rr[i].v)rr[i].v=lower_bound(lsh+1,lsh+1+ln,rr[i].v)-lsh;
	}
	B=pow(n,0.67); // 3D莫队的块大小，通常取N^(2/3)
	sort(q+1,q+1+qi,cmp);
	int l=1,r=0,tp=0; // l,r为当前莫队区间，tp为当前时间戳(修改次数)
	for(int i=1;i<=qi;i++){ // 莫队主循环
		while(q[i].l<l)add(b[--l]); // 区间左扩
		while(q[i].r>r)add(b[++r]); // 区间右扩
		while(q[i].l>l)delv(b[l++]); // 区间左缩
		while(q[i].r<r)delv(b[r--]); // 区间右缩
		while(q[i].ri>tp){ // 时间戳正向移动
			tp++;
			if(rr[tp].x>=l&&rr[tp].x<=r){
				add(rr[tp].v);
				delv(b[rr[tp].x]);
			}
			swap(b[rr[tp].x],rr[tp].v); // 交换以支持时间回退
		}
		while(q[i].ri<tp){ // 时间戳逆向移动
			if(rr[tp].x>=l&&rr[tp].x<=r){
				add(rr[tp].v);
				delv(b[rr[tp].x]);
			}
			swap(b[rr[tp].x],rr[tp].v);
			tp--;
		}
		if(q[i].op==1)ans[q[i].id]=s3; // 记录答案
		else ans[q[i].id]=s;
	}
	for(int i=1;i<=qi;i++){ // 输出答案
		cout<<ans[i]<<'\n';
	}
	return 0;
}