3223: Tyvj 1729 文艺平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

好久没写，水一发splay。。。。。。

 const

     maxn=;

 type

     node=record

       son:array[..]of longint;

       a,fa,size:longint;

       sw:boolean;

     end;

 var

     f:array[..maxn]of node;

     n,m,root:longint;

 function build(l,r,ff:longint):longint;

 var

     mid:longint;

 begin

     mid:=(l+r)>>;

     f[mid].fa:=ff;

     f[mid].size:=r-l+;

     if mid>l then f[mid].son[]:=build(l,mid-,mid);

     if (mid>) and (mid<n+) then f[mid].a:=mid-;

     if mid<r then f[mid].son[]:=build(mid+,r,mid);

     exit(mid);

 end;

 procedure swap(var x,y:longint);

 var

     t:longint;

 begin

     t:=x;x:=y;y:=t;

 end;

 procedure new(x:longint);

 begin

     with f[x] do

       begin

         size:=f[son[]].size+f[son[]].size+;

         if sw then

         begin

           swap(son[],son[]);

           f[son[]].sw:=not f[son[]].sw;

           f[son[]].sw:=not f[son[]].sw;

           sw:=not sw;

         end;

       end;

 end;

 function wh(x:longint):longint;

 begin

     if f[f[x].fa].son[]=x then exit();

     exit();

 end;

 procedure rotate(x,w:longint);

 var

     y:longint;

 begin

     y:=f[x].fa;

     f[y].son[w]:=f[x].son[w xor ];

     if f[x].son[w xor ]<> then f[f[x].son[w xor ]].fa:=y;

     f[x].son[w xor ]:=y;

     if root=y then root:=x

     else f[f[y].fa].son[wh(y)]:=x;

     f[x].fa:=f[y].fa;

     f[y].fa:=x;

     new(y);

 end;

 procedure splay(x,z:longint);

 var

     y:longint;

 begin

     while f[x].fa<>z do

       begin

         y:=f[x].fa;

         if f[y].fa<>z then

           begin

             if wh(x)=wh(y) then rotate(y,wh(y))

             else rotate(x,wh(x));

           end;

         rotate(x,wh(x));

       end;

     new(x);

 end;

 function find(k:longint):longint;

 begin

     find:=root;

     while true do

       begin

         new(find);

         if k=f[f[find].son[]].size+ then exit(find);

         if k<=f[f[find].son[]].size then find:=f[find].son[]

         else

           begin

             dec(k,f[f[find].son[]].size+);

             find:=f[find].son[];

           end;

       end;

 end;

 var

     aa:array[..maxn]of longint;

     tot:longint;

 procedure dfs(x:longint);

 begin

     new(x);

     with f[x] do

       begin

         if son[]<> then dfs(son[]);

         inc(tot);

         aa[tot]:=a;

         if son[]<> then dfs(son[]);

       end;

 end;

 procedure main;

 var

     i,l,r:longint;

 begin

     read(n,m);

     root:=build(,n+,);

     for i:= to m do

       begin

         read(l,r);

         splay(find(l),);

         splay(find(r+),root);

         f[f[f[root].son[]].son[]].sw:=not f[f[f[root].son[]].son[]].sw;

       end;

     splay(find(),);

     splay(find(n+),root);

     dfs(f[f[root].son[]].son[]);

     for i:= to n- do

       write(aa[i],' ');

     write(aa[n]);

 end;

 begin

     main;

 end.

巴特西

3223: Tyvj 1729 文艺平衡树 - BZOJ

最新文章

热门文章