「BZOJ2333」[SCOI2011] 棘手的操作
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: 输出所有节点中，权值最大的节点的权值
Input
输入的第一行是一个整数N，代表节点个数。
接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。
再下一行输入一个整数Q，代表接下来的操作数。
最后输入Q行，每行的格式如题目描述所示。
Output
对于操作F1, F2, F3，输出对应的结果，每个结果占一行。
Sample Input
3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
Sample Output
-10
10
10
HINT
对于30%的数据，保证 N<=100，Q<=10000
对于80%的数据，保证 N<=100000，Q<=100000
对于100%的数据，保证 N<=300000，Q<=300000
对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000
题解
离线+线段树。。。？？
不我怎么弱当然只会直接模拟。。。
给连通块增加一个值以及合并连通块，维护最大值
我们需要一个手写的可并堆，斜堆极好。。。
然后还要维护全局最大值，支持修改结点。。。
唔再来个可并堆也行，因为我比较偷懒，所以用了个set
其实用pb_ds的配对堆似乎更优越
U 找到x，y所在堆的堆顶，较小的从set中删除，合并两个堆
A1 处理x祖先的标记，把x所在堆顶删出set，把x从堆中取出，加完v再放进去，堆顶放入set
A2 x所在堆顶删出set，堆顶打标记，改权值后放回set
A3 开个变量存起来TAT
F1 处理x祖先的标记，输出
F2 输出x所在堆顶
F3 输出set中最大值
嘴巴上AC果然简单。。。
嫌我写的太sb的话大家还是看pyc神犇的blog吧
http://blog.csdn.net/charlie_pyc/article/details/20830305
我会告诉你我对拍半天的错误数据是。。。？如下
input
2
0 0
3
U 1 2
A1 1 -8
F3
output
0
。。。我负数乱做。。。跪烂了
顺便附sb的数据生成器
数据生成器
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } string s1[4]={"U","A1","A2","A3"}; string s2[3]={"F1","F2","F3"}; int main() { srand(time(0)); int n=10,m=5; cout<<n<<endl; for(int i=1;i<=n;i++)cout<<0<<' ';cout<<endl; cout<<5*m<<endl; for(int i=1;i<=m;i++) { int u=rand()%n+1,v=rand()%n+1; string s=s1[rand()%4]; cout<<s<<' '; if(s=="U")cout<<u<<' '<<v; else if(s!="A3")cout<<u<<' '<<-v; else cout<<u; cout<<endl; } for(int i=1;i<=4*m;i++) { int u=rand()%n+1,v=rand()%n+1; string s=s2[rand()%3]; cout<<s<<' '; if(s!="F3")cout<<u; cout<<endl; } return 0; } |
代码。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<set> #define inf 1000000000 using namespace std; int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,Q,overadd; int a[300005]; multiset<int> st; void erase(int x) { st.erase(st.find(x)); } void insert(int x) { st.insert(x); } struct Sheap{ int ls[300005],rs[300005],fa[300005]; int tag[300005],v[300005],q[300005]; int tot; int find(int x){ while(fa[x])x=fa[x]; return x; } void pushdown(int k){ if(!tag[k])return; int t=tag[k],l=ls[k],r=rs[k]; tag[k]=0; if(l)tag[l]+=t,v[l]+=t; if(r)tag[r]+=t,v[r]+=t; } void solvetag(int x){ while(x)q[++tot]=x,x=fa[x]; while(tot)pushdown(q[tot--]); } int top(int x){ return v[find(x)]; } int merge(int x,int y){ if(!x||!y)return x+y; if(v[x]<v[y])swap(x,y); pushdown(x); rs[x]=merge(rs[x],y); fa[rs[x]]=x; swap(ls[x],rs[x]); return x; } int del(int x){ solvetag(x); int t=merge(ls[x],rs[x]),f=fa[x]; ls[x]=rs[x]=fa[x]=0; if(x==ls[f])ls[f]=t; else rs[f]=t; fa[t]=f; return find(t); } void add(int x,int val){ solvetag(x); erase(v[find(x)]); v[x]+=val; insert(v[merge(x,del(x))]); } void heap_add(int x,int val){ int p=find(x); tag[p]+=val;v[p]+=val; erase(v[p]-val);insert(v[p]); } void addedge(int x,int y){ int t1=find(x),t2=find(y); if(t1!=t2) { if(merge(t1,t2)==t1)st.erase(st.find(v[t2])); else st.erase(st.find(v[t1])); } } }q; int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)q.v[i]=a[i]; for(int i=1;i<=n;i++)st.insert(a[i]); Q=read(); char ch[3];int x,v; while(Q--) { scanf("%s",ch+1); if(ch[1]=='A'){ if(ch[2]=='1') x=read(),v=read(),q.add(x,v); if(ch[2]=='2') x=read(),v=read(),q.heap_add(x,v); if(ch[2]=='3') x=read(),overadd+=x; } else if(ch[1]=='F'){ if(ch[2]=='1') { x=read();q.solvetag(x); printf("%d\n",q.v[x]+overadd); } if(ch[2]=='2') x=read(),printf("%d\n",q.top(x)+overadd); if(ch[2]=='3') printf("%d\n",*--st.find(inf)+overadd); } else x=read(),v=read(),q.addedge(x,v); } return 0; } |
OI 课件=>
这个左偏树为什么不记录深度啊，代码里直接交换了左右子树
这个并不是左偏树，而是斜堆
(⊙v⊙)嗯，谢谢
左偏树这样一直网上找根复杂度不会爆炸吗？
左偏树可以认为一直保持着不错的平衡，那么深度就是logn的
然而实力被卡
左偏树和斜堆的深度都是最坏O(n)的
实际最好是ON的
实测61行是没有必要的(然而时间并没有快多少）