wordpress 全文搜索,企业网站优化策略,珠海网站建设公,wordpress主题绕过激活码正题
题目链接:https://www.luogu.com.cn/problem/P3273 题目大意 nnn个点有权值#xff0c;要求支持操作
连接两个点单点加权联通块加权全图加权单点询问联通块询问最大值全图询问最大值 解题思路
把所有可能产生的联通块都变到一个区间里就好了
考虑怎么排这个东西…正题
题目链接:https://www.luogu.com.cn/problem/P3273 题目大意
nnn个点有权值要求支持操作
连接两个点单点加权联通块加权全图加权单点询问联通块询问最大值全图询问最大值 解题思路
把所有可能产生的联通块都变到一个区间里就好了
考虑怎么排这个东西可以先离线每次加边的时候连接两个联通块根这样跑出来的dfsdfsdfs序就是符合要求的。
注意因为邻接表是按照加边的顺序倒着枚举的所以要反过来加边。
然后用线段树直接维护答案就好了
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e510;
struct qnode{char op[3];int x,y;
}p[N];
struct node{int to,next;
}a[N];
int n,q,tot,cnt,ls[N],w[N],fa[N],l[N],r[N];
struct SegTree{int w[N2],lazy[N2];void Downdata(int x){if(!lazy[x])return;w[x*2]lazy[x];lazy[x*2]lazy[x];w[x*21]lazy[x];lazy[x*21]lazy[x];lazy[x]0;return;}void Change(int x,int L,int R,int l,int r,int val){if(LlRr){w[x]val;lazy[x]val;return;}int mid(LR)1;Downdata(x);if(rmid)Change(x*2,L,mid,l,r,val);else if(lmid)Change(x*21,mid1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*21,mid1,R,mid1,r,val);w[x]max(w[x*2],w[x*21]);return;}int Ask(int x,int L,int R,int l,int r){if(LlRr){return w[x];}int mid(LR)1;Downdata(x);if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return max(Ask(x*2,L,mid,l,mid),Ask(x*21,mid1,R,mid1,r));}
}T;
void addl(int x,int y){if(xy)return;a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
void dfs(int x){l[x]r[x]cnt;T.Change(1,1,n,cnt,cnt,w[x]);for(int ils[x];i;ia[i].next)dfs(a[i].to);return;
}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,w[i]),fa[i]i;scanf(%d,q);for(int i1;iq;i){scanf(%s,p[i].op);if(p[i].op[0]U){scanf(%d%d,p[i].x,p[i].y);p[i].xfind(p[i].x);p[i].yfind(p[i].y);if(p[i].xp[i].y)continue;if(p[i].xp[i].y)swap(p[i].x,p[i].y);fa[p[i].y]p[i].x;}else if(p[i].op[0]Ap[i].op[1]1)scanf(%d%d,p[i].x,p[i].y);else if(p[i].op[0]Ap[i].op[1]2)scanf(%d%d,p[i].x,p[i].y);else if(p[i].op[0]!F||p[i].op[1]!3)scanf(%d,p[i].x);}for(int iq;i1;i--)if(p[i].op[0]U)addl(p[i].x,p[i].y);for(int i1;in;i)if(find(i)i)dfs(i);for(int i1;in;i)fa[i]i;for(int i1;iq;i){int xp[i].x,yp[i].y;if(p[i].op[0]U){if(xy)continue;fa[y]x;r[x]r[y];}else if(p[i].op[0]Ap[i].op[1]1)T.Change(1,1,n,l[x],l[x],y);else if(p[i].op[0]Ap[i].op[1]2)xfind(x),T.Change(1,1,n,l[x],r[x],y);else if(p[i].op[0]Ap[i].op[1]3)T.Change(1,1,n,1,n,x);else if(p[i].op[0]Fp[i].op[1]1)printf(%d\n,T.Ask(1,1,n,l[x],l[x]));else if(p[i].op[0]Fp[i].op[1]2)xfind(x),printf(%d\n,T.Ask(1,1,n,l[x],r[x]));else printf(%d\n,T.Ask(1,1,n,1,n));}return 0;
}
