正定县建设局网站,东莞微信网站建设咨询,网站推广优化排名公司,设计书籍频道已开放题目传送门 棘手的操作 题目描述 有N个节点#xff0c;标号从1到N#xff0c;这N个节点一开始相互不连通。第i个节点的初始权值为a[i]#xff0c;接下来有如下一些操作#xff1a; U x y: 加一条边#xff0c;连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x… 题目传送门 棘手的操作 题目描述 有N个节点标号从1到N这N个节点一开始相互不连通。第i个节点的初始权值为a[i]接下来有如下一些操作 U x y: 加一条边连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x v: 将第x个节点所在的连通块的所有节点的权值都增加vA3 v: 将所有节点的权值都增加vF1 x: 输出第x个节点当前的权值F2 x: 输出第x个节点所在的连通块中权值最大的节点的权值F3: 输出所有节点中权值最大的节点的权值输入输出格式 输入格式 输入的第一行是一个整数N代表节点个数。接下来一行输入N个整数a[1], a[2], ..., a[N]代表N个节点的初始权值。再下一行输入一个整数Q代表接下来的操作数。最后输入Q行每行的格式如题目描述所示。 输出格式 对于操作F1, F2, F3输出对应的结果每个结果占一行。 输入输出样例 输入样例#1 3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3 输出样例#1 -10
10
10 说明 对于30%的数据保证 N100Q10000 对于80%的数据保证 N100000Q100000 对于100%的数据保证 N300000Q300000 对于所有的数据保证输入合法并且 -1000v, a[1], a[2], ..., a[N]1000 分析 真是一道恶心的左偏树题。 需要维护两个左偏树第一个维护正常的操作信息第二个维护所有点中的最大值。 第一种操作在第一个左偏树中$merge$即可另外有一个小优化合并的两个堆顶中较小的一个可以直接从第二个左偏树中删除正确性自己思考。 第二种操作将该点从两个左偏树中删除修改值以后再重新放回去。 第三种操作用$lazy$标记只修改堆顶的值后面再$merge$或者删除节点的时候下方标记。 第四种操作用一个变量记录需要输出的时候再加上。 第五种操作直接输出第一个左偏树中该节点的值。 第六种操作直接输出第一个左偏树中该节点所在堆的堆顶的值。 第七种操作直接输出第二个左偏树的根节点的值。 以上。 题如其名真$TM$又棘手又恶心。。。 Code //It is made by HolseLee on 28th Aug 2018
//Luogu.org P3273
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define Max(a,b) (a)(b) ? (a) : (b)
using namespace std;const int N3e57;
int n,a[N],m,allsign,root;
struct Leftist{int ch[N][2],val[N],sign[N],fa[N],dis[N];void clear(int x){ch[x][0]ch[x][1]fa[x]0;}int sum(int x){int ret0;while(xfa[x])retsign[x];return ret;}void pushdown(int x){int ulch[x][0], urch[x][1];if( ul )val[ul]sign[x], sign[ul]sign[x];if( ur )val[ur]sign[x], sign[ur]sign[x];sign[x]0;}int merge(int x,int y){if(!x||!y)return xy;if( val[x]val[y] )swap(x,y);pushdown(x);int ulch[x][0], urch[x][1];urmerge(ur,y); fa[ur]x;if( dis[ur]dis[ul] )swap(ul,ur);dis[x]dis[ur]1;return x;}int find(int x){while(fa[x])xfa[x];return x;}int delet(int x){pushdown(x);int fxfa[x];int kamerge(ch[x][0],ch[x][1]);fa[ka]fx;if( fx )ch[fx][xch[fx][1]]ka;while( fx ) {if( dis[ch[fx][0]]dis[ch[fx][1]] )swap(ch[fx][0],ch[fx][1]);if( dis[fx]dis[ch[fx][1]]1 )return root;dis[fx]dis[ch[fx][1]]1;kafx;fxfa[fx];}return ka;}int add_point(int x,int v){int fxfind(x);if( fxx ) {if( ch[x][0]ch[x][1]0 ){val[x]v; return x;} else {if( ch[x][0] ) fxch[x][0];else fxch[x][1];}}delet(x);val[x]vsum(x);clear(x);return merge(find(fx),x);}int build(){queueintt;for(int i1; in; i) t.push(i);int x,y,z;while( t.size()1 ) {xt.front(); t.pop();yt.front(); t.pop();zmerge(x,y);t.push(z);}return t.front();}
}T,H;void read(int x)
{x0; char chgetchar(); bool flagfalse;while( ch0 || ch9 ) {if( ch- )flagtrue;chgetchar();}while( ch0 ch9 ) {x(x1)(x3)(ch^48);chgetchar();}flag?x*(-1):1;
}int main()
{read(n);T.dis[0]H.dis[0]-1;for(int i1; in; i){read(a[i]);T.val[i]H.val[i]a[i];}rootH.build();read(m);char op[3];int x,y,fx,fy,temp;for(int i1; im; i){scanf(%s,op);if( op[0]A ) {switch( op[1] ){case 1:read(x), read(y);rootH.delet(T.find(x));tempT.add_point(x,y);H.val[temp]T.val[temp];H.clear(temp);rootH.merge(root,temp);break;case 2:read(x), read(y); fxT.find(x);rootH.delet(fx);T.val[fx]y; T.sign[fx]y;H.val[fx]T.val[fx];H.clear(fx);rootH.merge(root,fx);break;case 3:read(y);allsigny;break;}} else if( op[0]F ) {switch( op[1] ){case 1:read(x);printf(%d\n,T.val[x]allsignT.sum(x));break;case 2:read(x);printf(%d\n,T.val[T.find(x)]allsign);break;case 3:printf(%d\n,H.val[root]allsign);break;}} else {read(x), read(y);fxT.find(x), fyT.find(y);if( fxfy )continue;tempT.merge(fx,fy);if( tempfx )rootH.delet(fy);else rootH.delet(fx);}}return 0;
} 转载于:https://www.cnblogs.com/cytus/p/9551080.html
