Treap基本用法总结

Treap=Tree+Heap  起名的人非常有才

Treap是啥？

一棵二叉搜索树可能退化成链，那样各种操作的效率都比较低

于是可爱的Treap在每个节点原先值v的基础上加了一个随机数rnd，树的形态要满足是rnd的大根堆或小根堆

可以说是普通BST的进化版吧。

Q：为什么rnd要满足是大根堆或小根堆，不能是二叉搜索树吗？

A：不能！二叉搜索树旋转时一直满足是二叉搜索树，也就是说值与值之间的相对顺序不管怎么转都是一定的。Treap本身就是二叉搜索树，在每插入一个新节点时，该节点在二叉搜索树中的相对位置是一定的。根据v而插入的位置，若此时rnd不满足二叉搜索树，那怎么旋转都无法满足是rnd的二叉搜索树。

Q：那为什么rnd可满足大根堆或小根堆呢？

A：以大根堆为例。用类似循环不定式证明。

i)假设在插入一个点前树的形态已满足是rnd的大根堆。按照v先将这个点p插到treap中，如果v比其父节点pa的rnd值大，就把p旋转到pa的位置。pa旋到下面后，连上了p的一个子节点son。因为原来rnd满足大根堆，那么pa的rnd一定大于son的rnd，此时p及其子树满足是rnd的大根堆。以此类推不断把p向上旋转，直到p的rnd小于pa的rnd。此时整棵树满足是rnd的大根堆，也就满足treap的要求

ii)当只有一个节点时，显然满足treap要求

Treap基本操作

维护一个有序序列，支持插入、删除，询问前驱后继、排名，区间加减等

Treap V.S. Splay

不像splay用起来那样方便，也没有splay像reverse之类的操作，但是比较好写，常数也稍微小一点

Treap V.S. 红黑树

跟红黑树相比，红黑树的效率更稳定（毕竟Treap有随机数），但红黑树写起来太过复杂。

用STL的set很方便，但不能查排名等信息

模板（洛谷P3369）

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #define INF 100000007
 #define P1 39916801
 #define P2 4987657
 using namespace std;

 typedef long long ll;
 const int N = ;
 struct node{
     int v,rnd,size;
     node *ch[],*pa;
 }pool[N];
 int cnt;

 int rr;
 int Getrnd(){  //生成随机数
     rr=((ll)rr*P1)%P2;
     return rr;
 }

 struct treap{
     node *root,*rf;
     int size(node *p){
         return p?p->size:;
     }
     void update(node *p){
         p->size=size(p->ch[])+size(p->ch[])+;
     }
     void rotate(node *p,int t){
         node *son=p->ch[!t],*pa=p->pa,*gp=p->pa->pa;
         pa->ch[t]=son;
         if(son) son->pa=pa;
         p->ch[!t]=pa;
         pa->pa=p;
         p->pa=gp;
         gp->ch[pa==gp->ch[]]=p;
         if(root==pa) root=p;
         update(pa);update(p);
     }
     void insert(node *p,node *nd){
         int f=p->v<nd->v?:;
         if(!p->ch[f]){
             p->ch[f]=nd;
             nd->pa=p;
         }
         else insert(p->ch[f],nd);
         update(p);
         if(p->ch[f]->rnd>p->rnd) rotate(p->ch[f],f);
     }
     void Ins(int v){
         node *nd=&pool[++cnt];
         nd->v=v;nd->size=;nd->rnd=Getrnd();
         nd->pa=nd->ch[]=nd->ch[]=NULL;
         if(root) insert(root,nd);
         else{
             root=nd;
             root->pa=rf;
             rf->ch[]=root;
         }
     }
     void del(node *p,int v){ //删除 注意向上更新处容易写错
         if(p->v==v){
             if(!p->ch[] || !p->ch[]){
                 node *pa=p->pa,*son=p->ch[p->ch[]?:];
                 pa->ch[p==pa->ch[]]=son;
                 if(son) son->pa=pa;
                 if(p==root) root=son;
                 while(pa)
                     update(pa),pa=pa->pa;
             }
             else{
                 int f=p->ch[]->rnd>p->ch[]->rnd?:;
                 rotate(p->ch[f],f);del(p,v);
             }
         }
         else del(p->ch[v>p->v],v);
     }
     int rank(node *p,int v){ //比v小的节点个数
         if(!p) return ;
         if(p->v<v) return +size(p->ch[])+rank(p->ch[],v);
         else return rank(p->ch[],v);
     }
     int find(node *p,int k){ //询问排名第k的节点值
         if(size(p->ch[])>=k) return find(p->ch[],k);
         if(size(p->ch[])==k-) return p->v;
         return find(p->ch[],k-size(p->ch[])-);
     }
     int pre(node *p,int v){//前驱
         if(!p) return -INF;
         if(v>p->v) return max(p->v,pre(p->ch[],v));
         else return pre(p->ch[],v);
     }
     int sub(node *p,int v){//后继
         if(!p) return INF;
         if(v<p->v) return min(p->v,sub(p->ch[],v));
         else return sub(p->ch[],v);
     }
     void inorder(node *p){
         if(p->ch[]) inorder(p->ch[]);
         printf("%d ",p->v);
         if(p->ch[]) inorder(p->ch[]);
     }
 }tr;

 int main()
 {
     int n,opt,x;
     scanf("%d",&n);

     tr.rf=&pool[++cnt];
     while(n--){
         scanf("%d%d",&opt,&x);
         switch(opt){
             case :tr.Ins(x);break;//插入
             case :tr.del(tr.root,x);break;//删除
             case :printf("%d\n",tr.rank(tr.root,x)+);break;//某数排名=比该数小的个数+1
             case :printf("%d\n",tr.find(tr.root,x));break;//排名x的数
             case :printf("%d\n",tr.pre(tr.root,x));break;//前驱
             case :printf("%d\n",tr.sub(tr.root,x));break;//后继
             default:break;
         }
     }

     return ;
 }

应用

·普通应用

i)bzoj3173 最长上升子序列

Description

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

Input

第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

Output

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

Sample Input

3
0 0 2

Sample Output

1
1
2

HINT

100%的数据 n<=100000

代码：（这是几个月前写的，代码风格不太一样）

 #include<cstdio>
 #include<cstdlib>
 #include<iostream>
 #include<algorithm>
 #include<string.h>
 #define INF 2147483647
 using namespace std;

 const int MAXN=;
 struct node
 {
     int size,d,rnd;
     node *parent,*lson,*rson;
 }pool[MAXN],*root;
 int cnt,cnt1,n;
 int c[MAXN],dp[MAXN],ans[MAXN];

 void update(node *p)
 {
     p->size=;
     if(p->lson) p->size+=p->lson->size;
     if(p->rson) p->size+=p->rson->size;
 }

 void right_rotate(node *p)
 {
     node *lson=p->lson,*parent=p->parent,*gp=p->parent->parent;
     parent->rson=lson;
     if(lson) lson->parent=parent;
     p->lson=parent;parent->parent=p;
     p->parent=gp;
     if(gp)
     {
         if(parent==gp->lson) gp->lson=p;
         else gp->rson=p;
     }
     else root=p;
     update(parent);
     update(p);
 }

 void left_rotate(node *p)
 {
     node *rson=p->rson,*parent=p->parent,*gp=p->parent->parent;
     parent->lson=rson;
     if(rson) rson->parent=parent;
     p->rson=parent;parent->parent=p;
     p->parent=gp;
     if(gp)
     {
         if(parent==gp->lson) gp->lson=p;
         else gp->rson=p;
     }
     else root=p;
     update(parent);
     update(p);
 }

 int size(node *p)
 {
     if(p==NULL) return ;
     return p->size;
 }

 void insert(node *p,node *newnode,int rank)
 {
     if(size(p->lson)+>=rank)
     {
         if(p->lson==NULL)
         {
             p->lson=newnode;
             newnode->parent=p;
             p->size++;
             return;
         }
         insert(p->lson,newnode,rank);
         p->size++;
         if(p->lson->rnd>p->rnd) left_rotate(p->lson);
     }
     else
     {
         if(p->rson==NULL)
         {
             p->rson=newnode;
             newnode->parent=p;
             p->size++;
             return;
         }
         insert(p->rson,newnode,rank-size(p->lson)-);
         p->size++;
         if(p->rson->rnd>p->rnd) right_rotate(p->rson);
     }
 }

 int main()
 {
     int i,a,j;
     node *tmp;
     scanf("%d",&n);
     srand();
     for(i=;i<=n;i++)
     {
         scanf("%d",&a);
         tmp=&pool[++cnt];
         tmp->d=i;
         srand(rand()%);
         tmp->rnd=rand()%;
         tmp->size=;
         if(i==) root=tmp;
         else insert(root,tmp,++a);
     }

     cnt1=;
     memset(dp,,sizeof(dp));
     int len=,t;
     dp[]=-INF;
     for(i=;i<=n;i++)
     {
         t=upper_bound(dp,dp+len+,c[i])-dp;
         if(dp[t-]<=c[i])
         {
             dp[t]=min(dp[t],c[i]);
             ans[c[i]]=t;
             len=max(len,t);
         }
     }

     ans[]=;
     for(i=;i<=n;i++)
     {
         ans[i]=max(ans[i],ans[i-]);
         printf("%d\n",ans[i]);
     }

     return ;
 }

ii) noip2017提高day2-3 列队

（洛谷P3960）

n行以及最后一列各维护一个treap（这样共n+1个），反着来考虑，把每次出队的人加会队列

需要注意的是每行最后一列的要加到第n+1个treap中

细节还挺多的，要想清楚

代码：

 #include<cstdio>
 #include<iostream>
 #include<algorithm>
 #define P1 39916801
 #define P2 4987657
 using namespace std;

 typedef long long ll;
 const int N = ;

 int rr=;
 int Get_rnd(){
     rr=((ll)rr*P2)%P1;
     return rr;
 }

 struct node{
     int v,rnd,id,lazy,size;
     node *pa,*ch[];
 }pool[*N],*tmp,*num[N];
 int cnt;

 struct treap{
     node *root,*rf;
     int size(node *p){
         if(p) return p->size;
         return ;
     }
     void update(node *p){
         p->size=+size(p->ch[])+size(p->ch[]);
     }
     void pushdown(node *p){
         if(p->lazy){
             p->v+=p->lazy;
             if(p->ch[]) p->ch[]->lazy+=p->lazy;
             if(p->ch[]) p->ch[]->lazy+=p->lazy;
             p->lazy=;
         }
     }
     void rotate(node *p,int t){
         node *son=p->ch[!t],*pa=p->pa,*gp=p->pa->pa;
         pa->ch[t]=son;
         if(son) son->pa=pa;
         pa->pa=p;
         p->ch[!t]=pa;
         p->pa=gp;
         gp->ch[pa==gp->ch[]]=p;
         if(pa==root) root=p;
         update(pa);update(p);
     }
     void insert(node *p,node *nd,int t){
         pushdown(p);
         int f=;
         if(nd->v>p->v) f=;
         if(p->ch[f]==NULL){
             p->ch[f]=nd;
             nd->pa=p;
             nd->size=;nd->lazy=;
         }
         else insert(p->ch[f],nd,t);
         update(p);
         if(f== && t==){
             p->v++;
             if(p->ch[]) p->ch[]->lazy++;
         }
         if(p->ch[f]->rnd>p->rnd) rotate(p->ch[f],f);
     }
     void Ins(node *nd,int t){
         if(root==NULL){
             root=nd;
             root->pa=rf;
             rf->ch[]=root;
         }
         else insert(root,nd,t);
     }
     void add(node *p,int v){
         pushdown(p);
         if(p->v>=v) {
             p->v++;
             if(p->ch[]) p->ch[]->lazy++;
             if(p->ch[]) add(p->ch[],v);
         }
         else if(p->ch[]) add(p->ch[],v);
     }
     void del(node *p){
         pushdown(p);
         if(p->ch[]) del(p->ch[]);
         else{
             node *son=p->ch[],*pa=p->pa;
             pa->ch[]=son;/**/
             if(son) son->pa=pa;
             if(root==p) root=son;
         }
         update(p);
     }
     node *last(node *p){
         pushdown(p);
         if(p->ch[]) return last(p->ch[]);
         return p;
     }
     void update_all(node *p){
         pushdown(p);
         if(p->ch[]) update_all(p->ch[]);
         if(p->ch[]) update_all(p->ch[]);
     }
     void inorder(node *p){
         pushdown(p);
         if(p->ch[]) inorder(p->ch[]);
         printf("%d ",p->v);
         if(p->ch[]) inorder(p->ch[]);
     }
 }tr[N];

 int n,m,Q;
 int xx[N],yy[N];

 int main()
 {
     int i,j;
     scanf("%d%d%d",&n,&m,&Q);
     for(i=;i<=Q;i++)
         scanf("%d%d",&xx[i],&yy[i]);

     for(i=;i<=n+;i++)
         tr[i].rf=&pool[++cnt];

     for(i=Q;i>;i--){
         if(tr[n+].root && tr[n+].last(tr[n+].root)->v==n){
             tmp=tr[n+].last(tr[n+].root);
             tr[n+].del(tr[n+].root);
         }
         else tmp=&pool[++cnt];

         tmp->v=yy[i];tmp->id=xx[i];
         tmp->size=;tmp->lazy=;
         tmp->ch[]=tmp->ch[]=tmp->pa=NULL;
         tmp->rnd=Get_rnd();
         tr[xx[i]].Ins(tmp,);

         num[i]=tmp;
         if(tr[n+].root) tr[n+].add(tr[n+].root,xx[i]);

         tmp=tr[xx[i]].last(tr[xx[i]].root);
         if(tmp->v==m){
             tr[xx[i]].del(tr[xx[i]].root);
             tmp->v=xx[i];tmp->id=n+;
             tmp->size=;tmp->lazy=;
             tmp->ch[]=tmp->ch[]=tmp->pa=NULL;
             tmp->rnd=Get_rnd();
             tr[n+].Ins(tmp,);
         }
     }

     ll ret=;
     for(i=;i<=n+;i++)
         if(tr[i].root) tr[i].update_all(tr[i].root);
     for(i=;i<=Q;i++){
         ret=;
         if(num[i]->id==n+)
             ret=(ll)num[i]->v*m;
         else
             ret=((ll)num[i]->id-)*m+num[i]->v;
         printf("%lld\n",ret);/**/
     }

     return ;
 }

·树套树

i)三维偏序

树状数组套treap，树状数组每个点后都建一棵treap

洛谷P3810 （代码微丑，多多包涵 + 这是一周前写的，代码风格也略微不一样）

 #include<cstdio>
 #include<iostream>
 #include<cstdlib>
 #include<algorithm>
 #include<string.h>
 #define P1 39916801
 #define P2 4987657
 using namespace std;

 typedef long long ll;
 const int N = ;
 struct data{
     int a,b,c;
     int flag,num;
     bool operator < (const data &x){
         if(a!=x.a) return x.a<a;
         if(b!=x.b) return x.b<b;
         return x.c<c;
     }
 }d[N];
 int ans[N],n;
 int dd[N];
 bool cmp1(int x,int y){
     return d[x].a<d[y].a;
 }
 bool cmp2(int x,int y){
     return d[x].b<d[y].b;
 }
 bool cmp3(int x,int y){
     return d[x].c<d[y].c;
 }
 bool cmp(data x,data y){
     return y<x;
 }
 int lowbit(int x){
     return x&(-x);
 }

 int rr=;
 int Getrnd(){
     rr=((ll)rr*P1)%P2;
     return rr;
 }

 struct node{
     int v,rnd,id;
     int size;
     node *parent,*ch[];
 }pool[*N],*root[N];
 int cnt;
 int size(node *p){
     if(p) return p->size;
     return ;
 }
 void update(node *p){
     p->size=size(p->ch[])+size(p->ch[])+;
 }
 void rotate(node *p,int type){
     node *son=p->ch[!type],*parent=p->parent,*gp=p->parent->parent;
     parent->ch[type]=son;
     if(son) son->parent=parent;
     p->ch[!type]=parent;
     parent->parent=p;
     p->parent=gp;
     if(gp) gp->ch[parent==gp->ch[]]=p;
     else root[p->id]=p;
     update(parent);
     update(p);
 }
 void insert(node *p,node *newnode){
     int f=;
     if(newnode->v>p->v) f=;
     if(p->ch[f]==NULL){
         p->ch[f]=newnode;
         newnode->size=;
         newnode->parent=p;
     }
     else insert(p->ch[f],newnode);
     update(p);
     if(p->ch[f]->rnd>p->rnd) rotate(p->ch[f],f);
 }
 int find(node *p,int key){
     int ret=;
     if(p->v<=key){
         ret=ret++size(p->ch[]);
         if(p->ch[]) ret+=find(p->ch[],key);
     }
     else {
         if(p->ch[]) ret+=find(p->ch[],key);
     }
     return ret;
 }
 int Getans(int x){
     int ret=,y;
     y=d[x].b;
     while(y>){
         if(root[y]) ret+=find(root[y],d[x].c);
         y-=lowbit(y);
     }
     return ret;
 }
 void add(int x){
     int y=d[x].b;
     while(y<=n){
         node *newnode=&pool[++cnt];
         newnode->v=d[x].c;newnode->size=;newnode->id=y;
         newnode->rnd=Getrnd();
         if(root[y]) insert(root[y],newnode);
         else root[y]=newnode;
         y+=lowbit(y);
     }
 }

 int main()
 {
     int k,i,j,tot,pre;
     scanf("%d%d",&n,&k);
     for(i=;i<=n;i++){
         scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c);
         dd[i]=i;
     }
     sort(dd+,dd++n,cmp1);
     tot=;
     pre=d[dd[]].a;d[dd[]].a=tot;
     for(i=;i<=n;i++){
         if(pre!=d[dd[i]].a) tot++;
         pre=d[dd[i]].a;
         d[dd[i]].a=tot;
     }
     sort(dd+,dd++n,cmp2);
     tot=;
     pre=d[dd[]].b;d[dd[]].b=tot;
     for(i=;i<=n;i++){
         if(pre!=d[dd[i]].b) tot++;
         pre=d[dd[i]].b;
         d[dd[i]].b=tot;
     }
     sort(dd+,dd++n,cmp3);
     tot=;
     pre=d[dd[]].c;d[dd[]].c=tot;
     for(i=;i<=n;i++){
         if(pre!=d[dd[i]].c) tot++;
         pre=d[dd[i]].c;
         d[dd[i]].c=tot;
     }
     sort(d+,d++n,cmp);

     for(i=;i<=n;i++){
         j=;
         while(i<n && d[i].a==d[i+].a && d[i].b==d[i+].b && d[i].c==d[i+].c)
             i++,j++;
         d[i].flag=;d[i].num=j;
     }

     for(i=;i<=n;i++){
         if(d[i].flag==) ans[Getans(i)]+=d[i].num;
         add(i);
     }

     for(i=;i<n;i++)
         printf("%d\n",ans[i]);

     return ;
 }

ii)二逼平衡树 bzoj3196

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行，表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围：n,m<=50000

2.序列中每个数的数据范围：[0,1e8]

3.虽然原题没有，但事实上5操作的k可能为负数

线段树+treap，同样每一个节点后建一棵treap

 #include<cstdio>
 #include<iostream>
 #include<algorithm>
 #define P1 39916801
 #define P2 4987657
 using namespace std;

 typedef long long ll;
 const int N = ;
 struct node{
     int v,rnd,size;
     node *pa,*ch[];
 }pool[*N];
 int cnt,a[N];

 int rr=;
 int Get_rnd(){
     rr=((((ll)rr*P2)%P1)*P1)%P2;
     return rr;
 }

 struct treap{
     node *root,*rf;
     int size(node *p){
         if(p) return p->size;
         return ;
     }
     void update(node *p){
         p->size=+size(p->ch[])+size(p->ch[]);
     }
     void rotate(node *p,int t){
         node *son=p->ch[!t],*pa=p->pa,*gp=pa->pa;
         pa->ch[t]=son;
         if(son) son->pa=pa;
         p->ch[!t]=pa;
         pa->pa=p;
         p->pa=gp;
         gp->ch[pa==gp->ch[]]=p;
         if(pa==root) root=p;
         update(pa);update(p);
     }
     void insert(node *p,node *nd){
         int f=;
         if(nd->v>p->v) f=;
         if(p->ch[f]==NULL){
             p->ch[f]=nd;
             nd->pa=p;
         }
         else insert(p->ch[f],nd);
         update(p);
         if(p->ch[f]->rnd>p->rnd) rotate(p->ch[f],f);
     }
     node *find(node *p,int k){
         if(p->v>k) return find(p->ch[],k);
         else if(p->v==k) return p;
         else return find(p->ch[],k);
     }
     node *del(node *p,int v){/**/
         if(v==p->v){
             if(!p->ch[] || !p->ch[]){
                 int f=;
                 if(p->ch[]) f=;
                 node *son=p->ch[f],*pa=p->pa;
                 pa->ch[p==pa->ch[]]=son;
                 if(son) son->pa=pa;
                 if(root==p) root=son;
                 node *q=pa;
                 while(q!=NULL)
                     update(q),q=q->pa;
                 return p;
             }
             else {
                 int f=;
                 if(p->ch[]->rnd<p->ch[]->rnd) f=;
                 rotate(p->ch[f],f);
                 return del(p,v);
             }
         }
         else if(v<p->v) {
             node *q=del(p->ch[],v);
             return q;
         }
         else {
             node *q=del(p->ch[],v);
             return q;
         }
     }
     void remove(int x,int y){
         node *p=del(root,x);
         p->v=y;p->size=;
         p->pa=NULL;p->ch[]=NULL;p->ch[]=NULL;
         if(root) insert(root,p);/**/
         else{
             root=p;
             rf->ch[]=root;
             root->pa=rf;
         }
     }
     int rank(node *p,int v){
         int ret=;
         if(p->v<v){
             ret+=+size(p->ch[]);
             if(p->ch[]) ret+=rank(p->ch[],v);
         }
         else if(p->ch[]) ret+=rank(p->ch[],v);
         return ret;
     }
     int sub(node *p,int v){
         int ret=;
         if(p->v>v){
             ret=min(ret,p->v);
             if(p->ch[]) ret=min(ret,sub(p->ch[],v));
         }
         else if(p->ch[]) ret=min(ret,sub(p->ch[],v));
         return ret;
     }
     int pre(node *p,int v){
         int ret=-;
         if(p->v<v){
             ret=max(ret,p->v);
             if(p->ch[]) ret=max(ret,pre(p->ch[],v));
         }
         else if(p->ch[]) ret=max(ret,pre(p->ch[],v));
         return ret;
     }
     void inorder(node *p){
         if(p->ch[]) inorder(p->ch[]);
         printf("%d ",p->v);
         if(p->ch[]) inorder(p->ch[]);
     }
 };

 struct tree{
     int l,r;
     treap tr;
     tree *left,*right;
 }pool2[N*],*rt;
 int cnt2;
 void Build(tree *p,int l,int r){
     p->l=l;p->r=r;
     node *tmp=&pool[++cnt];p->tr.rf=tmp;
     if(l==r) return;
     int mid=(l+r)/;
     p->left=&pool2[++cnt2];p->right=&pool2[++cnt2];
     Build(p->left,l,mid);
     Build(p->right,mid+,r);
 }
 int q_rank(tree *p,int l,int r,int x){
     if(p->l==l && p->r==r){
         return p->tr.rank(p->tr.root,x);
     }
     if(p->left->r>=r) return q_rank(p->left,l,r,x);
     else if(p->right->l<=l) return q_rank(p->right,l,r,x);
     else return q_rank(p->left,l,p->left->r,x)+q_rank(p->right,p->right->l,r,x);
 }
 int q_pre(tree *p,int l,int r,int x){
     if(p->l==l && p->r==r)
         return p->tr.pre(p->tr.root,x);
     if(p->left->r>=r) return q_pre(p->left,l,r,x);
     else if(p->right->l<=l) return q_pre(p->right,l,r,x);
     else return max(q_pre(p->left,l,p->left->r,x),q_pre(p->right,p->right->l,r,x));
 }
 int q_sub(tree *p,int l,int r,int x){
     if(p->l==l && p->r==r)
         return p->tr.sub(p->tr.root,x);
     if(p->left->r>=r) return q_sub(p->left,l,r,x);
     else if(p->right->l<=l) return q_sub(p->right,l,r,x);
     else return min(q_sub(p->left,l,p->left->r,x),q_sub(p->right,p->right->l,r,x));
 }
 void add(tree *p,int l,int x){
     node *tmp=&pool[++cnt];
     tmp->v=x;tmp->size=;tmp->rnd=Get_rnd();
     if(p->tr.root!=NULL) p->tr.insert(p->tr.root,tmp);
     else {
         p->tr.root=tmp;
         p->tr.rf->ch[]=p->tr.root;
         p->tr.root->pa=p->tr.rf;
     }
     if(p->l==l && p->r==l) return;
     if(p->right->l<=l) add(p->right,l,x);
     else add(p->left,l,x);
 }
 void change(tree *p,int l,int x){
     p->tr.remove(a[l],x);
     if(p->l==l && p->r==l) return;
     if(p->right->l<=l) change(p->right,l,x);
     else change(p->left,l,x);
 }

 int main()
 {
     int n,m,i,opt,x,y,z,l,r,mid;
     scanf("%d%d",&n,&m);
     for(i=;i<=n;i++) scanf("%d",&a[i]);

     //build
     rt=&pool2[++cnt2];
     Build(rt,,n);
     for(i=;i<=n;i++)
         add(rt,i,a[i]);

     while(m--){
         scanf("%d",&opt);
         if(opt==){
             scanf("%d%d%d",&x,&y,&z);
             printf("%d\n",q_rank(rt,x,y,z)+);
         }
         else if(opt==){
             scanf("%d%d%d",&x,&y,&z);
             l=;r=1e8;
             while(l<r){
                 mid=(l+r+)/;
                 if(q_rank(rt,x,y,mid)+<=z) l=mid;
                 else r=mid-;
             }
             printf("%d\n",l);
         }
         else if(opt==){
             scanf("%d%d",&x,&y);
             change(rt,x,y);
             a[x]=y;
         }
         else if(opt==){
             scanf("%d%d%d",&x,&y,&z);
             printf("%d\n",q_pre(rt,x,y,z));
         }
         else{
             scanf("%d%d%d",&x,&y,&z);
             printf("%d\n",q_sub(rt,x,y,z));
         }
     }

     return ;
 }