最近下载的网站怎么找,宁波电商网站建设开发,在运营中seo是什么意思,中国拟在建项目网题目 有N个节点#xff0c;标号从1到N#xff0c;这N个节点一开始相互不连通。第i个节点的初始权值为a[i]#xff0c;接下来有如下一些操作#xff1a; U x y: 加一条边#xff0c;连接第x个节点和第y个节点 A1 x v: 将第x个节点的权值增加v A2 x v: 将第x个节点所在的连通… 题目 有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: 输出所有节点中权值最大的节点的权值 输入格式 输入的第一行是一个整数N代表节点个数。 接下来一行输入N个整数a[1], a[2], …, a[N]代表N个节点的初始权值。 再下一行输入一个整数Q代表接下来的操作数。 最后输入Q行每行的格式如题目描述所示。 输出格式 对于操作F1, F2, F3输出对应的结果每个结果占一行。 输入样例 3 0 0 0 8 A1 3 -20 A1 2 20 U 1 3 A2 1 10 F1 3 F2 3 A3 -10 F3 输出样例 -10 10 10 提示 对于30%的数据保证 N100Q10000 对于80%的数据保证 N100000Q100000 对于100%的数据保证 N300000Q300000 对于所有的数据保证输入合法并且 -1000v, a[1], a[2], …, a[N]1000 题解 据说此题很多人堆套堆怎么这么难写我那么弱当然是用线段树啦 我觉得线段树的确好写到不知哪里去 对于所有操作似乎在线段树上都很好实现唯一的难点就在于点的编号 那么问题就转化成了给定一种编号方法使任意时刻同一个联通块内的所有点编号连续 只需要分两种情况想就很容易实现了 我们想象一开始所有点相互独立没什么关系 ①当两个独立的点相连时它们的编号一定是连续的否则此时就不满足所需性质 那我们就先用链表将它们连起来表示编号连续 ②当两个联通块相连时由我们维护的性质得两个联通块内部的点编号一定是连续的现在我们需要两个联通块编号连续我们只需要将它们的编号衔接起来就好了那么我们把其中一个联通块所对应的链 接到另一个联通块对应的链末尾就好了 可以发现这样子操作之后我们就会得出若干个链表示链上的点编号必须按链上的顺序 所以我们按链的顺序标号就能保证所有时刻联通块内部点的编号连续 取链头链尾用并查集实现 我们在询问的时候也要用上并查集并且链接顺序与标号的时候相同保证每个联通块目前的代表元一定是标号时编号最小的点所以我们再维护并查集的大小就可以轻松求出每次操作的区间啦~ 数据结构部分就只用实现一个简单的线段树比堆套堆不知道要好写到哪里去 丑丑的代码 #includeiostream
#includecmath
#includecstdio
#includecstring
#includealgorithm
#define LL long long int
#define REP(i,n) for (int i 1; i (n); i)
#define Redge(u) for (int k h[u],to; k; k ed[k].nxt)
#define BUG(s,n) for (int i 1; i (n); i) couts[i] ; puts();
#define ls (u 1)
#define rs (u 1 | 1)
using namespace std;
const int maxn 300005,maxm 100005,INF 1000000000;
inline int read(){int out 0,flag 1; char c getchar();while (c 48 || c 57) {if (c -) flag -1; c getchar();}while (c 48 c 57) {out (out 3) (out 1) c - 0; c getchar();}return out * flag;
}
struct Query{int opt,a,b,c;}q[maxn];
int n,m,pre[maxn],post[maxn],id[maxn],Hash[maxn],val[maxn],cnt;
int nxt[maxn],siz[maxn];
int mx[4 * maxn],tag[4 * maxn];
char opt[10];
int findu(int u){return u pre[u] ? u : pre[u] findu(pre[u]);}
int findd(int u){return u post[u] ? u : post[u] findd(post[u]);}
void build(int u,int l,int r){if (l r) {mx[u] val[Hash[l]]; return;}int mid l r 1;build(ls,l,mid);build(rs,mid 1,r);mx[u] max(mx[ls],mx[rs]);
}
void pd(int u){if (tag[u]){mx[ls] tag[u]; tag[ls] tag[u];mx[rs] tag[u]; tag[rs] tag[u];tag[u] 0;}
}
void modify(int u,int l,int r,int L,int R,int v){if (l L r R){mx[u] v; tag[u] v; return;}pd(u);int mid l r 1;if (mid L) modify(ls,l,mid,L,R,v);if (mid R) modify(rs,mid 1,r,L,R,v);mx[u] max(mx[ls],mx[rs]);
}
int query(int u,int l,int r,int L,int R){if (l L r R) return mx[u];pd(u);int mid l r 1;if (mid R) return query(ls,l,mid,L,R);else if (mid L) return query(rs,mid 1,r,L,R);else return max(query(ls,l,mid,L,R),query(rs,mid 1,r,L,R));
}
int main(){n read();for (int i 1; i n; i) val[i] read(),pre[i] post[i] i;m read();int fa,fb,sa,sb;for (int i 1; i m; i){scanf(%s,opt);if (opt[0] U){q[i].opt 0,q[i].a read(),q[i].b read();fa findu(q[i].a); fb findu(q[i].b);if (fa fb) continue;sa findd(q[i].a); sb findd(q[i].b);nxt[sa] fb;pre[fb] fa;post[sa] sb;}else if (opt[0] A){q[i].a read();if (opt[1] 1) q[i].opt 1,q[i].b read();else if (opt[1] 2) q[i].opt 2,q[i].b read();else q[i].opt 3;}else {if (opt[1] 1) q[i].opt 4,q[i].a read();else if (opt[1] 2) q[i].opt 5,q[i].a read();else q[i].opt 6;}}for (int i 1; i n; i){if (id[i]) continue;int u findu(i);while (u) id[u] cnt,Hash[cnt] u,u nxt[u];}build(1,1,n);for (int i 1; i n; i) pre[i] i,siz[i] 1;for (int i 1; i m; i){switch(q[i].opt){case 0:fa findu(q[i].a); fb findu(q[i].b);if (fa ! fb){siz[fa] siz[fb];pre[fb] fa;}break;case 1:modify(1,1,n,id[q[i].a],id[q[i].a],q[i].b);break;case 2:fa findu(q[i].a);modify(1,1,n,id[fa],id[fa] siz[fa] - 1,q[i].b);break;case 3:modify(1,1,n,1,n,q[i].a);break;case 4:printf(%d\n,query(1,1,n,id[q[i].a],id[q[i].a]));break;case 5:fa findu(q[i].a);printf(%d\n,query(1,1,n,id[fa],id[fa] siz[fa] - 1));break;case 6:printf(%d\n,mx[1]);break;}}return 0;
}转载于:https://www.cnblogs.com/Mychael/p/8490297.html
