题目：

第一道的树套树。

线段树套平衡树。找了一个当模板。感觉还好啦。但跑得很慢。卡时过了。

1.好神奇呀，竟然都要加-INF和INF。别忘了求siz时-1；

2.去右儿子找的时候别忘了减去左儿子和自己的siz；

3.凡是有splay的地方就别忘了 & ；

4.想要 < 的就把它放在return y?y：cr里，想要 <= 的也就把它放在那个地方，大约就是这样就行；

5.线段树的 tt 别和Splay的 tot 混用，不然线段树节点的数组就得……

6.2e6是怎么算的呀？1e6为什么不行？

#include
     
      #include
      
       #include
       
        using namespace std;const int N=5e4+5,M=2e6+5,INF=1e9;int n,m,t[N],tot,tt,fa[M],c[M][2],val[M],siz[M];//struct Node{    int l,r,ls,rs,rt;}a[N<<1];void updt(int cr){    siz[cr]=siz[c[cr][0]]+siz[c[cr][1]]+1;}void rotate(int x,int &rt){    int y=fa[x],z=fa[y],d=(x==c[y][1]);    if(y==rt)rt=x;    else c[z][y==c[z][1]]=x;    fa[y]=x;fa[x]=z;fa[c[x][!d]]=y;    c[y][d]=c[x][!d];c[x][!d]=y;    updt(y);updt(x);}void splay(int x,int &rt){    while(x!=rt)    {        int y=fa[x],z=fa[y];        if(y!=rt)        {            if((x==c[y][0])^(y==c[z][0]))rotate(x,rt);            else rotate(y,rt);        }        rotate(x,rt);    }}int find_k(int cr,int x){    if(siz[c[cr][0]]==x-1)return cr;    if(siz[c[cr][0]]>=x)return find_k(c[cr][0],x);    return find_k(c[cr][1],x-c[cr][0]-1);}int find_pre(int cr,int x){    if(!cr)return 0;    if(val[cr]>=x)return find_pre(c[cr][0],x);    int y=find_pre(c[cr][1],x);    return y?y:cr;}void insert(int &rt,int x){    int y=find_pre(rt,x);splay(y,rt);    y=find_k(c[rt][1],1);splay(y,c[rt][1]);    fa[++tot]=y;c[y][0]=tot;siz[tot]=1;val[tot]=x;    updt(y);updt(rt);}void del(int &rt,int x){    int y=find_pre(rt,x);splay(y,rt);    y=find_k(c[rt][1],2);splay(y,c[rt][1]);    fa[c[y][0]]=0;c[y][0]=0;    updt(y);updt(rt);}void build(int l,int r,int cr){    a[cr].l=l;a[cr].r=r;a[cr].rt=++tot;    fa[tot]=0;c[tot][1]=tot+1;c[tot][0]=0;val[tot]=-INF;siz[tot]=2;    fa[++tot]=tot-1;c[tot][1]=c[tot][0]=0;val[tot]=INF;siz[tot]=1;    for(int i=l;i<=r;i++)insert(a[cr].rt,t[i]);    if(l==r)return;    int mid=((l+r)>>1);    a[cr].ls=++tt;build(l,mid,tt);    a[cr].rs=++tt;build(mid+1,r,tt);}int find_Suc(int rt,int x)    //Suc表示找的不是正常后继(>=){    if(!rt)return 0;    if(val[rt]
        
         =L&&a[cr].r<=R)return query_rnk(a[cr].rt,x);    int mid=((a[cr].l+a[cr].r)>>1),ret=0;    if(mid>=L)ret+=query_rnk(L,R,a[cr].ls,x);    if(mid
         
          =L&&a[cr].r<=R)return query_Rnk(a[cr].rt,x);    int mid=((a[cr].l+a[cr].r)>>1),ret=0;    if(mid>=L)ret+=query_Rnk(L,R,a[cr].ls,x);    if(mid
          
           >1); if(P<=mid)mdfy(P,a[cr].ls,x); else mdfy(P,a[cr].rs,x);}int query_pre(int L,int R,int cr,int x){ if(a[cr].l>=L&&a[cr].r<=R)return val[find_pre(a[cr].rt,x)]; int ret=-INF,mid=((a[cr].l+a[cr].r)>>1); if(mid>=L)ret=max(ret,query_pre(L,R,a[cr].ls,x)); if(mid
           
            =L&&a[cr].r<=R)return val[find_suc(a[cr].rt,x)]; int ret=INF,mid=((a[cr].l+a[cr].r)>>1); if(mid>=L)ret=min(ret,query_suc(L,R,a[cr].ls,x)); if(mid
            
             >1); if(query_Rnk(x,y,1,mid)>=k)ans=mid,r=mid-1;//不+1：包含了全部==自己的 else l=mid+1; } printf("%d\n",ans); } if(op==3)mdfy(x,1,y),t[x]=y; if(op==4)printf("%d\n",query_pre(x,y,1,k)); if(op==5)printf("%d\n",query_suc(x,y,1,k)); } return 0;}