[luogu2286] [pet house]

Title Link

thinking

A relatively naked problem of balance tree. A variable S is used to represent the current tree. When S is negative, the tree is a pet. When S is positive, the tree is a human. Then discuss each situation. If the tree is empty or the same thing (person or PET) as the tree memory. Then it can't be adopted. Just throw it into the tree. Otherwise, find a number closest to the current value from the tree, and then count it into the answer.

In the beginning, setting INF too small affected the statistical answer.

Code

#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<iostream>
#define ls TR[cur].ch[0]
#define rs TR[cur].ch[1]
using namespace std;
typedef long long ll;
const int N = 100000,mod = 1000000;
const ll INF = 1e17 + 10;
ll read() {
    ll 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 node {
    int ch[2],id;
    ll val;
}TR[N];
void rotate(int &cur,int f) {
    int son = TR[cur].ch[f];
    TR[cur].ch[f] = TR[son].ch[f ^ 1];
    TR[son].ch[f ^ 1] = cur;
    cur = son;
}
int tot;
void insert(int &cur,int val) {
    if(!cur) {
        cur = ++tot;
        TR[cur].val = val;
        TR[cur].id = rand();
        return;
    }
    int d = val > TR[cur].val;
    insert(TR[cur].ch[d],val);
    if(TR[TR[cur].ch[d]].id < TR[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
    if(!cur) return;
    if(val == TR[cur].val) {
        if(!ls || !rs) {cur = ls + rs;return;}
        int d = TR[ls].id > TR[rs].val;
        rotate(cur,d);
        del(cur,val);
    }
    del(TR[cur].ch[val > TR[cur].val],val);
}
ll pred(int cur,int val) {
    if(!cur) return -INF;
    if(val <= TR[cur].val) return pred(ls,val);
    return max(TR[cur].val,pred(rs,val));
}
ll nex(int cur,int val) {
    if(!cur) return INF;
    if(val >= TR[cur].val) return nex(rs,val);
    return min(TR[cur].val,nex(ls,val));
}
int S;
ll ans;
int main() {
    srand(time(0));
    int n = read(),rt = 0;
    while(n--) {
        int bz = read(),x = read();
        if(bz == 0) {
            if(S <= 0) insert(rt,x);
            else {
                int k1 = pred(rt,x),k2 = nex(rt,x);
                int dele = k1;
                if(k2 - x < x - k1) dele = k2;
                ans += abs(dele - x);
                ans %= mod;
                del(rt,dele);
            }
            S--;
        }
        if(bz == 1) {
            if(S >= 0) insert(rt,x);
            else {
                int k1 = pred(rt,x),k2 = nex(rt,x);
                int dele = k1;
                if(k2 - x < x - k1) dele = k2;
                ans += abs(dele - x);
                ans %= mod;
                del(rt,dele);
            }
            S++;
        }
    }
    cout<<ans<<endl;
}

a brief remark

No matter what you do, remember to do it for yourself, there is no complaint. ——Golden years

Tags: C++

Posted on Wed, 04 Dec 2019 12:02:35 -0800 by hkay1