更新原因：贴错代码
为了您现在及以后获得更好的阅读体验强行安利blog
思路和yybyyb差不多，但还是有区别的，
没有思路雷同 宠物和主人之间转换巧妙利用异或原理，缩短代码量
yybyyb大佬维护一颗splay，可我只会treap，精华主要还是在主程序啦
#include<bits/stdc++.h>
using namespace std;
int read() {
int x=1,ans=0;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ans=ans*10+ch-48;ch=getchar();}
return x*ans;
}
const int N=80008;
struct Node {
int l,r,val,pri,cnt;
}t[N];
int n,rt,top,ans;
inline void zig(int& k) {int y=t[k].l;t[k].l=t[y].r;t[y].r=k;k=y;}//右旋
inline void zag(int& k) {int y=t[k].r;t[k].r=t[y].l;t[y].l=k;k=y;}//左旋
void add(int& k,int val) {//添加
if(!k) { k=++top; t[k].val=val; t[k].pri=rand(); t[k].l=t[k].r=0; t[k].cnt=1; return; }
if(t[k].val==val) {t[k].cnt++; return; }
if(val<t[k].val) {
add(t[k].l,val);
if(t[t[k].l].pri<t[k].pri) zig(k);
}
else {
add(t[k].r,val);
if(t[t[k].r].pri<t[k].pri) zag(k);
}
}
void rem(int& k,const int& val) {//删除(remove)
if(t[k].val==val) {
if(t[k].cnt>1) t[k].cnt--;
else if(!t[k].l||!t[k].r) k=t[k].l+t[k].r;
else if(t[t[k].l].pri<t[t[k].r].pri) zig(k),rem(k,val);
else zag(k),rem(k,val);
return;
}
if(val<t[k].val) rem(t[k].l,val);
else rem(t[k].r,val);
}
inline int qpre(const int& val) {//寻找比小于等于val中最大的数
int k=rt,res=0;
while(k) {
if(t[k].val==val) return val;
if(t[k].val<val) res=t[k].val,k=t[k].r;
else k=t[k].l;
}
return res;
}
inline int qnxt(const int& val) {//寻找大于等于val中最小的数
int k=rt,res=0;
while(k) {
if(t[k].val==val) return val;
if(t[k].val>val) res=t[k].val,k=t[k].l;
else k=t[k].r;
}
return res;
}
inline int ask(const int& val) {//利用上面两个函数猥琐得出答案
int l=qpre(val),r=qnxt(val);
if(l==0) return r;
if(r==0) return l;
if(l==val||r==val) return val;
if(val-l==r-val) return l;
if(val-l<r-val) return l;
return r;
}
int main() {
n=read();
bool now=0;
while(n--) {
bool x=read();int val=read();
if(x^now) add(rt,val);//if判断巧妙异或
else {
if(!rt) { now^=1; add(rt,val); continue;}//异或偷懒
int res=ask(val);
ans=(ans+abs(res-val))%1000000;//千万不要忘记取模！！！我经常犯这个错误！
rem(rt,res);
}
}
printf("%dn",ans); //华丽output
return 0;
}
