bzoj3223

很久没写splay了，这是用splay解决动态区间问题
平常splay树的建立都是以键值建立的
而这里是以位置序号为优先级建立的
不难发现，tree上的点代表的位置就是它的名次
splay的区间操作最重要的一点就是提取区间
设提取区间[a,b]，则我们只要代表位置a-1的点伸展到根，再把代表位置b+1的点伸展到根的子树（显然在右子树）
然后显然，b+1的左子树就表示区间[a,b]
为了方便提取，我们常常会加入额外位置点0，n+1
这道题比较简单，只有翻转操作
显然这个是可以打标记的，每个点节点打上当前以这个点为根的子树是否要翻转
我们先提取区间，然后在根节点节点打上标记，显然这就表示这个区间要翻转
然后在之后的splay操作中维护这个标记即可

var son:array[-1..100010,1..2] of longint;
    count,fa,a,b:array[-1..100010] of longint;
    v:array[-1..100010] of boolean;
    i,n,m,t,root,x,y:longint;

procedure swap(var a,b:longint);
  var c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure change(x:longint);
  begin
    if x=-1 then exit;
    swap(son[x,1],son[x,2]);
    v[x]:=not v[x];
  end;

procedure push(x:longint);
  begin
    if v[x] then
    begin
      change(son[x,1]);
      change(son[x,2]);
      v[x]:=false;
    end;
  end;

procedure update(x:longint);
  begin
    count[x]:=count[son[x,1]]+count[son[x,2]]+1;
  end;

procedure rotate(x,w:longint);
  var y:longint;
  begin
    push(x);
    y:=fa[x];
    if fa[y]<>-1 then
    begin
      if son[fa[y],1]=y then son[fa[y],1]:=x
      else son[fa[y],2]:=x;
    end;
    fa[x]:=fa[y];
    son[y,3-w]:=son[x,w];
    if son[x,w]<>-1 then fa[son[x,w]]:=y;
    son[x,w]:=y;
    fa[y]:=x;
    update(y);
    update(x);
  end;

procedure splay(x,f:longint);
  var y:longint;
  begin
    while fa[x]<>f do
    begin
      y:=fa[x];
      if fa[y]=f then
      begin
        if son[y,1]=x then rotate(x,2)
        else rotate(x,1);
      end
      else begin
        if son[fa[y],1]=y then
        begin
          if son[y,1]=x then rotate(y,2) else rotate(x,1);
          rotate(x,2);
        end
        else begin
          if son[y,1]=x then rotate(x,2) else rotate(y,1);
          rotate(x,1);
        end;
      end;
    end;
    if f=-1 then root:=x;
  end;

function build(l,r:longint):longint;
  var m:longint;
  begin
    m:=(l+r) shr 1;
    build:=m;
    if l<=m-1 then
    begin
      son[m,1]:=build(l,m-1);
      fa[son[m,1]]:=m;
    end;
    if m+1<=r then
    begin
      son[m,2]:=build(m+1,r);
      fa[son[m,2]]:=m;
    end;
    update(m);
  end;

function find(k:longint):longint;
  var p:longint;
  begin
    p:=root;
    while true do
    begin
      push(p);
      if count[son[p,1]]+1=k then exit(p)
      else if count[son[p,1]]+1>k then p:=son[p,1]
      else begin
        k:=k-count[son[p,1]]-1;
        p:=son[p,2];
      end;
    end;
  end;

procedure work(x,y:longint);
  begin
    x:=find(x);
    y:=find(y+2);
    splay(x,-1);
    splay(y,x);
    change(son[y,1]);
  end;

procedure mid(x:longint);
  begin
    push(x);
    if son[x,1]<>-1 then mid(son[x,1]);
    inc(t);
    b[t]:=a[x];
    if son[x,2]<>-1 then mid(son[x,2]);
  end;

begin
  fillchar(son,sizeof(son),255);
  fillchar(fa,sizeof(fa),255);
  readln(n,m);
  for i:=0 to n+1 do
    a[i]:=i;
  root:=build(0,n+1);  //先直接建立一棵平衡的BST
  for i:=1 to m do
  begin
    readln(x,y);
    work(x,y);
  end;
  t:=-1;
  mid(root);
  for i:=1 to t-1 do
    write(b[i],' ');
end.