tyvj 1729 文艺平衡树

文艺平衡树

From admin

背景 Background

此为平衡树系列第二道：文艺平衡树

描述 Description

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

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput [复制数据]

5 3
1 3
1 3
1 4

样例输出 SampleOutput [复制数据]

4 3 2 1 5 

数据范围和注释 Hint

n,m<=100000 

题解：

终于A了这道题，好激动。。。

也终于找到了一个好的splay模版

向序列之神--splay进发！

代码：

 const maxn=+;
 var s,id,fa:array[..maxn] of longint;
     rev:array[..maxn] of boolean;
     c:array[..maxn,..] of longint;
     i,n,m,rt,x,y:longint;
     procedure swap(var x,y:longint);
      var t:longint;
      begin
      t:=x;x:=y;y:=t;
      end;

 procedure pushup(x:longint);
  begin
    s[x]:=s[c[x,]]+s[c[x,]]+;
  end;
 procedure pushdown(x:longint);
  var l,r:longint;
  begin
    l:=c[x,];r:=c[x,];
    if rev[x] then
     begin
       swap(c[x,],c[x,]);
       rev[l]:=not(rev[l]);
       rev[r]:=not(rev[r]);
       rev[x]:=false;
     end;
  end;
 procedure rotate(x:longint;var k:Longint);
  var l,r,y,z:longint;
  begin
    y:=fa[x];z:=fa[y];
    if c[y,]=x then l:= else l:=;r:=l xor ;
    if y=k then k:=x else c[z,ord(c[z,]=y)]:=x;
    fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y;
    c[y,l]:=c[x,r];c[x,r]:=y;
    pushup(y);pushup(x);
  end;
 procedure splay(x:longint;var k:longint);
  var y,z:longint;
  begin
    while x<>k do
     begin
       y:=fa[x];z:=fa[y];
       if y<>k then
         begin
           if (c[z,]=y) xor (c[y,]=x) then rotate(x,k)
           else rotate(y,k);
         end;
       rotate(x,k);
     end;
  end;
 function find(x,rank:longint):longint;
  var l,r:longint;
  begin
  pushdown(x);l:=c[x,];r:=c[x,];
  if s[l]+=rank then exit(x)
  else if s[l]>=rank then exit(find(l,rank))
  else exit(find(r,rank-s[l]-));
  end;
 procedure rever(l,r:longint);
  var x,y:longint;
  begin
  x:=find(rt,l);y:=find(rt,r+);
  splay(x,rt);splay(y,c[x,]);
  rev[c[y,]]:=not(rev[c[y,]]);
  end;
 procedure build(l,r,f:longint);
  var mid,now,last:longint;
  begin
  if l>r then exit;
  now:=id[l];last:=id[f];
  if l=r then
     begin
       fa[now]:=last;s[now]:=;
       c[last,ord(l>f)]:=now;
       exit;
     end;
  mid:=(l+r)>>;
  build(l,mid-,mid);build(mid+,r,mid);
  now:=id[mid];pushup(mid);
  fa[now]:=last;
  c[last,ord(mid>f)]:=now;
  end;
 procedure init;
  begin
    readln(n,m);
    for i:= to n+ do id[i]:=i;
    build(,n+,);rt:=(n+)>>;
  end;
 procedure main;
  begin
    for i:= to m do
     begin
       readln(x,y);
       rever(x,y);
     end;
    for i:= to n+ do write(find(rt,i)-,' ');
  end;
 begin
   assign(input,'input.txt');assign(output,'output.txt');
   reset(input);rewrite(output);
   init;
   main;
   close(input);close(output);
 end.