洛谷P3960 列队(动态开节点线段树)

#include<bits/stdc++.h>
#define LL long long int
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf,  obuf[1 << 24], *O = obuf;
void print(LL x) {
    if(x > 9) print(x / 10);
    *O++= x % 10 + '0';
}
using namespace std;
const int MAXN = 3e5 + 10, SS = MAXN * 20;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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;
}
int N, M, Q, cnt, siz[SS], ls[SS], rs[SS], rt[MAXN], tot;
LL las[MAXN << 1];
vector<LL> pos[MAXN];
int Modify(int &k, int l, int r, int kth) {
    if(!k) k = ++tot, siz[k] = r - l + 1;  siz[k]--;
    if(l == r) return l;
    int mid = l + r >> 1, now = (!ls[k] ? mid - l + 1 : siz[ls[k]]);
    if(now < kth) return Modify(rs[k], mid + 1, r, kth - now);
    else return Modify(ls[k], l, mid, kth);
}
LL Query(int y, int x) {
    LL ans = 0;
    if(y == M) ans = las[Modify(rt[0], 1, N + Q, x)];
    else {
        int tmp = Modify(rt[x], 1, M + Q, y);
        if(tmp < M) ans = 1ll * (x - 1) * M + tmp;
        else ans = pos[x][tmp - M];
        pos[x].push_back(las[Modify(rt[0], 1, N + Q, x)]);
    }
    return las[++cnt] = ans;
}
int main() {
    N = read(); M = read(); Q = read();
    for(int i = 1; i <= N; i++) las[++cnt] = 1ll * i * M;
    for(int i = 1; i <= Q; i++) print(Query(read(), read())), *O++ = '\n';
    fwrite(obuf, O-obuf, 1 , stdout);
    return 0;
}