1、题目大意：给你一个序列，有5种操作，都有什么呢。。。
1> 区间第k小 这个直接用二分+树套树做
2> 区间小于k的有多少 这个直接用树套树做
3> 单点修改 这个直接用树套树做
4> 区间内k的前驱 这个就是1和2操作的合并，就是查询k的排名，然后就是知道他的前驱的排名，然后第k小
5> 区间内k的后继 这个和4同理
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
Node *ch[2];
int num, cnt, v, r;
bool operator < (const Node& rhs) const{
return r < rhs.r;
}
inline int cmp(int x){
if(x == v) return -1;
if(x < v) return 0;
return 1;
}
inline void maintain(){
cnt = num;
if(ch[0]) cnt += ch[0] -> cnt;
if(ch[1]) cnt += ch[1] -> cnt;
return;
}
} ft[5000000], *root[400000];
int tot;
int a[100000];
inline void treap_rotate(Node* &o, int d){
Node *k = o -> ch[d ^ 1];
o -> ch[d ^ 1] = k -> ch[d];
k -> ch[d] = o;
o -> maintain();
k -> maintain();
o = k;
return;
}
inline void treap_insert(Node* &o, int value){
if(!o){
o = &ft[tot ++];
o -> ch[0] = o -> ch[1] = NULL;
o -> num = 1;
o -> v = value;
o -> r = rand();
}
else{
int d = o -> cmp(value);
if(d == -1){
o -> num ++;
}
else{
treap_insert(o -> ch[d], value);
if(o -> ch[d] > o) treap_rotate(o, d ^ 1);
}
}
o -> maintain();
}
inline void treap_remove(Node* &o, int value){
if(!o) return;
int d = o -> cmp(value);
if(d == -1){
if(o -> num > 1) o -> num --;
else if(!o -> ch[0]) o = o -> ch[1];
else if(!o -> ch[1]) o = o -> ch[0];
else{
int d2;
if(o -> ch[0] > o -> ch[1]) d2 = 1;
else d2 = 0;
treap_rotate(o, d2);
treap_remove(o -> ch[d2], value);
}
}
else{
treap_remove(o -> ch[d], value);
}
if(o) o -> maintain();
}
inline int treap_lessk(Node* &o, int k){
if(!o) return 0;
int d = o -> cmp(k);
if(d == -1){
int ret = o -> num;
if(o -> ch[0]) ret += o -> ch[0] -> cnt;
return ret;
}
else if(d == 0){
return treap_lessk(o -> ch[d], k);
}
else{
int ss = o -> num;
if(o -> ch[0]) ss += o -> ch[0] -> cnt;
return treap_lessk(o -> ch[d], k) + ss;
}
}
inline int treap_find(Node* &o, int k){
if(!o) return 0;
int d = o -> cmp(k);
if(d == -1) return o -> num;
else return treap_find(o -> ch[d], k);
}
inline int segment_tree_find(int l, int r, int o, int x, int y, int k){
if(x <= l && r <= y){
return treap_find(root[o], k);
}
int mid = (l + r) / 2;
int ret = 0;
if(x <= mid) ret += segment_tree_find(l, mid, 2 * o, x, y, k);
if(y > mid) ret += segment_tree_find(mid + 1, r, 2 * o + 1, x, y, k);
return ret;
}
inline void segment_tree_add(int l, int r, int o, int x, int value){
treap_remove(root[o], a[x]);
treap_insert(root[o], value);
if(l == r){
a[x] = value;
return;
}
int mid = (l + r) / 2;
if(x <= mid) segment_tree_add(l, mid, 2 * o, x, value);
else segment_tree_add(mid + 1, r, 2 * o + 1, x, value);
}
inline int segment_tree_query_lessk(int l, int r, int o, int x, int y, int k){
if(x <= l && r <= y){
return treap_lessk(root[o], k);
}
int mid = (l + r) / 2;
int ret = 0;
if(x <= mid) ret += segment_tree_query_lessk(l, mid, 2 * o, x, y, k);
if(y > mid) ret += segment_tree_query_lessk(mid + 1, r, 2 * o + 1, x, y, k);
return ret;
}
inline int segment_tree_query_NO_k(int l, int r, int o, int x, int y, int k, int n){
int L = 0, R = 100000000;
while(L < R){
int mid = (L + R) / 2;
if(segment_tree_query_lessk(1, n, 1, x, y, mid) < k) L = mid + 1;
else R = mid;
}
return L;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++){
int x;
scanf("%d", &x);
segment_tree_add(1, n, 1, i, x);
}
for(int i = 1; i <= m; i ++){
int op, x, y, z;
scanf("%d", &op);
if(op == 1){
scanf("%d%d%d", &x, &y, &z);
int ans = segment_tree_query_lessk(1, n, 1, x, y, z);
ans -= segment_tree_find(1, n, 1, x, y, z);
ans ++;
printf("%d\n", ans);
}
else if(op == 2){
scanf("%d%d%d", &x, &y, &z);
int ans = segment_tree_query_NO_k(1, n, 1, x, y, z, n);
printf("%d\n", ans);
}
else if(op == 3){
scanf("%d%d", &x, &y);
segment_tree_add(1, n, 1, x, y);
}
else if(op == 4){
scanf("%d%d%d", &x, &y, &z);
int k = segment_tree_query_lessk(1, n, 1, x, y, z);
k -= segment_tree_find(1, n, 1, x, y, z);
int ans = segment_tree_query_NO_k(1, n, 1, x, y, k, n);
printf("%d\n", ans);
}
else{
scanf("%d%d%d", &x, &y, &z);
int k = segment_tree_query_lessk(1, n, 1, x, y, z);
k ++;
int ans = segment_tree_query_NO_k(1, n, 1, x, y, k, n);
printf("%d\n", ans);
}
}
return 0;
}