我 想 扇 死 自 己

void up(int x)    {        if(x)        {            size[x]=cnt[x];//我TM这行忘了            if(son[x][0])size[x]+=size[son[x][0]];            if(son[x][1])size[x]+=size[son[x][1]];        }    }

4个小时！调一道模板！我敲里码！

上道splay刚因为细节打错浪费了3个小时时间，这次就又**重现了

不多说了，先把splay抄上10遍，手写！

-----------以下是正经题解----------------

第一道树套树：线段树套splay

对于线段树的每一段区间建splay维护这段的信息

在合并时：

排名相加；

前驱取max；

后继取min；

 

比较麻烦的是查询数值，需要二分答案.

以数值为值域进行二分，不断询问mid的排名来缩小范围。

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=4000005,inf=1e9;int n,m,a[N];    int root[N],son[N][3],fa[N],key[N],size[N],type,cnt[N];    void clear(int x)    {        if(!x)return ;        fa[x]=cnt[x]=son[x][0]=son[x][1]=size[x]=key[x]=0;    }    int pre(int k)    {        int now=son[root[k]][0];        while(son[now][1])now=son[now][1];        return now;    }    bool judge(int x)    {        return son[fa[x]][1]==x;    }    void up(int x)    {        if(x)        {            size[x]=cnt[x];            if(son[x][0])size[x]+=size[son[x][0]];            if(son[x][1])size[x]+=size[son[x][1]];        }    }    void rotate(int x)    {        int old=fa[x],oldf=fa[old],lr=judge(x);        son[old][lr]=son[x][lr^1];        fa[son[old][lr]]=old;        son[x][lr^1]=old;        fa[old]=x;        fa[x]=oldf;        if(oldf)son[oldf][son[oldf][1]==old]=x;        up(old);up(x);    }    void splay(int k,int x)    {        for(int f;f=fa[x];rotate(x))            if(fa[f])rotate(judge(x)==judge(f)?f:x);        root[k]=x;    }    void ins(int k,int x)    {        if(!root[k])        {            type++;            key[type]=x;            root[k]=type;            cnt[type]=size[type]=1;            fa[type]=son[type][0]=son[type][1]=0;            return ;        }        int now=root[k],f=0;        while(1)        {            if(x==key[now])            {                cnt[now]++;                up(now);                up(f);                splay(k,now);                return ;            }            f=now;now=son[now][key[now]
         
          key[f]]=type;                fa[type]=f;                key[type]=x;                up(f);splay(k,type);                return ;            }        }    }    int getrank(int k,int x)    {        int now=root[k],ans=0;        while(1)        {            if(!now)return ans;            if(x==key[now])return (son[now][0]?size[son[now][0]]:0)+ans;            else if(x>key[now])            {                ans+=(son[now][0]?size[son[now][0]]:0)+cnt[now];                now=son[now][1];            }            else if(x
          
           x) { if(ans>key[now])ans=key[now]; now=son[now][0]; } else now=son[now][1]; } return ans; } void del(int k,int x) { int now=findpos(k,x); splay(k,now); if(cnt[root[k]]>1) { cnt[root[k]]--; up(root[k]); return ; } else if(!son[root[k]][0]&&(!son[root[k]][1])) { clear(root[k]); root[k]=0; return ; } int old=root[k]; if(son[root[k]][0]*son[root[k]][1]==0) { if(!son[root[k]][0])root[k]=son[root[k]][1]; else root[k]=son[root[k]][0]; fa[root[k]]=0; clear(old); return ; } int L=pre(k); splay(k,L); son[root[k]][1]=son[old][1]; fa[son[old][1]]=root[k]; clear(old); up(root[k]); } #define ls(k) k<<1 #define rs(k) k<<1|1 void update(int k,int l,int r,int pos,int val) { ins(k,val); if(l==r)return ; int mid=l+r>>1; if(pos<=mid)update(ls(k),l,mid,pos,val); else update(rs(k),mid+1,r,pos,val); return ; } int rank(int k,int l,int r,int L,int R,int val) { if(l>=L&&r<=R) { int res=getrank(k,val); return res; } int mid=l+r>>1,res=0; if(L<=mid)res+=rank(ls(k),l,mid,L,R,val); if(R>mid)res+=rank(rs(k),mid+1,r,L,R,val); return res; } void modify(int k,int l,int r,int pos,int val) { del(k,a[pos]); ins(k,val); if(l==r)return ; int mid=l+r>>1; if(pos<=mid)modify(ls(k),l,mid,pos,val); else modify(rs(k),mid+1,r,pos,val); } int getpre(int k,int l,int r,int L,int R,int val) { if(l>=L&&r<=R)return findpre(k,val); int mid=l+r>>1,res=0; if(L<=mid)res=max(res,getpre(ls(k),l,mid,L,R,val)); if(R>mid)res=max(res,getpre(rs(k),mid+1,r,L,R,val)); return res; } int getnxt(int k,int l,int r,int L,int R,int val) { if(l>=L&&r<=R)return findnxt(k,val); int mid=l+r>>1,res=inf; if(L<=mid)res=min(res,getnxt(ls(k),l,mid,L,R,val)); if(R>mid)res=min(res,getnxt(rs(k),mid+1,r,L,R,val)); return res; }inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}int main(){ n=read();m=read(); int op,maxx=0; for(int i=1;i<=n;i++) { a[i]=read(); update(1,1,n,i,a[i]); maxx=max(maxx,a[i]); } while(m--) { op=read(); if(op==1) { int l=read(),r=read(),val=read(); printf("%d\n",rank(1,1,n,l,r,val)+1); } else if(op==2) { int l=read(),r=read(),val=read(); int L=0,R=maxx+1; while(L!=R) { int mid=L+R>>1; int res=rank(1,1,n,l,r,mid); //cout<<"***"<
           
            <