#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
const int MAX = 8e4 + 5, mod = 1e6;
int n, m, inf = 0x3f3f3f3f;
int ans, rt, tot;
bool flag;
struct Node {
int lc, rc, key, pri, cnt, size;
#define lc(x) t[x].lc
#define rc(x) t[x].rc
#define key(x) t[x].key
#define pri(x) t[x].pri
#define cnt(x) t[x].cnt
#define size(x) t[x].size
} t[MAX];
inline int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * f;
}
void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
void update(int r) { size(r) = size(lc(r)) + size(rc(r)) + cnt(r); }
void zig(int &r) {
int s = lc(r);
lc(r) = rc(s);
rc(s) = r;
size(s) = size(r);
update(r);
r = s;
}
void zag(int &r) {
int s = rc(r);
rc(r) = lc(s);
lc(s) = r;
size(s) = size(r);
update(r);
r = s;
}
void insert(int &r, int k) {
if (!r) {
r = ++tot, key(r) = k, pri(r) = rand();
cnt(r) = size(r) = 1, lc(r) = rc(r) = 0;
return;
} else ++size(r);
if (k == key(r)) ++cnt(r);
else if (k < key(r)) {
insert(lc(r), k);
if (pri(lc(r)) < pri(r)) zig(r);
} else {
insert(rc(r), k);
if (pri(rc(r)) < pri(r)) zag(r);
}
}
void del(int &r, int k) {
if (key(r) == k) {
if (cnt(r) >= 2) --cnt(r), --size(r);
else if(!lc(r) || !rc(r)) r = lc(r) + rc(r);
else if(pri(lc(r)) < pri(rc(r))) zig(r), del(r, k);
else zag(r), del(r, k);
return;
}
--size(r);
if (k < key(r)) del(lc(r), k);
else del(rc(r), k);
}
int queryPre(int k) {
int r = rt, res = inf;
while (r) {
if (key(r) <= k) res = key(r), r = rc(r);
else r = lc(r);
}
return res;
}
int queryNxt(int k) {
int r = rt, res = inf;
while (r) {
if (k < key(r)) res = key(r), r = lc(r);
else r = rc(r);
}
return res;
}
int queryKth(int k) {
int r = rt, res = inf;
while (r) {
if (size(lc(r)) < k && size(lc(r)) + cnt(r) >= k) return key(r);
else if(size(lc(r)) >= k) r = lc(r);
else k -= size(lc(r)) + cnt(r), r = rc(r);
}
return res;
}
int queryRand(int k) {
int r = rt, res = 0;
while (r) {
if (k == key(r)) return size(lc(r)) + cnt(r) + 1;
else if (k < key(r)) r = lc(r);
else res += size(lc(r)) + cnt(r), r = rc(r);
}
return res;
}
void show(int x) {
printf("%d %d %d %dn", lc(x), rc(x), key(x), pri(x));
if (lc(x) != 0) show(lc(x));
if (rc(x) != 0) show(rc(x));
}
int main() {
n = read();
srand(time(NULL));
for (int i = 1, a, b, p, q, j; i <= n; ++i) {
a = read(), b =read();
if (a == 0) {
if (flag) insert(rt, b);
else {
if (!flag && rt == 0) insert(rt, b), flag = true;
else {
j = inf;
p = queryPre(b), q = queryNxt(b);
if (p != inf) j = b - p;
if (q != inf && q - b < j) j = q - b;
if (j != inf) ans = ((long long)ans + j % mod) % mod;
if (p != inf && j == b - p) del(rt, p);
else if(q != inf && j == q - b) del(rt, q);
}
}
} else if (a == 1) {
if (!flag) insert(rt, b);
else {
if (flag && rt == 0) insert(rt, b), flag = false;
else {
j = inf;
p = queryPre(b), q = queryNxt(b);
if (p != inf) j = b - p;
if (q != inf && q - b < j) j = q - b;
if (j != inf) ans = ((long long)ans + j % mod) % mod;
if (p != inf && j == b - p) del(rt, p);
else if(q != inf && j == q - b) del(rt, q);
}
}
}
}
write(ans);
return 0;
}
转载于:https://www.cnblogs.com/liuzz-20180701/p/11546100.html
