問題概要

1からnまでの順列に対してm回の部分ソート操作を実行し、q番目の位置にある数値を求める問題。ソート操作は昇順または降順のどちらかで、指定された区間内の要素を並び替える。

入力形式

n m
a_1 a_2 ... a_n
op_1 l_1 r_1
...
op_m l_m r_m
q

解法概要

二分探索とセグメント木を組み合わせたO(n log²n)のアルゴリズムを使用する。重要なのは「ある値Xより大きい要素の数」を管理しながらソート操作をシミュレートすること。

アルゴリズムの詳細

1. 二分探索で答えの候補Xを決定
2. Xより大きい要素を1、小さい要素を0としてセグメント木を構築
3. 各ソート操作をセグメント木で以下の手順でシミュレート：
   • 区間内の1の個数をカウント
   • その区間を0で初期化
   • 昇順ソートの場合は後半に1を配置
   • 降順ソートの場合は前半に1を配置
4. 最終的にq位置の値がX以下かどうかで二分探索の範囲を調整

コード例

#include <iostream>
#include <vector>
using namespace std;

struct SortOperation {
    int type, left, right;
};

class SegmentTree {
private:
    int size;
    vector<int> sum, lazy;
    
    void push(int node, int l, int r) {
        if (lazy[node] != -1) {
            int mid = (l + r) / 2;
            sum[node*2] = lazy[node] * (mid - l + 1);
            sum[node*2+1] = lazy[node] * (r - mid);
            lazy[node*2] = lazy[node];
            lazy[node*2+1] = lazy[node];
            lazy[node] = -1;
        }
    }
    
    void update(int node, int l, int r, int ql, int qr, int val) {
        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            sum[node] = val * (r - l + 1);
            lazy[node] = val;
            return;
        }
        push(node, l, r);
        int mid = (l + r) / 2;
        update(node*2, l, mid, ql, qr, val);
        update(node*2+1, mid+1, r, ql, qr, val);
        sum[node] = sum[node*2] + sum[node*2+1];
    }
    
    int query(int node, int l, int r, int ql, int qr) {
        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return sum[node];
        push(node, l, r);
        int mid = (l + r) / 2;
        return query(node*2, l, mid, ql, qr) + query(node*2+1, mid+1, r, ql, qr);
    }

public:
    SegmentTree(int n) : size(n) {
        sum.assign(4*n, 0);
        lazy.assign(4*n, -1);
    }
    
    void build(const vector<int>& a, int X) {
        for (int i = 0; i < size; ++i) {
            sum[i+size] = (a[i] > X);
        }
        for (int i = size-1; i > 0; --i) {
            sum[i] = sum[i*2] + sum[i*2+1];
        }
    }
    
    bool simulate(const vector<SortOperation>& ops) {
        for (auto& op : ops) {
            int count = query(1, 0, size-1, op.left, op.right);
            update(1, 0, size-1, op.left, op.right, 0);
            if (count > 0) {
                if (op.type == 0) {  // 昇順
                    update(1, 0, size-1, op.right - count + 1, op.right, 1);
                } else {  // 降順
                    update(1, 0, size-1, op.left, op.left + count - 1, 1);
                }
            }
        }
        return query(1, 0, size-1, q, q) == 0;
    }
};

int main() {
    int n, m, q;
    vector<int> a;
    vector<SortOperation> operations;
    
    // 入力処理
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) {
        SortOperation op;
        cin >> op.type >> op.left >> op.right;
        operations.push_back(op);
    }
    cin >> q;
    
    // 二分探索
    int low = 1, high = n;
    while (low < high) {
        int mid = (low + high) / 2;
        SegmentTree st(n);
        st.build(a, mid);
        if (st.simulate(operations)) high = mid;
        else low = mid + 1;
    }
    
    cout << low << endl;
    return 0;
}