UVALive 5031 Graph and Queries (Treap)

时间:2024-04-04 12:34:15

删除边的操作不容易实现,那么就先离线然后逆序来做。

逆序就变成了合并,用并存集判断连通,用Treap树来维护一个连通分量里的名次。

Treap = Tree + Heap。用一个随机的优先级来平衡搜索树。

名次查询需要维护树的结点数量,假设当前在u点,u的左子树有n个结点,那么u的就是以u为根的树上第n+1小的。

如果查询的不是n+1,那么根据结点数量判断一下在哪颗子树上,然后去查询。

树的合并就将结点数少的树上的点往结点数多的树里面插,然后删掉结点少的树。

修改权值就分解成删除点和插点。

写的时候要分清哪些指针本身是要修改的,要用引用。哪些指针可能是NULL,不应该访问。

试过将null设定为常指针,快了25ms,用内存池模拟new 分配内存,快了50ms,但是结点数要开到maxn的两倍,(在这RE了很多次)。

如果new 的效率足够的话还是不要用内存池了,搞不好就RE了。

这题刷新了挂题发数,不过总算是会写Treap了。

#include<bits/stdc++.h>
using namespace std; struct Node
{
Node *ch[];
int v,r,s;
void maintain()
{
s = +ch[]->s+ch[]->s;
}
}; Node *const null = new Node(); inline Node *newNode(int x)
{
Node* t = new Node();
t->ch[]=t->ch[] = null;
t->s = ; t->r = rand(); t->v = x;
return t;
} void rot(Node*&o,int d)
{
Node*t = o->ch[d^]; o->ch[d^] = t->ch[d]; t->ch[d] = o;
o->maintain(); t->maintain();
o = t;
} void inst(Node*&o,int x)
{
if(o==null){
o = newNode(x);
}else {
int d = x > o->v ? :;
inst(o->ch[d],x);
if(o->ch[d]->r > o->r) rot(o,d^);
}
o->maintain();
} inline int tcmp(int a,int b)
{
if(a == b) return -;
return a > b? : ;
} void rmov(Node*&o,int x)
{
//if(o == null) return;
int d = tcmp(o->v,x);
if(~d){
rmov(o->ch[d],x);
}else {
Node*lc = o->ch[],*rc = o->ch[];
if(lc!=null &&rc != null){
int d2 = lc->r > rc->r? :;
rot(o,d2); rmov(o->ch[d2],x);
}else {
Node *t = o;
if(lc == null) o = rc;
else o = lc;
delete t;
}
}
if(o != null) o->maintain();
} const int maxc = 5e5+, maxn = 2e4+, maxm = 6e4+;
struct Cmd
{
char tp;
int x,p;
}cmd[maxc]; int n,m,wei[maxn],fro[maxm],to[maxm],rmvd[maxm]; int pa[maxn];
int fdst(int x){ return x==pa[x]?x:pa[x]=fdst(pa[x]); } Node *rt[maxn]; //k>0
int kth(Node*o,int k)
{
if(o == null || k <= || k > o->s) return ; //
int s = o->ch[]->s;
if(k == s+) return o->v;
if(k <= s) return kth(o->ch[],k);
return kth(o->ch[],k-s-);
} void mgto(Node*&u,Node*&v)
{
if(u->ch[] != null) mgto(u->ch[],v);
if(u->ch[] != null) mgto(u->ch[],v);
inst(v,u->v);
delete u;
u = null;
} void rmvTree(Node*&o)
{
if(o->ch[] != null) rmvTree(o->ch[]);
if(o->ch[] != null) rmvTree(o->ch[]);
delete o;
o = null;
} inline void addEdge(int i)
{
int u = fdst(fro[i]), v = fdst(to[i]);
if(u != v){
if(rt[u]->s < rt[v]->s){
pa[u] = v;
mgto(rt[u],rt[v]);
}else {
pa[v] = u;
mgto(rt[v],rt[u]);
}
}
} int qct;
long long qtot; inline void qry(int x,int p)
{
if(p>){
qtot+=kth(rt[fdst(x)],p);
}
qct++;
} inline void chgw(int x,int p)
{
int u = fdst(x);
rmov(rt[u],wei[x]);
inst(rt[u],wei[x]=p);
} int main()
{
//freopen("in.txt","r",stdin);
int kas = ;
null->s = ; null->ch[] = null->ch[] = null;
fill(rt,rt+maxn,null);
while(~scanf("%d%d",&n,&m)&&n){
for(int i = ; i <= n; i++) scanf("%d",wei+i);
for(int i = ; i <= m; i++) scanf("%d%d",fro+i,to+i);
kas++; int c = ;
while(true){
char tp; int x,p;
scanf(" %c",&tp);
if(tp == 'E') break;
scanf("%d",&x);
if(tp == 'D') rmvd[x] = kas;
else if(tp == 'Q') scanf("%d",&p);
else if(tp == 'C') {
p = wei[x];
scanf("%d",wei+x);
}
cmd[c++] = {tp,x,p};
} for(int i = ; i <= n; i++){
pa[i] = i;
if(rt[i] != null) rmvTree(rt[i]);
rt[i] = newNode(wei[i]);
}
for(int i = ; i <= m; i++) if(rmvd[i] != kas) addEdge(i); qtot = qct = ;
while(c--){
Cmd &cq = cmd[c];
if(cq.tp == 'Q') qry(cq.x,cq.p);
else if(cq.tp == 'C') chgw(cq.x,cq.p);
else if(cq.tp == 'D')addEdge(cq.x);
}
printf("Case %d: %.6lf\n",kas,qtot/(double)qct);
}
return ;
}