python/TangDou/AcWing/SegmentTree/P3960.cpp

// #define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define re register
const int maxn = 3e5 + 5;

int n, m, q, now;
int cnt, Max;

ll ans;

struct node {
    int ls, rs, size; // size:当前区间内有多少个数没有被标记
    ll val;

    node() {
    }
    node(const int _ls, const int _rs, const int _size, const ll _val) :
        ls(_ls), rs(_rs), size(_size), val(_val) {
    }
} st[maxn << 5]; // 严格来讲应该开 Q * log2(N)，也就是20倍 ，为了方便与保险，我们直接开32倍

int ins[maxn], root[maxn];
// ins[i]记录第i棵树插入了多少个新数
// root[i]记录第i棵树的根节点

inline int len(int l, int r) {
    if (now == n + 1) {
        if (r <= n) return r - l + 1;
        if (l <= n) return n - l + 1;
        return 0;
    }
    if (r < m) return r - l + 1;
    if (l < m) return (m - 1) - l + 1;

    return 0;
}

ll query(int &rt, int l, int r, int pos) {
    if (!rt) { // 动态开点
        rt = ++cnt;
        st[rt].size = len(l, r);

        if (l == r) {
            if (now == n + 1)
                st[rt].val = 1ll * l * m;
            else
                st[rt].val = 1ll * (now - 1) * m + l;
        }
    }
    st[rt].size--;
    这个区间有一个数被取出
    if (l == r) return st[rt].val;

    int mid = (l + r) >> 1;
    if (!st[rt].ls && len(l, mid) >= pos || st[st[rt].ls].size >= pos) {
        query(st[rt].ls, l, mid, pos);
    } else {
        int tmp;
        if (!st[rt].ls)
            tmp = len(l, mid);
        else
            tmp = st[st[rt].ls].size;
        return query(st[rt].rs, mid + 1, r, pos - tmp);
    }
}

void modify(int &rt, int l, int r, int pos, ll num) {
    if (!rt) {
        rt = ++cnt;
        st[rt].size = len(l, r);
        if (l == r) {
            st[rt].val = num;
        }
    }

    ++st[rt].size; // 这个区间末尾有一个人进去
    if (l == r) return;

    int mid = (l + r) >> 1;
    if (pos <= mid)
        modify(st[rt].ls, l, mid, pos, num);
    else
        modify(st[rt].rs, mid + 1, r, pos, num);
}

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
    n = read();
    m = read();
    q = read();
    Max = max(n, m) + q; // 一共有q次离队，于是最多有q个人再次进队，于是最大也就是队列长度加上他们本身（因为我们取出以后在位置进行标记，相当于占上了位置

    while (q--) {
        int x = read(), y = read();
        if (y == m) {    // 如果是最后一列
            now = n + 1; // 那么一定要放到那个单独的区间里面去，也就是上面说到的蓝色区域
            ans = query(root[now], 1, Max, x);
        } else {
            now = x; // 否则，那么一定在红色区域
            ans = query(root[now], 1, Max, y);
        }

        printf("%lld\n", ans); // 输出答案

        now = n + 1; // 让被选出的人进入蓝色区域的最后一个位置
        modify(root[now], 1, Max, n + (++ins[now]), ans);

        if (y != m) {
            ans = query(root[now], 1, Max, x);
            now = x;
            modify(root[now], 1, Max, m - 1 + (++ins[now]), ans);
        }
    }

    return 0;
}