注意upper_bound的使用方式，目前没时间调，你可以看看我写的pbds
```cpp
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define m_p(a, b) make_pair(a, b)
#define N 100010
using namespace std;
using namespace __gnu_pbds;
tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> tr[N << 1];
ll n, val[N], multimode = 1, tmax = 0, trm[N << 1];
void build(ll x, ll l, ll r){
if (l == r){
tr[x].insert(m_p(val[l], multimode++));
trm[x] = val[l];
return;
}
for (ll i = l; i <= r; i++)tr[x].insert(m_p(val[i], multimode++));
ll mid = l + r >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
trm[x] = max(trm[x << 1], trm[x << 1 | 1]);
}
ll rk_ask(ll k, ll x, ll y, ll l, ll r, pair<ll, ll> w){
if (x > r || y < l)return 0;
if (x >= l && y <= r)return tr[k].order_of_key(w);
ll mid = x + y >> 1, ans = 0;
if (l <= mid)ans += rk_ask(k << 1, x, mid, l, r, w);
if (r > mid)ans += rk_ask(k << 1 | 1, mid + 1, y, l, r, w);
return ans;
}
ll kth_num(ll l, ll r, ll k){
ll _l = 0, _r = tmax + 1, mid = _l + _r >> 1, ans, kt;
while (_l < _r){
kt = rk_ask(1, 1, n, l, r, m_p(mid, multimode + 1));
(kt < k) ? _l = mid + 1 : _r = mid;
mid = _l + _r >> 1;
}
return _l;
}
void tr_c(ll x, ll l, ll r, ll k, ll w,pair<ll,ll>cw){
if (l > k || r < k) return;
if (l == r && l == k){
trm[x] = w;
tr[x].erase(tr[x].begin());
tr[x].insert(m_p(w, ++multimode));
return;
}
ll mid = l + r >> 1;
tr[x].erase(tr[x].lower_bound(cw));
tr[x].insert(m_p(w, ++multimode));
(mid >= k) ? tr_c(x << 1, l, mid, k, w,cw) : tr_c(x << 1 | 1, mid + 1, r, k, w,cw);
trm[x] = max(trm[x << 1], trm[x << 1 | 1]);
}
ll mx(bool ty, ll a, ll b){
return ty ? ((a > b) ? a : b) : ((a < b) ? a : b);
}
ll pn_ask(ll k, ll x, ll y, ll l, ll r, ll w, bool ty){
if (x > r || y < l)return 0;
if (x >= l && y <= r){
auto it = tr[k].lower_bound(m_p(w, ty ? 0 : multimode + 1));
return ((ty ? --it : it) == tr[k].end()) ? (ty ? -2147483647 : INT_MAX) : (it->first);
}
ll mid = x + y >> 1, ans = ty ? -2147483647 : INT_MAX;
if (l <= mid) ans = mx(ty, pn_ask(k << 1, x, mid, l, r, w, ty), ans);
if (r > mid) ans = mx(ty, pn_ask(k << 1 | 1, mid + 1, y, l, r, w, ty), ans);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m, opt, l, r, k, ans;
cin >> n >> m;
for (ll i = 1; i <= n; i++){
cin >> val[i];
tmax = max(tmax, val[i]);
}
build(1, 1, n);
while (m--){
cin >> opt >> l >> r;
if (opt != 3){
cin >> k;
ans = (opt == 1) ? (rk_ask(1, 1, n, l, r, m_p(k, 0)) + 1) : ((opt == 2) ? (kth_num(l, r, k)) : (pn_ask(1, 1, n, l, r, k, (opt == 4))));
cout << ans << endl;
}
else{
tr_c(1, 1, n, l, r,m_p(val[l], 0));
tmax = trm[1];
val[l] = r;
}
}
return 0;
}
```
by _WRYYY_ @ 2023-10-31 17:36:31