题意简单明了，两种数，如果加入一个数的时候有另一种数还存在，那就取出另一种数中与这个数差值的绝对值最小的将其删除（多个则取较小），并对答案产生它们差值的绝对值的贡献，如果没有另一种数存在，那就先将这个数存下
平衡树裸题，直接两个平衡树维护就ok了，一个也能维护，稍麻烦一点
线段树好像也可做，我没写，应该不难
我写的是Splay，把Splay用结构体封装好，开两个Splay异常好写
下面放代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 80005
#define mo 1000000
using namespace std;
inline ll read(){
ll a=0;int f=0;char p=gc();
while(!isdigit(p)){f|=p=='-';p=gc();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
return f?-a:a;
}int n;ll ans;
struct ahaha{ //Splay的结构体
struct ahaha1{
int sz,cnt,ch[2];ll v;
}t[maxn];int rt,tot,f[maxn];
#define lc t[i].ch[0]
#define rc t[i].ch[1]
inline int get(int i){return i==t[f[i]].ch[1];}
inline void update(int i){
t[i].sz=t[i].cnt+t[lc].sz+t[rc].sz;
}
inline void del(int i){
t[i].v=t[i].sz=t[i].cnt=f[i]=0;
}
inline int newnode(ll v){
int i=++tot;
t[i].sz=t[i].cnt=1;t[i].v=v;
return i;
}
inline void rotate(int x){
int y=f[x],z=f[y],k=get(x);
f[x]=z;f[t[x].ch[k^1]]=y;f[y]=x;
if(z)t[z].ch[y==t[z].ch[1]]=x;
t[y].ch[k]=t[x].ch[k^1];t[x].ch[k^1]=y;
update(y);update(x);
}
void Splay(int x){
for(int y=f[x];f[x];rotate(x),y=f[x]){
if(f[y])rotate(get(x)==get(y)?y:x);
rt=x;
}
}
void insert(ll v){
int i=rt,k;
if(!rt){rt=newnode(v);return;}
while(1){
k=v>t[i].v;
if(v==t[i].v){
++t[i].sz;++t[i].cnt;
Splay(i);return;
}
if(!t[i].ch[k]){
t[i].ch[k]=newnode(v);f[t[i].ch[k]]=i;
Splay(t[i].ch[k]);return;
}
i=t[i].ch[k];
}
}
void find(ll v){
int i=rt;
while(1){
if(v<t[i].v){
i=lc;
if(!i)return;
}
else{
if(!rc||v==t[i].v){
Splay(i);return ;
}
i=rc;
}
}
}
inline void earase(ll v){
find(v);int old=rt,i=rt;
if(t[rt].cnt!=1){--t[rt].cnt;return;}
if(t[rt].sz==1){del(rt);rt=0;return;}
if(!lc){rt=rc;f[rt]=0;del(old);return;}
if(!rc){rt=lc;f[rt]=0;del(old);return;}
i=lc;while(rc)i=rc;Splay(i);
t[rt].ch[1]=t[old].ch[1];f[t[rt].ch[1]]=rt;
del(old);update(rt);
}
ll pre(ll v){
int i=rt;ll maxa=-1;
while(i){
if(t[i].v==v)return v;
if(t[i].v<v){
maxa=max(maxa,t[i].v);
i=rc;
}
else i=lc;
}
return maxa;
}
ll next(ll v){
int i=rt;ll mina=2147483649;
while(i){
if(t[i].v==v)return v;
if(t[i].v>v){
mina=min(mina,t[i].v);
i=lc;
}
else i=rc;
}
return mina;
}
}t1,t2;
inline void solve_1(){
ll v=read();
if(!t2.rt) //如果没有另一种数，先存起来
t1.insert(v);
else{
ll pre=t2.pre(v),next=t2.next(v); //查询前后缀，没有前缀则前缀为-1，没有后缀则后缀为2147483649
if(pre==-1){
ans=(ans+next-v)%mo;
t2.earase(next);return;
}
if(next==2147483649){
ans=(ans+v-pre)%mo;
t2.earase(pre);return;
}
if(v-pre<=next-v){ //按照题意取较小，然后删除就可以了
ans=(ans+v-pre)%mo;
t2.earase(pre);return;
}
else{
ans=(ans+next-v)%mo;
t2.earase(next);return;
}
}
}
inline void solve_2(){ //同上
ll v=read();
if(!t1.rt)
t2.insert(v);
else{
ll pre=t1.pre(v),next=t1.next(v);
if(pre==-1){
ans=(ans+next-v)%mo;
t1.earase(next);return;
}
if(next==2147483649){
ans=(ans+v-pre)%mo;
t1.earase(pre);return;
}
if(v-pre<=next-v){
ans=(ans+v-pre)%mo;
t1.earase(pre);return;
}
else{
ans=(ans+next-v)%mo;
t1.earase(next);return;
}
}
}
int main(){
n=read();
while(n--){
int zz=read();
switch(zz){
case 0:solve_1();break;
case 1:solve_2();break;
}
}
printf("%lld
",ans);
return 0;
}
不要抄代码哦