思路与算法

把每行前m-1列各看作一个动态序列，最后一列单独维护。每次先从最后列取出第x项v；若y<m，再从行x取第y项作为答案，将v追加该行；否则答案就是v。最后把答案追加最后列。用动态开点线段树维护仍存在的位置数，支持删除第k项与尾部追加。初始编号按公式算，只有后来追加的值显式存储。

正确性说明

向左标齐只改离队所在行，之后向上标齐只改最后列，因此上述两个序列操作恰对应原矩阵变化。线段树每个结点记录区间剩余项数，左子树计数决定第k项在哪一侧，删除后沿路径减计数、追加时增计数，保持序列秩与位置对应。原始前缀未开结点的计数按区间与初始范围交集长度计算，省略存储不改变逻辑。

复杂度

令U=max(n,m)+q。含行根数组与所有操作，时间O(n+q log U)，空间O(n+q log U)；不分配n乘m矩阵。

易错点

m=1时行内序列为空，只操作最后列。编号最大n*m达9×10^10，需64位。动态结点池扩容时不能保留可能失效的vector元素引用。

参考代码（C++11）

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

struct Node {
    int l, r, c;
};
struct Seq {
    vector<Node> t;
    Seq(int q) {
        t.reserve((size_t)q * 45 + 1);
        t.push_back({0, 0, 0});
    }
    int initial(int l, int r, int len) {
        return max(0, min(r, len) - l + 1);
    }
    int count(int p, int l, int r, int len) {
        return p ? t[p].c : initial(l, r, len);
    }
    int change(int p, int l, int r, int pos, int delta, int len) {
        if (!p) {
            p = t.size();
            t.push_back({0, 0, initial(l, r, len)});
        }
        t[p].c += delta;
        if (l < r) {
            int mid = (l + r) / 2;
            if (pos <= mid) {
                int x = change(t[p].l, l, mid, pos, delta, len);
                t[p].l = x;
            } else {
                int x = change(t[p].r, mid + 1, r, pos, delta, len);
                t[p].r = x;
            }
        }
        return p;
    }
    int kth(int p, int l, int r, int k, int len) {
        if (!p)
            return l + k - 1;
        if (l == r)
            return l;
        int mid = (l + r) / 2, left = count(t[p].l, l, mid, len);
        return k <= left ? kth(t[p].l, l, mid, k, len) : kth(t[p].r, mid + 1, r, k - left, len);
    }
};
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    Seq st(q);
    vector<int> roots(n + 1), append(n + 1);
    vector<vector<long long>> extra(n + 1);
    vector<long long> last;
    int global = 0, limit = max(n, m) + q + 1;
    auto pop = [&](int &root, int k, int len) {
        int pos = st.kth(root, 1, limit, k, len);
        root = st.change(root, 1, limit, pos, -1, len);
        return pos;
    };
    while (q--) {
        int x, y;
        cin >> x >> y;
        int gp = pop(global, x, n);
        long long from = gp <= n ? 1LL * gp * m : last[gp - n - 1], answer;
        if (y == m)
            answer = from;
        else {
            int p = pop(roots[x], y, m - 1);
            answer = p < m ? 1LL * (x - 1) * m + p : extra[x][p - m];
            extra[x].push_back(from);
            int where = m - 1 + extra[x].size();
            roots[x] = st.change(roots[x], 1, limit, where, 1, m - 1);
        }
        last.push_back(answer);
        global = st.change(global, 1, limit, n + last.size(), 1, n);
        cout << answer << "\n";
    }
}