题目传送门
做法：维护一棵Splay，如果现在来的是人，且还有宠物，那就找前驱和后缀与之差值的较小值，否则就加到树上。如果是宠物则同理。（这里的前驱后缀可以等于对应的值）
Code:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
//Mystery_Sky
//
#define M 1000100
#define INF 0x3f3f3f3f
#define Mod 1000000
inline int read()
{
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct Splay{
int cnt, size;
int val;
int fa, son[2];
}t[M];
int root, tot;
int n, opt, x;
int peo, ani, ans;
inline void push_up(int x)
{
if(x) {
t[x].size = t[x].cnt;
if(t[x].son[0]) t[x].size += t[t[x].son[0]].size;
if(t[x].son[1]) t[x].size += t[t[x].son[1]].size;
}
}
inline bool check(int x) {return t[t[x].fa].son[1] == x;}
inline void Clear(int x) {t[x].val = t[x].size = t[x].cnt = t[x].fa = t[x].son[0] = t[x].son[1] = 0;}
inline int New(int x, int fa)
{
t[++tot].val = x;
t[tot].size = t[tot].cnt = 1;
t[tot].son[0] = t[tot].son[1] = 0;
t[tot].fa = fa;
return tot;
}
inline void Rotate(int x)
{
int y = t[x].fa, z = t[y].fa, k = check(x), w = t[x].son[k^1];
t[y].son[k] = w; t[t[y].son[k]].fa = y;
t[y].fa = x;
t[x].son[k^1] = y;
t[x].fa = z;
if(z) t[z].son[t[z].son[1] == y] = x;
push_up(y);
push_up(x);
}
inline void splay(int x)//Splay->一直Rotate到根节点
{
for(int y; (y = t[x].fa); Rotate(x))
if(t[y].fa) Rotate((check(x) == check(y) ? y : x));
root = x;
}
inline void Insert(int x)
{
if(!root) {
root = New(x, 0);
return;
}
int now = root, y = 0;
while(1) {
//printf("1
");
if(t[now].val == x) {
t[now].cnt++;
push_up(now), push_up(y);
splay(now);
break;
}
y = now;
now = t[now].son[t[now].val < x];
if(!now) {
New(x, y);
t[y].son[t[y].val < x] = tot;
push_up(y);
splay(tot);
return;
}
}
}
inline int query_rank(int x)
{
int ans = 0, now = root;
while(1) {
if(x < t[now].val) now = t[now].son[0];
else {
ans += t[t[now].son[0]].size;
if(x == t[now].val) {
splay(now);
return ans + 1;
}
ans += t[now].cnt;
now = t[now].son[1];
}
}
}
inline int query_val(int rank)
{
int now = root;
while(1) {
if(t[now].son[0] && rank <= t[t[now].son[0]].size) now = t[now].son[0];
else {
int temp = t[t[now].son[0]].size + t[now].cnt;
if(rank <= temp) return t[now].val;
rank -= temp;
now = t[now].son[1];
}
}
}
inline int Pre()
{
int now = t[root].son[0];
while(t[now].son[1]) now = t[now].son[1];
return now;
}
inline int Succ()
{
int now = t[root].son[1];
while(t[now].son[0]) now = t[now].son[0];
return now;
}
inline void Delete(int x)
{
int q = query_rank(x);
if(t[root].cnt > 1) {
t[root].cnt--;
push_up(root);
return;
}
if(!t[root].son[0] && !t[root].son[1]) {
Clear(root);
root = 0;
return;
}
if(!t[root].son[0]) {
int y = root;
root = t[y].son[1];
t[root].fa = 0;
Clear(y);
return;
}
else if(!t[root].son[1]) {
int y = root;
root = t[y].son[0];
t[root].fa = 0;
Clear(y);
return;
}
int lc = Pre(), y = root;
splay(lc);
t[t[y].son[1]].fa = root;
t[root].son[1] = t[y].son[1];
Clear(y);
push_up(root);
return;
}
int main() {
n = read();
Insert(INF), Insert(-INF);
for(int i = 1; i <= n; i++) {
opt = read(), x = read();
if(opt == 0) {
if(peo > 0) {
Insert(x);
if(t[root].cnt > 1) {
Delete(x);
}
else {
int pre = Pre();
int nxt = Succ();
int del_1 = abs(x - t[pre].val);
int del_2 = abs(t[nxt].val - x);
if(del_1 <= del_2) {
Delete(t[pre].val);
ans += del_1;
ans %= Mod;
}
else {
Delete(t[nxt].val);
ans += del_2;
ans %= Mod;
}
}
Delete(x);
peo--;
}
else Insert(x), ani++;
}
else {
if(ani > 0) {
Insert(x);
if(t[root].cnt > 1) {
Delete(x);
}
else {
int pre = Pre();
int nxt = Succ();
int del_1 = abs(x - t[pre].val);
int del_2 = abs(t[nxt].val - x);
if(del_1 <= del_2) {
Delete(t[pre].val);
ans += del_1;
ans %= Mod;
}
else {
Delete(t[nxt].val);
ans += del_2;
ans %= Mod;
}
}
Delete(x);
ani--;
}
else Insert(x), peo++;
}
}
printf("%d
", ans);
return 0;
}