哎，一道裸splay的題目，網(wǎng)上竟然木有解題報(bào)告。我第一次寫(xiě)splay，犯了很多很多NC的錯(cuò)誤。。調(diào)了有一個(gè)下午，最后寫(xiě)了個(gè)測(cè)試模塊+生成了隨機(jī)數(shù)據(jù)，才發(fā)現(xiàn)錯(cuò)誤。
說(shuō)說(shuō)我的失誤吧。。
1、首先zig zag實(shí)現(xiàn)的時(shí)候一定要配對(duì)，不能亂，加個(gè)兒子節(jié)點(diǎn)就要把兒子節(jié)點(diǎn)的父親節(jié)點(diǎn)同時(shí)初始化好
2、新加入節(jié)點(diǎn)的size域及其祖先的size域名不用調(diào)整，會(huì)在splay過(guò)程中自動(dòng)修正完畢
3、千萬(wàn)別要試圖將一顆子樹(shù)的根節(jié)點(diǎn)插入到另外一棵樹(shù)中，以為將兩棵樹(shù)給合并住了。。BST的定義是左子樹(shù)中的所有節(jié)點(diǎn)嚴(yán)格小于根節(jié)點(diǎn)，而不僅僅是左兒子節(jié)點(diǎn)，右子樹(shù)亦同。
然后針對(duì)本題說(shuō)說(shuō)，要倒過(guò)來(lái)操作，不斷的將連通分支合并，相當(dāng)于合并兩顆splay，沒(méi)有快速的方法，把size小的子樹(shù)里的節(jié)點(diǎn)一個(gè)一個(gè)塞到大樹(shù)中。記得這個(gè)思想MS是09年一場(chǎng)網(wǎng)絡(luò)賽里有過(guò)的，不過(guò)那題的詢(xún)問(wèn)很簡(jiǎn)單，恩
代碼
# include <cstdio>
# include <utility>
# include <functional>
# include <cstdlib>
# include <vector>
using namespace std;
struct node
{
int sz;
pair<int,int> val;
node *l,*r,*pre;
void clear()
{
l=r=pre=NULL;
}
}buff[20005];
inline bool cmp(const pair<int,int> &a,const pair<int,int> &b)
{
if(a.first!=b.first) return a.first<b.first;
else return a.second<b.second;
}
inline void update(node *pos)
{
pos->sz=(pos->l?(pos->l->sz):0)+(pos->r?(pos->r->sz):0)+1;
}
void zig(node *pos)
{
node *gf=pos->pre->pre,*f=pos->pre;
(f->l)=(pos->r);
if(pos->r) (pos->r->pre)=f;
update(f);
(pos->r)=f;
(f->pre)=pos;
(pos->pre)=gf;
if(gf&&(gf->l)==f) gf->l=pos;
else if(gf&&(gf->r)==f) (gf->r)=pos;
}
void zag(node *pos)
{
node *gf=pos->pre->pre,*f=pos->pre;
(f->r)=(pos->l);
if(pos->l) (pos->l->pre)=f;
update(f);
f->pre=pos;
pos->l=f;
pos->pre=gf;
if(gf&&gf->l==f) (gf->l)=pos;
else if(gf&&gf->r==f) (gf->r)=pos;
}
void spaly(node *pos)
{
while(pos->pre)
{
if(pos->pre->pre==NULL)
if(pos==(pos->pre->l)) zig(pos);
else zag(pos);
else
{
node *t=pos->pre->pre;
if(t->l&&pos==(t->l->l))
zig(pos->pre),zig(pos);
else if(t->r&&pos==(t->r->r))
zag(pos->pre),zag(pos);
else if(t->l&&pos==(t->l->r))
zag(pos),zig(pos);
else
{
zig(pos);
zag(pos);
}
}
}
update(pos);
}
void sub_insert(node *p1,node *p2)
{
node *pre;
spaly(p2);
while(p2)
{
pre=p2;
if(cmp(p1->val,p2->val)) p2=p2->l;
else p2=p2->r;
}
if(cmp(p1->val,pre->val))
pre->l=p1,p1->pre=pre,spaly(p1);
else
pre->r=p1,p1->pre=pre,spaly(p1);
}
void ins(node *p1,node *p2)
{
if(p1->l) ins(p1->l,p2);
if(p1->r) ins(p1->r,p2);
p1->l=p1->r=p1->pre=NULL;
p1->sz=1;
sub_insert(p1,p2);
}
void insert(node *p1,node *p2)
{
spaly(p1),spaly(p2);
if(p1->sz<p2->sz)
ins(p1,p2);
else ins(p2,p1);
}
int select(int pos,int k)
{
node *p=buff+pos;
spaly(p);
if(k>(p->sz)||k<1) return 0;
else k=(p->sz)+1-k;
int co=0;
while(true)
{
if(co++>500000) exit(0);
if((p->l?p->l->sz:0)>=k) p=p->l;
else if((p->l?p->l->sz:0)+1==k)
break;
else k-=(p->l?(p->l->sz):0)+1,p=p->r;
}
spaly(p);
return p->val.first;
}
void change(pair<int,int> val)
{
node *p=buff+val.second;
spaly(p);
p->val=val;
if(p->l&&p->r)
{
node *t1=(p->l),*t2=(p->r);
(t1->pre)=(t2->pre)=(p->l)=(p->r)=NULL;
while(t1->r) t1=t1->r;
spaly(t1);
(t1->r)=t2;
(t2->pre)=t1;
spaly(t2);
insert(t2,p);
}
else if(p->l)
{
node *t=p->l;
(p->l)=(t->pre)=NULL;
insert(t,p);
}
else if(p->r)
{
node *t=p->r;
(p->r)=(t->pre)=NULL;
insert(t,p);
}
}
int n,m;
pair<int,int> edge[60005];
bool used[60005];
int father[20005];
pair<int,pair<int,int> > ask[1000005];
int co=0;
int find(int pos)
{
if(father[pos]==pos) return pos;
else return father[pos]=find(father[pos]);
}
int main()
{
int test=1;
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
for(int i=1;i<=n;i++)
{
buff[i].clear();
buff[i].val.second=i;
father[i]=i;
scanf("%d",&buff[i].val.first);
}
for(int i=1;i<=m;i++)
{
used[i]=true;
scanf("%d%d",&edge[i].first,&edge[i].second);
}
char type[5];
int number=0;
co=0;
while(scanf("%s",type)&&*type!='E')
{
pair<int,pair<int,int> > tmp;
switch(*type)
{
case 'D':
tmp.first=2;
scanf("%d",&tmp.second.first);
used[tmp.second.first]=false;
break;
case 'C':
{
tmp.first=1;
scanf("%d%d",&tmp.second.second,&tmp.second.first);
int tt=buff[tmp.second.second].val.first;
buff[tmp.second.second].val=tmp.second;
tmp.second.first=tt;
break;
}
case 'Q':
tmp.first=0;
number++;
scanf("%d%d",&tmp.second.first,&tmp.second.second);
break;
};
ask[co++]=tmp;
}
for(int i=1;i<=m;i++)
if(used[i]&&find(edge[i].first)!=find(edge[i].second))
insert(buff+edge[i].first,buff+edge[i].second),father[find(edge[i].first)]=find(edge[i].second);
double total=0;
for(int i=co-1;i>=0;i--)
{
switch(ask[i].first)
{
case 0:
total+=select(ask[i].second.first,ask[i].second.second);
break;
case 1:
change(ask[i].second);
break;
case 2:
//break;
if(find(edge[ask[i].second.first].first)!=find(edge[ask[i].second.first].second))
insert(buff+edge[ask[i].second.first].first,buff+edge[ask[i].second.first].second),
father[find(edge[ask[i].second.first].first)]=find(edge[ask[i].second.first].second);
break;
};
}
printf("Case %d: %.6f\n",test++,number?total/number:0);
}
return 0;
}