BZOJ 1208 [HNOI2004]宠物收养所 treap

题意: 太长了不好概括自己看吧。 解析: 显然这有查找前驱后继的操作。 直接上treap就行，，复杂度也放的很宽 但是我们要记录treap里当前存的是宠物还是领养人即可。 讨论一下就是sb题了。 代码:

using namespace std;int n,size;int ans;int root;struct node{int l,r,val,siz,rnd;}tr[N];void pushup(int rt){tr[rt].siz=tr[tr[rt].l].siz+tr[tr[rt].r].siz+1;}void lturn(int &rt){int t=tr[rt].r;tr[rt].r=tr[t].l;tr[t].l=rt;tr[t].siz=tr[rt].siz;pushup(rt);rt=t;}void rturn(int &rt){int t=tr[rt].l;tr[rt].l=tr[t].r;tr[t].r=rt;tr[t].siz=tr[rt].siz;pushup(rt);rt=t;}void insert(int &rt,int v){if(!rt){rt=++size;tr[rt].l=tr[rt].r=0;tr[rt].siz=1,tr[rt].rnd=rand();tr[rt].val=v;return;}tr[rt].siz++;if(v<=tr[rt].val){insert(tr[rt].l,v);if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt);}else{insert(tr[rt].r,v);if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt);}}void del(int &rt,int v){tr[rt].siz–;if(tr[rt].val==v){if(tr[rt].l==0||tr[rt].r==0){rt=tr[rt].l+tr[rt].r;return;}if(tr[tr[rt].l].rnd<tr[tr[rt].r].rnd)rturn(rt),del(rt,v);else lturn(rt),del(rt,v);}else if(v<tr[rt].val)del(tr[rt].l,v);else del(tr[rt].r,v);}int ask_pre(int rt,int v){if(!rt)return 0;if(v<=tr[rt].val)return ask_pre(tr[rt].l,v);else{int ret=ask_pre(tr[rt].r,v);return max(tr[rt].val,ret);}}int ask_sub(int rt,int v){if(!rt)return INF;if(v>=tr[rt].val)return ask_sub(tr[rt].r,v);else{int ret=ask_sub(tr[rt].l,v);return min(tr[rt].val,ret);}}int main(){scanf(“%d”,&n);int cnt=0;for(int i=1;i<=n;i++){int x,y;scanf(“%d%d”,&x,&y);if(!cnt){if(x)cnt–,insert(root,y);else cnt++,insert(root,y);}else if(cnt>0){if(x){cnt–;int tmp1=ask_pre(root,y),tmp2=ask_sub(root,y);if(!tmp1){ans=(ans+abs(tmp2-y))%mod,del(root,tmp2);continue;}if(tmp2==INF){ans=(ans+abs(tmp1-y))%mod,del(root,tmp1);continue;}if(y-tmp1<=tmp2-y){ans=(ans+abs(y-tmp1))%mod;del(root,tmp1);}else{ans=(ans+abs(tmp2-y))%mod;del(root,tmp2);}}else cnt++,insert(root,y);}else{if(x)cnt–,insert(root,y);else{cnt++;int tmp1=ask_pre(root,y),tmp2=ask_sub(root,y);if(!tmp1){ans=(ans+abs(tmp2-y))%mod,del(root,tmp2);continue;}if(tmp2==INF){ans=(ans+abs(tmp1-y))%mod,del(root,tmp1);continue;}if(y-tmp1<=tmp2-y){ans=(ans+abs(y-tmp1))%mod;del(root,tmp1);}else{ans=(ans+abs(tmp2-y))%mod;del(root,tmp2);}}}}printf(“%d\n”,ans);}

那么威尼斯就是一艘轻盈和流动的舟船，