题解：追踪排序操作后的目标位置

问题分析

题目要求经过多次区间排序操作后，查询第(k)个位置的元素值。由于(n)和(m)均可达(10^5)，正向模拟每次排序会超时（时间复杂度(O(m \cdot n \log n))）。核心优化点是：仅需关注最终第(k)个位置的元素，可通过反向追踪该元素在每次操作前的位置，最终定位到初始数组中的位置。

核心思路

1. 反向追踪：从最终查询的位置(k)开始，逆序处理所有排序操作，追踪该位置的元素在每次操作前的位置。
2. 区间判断：对于每个操作（从后往前），若当前位置不在操作区间内，则位置不变；若在区间内，则根据排序类型（升序/降序）计算操作前的位置。
3. 位置映射：
   • 升序排序（(op=0)）：操作后区间内第(p)个位置（相对位置）的元素，对应操作前区间内第(p)小的元素，其操作前的位置为区间起始(l)加上(p-1)。
   • 降序排序（(op=1)）：操作后区间内第(p)个位置的元素，对应操作前区间内第(p)大的元素，其操作前的位置为区间起始(l)加上（区间长度(-p)）。

代码实现

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

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> w(n + 1);  // 1-based
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }

    vector<tuple<int, int, int>> ops;  // 存储操作：op, l, r
    for (int i = 0; i < m; ++i) {
        int op, l, r;
        cin >> op >> l >> r;
        ops.emplace_back(op, l, r);
    }

    // 反向追踪位置
    int pos = k;
    for (int i = m - 1; i >= 0; --i) {
        auto [op, l, r] = ops[i];
        if (pos < l || pos > r) {
            continue;  // 位置不在当前操作区间内，不变
        }
        // 计算相对位置
        int len = r - l + 1;
        int p = pos - l + 1;  // 1-based相对位置
        if (op == 0) {  // 升序，反向映射
            pos = l + p - 1;
        } else {  // 降序，反向映射
            pos = l + (len - p);
        }
    }

    cout << w[pos] << endl;

    return 0;
}

代码解释

• 反向追踪：从最终位置(k)开始，逆序遍历所有操作，逐步修正位置至初始状态。
• 区间映射：对于每个操作，若当前位置在操作区间内，根据排序类型计算操作前的位置。升序时直接按相对位置映射，降序时按区间长度反向映射。
• 时间复杂度：(O(m))，仅遍历所有操作一次，高效适配(m \leq 10^5)的规模。

该方法通过聚焦单一位置的反向追踪，避免了正向模拟的高额开销，精准定位初始数组中的目标元素。