NOIP2017 phalanx2 FENWICK

#include <cstdio>

#include <vector>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Phalanx {
    struct Node {
        int sum;
        bool f;
        Node *prt, *l, *r;
    };

    Node* fw;
    int len, dif;
    ll fst;
    vector<ll> ins;

    static Node* create(int sum) {
        static Node pool[300010 * 80];
        static Node* p = pool;
        p->f = true;
        p->sum = sum;
        return p++;
    }

    int lowBit(int k) {
        return k & -k;
    }

    ll rmv(int k) {
        int id = 0;
        Node* p = fw;
        for (int l = 20; l >= 0; --l) {
            if (p->sum == k && p->f) {
                id |= 1 << l;
                break;
            }
            if (p->sum < k) {
                id |= 1 << l;
                k -= p->sum;
                if (!p->r) {
                    p->r = create(1 << (l - 1));
                    p->r->prt = p->prt;
                }
                p = p->r;
            } else {
                if (!p->l) {
                    p->l = create(1 << (l - 1));
                    p->l->prt = p;
                }
                p = p->l;
            }
        }
        p->f = false;
        while (p) {
            --p->sum;
            p = p->prt;
        }
        LOG("[LOG] %d %d\n", id, len);
        if (id <= len)
            return fst + id * (ll)dif;
        return ins[id - len - 1];
    }

    void push(ll v) {
        ins.push_back(v);
    }
};

const int N = 300010;

int n, m, q;

Phalanx r[N], c;

int main() {
//  freopen("phalanx1.in", "r", stdin);
//  freopen("phalanx1.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        r[i].fst = (i - 1) * (ll)m;
        r[i].len = m - 1;
        r[i].dif = 1;
        r[i].fw = r[i].create(1 << 20);
    }
    c.len = n;
    c.dif = m;
    c.fw = c.create(1 << 20);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (y == m) {
            ll v = c.rmv(x);
            printf("%lld\n", v);
            c.push(v);
        } else {
            ll v = r[x].rmv(y);
            printf("%lld\n", v);
            r[x].push(c.rmv(x));
            c.push(v);
        }
    }
    return 0;
}