暴力的，O（NQ）可过的

· · 题解

大家好，我非常喜欢暴力数据结构，于是我就用分块过了这道题。

大家好，我非常喜欢暴力，于是我就没用数据结构过了这道题。

并且可能比大多数人的树套树和分块都块

跑到了峰值 800ms

在阅读之前你需要准备

考虑本题每个操作的暴力算法：

  1. 查询 k 在区间内的排名：循环统计 <k 的数的数量就行，O(\text{len})。
  2. 查询区间内排名为 k 的值：暴力 nth_element 时间复杂度 O(\text{len})，可能会有较大常数。
  3. 修改某一位置上的数值：显然 O(1)。
  4. 查询 k 在区间内的前驱：扫描整个区间，找到 <k 的最大值即可，O(\text{len})。
  5. 查询 k 在区间内的后继：与 4 操作同理，O(\text{len})。

总时间复杂度 O(nm)，在时间限制 4s，n,m\le 5\times10^4 的限制下极有可能通过。

提交发现 80pts TLE on #2 #9，对每个操作构造最坏情况发现最慢的操作是 2，考虑综合 2 与 3 操作的时间复杂度。

回顾 2 操作，如果 [l,r] 是已经排序的数组则可以 O(1) 得出答案，如果有整个排序的数组，且记录了每个位置对应的原位置，可以用 O(n) 的时间复杂度提出 [l,r] 排序的结果。

上面算法已经严格 O(n)，对于常数优化，可以在 \text{len} 比较小的时候用 nth_element 状物（不用也能过）。

此时问题转变为维护 [1,n] 排序的数组，需要支持单点修改，这个傻子都会。

使用 vector 维护，因为 vector 对于 insert 操作和 erase 操作都有较优常数，那么 3 操作的时间复杂度就是 O(n) 的。

现在所有操作都是小常数 O(n)，总时间复杂度 O(nq)，跑到了文章开头的峰值 800ms。

放一下我想到的，最应景的：WC2026 文艺汇演《暴力的，O（NQ）可过的》

全文没用用到任何普及组知识。

下面是平凡的代码：

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
//快读，不必要。
#define ds(x) (x=='\r'||x=='\n'||x==' ')
#define MAX 20
namespace fastIO {//吾常于「oi-wiki」习，自悟「快读快写」之术。
    template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
    template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
    struct FIstream {
        inline FIstream operator>>(int& a) { r(a); return{}; }
        inline FIstream operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; }
        inline FIstream operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; }
        template<typename T>inline FIstream operator<<(T& a) { r(a); return{}; }
        inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } }
    }in;
    struct FOstream {
        inline FOstream operator<<(const int a) { w(a); return{}; }
        inline FOstream operator<<(const char ch) { pc(ch); return{}; }
        inline FOstream operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
        template<typename T>inline FOstream operator>>(const T a) { w(a); return{}; }
    }out;
}using fastIO::in; using fastIO::out;
#undef ds
int a[50004];
int b[50004];
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
vector<pii>sorted;
map<pair<pii,int>,int>mp;
void Main() {
    int n, m; in >> n >> m;
    sorted.reserve(n+1);
    for (int i = 1; i <= n; i++){
        in >> a[i];
        sorted.push_back({a[i],i});
    }sort(all(sorted));
    for (; m--;) {
        int opt; in >> opt;
        if (opt == 1) {
            int l, r, k; in >> l >> r >> k;
            int cnt = 1;
            for (int i = l; i <= r; i++)cnt += (a[i] < k);
            out << cnt << '\n';
        }
        else if (opt == 2) {
            int l, r, k; in >> l >> r >> k;
            pair<pii,int> x={{l,r},k};
            if(mp.find(x)!=mp.end())//不必要
                out<<mp[x]<<"\n";
            else if(r-l<10000){//不必要
                int len = r - l + 1;
                memcpy(b, a + l, len * sizeof(int)); 
                nth_element(b, b + k - 1, b + len);
                out << (mp[x]=b[k - 1]) << '\n';
            }else for(int i=0;i<n;i++){
                k-=(sorted[i].second<=r&&sorted[i].second>=l);
                if(!k){
                    out<<(mp[x]=sorted[i].first)<<'\n';
                    break;
                }
            }
        }
        else if (opt == 3) {
            int pos, x; in >> pos >> x;
            if(a[pos]==x)continue;
            mp.clear();
            int oldv=a[pos];
            a[pos]=x;
            auto it_old = lower_bound(all(sorted),make_pair(oldv,pos));
            sorted.erase(it_old);
            auto it_new = lower_bound(all(sorted),make_pair(x,pos));
            sorted.insert(it_new, {x,pos});
        }
        else if (opt == 4) {
            int ans = -2147483647;
            int l, r, x; in >> l >> r >> x;
            for (int i = l; i <= r; i++) {
                if (a[i] < x)ans = max(ans, a[i]);
            }
            out << ans << '\n';
        }
        else {
            int ans = 2147483647;
            int l, r, x; in >> l >> r >> x;
            for (int i = l; i <= r; i++) {
                if (a[i] > x)ans = min(ans, a[i]);
            }
            out << ans << '\n';
        }
    }
}
signed main() {
    Main();
    return 0;
}