codevs1743

http://codevs.cn/problem/1743/
splay区间翻转。
数字在原序列中的位置保存在splay的data[]中。splay中点的编号为原序列的数字大小。
每次pushdown只在find时进行就行，因为find结束时splay只会改动i点祖先的信息，而其余时候没有splay操作了。
记得加个+INF 一个-INF。
 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define N 400000

 #define INF 2000000000

 int lazy[N],s[N][],f[N],cnt[N],data[N],root,total;//son：1left 2right

 int fi,num,p,q,le[N],m,n,i,j,ans;

 char opt;

 struct lbz

 {

     int a,b;

 }x[N];

 bool cmp(lbz a,lbz b)

 {

     return a.a<b.a;

 }

 void rotate(int x,int w)//w:1leftZag 2rightZig

 {

     int y;

     y=f[x];

     cnt[y]=cnt[y]-cnt[x]+cnt[s[x][w]];

     cnt[x]=cnt[x]-cnt[s[x][w]]+cnt[y];

     s[y][-w]=s[x][w];

     if (s[x][w]!=)

         f[s[x][w]]=y;

     f[x]=f[y];

     if (f[y]!=)

         if (y==s[f[y]][])

             s[f[y]][]=x;

         else

             s[f[y]][]=x;

     f[y]=x;

     s[x][w]=y;

 }

 void splay(int x,int t)

 {

     int y;

     while (f[x]!=t)

     {

         y=f[x];

         if (f[y]==t)

             if (x==s[y][])

                 rotate(x,);

             else

                 rotate(x,);

         else

             if (y==s[f[y]][])

                 if (x==s[y][])

                 {

                     rotate(y,);

                     rotate(x,);

                 }

                 else

                 {

                     rotate(x,);

                     rotate(x,);

                 }

             else

                 if (x==s[y][])

                 {

                     rotate(y,);

                     rotate(x,);

                 }

                 else

                 {

                     rotate(x,);

                     rotate(x,);

                 }

     }

     if (f[x]==) root=x;

 }

 int sea(int x,int w)

 {

     int t;

     t=x;

     while ()

     {

         if (data[t]==w) break;

         if (w<=data[t])

         {

             if (s[t][]==) break;

             t=s[t][];

         }

         else

         {

             if (s[t][]==) break;

             t=s[t][];

         }

     }

     splay(t,);

     return t;

 }

 void add(int w)

 {

     int x;

     if (total==)

     {

         total++;

         f[]=;cnt[]=;data[]=w;root=;

         return;

     }

     x=root;

     while()

     {

         cnt[x]++;

         if (w<=data[x])

         {

             if (s[x][]==)    break;

             x=s[x][];

         }

         else

         {

             if (s[x][]==)    break;

             x=s[x][];

         }

     }

     total++;

     data[total]=w;

     f[total]=x;

     cnt[total]=;

     if (w<=data[x])

         s[x][]=total;

     else

         s[x][]=total;

     splay(total,);

 }

 void pushdown(int x)

 {

     lazy[x]^=;

     lazy[s[x][]]^=;

     lazy[s[x][]]^=;

     swap(s[x][],s[x][]);

 }

 int find(int k,int w)//w=1 Kthsmall;w=2 Kthbig

 {

     int i,t;

     i=root;t=k;

     if (lazy[i]==)

         pushdown(i);

     while (t!=cnt[s[i][w]]+)

     {

         if (t>cnt[s[i][w]]+)

         {

             t-=cnt[s[i][w]]+;

             i=s[i][-w];

         }

         else

             i=s[i][w];

         if (lazy[i]==)

             pushdown(i);

     }

     splay(i,);

     return i;

 }

 int rec(int l,int r)

 {

     int ll,rr;

     ll=find(l,);

     rr=find(r+,);

     splay(ll,);

     splay(rr,ll);

     lazy[s[rr][]]^=;

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         scanf("%d",&x[i].a);

         x[i].b=i;

     }

     sort(x+,x++n,cmp);

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

         add(x[i].b);

     add();

     add(-);

     while ()

     {

         fi=find(,);

         if (fi==) break;

         rec(,fi);

         ans++;

     }

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

     return ;

 }
巴特西

codevs1743

最新文章

热门文章
