Problem Overview

Consider an n×m grid where each cell contains its position number: the cell at row i, column j holds value (i-1)×m + j. We process q queries, each specifying a position (x, y). The queried element is removed and appended to the end of its row, while the element displaced from the row's end moves to the end of the last column.

The key insight: operations on different row are independent but all interact with the last column.

Solution 1: Treap with Implicit Keys

This problem requires maintaining sequences with deletion, insertion, and k-th element queries—classic operations for balanced binary search trees. The fhq-Treap serves well here.

The naive approach would build individual nodes for all n×m elements, requiring O(nm) memory, wich is infeasible. Instead, we compress contiguous intervals of unremoved "vanilla" elements into single nodes. Each node stores its interval boundaries [l, r] and computes its "real size" as r-l+1.

When removing element at position k from a row:

1. Locate the node containing position k using rank queries
2. Split the tree to isolate that node
3. If the interval spans more than one element, split it into [l, k-1] and [k+1, r]
4. Merge the remaining parts back

For y=m queries (last column), we move the x-th element to the end of that column.

For y≠m queries:

1. Extract element at (x, y) from row x
2. Move last column's x-th element to row x's end
3. Insert the extracted element into the last column's end

The code uses vector-based node storage, which requires caution during recursive building. When recursively constructing child nodes, store the recursive result in a temporary variable before assigning, as vector reallocation during push_back can invalidate references.

Complexities: Time O(q log n), Space O(n + q)

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
    struct Node {
        unsigned priority;
        int left, right;
        int subtreeSize;
        int actualCount;
        long long leftBound, rightBound;
    };
    
    vector<Node> nodes;
    stack<int> deletedPool;
    int root = 0;
    
    Treap() { nodes.emplace_back(Node{0, 0, 0, 0, 0, 0, 0}); }
    
    int newNode(long long l, long long r) {
        if (l > r) return 0;
        if (!deletedPool.empty()) {
            int idx = deletedPool.top();
            deletedPool.pop();
            nodes[idx] = {rng(), 0, 0, 1, int(r - l + 1), l, r};
            return idx;
        }
        nodes.push_back({rng(), 0, 0, 1, int(r - l + 1), l, r});
        return (int)nodes.size() - 1;
    }
    
    void pullUp(int p) {
        if (!p) return;
        nodes[p].subtreeSize = nodes[nodes[p].left].subtreeSize + 1 + nodes[nodes[p].right].subtreeSize;
        nodes[p].actualCount = nodes[nodes[p].left].actualCount + 
            (nodes[p].rightBound - nodes[p].leftBound + 1) + 
            nodes[nodes[p].right].actualCount;
    }
    
    int build(int l, int r, long long base) {
        if (l > r) return 0;
        int mid = (l + r) >> 1;
        long long val = base + mid;
        int p = newNode(val, val);
        
        int child;
        if (l <= mid - 1) {
            child = build(l, mid - 1, base);
            nodes[p].left = child;
        }
        if (mid + 1 <= r) {
            child = build(mid + 1, r, base);
            nodes[p].right = child;
        }
        pullUp(p);
        return p;
    }
    
    pair<int, int> split(int p, int k) {
        if (!p || k <= 0) return {0, p};
        int leftSize = nodes[nodes[p].left].subtreeSize;
        
        if (k <= leftSize) {
            auto [l, r] = split(nodes[p].left, k);
            nodes[p].left = r;
            pullUp(p);
            return {l, p};
        } else {
            auto [l, r] = split(nodes[p].right, k - leftSize - 1);
            nodes[p].right = l;
            pullUp(p);
            return {p, r};
        }
    }
    
    int merge(int p, int q) {
        if (!p || !q) return p | q;
        if (nodes[p].priority < nodes[q].priority) {
            nodes[p].right = merge(nodes[p].right, q);
            pullUp(p);
            return p;
        } else {
            nodes[q].left = merge(p, nodes[q].left);
            pullUp(q);
            return q;
        }
    }
    
    pair<int, long long> findKth(int p, int k) {
        int leftCount = nodes[nodes[p].left].actualCount;
        long long currentLeft = nodes[p].leftBound;
        long long currentRight = nodes[p].rightBound;
        
        if (k <= leftCount) {
            return findKth(nodes[p].left, k);
        } else if (k <= leftCount + (currentRight - currentLeft + 1)) {
            long long offset = k - leftCount - 1;
            return {nodes[nodes[p].left].subtreeSize + 1, currentLeft + offset};
        } else {
            auto res = findKth(nodes[p].right, k - leftCount - (currentRight - currentLeft + 1));
            res.first += nodes[nodes[p].left].subtreeSize + 1;
            return res;
        }
    }
    
    long long erase(int k) {
        auto [treeIdx, val] = findKth(root, k);
        auto [t1, t2] = split(root, treeIdx - 1);
        auto [t3, t4] = split(t2, 1);
        
        deletedPool.push(t3);
        
        long long v = nodes[t3].leftBound + (val - nodes[t3].leftBound);
        long long leftPart = nodes[t3].leftBound;
        long long rightPart = nodes[t3].rightBound;
        
        int leftNode = newNode(leftPart, val - 1);
        int rightNode = newNode(val + 1, rightPart);
        
        root = merge(t1, merge(leftNode, merge(rightNode, t4)));
        return val;
    }
    
    long long moveToBack(int k) {
        auto [treeIdx, val] = findKth(root, k);
        auto [t1, t2] = split(root, treeIdx - 1);
        auto [t3, t4] = split(t2, 1);
        
        long long result = nodes[t3].leftBound + (val - nodes[t3].leftBound);
        
        nodes[t3].leftBound = nodes[t3].rightBound = result;
        nodes[t3].actualCount = 1;
        
        root = merge(t1, merge(t3, merge(t4, t3)));
        return result;
    }
    
    void pushBack(long long v) {
        root = merge(root, newNode(v, v));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<Treap> rowTree(n + 1);
    Treap lastCol;
    
    for (int i = 1; i <= n; i++) {
        rowTree[i].root = rowTree[i].build(1, m - 1, 1LL * (i - 1) * m);
    }
    lastCol.root = lastCol.build(1, n, 0);
    
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        if (y == m) {
            cout << lastCol.moveToBack(x) << '\n';
        } else {
            long long ans = rowTree[x].erase(y);
            cout << ans << '\n';
            rowTree[x].pushBack(lastCol.moveToBack(x));
        }
    }
    return 0;
}

Solution 2: Dynamic Segment Tree

An alternative approach represents each position as alive (1) or deleted (0). Deletion sets a position to 0, and finding the k-th element requires binary search on prefix sums. This naturally leads to segment tree or binary indexed tree with binary search on the tree structure.

The challenge: pre-allocating space for all n×m positions is impossible. Since insertions only occur at the end, we use dynamic node creation—nodes are created only when accessed during queries.

Solution 3: Offline Processing with BIT (Optimal)

This approach further optimizes space. Single-point updates and k-th element queries (via binary lifting) are exactly what BIT excels at.

The solution processes queries offline in two phases:

Phase 1: Process all non-last-column queries row by row. For each row, we know its queries in chronological order. We maintain a BIT over positions [1, m-1] initially set to 1 (all positions alive). When processing a query for position y in a row:

1. Find the actual position (accounting for previous deletions in this row) using BIT's find-by-order operation
2. Record this value
3. Temporarily mark this position as deleted and insert at position m+j (where j is the query index within this row)
4. After processing all queries in the row, restore the BIT to its original state

This gives us results for all non-last-column queries without affecting subsequent rows.

Phase 2: Process queries in original order. The last column is maintained online using BIT and vectors for appended elements. For each query:

• If y=m: find x-th alive element in last column, output it, move to the back
• If y≠m: output precomputed result for this position, move last column's x-th element to the row's end

Each row and the last column maintain a vector of appended values to handle the displaced elements.

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

struct FenwickTree {
    vector<int> bit;
    int size;
    
    void initialize(int n) {
        size = n;
        bit.assign(n + 1, 0);
    }
    
    void update(int idx, int delta) {
        for (; idx <= size; idx += idx & -idx) {
            bit[idx] += delta;
        }
    }
    
    int prefixSum(int idx) {
        int result = 0;
        for (; idx > 0; idx -= idx & -idx) {
            result += bit[idx];
        }
        return result;
    }
    
    int findByOrder(int k) {
        int pos = 0;
        int currentSum = 0;
        for (int i = 20; i >= 0; i--) {
            int next = pos + (1 << i);
            if (next <= size && currentSum + bit[next] < k) {
                pos = next;
                currentSum += bit[next];
            }
        }
        return pos + 1;
    }
};

struct Query {
    int row, col;
    int originalIndex;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<Query> allQueries(q + 1);
    vector<vector<Query>> queriesByRow(n + 1);
    vector<int> answer(q + 1);
    
    for (int i = 1; i <= q; i++) {
        cin >> allQueries[i].row >> allQueries[i].col;
        allQueries[i].originalIndex = i;
        if (allQueries[i].col < m) {
            queriesByRow[allQueries[i].row].push_back(allQueries[i]);
        }
    }
    
    FenwickTree bit;
    bit.initialize(m + q);
    
    for (int i = 1; i < m; i++) {
        bit.update(i, 1);
    }
    
    for (int row = 1; row <= n; row++) {
        auto& vec = queriesByRow[row];
        sort(vec.begin(), vec.end(), 
            [](const Query& a, const Query& b) {
                return a.originalIndex < b.originalIndex;
            });
        
        for (size_t j = 0; j < vec.size(); j++) {
            const Query& qq = vec[j];
            int targetPos = bit.findByOrder(qq.col);
            answer[qq.originalIndex] = targetPos;
            
            bit.update(targetPos, -1);
            bit.update(m + j, 1);
        }
        
        for (size_t j = 0; j < vec.size(); j++) {
            bit.update(answer[vec[j].originalIndex], 1);
            bit.update(m + j, -1);
        }
    }
    
    bit.initialize(n + q);
    for (int i = 1; i <= n; i++) {
        bit.update(i, 1);
    }
    
    vector<long long> lastColHistory;
    vector<vector<long long>> rowHistory(n + 1);
    
    for (int i = 1; i <= q; i++) {
        int row = allQueries[i].row;
        int col = allQueries[i].col;
        
        if (col == m) {
            int targetPos = bit.findByOrder(row);
            long long result;
            if (targetPos <= n) {
                result = 1LL * targetPos * m;
            } else {
                result = lastColHistory[targetPos - n - 1];
            }
            cout << result << '\n';
            
            lastColHistory.push_back(result);
            bit.update(targetPos, -1);
            bit.update(n + (int)lastColHistory.size(), 1);
        } else {
            int targetPos = answer[i];
            long long result;
            if (targetPos < m) {
                result = 1LL * (row - 1) * m + targetPos;
            } else {
                result = rowHistory[row][targetPos - m];
            }
            cout << result << '\n';
            
            int colTargetPos = bit.findByOrder(row);
            long long displaced;
            if (colTargetPos <= n) {
                displaced = 1LL * colTargetPos * m;
            } else {
                displaced = lastColHistory[colTargetPos - n - 1];
            }
            
            rowHistory[row].push_back(displaced);
            lastColHistory.push_back(result);
            
            bit.update(colTargetPos, -1);
            bit.update(n + (int)lastColHistory.size(), 1);
        }
    }
    
    return 0;
}

Complexities: Time O((n + q) log(n + q)), Space O(n + q)

This approach runs comfortably within 1 second per test case without optimization flags, making it the optimal solution for this problem.