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可能为负数

Solution

板子题也没啥好写的……找个好看点的板子比如我的抄抄吧

Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #define N (3000000+100)  5 using namespace std;  6   7 int Root[N],sz,Father[N],Son[N][2];  8 int Cnt[N],Val[N],Size[N];  9 int n,m,a[N],Ans,maxn; 10  11 inline int read() 12 { 13     int x=0,f=1;char ch=getchar(); 14     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();} 15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16     return x*f; 17 } 18  19 struct Splay_Tree 20 { 21     int Get(int x) { return Son[Father[x]][1]==x; } 22     void Update(int x) { Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+Cnt[x]; } 23     void New(int x) { ++sz; Size[sz]=1; Val[sz]=x; Cnt[sz]=1; } 24     void Clear(int x) { Size[x]=Father[x]=Son[x][0]=Son[x][1]=Cnt[x]=Val[x]=0; } 25     int Pre(int Root) { int now=Son[Root][0]; while (Son[now][1]) now=Son[now][1]; return now; } 26     int Next(int Root) { int now=Son[Root][1]; while (Son[now][0]) now=Son[now][0]; return now; } 27      28     void Rotate(int x) 29     { 30         int wh=Get(x),fa=Father[x],fafa=Father[fa]; 31         if (fafa) Son[fafa][Son[fafa][1]==fa]=x; 32         Father[fa]=x; Son[fa][wh]=Son[x][wh^1]; 33         if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 34         Father[x]=fafa; Son[x][wh^1]=fa; 35         Update(fa); Update(x); 36     } 37     void Splay(int &Root,int x) 38     { 39         for (int fa;fa=Father[x];Rotate(x)) 40             if (Father[fa]) 41                 Rotate(Get(fa)==Get(x)?fa:x); 42         Root=x; 43     }  44     int Findx(int &Root,int x) 45     { 46         int now=Root; 47         while (1) 48             if (x<=Size[Son[now][0]]) 49                 now=Son[now][0]; 50             else 51             { 52                 if (x<=Cnt[now]) 53                 { 54                     Splay(Root,now); 55                     return now; 56                 } 57                 x-=Cnt[now]; 58                 now=Son[now][1]; 59             } 60     } 61     int Find(int &Root,int x) 62     { 63         int now=Root,ans=0; 64         while (1) 65         { 66             if (!now) return ans; 67             if (x
         
          Val[now]]; 90             if (now==0){ New(x); Father[sz]=fa; Son[fa][x>Val[fa]]=sz; Splay(Root,sz); return; } 91         } 92     } 93     void Delete(int &Root,int x) 94     { 95         Find(Root,x); 96         if (Cnt[Root]>1) { Cnt[Root]--; Update(Root); return; } 97         if (!Son[Root][0] && !Son[Root][1]) { Clear(Root); Root=0; return; } 98         if (!Son[Root][1]) { Root=Son[Root][0]; Clear(Father[Root]); Father[Root]=0; return; } 99         if (!Son[Root][0]) { Root=Son[Root][1]; Clear(Father[Root]); Father[Root]=0; return; }100         101         int oldroot=Root,pre=Pre(Root);102         Splay(Root,pre);103         Son[Root][1]=Son[oldroot][1];104         Father[Son[oldroot][1]]=Root;105         Clear(oldroot);106         Update(Root);107     }108 };109 110 struct Segt_Tree111 {112     Splay_Tree Splay[200001];113     void Get_rank(int node,int l,int r,int l1,int r1,int k)114     {115         if (l>r1 || r
          
           >1;122         Get_rank(node<<1,l,mid,l1,r1,k);123         Get_rank(node<<1|1,mid+1,r,l1,r1,k);124     }125     void Update(int node,int l,int r,int x,int k)126     {127         Splay[node].Delete(Root[node],a[x]);128         Splay[node].Insert(Root[node],k);129         if (l==r) return;130         int mid=(l+r)>>1;131         if (x<=mid) Update(node<<1,l,mid,x,k);132         else Update(node<<1|1,mid+1,r,x,k);133     }134     void Pre(int node,int l,int r,int l1,int r1,int k)135     {136         if (l>r1 || r
           
            >1;146 Pre(node<<1,l,mid,l1,r1,k);147 Pre(node<<1|1,mid+1,r,l1,r1,k);148 }149 void Next(int node,int l,int r,int l1,int r1,int k)150 {151 if (l>r1 || r
            
             >1;161 Next(node<<1,l,mid,l1,r1,k);162 Next(node<<1|1,mid+1,r,l1,r1,k);163 }164 void Ins(int node,int l,int r,int x,int k)165 {166 Splay[node].Insert(Root[node],k);167 if (l==r) return;168 int mid=(l+r)>>1;169 if (x<=mid) Ins(node<<1,l,mid,x,k);170 else Ins(node<<1|1,mid+1,r,x,k);171 }172 }T;173 174 int main()175 {176 n=read(),m=read();177 for (int i=1; i<=n; ++i)178 a[i]=read(),maxn=max(maxn,a[i]),T.Ins(1,1,n,i,a[i]);179 int opt,l,r,k,pos;180 for (int i=1; i<=m; ++i)181 {182 opt=read();183 switch(opt)184 {185 case 1:186 {187 l=read(),r=read(),k=read();188 Ans=0;189 T.Get_rank(1,1,n,l,r,k);190 printf("%d\n",Ans+1);191 break;192 }193 case 2:194 {195 l=read(),r=read(),k=read();196 int L=0,R=maxn;197 while (L
             
              >1;200 Ans=0;201 T.Get_rank(1,1,n,l,r,mid);202 if (Ans