专栏文章

P3273 题解

xxyz123
P3273题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqf59qz
此快照首次捕获于
2025/12/04 03:47
3 个月前
此快照最后确认于
2025/12/04 03:47
3 个月前
查看原文
可以强制在线的线段树做法。
如果你不会线段树合并，左转 P4556【模板】线段树合并。
对于第 ii 个点，建一颗线段树，并将第 ii 个位置的值改为 aia_i。
再用一个并查集维护这个点所在的连通块，第 ii 个点初始属于第 ii 个连通块。
再用一个线段树（称为总线段树）维护连通块的最大值。
再用一个变量（记为 dd）维护所有点的增加量。
对于操作 U，先找到 xx 和 yy 对应的连通块编号 vxv_x 和 vyv_y。 如果不同，在并查集中将 vxv_x 合并到 vyv_y，并将第 vxv_x 个线段树合并到第 vyv_y 个线段树，然后在总线段树中将 vxv_x 的值改为极小值，vyv_y 的值改为该连通块内的最大值。
对于操作 A1，先找到 xx 对应的连通块编号 vxv_x，然后修改第 vxv_x 个线段树第 xx 个位置为 vv，修改后在总线段树中修改第 vxv_x 个连通块的值。
对于操作 A2，先找到 xx 对应的连通块编号 vxv_x，然后在该树的根节点打标记，并在总线段树中做对应修改。
对于操作 A3，将 dd 增加 vv。
对于所有的 F 类操作，在输出答案时要将线段树中的查询结果增加 dd 后输出。
对于 F1 操作，先找到 xx 对应的连通块编号 vxv_x，然后查询第 vxv_x 个线段树第 xx 个位置的值。
对于 F2 操作，先找到 xx 对应的连通块编号 vxv_x，然后查询结果为第 vxv_x 个线段树根节点上的值。
对于 F3 操作，查询结果为总线段树的根节点的值。
注意：合并线段树时一定要下放懒标记！
code:
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int f[N];
int find(int x){return x==f[x]?f[x]:f[x]=find(f[x]);}
int rt[N];
int val[N<<5],ls[N<<5],rs[N<<5],lazy[N<<5],idx;
void pushdown(int k){
	if(ls[k]){lazy[ls[k]]+=lazy[k];val[ls[k]]+=lazy[k];}
	if(rs[k]){lazy[rs[k]]+=lazy[k];val[rs[k]]+=lazy[k];}
	lazy[k]=0;
}
void update(int&k,int l,int r,int x,int v){
	if(!k)	k=++idx;
	if(l==r){val[k]+=v;return;}
	pushdown(k);
	int mid=(l+r)>>1;
	if(x<=mid)	update(ls[k],l,mid,x,v);
	else	update(rs[k],mid+1,r,x,v);
	val[k]=max(val[ls[k]],val[rs[k]]);
}
int query(int k,int l,int r,int x){
	if(l==r)	return val[k];
	pushdown(k);
	int mid=(l+r)>>1;
	if(x<=mid)	return query(ls[k],l,mid,x);
	else	return query(rs[k],mid+1,r,x);
}
void merge(int&k1,int&k2){
	if(!k1){k1=k2;return;}
	if(!k2)	return;
	pushdown(k1);pushdown(k2);
	merge(ls[k1],ls[k2]);
	merge(rs[k1],rs[k2]);
	val[k1]=max(val[ls[k1]],val[rs[k1]]);
}
int tree[N<<2];
void update2(int k,int l,int r,int x,int v){
	if(l==r){tree[k]=v;return;}
	int mid=(l+r)>>1;
	if(x<=mid)	update2(k<<1,l,mid,x,v);
	else	update2(k<<1|1,mid+1,r,x,v);
	tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
int gl;
int n;
char op[4];
int main(){
	//freopen("test.in","r",stdin);
	//freopen("test1.out","w",stdout);
	val[0]=-0x3f3f3f3f;
	memset(tree,-0x3f,sizeof tree);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	f[i]=i;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		update(rt[i],1,n,i,x);
		update2(1,1,n,i,x);
	}
	int q;scanf("%d",&q);
	while(q--){
		scanf("%s",op);
		if(op[0]=='U'){
			int x,y;scanf("%d%d",&x,&y);
			x=find(x);y=find(y);
			if(x!=y){
				int mx=max(val[rt[x]],val[rt[y]]);
				update2(1,1,n,y,mx);
				update2(1,1,n,x,-0x3f3f3f3f);
				f[x]=y;
				merge(rt[y],rt[x]);
			}
		}
		if(op[0]=='A'){
			if(op[1]=='1'){
				int x,v;scanf("%d%d",&x,&v);
				update(rt[find(x)],1,n,x,v);
				update2(1,1,n,find(x),val[rt[find(x)]]);
			}
			if(op[1]=='2'){
				int x,v;scanf("%d%d",&x,&v);
				val[rt[find(x)]]+=v;
				lazy[rt[find(x)]]+=v;
				update2(1,1,n,find(x),val[rt[find(x)]]);
			}
			if(op[1]=='3'){
				int v;scanf("%d",&v);
				gl+=v;
			}
		}
		if(op[0]=='F'){
			if(op[1]=='1'){
				int x;scanf("%d",&x);
				printf("%d\n",query(rt[find(x)],1,n,x)+gl);
			}
			if(op[1]=='2'){
				int x;scanf("%d",&x);
				printf("%d\n",val[rt[find(x)]]+gl);
			}
			if(op[1]=='3'){
				printf("%d\n",tree[1]+gl);
			}
		}
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...