解题思路

核心挑战

• 数据规模巨大：用户数 n ≤ 10^8，操作数 m ≤ 10^5
• 实时排名维护：需要高效支持排名查询和更新
• 加密处理：需要动态解密输入参数

算法设计

1. 数据结构选择

使用 GNU Policy-Based Data Structures 中的有序统计树：

• spos：存储 (位置, 用户ID) 对，按位置排序
• sidset：存储所有被操作过的用户ID
• id2pos：哈希表，记录用户ID到位置的映射

2. 位置管理策略

• 初始状态：用户i的默认位置就是i
• 边界扩展：使用 min_pos 和 max_pos 动态分配新位置
  • 提升排名：分配 min_pos-- 的新位置
  • 降低排名：分配 max_pos++ 的新位置

3. 排名计算

排名 = 显式用户中位置较小的数量 + 隐式用户中编号较小的数量

ll get_rank(int x) {
    ll pos = id2pos.count(x) ? id2pos[x] : (ll)x;
    
    ll explicit_less = spos.order_of_key({pos, INF_INT});
     
    ll implicit_less = min((ll)n, pos-1) - sidset.order_of_key((int)pos);
    
    return explicit_less + implicit_less + 1;
}

4. 第k名查询

使用二分查找确定第k名对应的位置：

int get_kth(ll k) {
    ll lo = min_pos, hi = max_pos;
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        ll total = count_users_up_to(mid);
        if (total >= k) hi = mid;
        else lo = mid + 1;
    }
    
    return find_user_at(lo);
}

复杂度分析

• 时间复杂度：每个操作 O(log m)，总复杂度 O(m log m)
• 空间复杂度：O(m)，只存储被操作过的用户

代码实现

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
const int INF_INT = numeric_limits<int>::min();

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    ordered_set<pair<ll,int>> spos;
    ordered_set<int> sidset;
    unordered_map<int, ll> id2pos;

    ll min_pos = 0, max_pos = (ll)n + 1;
    ll a = 0;

    auto count_explicit_pos_less = [&](ll v)->ll {
        return spos.order_of_key({v, INF_INT});
    };
    auto count_explicit_pos_le = [&](ll v)->ll {
        return spos.order_of_key({v + 1, INF_INT});
    };
    auto count_touched_ids_le = [&](int v)->ll {
        if (v < 1) return 0;
        return sidset.order_of_key(v + 1);
    };

    auto get_rank = [&](int x)->ll {
        ll pos;
        if (id2pos.count(x)) pos = id2pos[x];
        else pos = (ll)x;

        ll cnt_explicit_less = count_explicit_pos_less(pos);

        ll t = pos - 1;
        if (t < 0) t = 0;
        if (t > n) t = n;
        ll cnt_touched_le_t = count_touched_ids_le((int)t);
        ll cnt_implicit_less = t - cnt_touched_le_t;
        if (cnt_implicit_less < 0) cnt_implicit_less = 0;

        return cnt_explicit_less + cnt_implicit_less + 1;
    };

    auto get_kth = [&](ll k)->int {
        ll lo = min_pos, hi = max_pos;
        while (lo < hi) {
            ll mid = lo + (hi - lo) / 2;
            ll cnt_pos_le = count_explicit_pos_le(mid);
            ll t = mid;
            if (t < 0) t = 0;
            if (t > n) t = n;
            ll cnt_touched_le_t = count_touched_ids_le((int)t);
            ll total = cnt_pos_le + t - cnt_touched_le_t;
            if (total >= k) hi = mid;
            else lo = mid + 1;
        }
        ll v = lo;
        auto it = spos.lower_bound({v, INF_INT});
        if (it != spos.end() && it->first == v) {
            return it->second;
        } else {
            return (int)v;
        }
    };

    for (int i = 0; i < m; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            ll x, y; cin >> x >> y; x -= a; y -= a;
            int xi = (int)x, yi = (int)y;

            ll rank = get_rank(xi);
            cout << rank << '\n';
            a = rank;

            ll pos;
            if (id2pos.count(xi)) {
                pos = id2pos[xi];
                spos.erase({pos, xi});
                id2pos.erase(xi);
            } else {
                pos = x;
                sidset.insert(xi);
            }
            id2pos[yi] = pos;
            spos.insert({pos, yi});
            sidset.insert(yi);
        }

        else if (t == 2) {
            ll x; cin >> x; x -= a;
            int xi = (int)x;

            ll rank = get_rank(xi);
            cout << rank << '\n';
            a = rank;

            ll pos;
            if (id2pos.count(xi)) {
                pos = id2pos[xi];
                spos.erase({pos, xi});
                id2pos.erase(xi);
            } else {
                pos = x;
                sidset.insert(xi);
            }
            min_pos--;
            ll new_pos = min_pos;
            id2pos[xi] = new_pos;
            spos.insert({new_pos, xi});
            sidset.insert(xi);
        }

        else if (t == 3) {
            ll x; cin >> x; x -= a;
            int xi = (int)x;

            ll rank = get_rank(xi);
            cout << rank << '\n';
            a = rank;

            ll pos;
            if (id2pos.count(xi)) {
                pos = id2pos[xi];
                spos.erase({pos, xi});
                id2pos.erase(xi);
            } else {
                pos = x;
                sidset.insert(xi);
            }
            max_pos++;
            ll new_pos = max_pos;
            id2pos[xi] = new_pos;
            spos.insert({new_pos, xi});
            sidset.insert(xi);
        }

        else if (t == 4) {
            ll k; cin >> k; k -= a;
            int id = get_kth(k);
            cout << id << '\n';
            a = id;
        }
    }

    return 0;
}