给出N个数，要求做M次区间翻转（如1 2 3 4变成4 3 2 1），求出最后的序列

第一行一个数N，下一行N个数表示原始序列，在下一行一个数M表示M次翻转，之后的M行每行两个数L，R表示将区间[L,R]翻转。

一行N个数 ， 表示最终序列。

4

1 2 3 4

2

1 2

3 4

2 1 4 3

对于30%的数据满足n<=100 , m <= 10000

对于100%的数据满足n <= 150000 , m <= 150000

对于100%的数据满足n为2的幂，且L = i * 2^j + 1 , R = (i + 1) * 2^j

题解：

要不要这么卡时啊。。。不加inline就不能过？

代码：

 {$inline on}

 const maxn=+;

 var s,id,fa,a: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);inline;

      var t:longint;

      begin

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

      end;

 procedure pushup(x:longint);inline;

  begin

    s[x]:=s[c[x,]]+s[c[x,]]+;

  end;

 procedure pushdown(x:longint);inline;

  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);inline;

  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);inline;

  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;inline;

  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);inline;

  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);inline;

  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);

    for i:= to n do read(a[i]);readln;

    readln(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(a[find(rt,i)-],' ');

  end;

 begin

   assign(input,'input.txt');assign(output,'output.txt');

   reset(input);rewrite(output);

   init;

   main;

   close(input);close(output);

 end.