题目思路:splay,主要用到找某个数(不一定在树中)的前驱,后继,和插入,删除。
#include<stdio.h> #include<stdlib.h> #include<string.h> #define mod 1000000 using namespace std; #define inf 0x3f3f3f3f #define Max 84000 int max(int a,int b) { return a>b?a:b; } int min(int a,int b) { return a<b?a:b; } int p[Max],ch[Max][2],top1,ans,val[Max],root; int num[2]; void debug(); void newnode(int &x,int fa,int data) { x=++top1; p[x]=fa; val[x]=data; ch[x][0]=ch[x][1]=0; } void init() { top1=0;ans=0; newnode(root,0,-inf); newnode(ch[root][1],root,inf); num[0]=num[1]=0; } void rot(int x,int f)//旋转 { int y=p[x]; ch[y][!f]=ch[x][f]; p[ch[x][f]]=y; if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x; p[x]=p[y]; ch[x][f]=y; p[y]=x; if(p[x]==0) root=x; } void splay(int x,int goal) { while(p[x]!=goal)//旋转直到指定位置 { if(p[p[x]]==goal) { rot(x,ch[p[x]][0]==x); } else//根据情况选择旋转方式 { int y=p[x]; int f=(ch[p[y]][0]==y); if(ch[y][f]==x) { rot(x,!f),rot(x,f); } else { rot(y,f),rot(x,f); } } } if(!goal) root=x; } int pre(int a) { int x=root; int tmp; while(x) { if(val[x]==a) return x; if(val[x]<a) tmp=x; x=ch[x][val[x]<a]; } return tmp; } int suc(int a) { int x=root; int tmp; while(x) { if(val[x]==a) return x; if(val[x]>a) tmp=x;//为什么不用加v[x]<v[tmp],因为当遇到一个大于a的数时会一直向左走直到遇到小于a的数,而从遇到大于a的数后,数值都会比那个数小,也就是说后面找到的数一定越来越小。所以不用加,加的情况是找不到后继且原来建树没有加两个极值点。 x=ch[x][val[x]<a]; } return tmp; } void ins(int a) { int x=root; while(ch[x][val[x]<a]) x=ch[x][val[x]<a];//找到加点的位置,即前驱和后继的这前。 newnode(ch[x][val[x]<a],x,a);//将结点插入 splay(ch[x][val[x]<a],0); } void del(int x) { splay(x,0); int tmp=ch[root][1]; while(ch[tmp][0]) tmp=ch[tmp][0];//找根结点的后继 splay(tmp,root);//将后继伸展到根下面,这时成为了根结点的右儿子。 ch[tmp][0]=ch[root][0];//将后继作为根结点,根结点删除 p[ch[root][0]]=tmp; p[tmp]=0; root=tmp; } int main() { int n,ty,a; while(scanf("%d",&n)!=EOF) { init(); while(n--) { scanf("%d%d",&ty,&a); if(num[!ty]) { int tmp1=pre(a),tmp2=suc(a); if(a-val[tmp1]<=val[tmp2]-a) { ans+=a-val[tmp1]; ans%=mod; del(tmp1); num[!ty]--; } else { ans+=val[tmp2]-a; del(tmp2); ans%=mod; num[!ty]--; } } else { num[ty]++; ins(a); } } printf("%d\n",ans); } }