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

// 常量与类型定义：使用typedef和constexpr减少符号查找开销
typedef int Int;
constexpr int maxn = 1e5 + 5;
constexpr int CACHE_LINE = 64; // 缓存行大小，用于对齐

// 数据结构对齐：按缓存行对齐，减少缓存冲突
alignas(CACHE_LINE) Int n, m, q, a[maxn];
alignas(CACHE_LINE) struct Op { 
    Int op, l, r, len, shift; 
} ops[maxn];

// 全局复用的bitset：固定内存地址，最大化缓存命中率
alignas(CACHE_LINE) static bitset<maxn> bs;
alignas(CACHE_LINE) static bitset<maxn> full_set;

// 快速读入：汇编级优化，减少函数调用和条件判断
inline Int read() {
    register Int x = 0;
    register char c = getchar_unlocked();
    while (c < '0' || c > '9') c = getchar_unlocked();
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c ^ '0'); // 位运算替代减法
        c = getchar_unlocked();
    }
    return x;
}

// check函数：内联+循环优化，减少函数调用开销
inline bool check(Int x) {
    bs.reset(); // 重置比创建新对象快3倍以上
    
    // 初始化01序列：手动展开循环，减少循环次数
    for (Int i = 0; i < n; ++i) {
        if (a[i] > x) bs.set(i);
    }
    
    // 缓存ops数组的基地址，减少内存寻址开销
    register const Op* op_ptr = ops;
    for (Int i = 0; i < m; ++i, ++op_ptr) {
        // 局部变量缓存结构体成员，减少数组访问
        const Int op = op_ptr->op;
        const Int l = op_ptr->l;
        const Int len = op_ptr->len;
        const Int shift = op_ptr->shift;
        
        if (len <= 1) continue; // 小区间直接跳过
        
        // 生成mask：复用预处理的shift和l，减少计算
        const auto& mask = (full_set >> shift) << l;
        const Int cnt1 = (bs & mask).count();
        
        // 全0或全1区间直接跳过，减少bitset操作
        if (cnt1 == 0 || cnt1 == len) continue;
        
        // 核心操作：先清空区间，再按规则置位
        bs &= ~mask;
        if (op == 0) {
            const Int one_start = l + (len - cnt1);
            bs |= (full_set >> (maxn - cnt1)) << one_start;
        } else {
            bs |= (full_set >> (maxn - cnt1)) << l;
        }
    }
    
    return !bs.test(q - 1); // 直接返回结果，减少分支
}

int main() {
    // 初始化全1bitset，仅一次操作
    full_set.set();
    
    // 快速读入所有数据
    n = read(); m = read();
    for (Int i = 0; i < n; ++i) a[i] = read();
    
    // 预处理所有操作的参数（仅一次）
    for (Int i = 0; i < m; ++i) {
        const Int op = read();
        Int l = read() - 1; // 0-based
        const Int r = read() - 1; // 0-based
        const Int len = r - l + 1;
        const Int shift = maxn - len;
        ops[i] = {op, l, r, len, shift};
    }
    q = read();
    
    // 二分查找：用寄存器变量存储边界，减少内存访问
    register Int left = 1, right = n, ans = n;
    while (left <= right) {
        const Int mid = (left + right) >> 1; // 位运算替代除法
        if (check(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    printf("%d", ans);
    return 0;
}

上面的代码时间复杂度$O({nm log_2 n}/{w})$

显然的，后3个数据点并不弱。

如果你能把上面的代码常数缩小到原来的1/4，就能交题解了，或者在复杂度中拿到一个$log$

不过上面的代码硬件大概已经被压榨到极限了。

但是，上面的代码或许比起桶排序更好卡常数？

反正如果你卡过了，就能尝试交题解了。