bzoj 3196 树套树模板

然而我还是在继续刷水题。。。

终于解开了区间第k大的心结。。。

比较裸的线段树套平衡树，比较不好想的是求区间第k大时需要二分一下答案，然后问题就转化为了第一个操作。复杂度nlog3n。跑的比较慢。。。

在查前驱后继的时候写错了。。。如果要直接赋值ans的话前驱是k[x]<=z,后继是k[x]<z,如果都写<的话需要取max和min。。。（不是第一次犯这种错了）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define lc x*2,l,mid

 #define rc x*2+1,mid+1,r

 #define ls(x) ch[x][0]

 #define rs(x) ch[x][1]

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,m;

 int root[*];

 int size[*],k[*];

 int ch[*][],fa[*];

 int a[];

 int cnt;

 inline void push_up(int x)

 {

     size[x]=size[ch[x][]]+size[ch[x][]]+;

     return ;

 }

 inline void rotate(int p)

 {

     int q=fa[p],y=fa[q],x=(ch[q][]==p);

     ch[q][x]=ch[p][x^];fa[ch[q][x]]=q;

     ch[p][x^]=q;fa[q]=p;fa[p]=y;

     if(y)

     {

         if(ls(y)==q)ch[y][]=p;

         else ch[y][]=p;

     }

     push_up(q);push_up(p);

 }

 inline void splay(int now,int x)

 {

     for(int y;y=fa[x];rotate(x))

     {

         if(fa[y])

         {

             if((ls(y)==x&&ls(fa[y])==y)||(rs(y)==x&&rs(fa[y])==y))rotate(y);

             else rotate(x);

         }

     }

     root[now]=x;

 }

 inline void insert(int now,int x,int z)

 {

     size[x]++;

     while(ch[x][k[x]<z])x=ch[x][k[x]<z],size[x]++;

     ch[x][k[x]<z]=++cnt;fa[cnt]=x;size[cnt]=;k[cnt]=z;splay(now,cnt);

 }

 inline void build(int x,int l,int r)

 {

     root[x]=++cnt;k[cnt]=a[l];size[cnt]=;

     for(int i=l+;i<=r;i++)insert(x,root[x],a[i]);

     int mid=(l+r)>>;

     if(l<r)build(lc),build(rc);

     return ;

 }

 inline int fd(int x,int z)

 {

    int ans=;

    while(x)

    {

          if(k[x]>z)

          {

               x=ch[x][];

       }

       else ans+=size[ch[x][]]+,x=ch[x][];

    }

    return ans;

 }

 inline int qur(int x,int l,int r,int ll,int rr,int kk)

 {

     if(ll<=l&&rr>=r)

     {

         return fd(root[x],kk);

     }

     int mid=(l+r)>>;

     int ans=;

     if(ll<=mid)ans+=qur(lc,ll,rr,kk);

     if(rr>mid)ans+=qur(rc,ll,rr,kk);

     return ans;

 }

 inline int find(int x,int z)

 {

     if(k[x]==z)return x;

     while(ch[x][k[x]<z])

     {

         x=ch[x][k[x]<z];if(k[x]==z)return x;

     }

     return ;

 }

 inline void del(int now,int x)

 {

     splay(now,x);

     if(!ch[x][])root[now]=ch[x][],fa[ch[x][]]=;

     else if(!ch[x][])root[now]=ch[x][],fa[ch[x][]]=;

     else

     {

         fa[ch[x][]]=;int tmp=ch[x][];

         while(ch[tmp][])tmp=ch[tmp][];

         splay(now,tmp);ch[tmp][]=ch[x][];fa[ch[x][]]=tmp;push_up(tmp);

     }

 }

 inline void gai(int x,int l,int r,int pos,int z)

 {

     insert(x,root[x],z);

     int x1=find(root[x],a[pos]);

     del(x,x1);

     if(l==r)return ;

     int mid=(l+r)>>;

     if(pos<=mid)gai(lc,pos,z);

     else gai(rc,pos,z);

 }

 inline int pre(int x,int z)

 {

     int ans=-inf;

     while(ch[x][k[x]<=z])

     {

         if(k[x]<=z)ans=k[x];

         x=ch[x][k[x]<=z];

     }if(k[x]<=z)ans=max(ans,k[x]);

     return ans;

 }

 inline int suc(int x,int z)

 {

     int ans=inf;

     while(ch[x][k[x]<z])

     {

         if(k[x]>=z)ans=k[x];

         x=ch[x][k[x]<z];

     }if(k[x]>=z)ans=min(ans,k[x]);

     return ans;

 }

 inline int qur_pre(int x,int l,int r,int ll,int rr,int kk)

 {

     if(l>=ll&&r<=rr)

     {

         return pre(root[x],kk);

     }

     int ans=-inf;

     int mid=(l+r)>>;

     if(ll<=mid)ans=max(ans,qur_pre(lc,ll,rr,kk));

     if(rr>mid)ans=max(ans,qur_pre(rc,ll,rr,kk));

     return ans;

 }

 inline int qur_suc(int x,int l,int r,int ll,int rr,int kk)

 {

     if(l>=ll&&r<=rr)

     {

         return suc(root[x],kk);

     }

     int ans=inf;

     int mid=(l+r)>>;

     if(ll<=mid)ans=min(ans,qur_suc(lc,ll,rr,kk));

     if(rr>mid)ans=min(ans,qur_suc(rc,ll,rr,kk));

     return ans;

 }

 int mn,mx;

 int main()

 {

     scanf("%d%d",&n,&m);mn=inf;mx=-inf;

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);mn=min(mn,a[i]);mx=max(mx,a[i]);

     }

     build(,,n);

     for(int i=;i<=m;i++)

     {

         int t1;

         scanf("%d",&t1);

         int l,r,kk;

         if(t1==)

         {

            scanf("%d%d%d",&l,&r,&kk);

            printf("%d\n",qur(,,n,l,r,kk-)+);

         }

         else if(t1==)

         {

             scanf("%d%d%d",&l,&r,&kk);

             int ha=mn;int ta=mx;

             while(ha<=ta)

             {

                 int mid=(ha+ta)>>;

                 if(qur(,,n,l,r,mid)<kk)ha=mid+;

                 else ta=mid-;

             }

             printf("%d\n",ha);

         }

         else if(t1==)

         {

             scanf("%d%d",&l,&kk);

             gai(,,n,l,kk);a[l]=kk;

         }

         else if(t1==)

         {

             scanf("%d%d%d",&l,&r,&kk);

             printf("%d\n",qur_pre(,,n,l,r,kk-));

         }

         else

         {

             scanf("%d%d%d",&l,&r,&kk);

             printf("%d\n",qur_suc(,,n,l,r,kk+));

         }

     }

     return ;

 }

巴特西

bzoj 3196 树套树模板

最新文章

热门文章