题目描述 https://loj.ac/problem/10144
思路
代码
- #include
- #include
- #include
- #include
- 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 %d\n", 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));
- // write(n), putchar('\n');
- for (int i = 1, a, b, p, q, j; i <= n; ++i) {
- a = read(), b =read();
- // printf("%d %d\n", a, b);
- 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;
- }
宠物收养所
来源: http://www.bubuko.com/infodetail-3203747.html