[BZOJ1208] [HNOI2004]宠物收养所

本文主要是介绍[BZOJ1208] [HNOI2004]宠物收养所，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1208

题目大意

。。

题解

模板题

constmaxn=100005;
varw:array[1..2,-1..maxn,1..6]of longint;sum,root:array[1..2]of longint;i,j,k:longint;n,a,b:longint;ans,c,d:int64;
procedure print(key,a:longint);
beginif w[key,a,1]<>-1 then print(key,w[key,a,1]);write(w[key,a,6],' ');if w[key,a,2]<>-1 then print(key,w[key,a,2]);if a=root[key] then writeln;
end;procedure rotate(key,a,kind:longint);
var b,unkind:longint;
beginb:=w[key,a,3]; unkind:=kind xor 3;w[key,a,4]:=w[key,b,4]; dec(w[key,b,4],w[key,a,5]+w[key,w[key,a,kind],4]);w[key,w[key,a,unkind],3]:=b; w[key,b,kind]:=w[key,a,unkind];w[key,a,unkind]:=b; w[key,a,3]:=w[key,b,3]; w[key,b,3]:=a;if w[key,a,3]<>-1thenif w[key,w[key,a,3],1]=bthen w[key,w[key,a,3],1]:=aelse w[key,w[key,a,3],2]:=a;
end;procedure splay(key,a,goal:longint);
var b,kind,unkind:longint;
beginwhile w[key,a,3]<>goal dobeginb:=w[key,a,3]; if w[key,b,1]=a then kind:=1 else kind:=2; unkind:=kind xor 3;if w[key,b,3]=goal then rotate(key,a,kind)elseif w[key,w[key,b,3],kind]=bthen begin rotate(key,b,kind); rotate(key,a,kind); endelse begin rotate(key,a,kind); rotate(key,a,unkind); endend;if goal=-1 then root[key]:=a;
end;procedure init(key,a:longint);
var tt,fa,kind:longint;
begintt:=root[key];while tt<>-1 dobegininc(w[key,tt,4]); fa:=tt;if w[key,tt,6]=a then break;if a<w[key,tt,6]then begin tt:=w[key,tt,1]; kind:=1; endelse begin tt:=w[key,tt,2]; kind:=2; end;end;if tt<>-1then begin inc(w[key,tt,5]); splay(key,tt,-1); endelse begin inc(sum[key]); w[key,sum[key],1]:=-1; w[key,sum[key],2]:=-1; w[key,sum[key],3]:=fa; w[key,sum[key],4]:=1; w[key,sum[key],5]:=1; w[key,sum[key],6]:=a; w[key,fa,kind]:=sum[key]; splay(key,sum[key],-1); end;
end;function getmax(key,a:longint):longint;
var tt:longint;
begintt:=a;while w[key,tt,2]<>-1 dott:=w[key,tt,2];exit(tt);
end;function getmin(key,a:longint):longint;
var tt:longint;
begintt:=a;while w[key,tt,1]<>-1 dott:=w[key,tt,1];exit(tt);
end;procedure del(key,a:longint);
var tt:longint;
begintt:=root[key];while w[key,tt,6]<>a doif a<w[key,tt,6]then tt:=w[key,tt,1]else tt:=w[key,tt,2];splay(key,tt,-1);if w[key,tt,5]=1then beginsplay(key,getmax(key,w[key,root[key],1]),root[key]);w[key,w[key,root[key],1],2]:=w[key,root[key],2];root[key]:=w[key,root[key],1];w[key,root[key],3]:=-1;w[key,w[key,root[key],2],3]:=root[key];inc(w[key,root[key],4],w[key,w[key,root[key],2],4]);endelse begin dec(w[key,tt,4]); dec(w[key,tt,5]); end;
end;beginreadln(n); ans:=0;root[1]:=1; sum[1]:=1;w[1,1,1]:=-1; w[1,1,2]:=-1; w[1,1,3]:=-1; w[1,1,4]:=1; w[1,1,5]:=1; w[1,1,6]:=-1000000000;root[2]:=1; sum[2]:=1;w[2,1,1]:=-1; w[2,1,2]:=-1; w[2,1,3]:=-1; w[2,1,4]:=1; w[2,1,5]:=1; w[2,1,6]:=-1000000000;for i:=1 to n dobeginreadln(a,b);if a=0then beginif w[2,root[2],4]>=2then begininit(2,b);if w[2,root[2],5]>=3then del(2,b)else beginc:=100000000000; d:=100000000000;if w[2,w[2,root[2],1],4]>=2then c:=w[2,getmax(2,w[2,root[2],1]),6];if w[2,w[2,root[2],2],4]>=1then d:=w[2,getmin(2,w[2,root[2],2]),6];if abs(c-b)<=abs(d-b)then begin ans:=(ans+abs(c-b))mod 1000000; del(2,c); endelse begin ans:=(ans+abs(d-b))mod 1000000; del(2,d); end;del(2,b);end;endelse init(1,b);endelse beginif w[1,root[1],4]>=2then begininit(1,b);if w[1,root[1],5]>=3then del(1,b)else beginc:=100000000000; d:=100000000000;if w[1,w[1,root[1],1],4]>=2then c:=w[1,getmax(1,w[1,root[1],1]),6];if w[1,w[1,root[1],2],4]>=1then d:=w[1,getmin(1,w[1,root[1],2]),6];if abs(c-b)<=abs(d-b)then begin ans:=(ans+abs(c-b))mod 1000000; del(1,c); endelse begin ans:=(ans+abs(d-b))mod 1000000; del(1,d); end;del(1,b);end;endelse init(2,b);end;end;writeln(ans);
end.