NOIP2017D2T3 phalanx

#include <cstdio>
#include <ctime>

#include <algorithm>
#include <utility>

#define GET_CH(P, F) ((F) ? (P)->rs : (P)->ls)
#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct data {
    int step, sz;
    ll start;

    data() {}

    data(int step, int sz, ll start) : step(step), sz(sz), start(start) {}

    data(ll x) : step(0), sz(1), start(x) {}
};

struct node {
    int cnt, rnd;
    data x;
    node *ls, *rs;
};

struct que {
    node* t;

    void insert(ll x);
    ll remove(int x);
};

const int N = 300010;

node *res1, *res2;
int resy;
que q1[N], q2;

int fast_rand();
node* create(const data& x);
int get_cnt(node* p);
void ninsert(node*& p, node* q, int x);
void rotate(node*& p, bool f);
void update(node* p);
pair<data, int> nremove(node*& p, int x);
void debug_order(node* p);

int main() {
    int n, m, q, x, y;
    ll id1, id2;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
        q1[i].t = create(data(1, m - 1, (ll)(i - 1) * m));
    q2.t = create(data(m, n, 0));
    while (q--) {
        scanf("%d%d", &x, &y);
        if (y == m) {
            id2 = q2.remove(x);
            printf("%lld\n", id2);
            q2.insert(id2);
        } else {
            id1 = q1[x].remove(y);
            printf("%lld\n", id1);
            id2 = q2.remove(x);
            q1[x].insert(id2);
            q2.insert(id1);
        }
    }
    return 0;
}

inline int fast_rand() {
    static int x = time(NULL) << 4, y = time(NULL) >> 2, z = time(NULL);
    int t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;
    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;
    return z;
}

inline node* create(const data& x) {
    static node pool[N << 3];
    static node* p = pool;
    ++p;
    p->rnd = fast_rand();
    p->x = x;
    p->cnt = x.sz;
    return p;
}

inline void rotate(node*& p, bool f) {
    node *son = GET_CH(p, f), *pson = GET_CH(son, !f);
    GET_CH(p, f) = pson;
    GET_CH(son, !f) = p;
    update(p);
    p = son;
    update(p);
}

inline int get_cnt(node* p)
{ return p ? p->cnt : 0; }

inline void update(node* p)
{ p->cnt = get_cnt(p->ls) + get_cnt(p->rs) + p->x.sz; }

void que::insert(ll x)
{ ninsert(t, create(data(x)), get_cnt(t) + 1); }

ll que::remove(int x) {
    pair<data, int> p = nremove(t, x);
    data d = p.first;
    int y = p.second;
    if (res2)
        ninsert(t, res2, resy + 1);
    if (res1)
        ninsert(t, res1, resy + 1);
    ll cur = (ll)(x - y) * d.step + d.start;
    if (x - y < d.sz)
        ninsert(t, create(data(d.step, d.sz - x + y, cur)), y + 1);
    if (x - y > 1)
        ninsert(t, create(data(d.step, x - y - 1, d.start)), y + 1);
    return cur;
}

pair<data, int> nremove(node*& p, int x) {
    pair<data, int> ret;
    if (x <= get_cnt(p->ls)) {
        ret = nremove(p->ls, x);
        update(p);
        return ret;
    }
    if (get_cnt(p->ls) + p->x.sz >= x) {
        ret = make_pair(p->x, get_cnt(p->ls));
        res1 = p->ls;
        res2 = p->rs;
        p = NULL;
        resy = 0;
        return ret;
    }
    ret = nremove(p->rs, x - get_cnt(p->ls) - p->x.sz);
    resy += get_cnt(p->ls) + p->x.sz;
    ret.second += get_cnt(p->ls) + p->x.sz;
    update(p);
    return ret;
}

void ninsert(node*& p, node* q, int x) {
    if (!p) {
        p = q;
        return;
    }
    if (x <= get_cnt(p->ls) + p->x.sz) {
        ninsert(p->ls, q, x);
        update(p);
        if (p->rnd < p->ls->rnd)
            rotate(p, 0);
        return;
    }
    ninsert(p->rs, q, x - get_cnt(p->ls) - p->x.sz);
    update(p);
    if (p->rnd < p->rs->rnd)
        rotate(p, 1);
    return;
}

void debug_order(node* p) {
    if (!p)
        return;
    debug_order(p->ls);
    LOG("(%lld %d %d) ", p->x.start, p->x.step, p->x.sz);
    debug_order(p->rs);
}