T494185 BRPT/QPS/SWM/BRGS/MNHT/DIT/DIT/FIC/AST

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class SegmentTree {
public:
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 0, 0, n - 1);
    }

    void rebuild(const vector<int>& arr) {
        build(arr, 0, 0, n - 1);
    }

    int queryMin(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

private:
    int n;
    vector<int> tree;

    void build(const vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) return INT_MAX;
        if (l <= start && r >= end) return tree[node];
        int mid = (start + end) / 2;
        int left_min = query(2 * node + 1, start, mid, l, r);
        int right_min = query(2 * node + 2, mid + 1, end, l, r);
        return min(left_min, right_min);
    }
};

void partitionAndReconstruct(vector<int>& arr, vector<int>& index, SegmentTree& segTree, int l, int r) {
    vector<pair<int, int>> subarray;
    for (int i = l; i <= r; ++i) {
        subarray.push_back({arr[i], index[i]});
    }
    sort(subarray.begin(), subarray.end());
    for (int i = 0; i < subarray.size(); ++i) {
        arr[l + i] = subarray[i].first;
        index[l + i] = subarray[i].second;
    }
    segTree.rebuild(arr);  // 重新构建线段树
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    vector<int> index(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        index[i] = i + 1;  // 1-based index
    }

    SegmentTree segTree(arr);

    for (int i = 0; i < m; ++i) {
        int op, l, r;
        cin >> op >> l >> r;
        l--; r--;  // 转换为0索引

        if (op == 1) {
            int minValue = segTree.queryMin(l, r);
            for (int j = l; j <= r; ++j) {
                if (arr[j] == minValue) {
                    cout << minValue << " " << index[j] << endl;
                    break;
                }
            }
        } else if (op == 2) {
            partitionAndReconstruct(arr, index, segTree, l, r);
        }
    }

    return 0;
}