坪山网站建设平台,网站图片展示源码,系统开发平台,安徽池州建设厅网站传送门 Description 有\(N\)个节点#xff0c;标号从\(1\)到\(N\)#xff0c;这\(N\)个节点一开始相互不连通。第$ i\(个节点的初始权值为\)a_i$ #xff0c;接下来有如下一些操作#xff1a; U x y 加一条边#xff0c;连接第 \(x\) 个节点和第\(y\) 个节点。 A1 x v 将… 传送门 Description 有\(N\)个节点标号从\(1\)到\(N\)这\(N\)个节点一开始相互不连通。第$ i\(个节点的初始权值为\)a_i$ 接下来有如下一些操作 U x y 加一条边连接第 \(x\) 个节点和第\(y\) 个节点。 A1 x v 将第 \(x\) 个节点的权值增加 \(v\)。 A2 x v 将第 \(x\) 个节点所在的连通块的所有节点的权值都增加 \(v\)。 A3 v 将所有节点的权值都增加\(v\) 。 F1 x 输出第 \(x\) 个节点当前的权值。 F2 x 输出第 \(x\) 个节点所在的连通块中权值最大的节点的权值。 F3 输出所有节点中权值最大的节点的权值。 Solution 离线处理 对原序列进行重新排序使得每次合并时两个集合的存在区间恰好相邻 转化为简单的线段树区间修改区间询问 Code #includebits/stdc.h
#define ll long long
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(b):(a))
#define pi std::pairint,int
#define reg register
using namespace std;
inline int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x3)(x1)ch-0;chgetchar();}return x*f;
}
const int MN6e55;
int A[MN],Map[MN],fMap[MN];
struct Mapper
{int fa[MN],L[MN],R[MN],suf[MN];void init(int N){reg int i;for(i1;iN;i) fa[i]L[i]R[i]i,suf[i]-1;}int getf(int x){return fa[x]x?x:fa[x]getf(fa[x]);}void insert(int x,int y){xgetf(x);ygetf(y);if(xy) return;suf[R[x]]L[y];L[y]L[x];fa[x]y;}bool vis[MN];void getMap(int N){memset(vis,0,sizeof vis);reg int i,l,r,cnt0;for(i1;iN;i)if(!vis[i])for(lL[getf(i)];l0;lsuf[l]) vis[fMap[cnt]l]true;for(i1;iN;i) Map[fMap[i]]i;}
}a;
struct Operation{int opt,x,y;}O[MN];
int readchar()
{static char s[5];scanf(%s,s1);if(s[1]U) return 1;if(s[1]A) return 1s[2]-0;if(s[1]F) return 4s[2]-0;
}
struct Union_Find
{int fa[MN],L[MN],R[MN];void init(int N){reg int i;for(i1;iN;i) fa[i]i,L[i]R[i]Map[i];}int getf(int x){return fa[x]x?x:fa[x]getf(fa[x]);}void combine(int x,int y){xgetf(x);ygetf(y);if(xy) return;fa[x]y;L[y]min(L[y],L[x]);R[y]max(R[x],R[y]);}pi get(int x){xgetf(x);return make_pair(L[x],R[x]);}
}b;
struct SegTree
{#define ls x1#define rs x1|1#define mid ((lr)1)int t[MN2],lazy[MN1];void up(int x){t[x]max(t[ls],t[rs]);}void Build(int x,int l,int r){if(lr) return (void)(t[x]A[fMap[l]]);Build(ls,l,mid);Build(rs,mid1,r);up(x);}void C(int x,int val){t[x]val,lazy[x]val;}void down(int x){if(lazy[x])C(ls,lazy[x]),C(rs,lazy[x]),lazy[x]0;}void Modify(int x,int l,int r,int a,int b,int val){if(larb) return (void)(C(x,val));down(x);if(bmid) Modify(ls,l,mid,a,b,val);else if(amid) Modify(rs,mid1,r,a,b,val);else Modify(ls,l,mid,a,mid,val),Modify(rs,mid1,r,mid1,b,val);up(x);}int Query(int x,int l,int r,int a,int b){if(larb) return t[x];down(x);if(bmid) return Query(ls,l,mid,a,b);else if(amid) return Query(rs,mid1,r,a,b);else return max(Query(ls,l,mid,a,mid),Query(rs,mid1,r,mid1,b));}
}c;
int main()
{reg int i,Nread(); a.init(N);for(i1;iN;i) A[i]read();reg int Mread();for(i1;iM;i){O[i].optreadchar();if(O[i].opt7) O[i].xread();if(O[i].opt4) O[i].yread();if(O[i].opt1) a.insert(O[i].x,O[i].y);}a.getMap(N);c.Build(1,1,N);b.init(N);pi xxx;for(i1;iM;i){if(O[i].opt1) b.combine(O[i].x,O[i].y);if(O[i].opt2) c.Modify(1,1,N,Map[O[i].x],Map[O[i].x],O[i].y);if(O[i].opt3) xxxb.get(O[i].x),c.Modify(1,1,N,xxx.first,xxx.second,O[i].y);if(O[i].opt4) c.Modify(1,1,N,1,N,O[i].x);if(O[i].opt5) printf(%d\n,c.Query(1,1,N,Map[O[i].x],Map[O[i].x]));if(O[i].opt6) xxxb.get(O[i].x),printf(%d\n,c.Query(1,1,N,xxx.first,xxx.second));if(O[i].opt7) printf(%d\n,c.Query(1,1,N,1,N));}return 0;
} Blog来自PaperCloud未经允许请勿转载TKS 转载于:https://www.cnblogs.com/PaperCloud/p/10657606.html
