学步园

splay区间反转  

我的WScode：

type
tree=record
f,l,r,bg,size:longint;
end;
var
root,n,m,i,j,x,y,l,r:longint;
t:array[0..500000] of tree;

procedure ch(x:longint);
begin
if t[x].bg=1 then
  t[x].bg:=0
else t[x].bg:=1;
end;
procedure down(x:longint);
var sw:longint;
begin
if x<>0 then
if t[x].bg=1 then
begin
  if t[x].l<>0 then
    ch(t[x].l);
  if t[x].r<>0 then
    ch(t[x].r);
  sw:=t[x].l;
  t[x].l:=t[x].r;
  t[x].r:=sw;
  t[x].bg:=0;
end;
end;

procedure left(p:longint);
var gp,f,ll:longint;
begin
f:=t[p].f;
t[f].size:=t[f].size-t[t[p].r].size-1;
t[p].size:=t[p].size+t[t[f].l].size+1;

ll:=t[p].l;
t[ll].f:=f;
t[f].r:=ll;

gp:=t[f].f;
if t[gp].l=f then
  t[gp].l:=p
else t[gp].r:=p;
t[p].f:=gp;

t[f].f:=p;
t[p].l:=f;
end;
procedure right(p:longint);
var gp,f,rr:longint;
begin
f:=t[p].f;
t[f].size:=t[f].size-t[t[p].l].size-1;
t[p].size:=t[p].size+t[t[f].r].size+1;

rr:=t[p].r;
t[rr].f:=f;
t[f].l:=rr;

gp:=t[f].f;
if t[gp].l=f then
  t[gp].l:=p
else t[gp].r:=p;
t[p].f:=gp;

t[f].f:=p;
t[p].r:=f;
end;
procedure splay(ff,x:longint);
var p:longint;
begin
while t[x].f<>ff do
begin
  p:=t[x].f;
  if t[p].f=ff then
  begin
    if x=t[p].l then
      right(x)
    else left(x);
    break;
  end;
  if x=t[p].l then
  begin
    if p=t[t[p].f].l then
    begin
      right(p);
      right(x);
    end
    else
    begin
      right(x);
      left(x);
    end;
  end
  else
  begin
    if p=t[t[p].f].r then
    begin
      left(p);
      left(x);
    end
    else
    begin
      left(x);
      right(x);
    end;
  end;
end;
end;

function find(p,k:longint):longint;
begin
down(p);
if t[t[p].l].size=k-1 then
  exit(p);
if k<=t[t[p].l].size then
  exit(find(t[p].l,k))
else exit(find(t[p].r,k-t[t[p].l].size-1));
end;

procedure wri(p:longint);
begin
if p=0 then exit;
down(p);
wri(t[p].l);
write(p,' ');
wri(t[p].r);
end;

begin
readln(n,m);
for i:=1 to n do
begin
  t[i].f:=i-1;
  if i<>1 then
    t[i-1].r:=i;
  if i=1 then
    t[i].size:=n
  else t[i].size:=t[t[i].f].size-1;
end;
root:=1;

for j:=1 to m do
begin
  readln(x,y);
  if (x=1)and(y=n) then
  begin
    ch(root);
    continue;
  end;
  if x=1 then
  begin
    l:=find(root,y+1);
    splay(0,l);root:=l;
    ch(t[l].l);
    continue;
  end;
  if y=n then
  begin
    l:=find(root,x-1);
    splay(0,l);root:=l;
    ch(t[l].r);
    continue;
  end;

  l:=find(root,x-1);r:=find(root,y+1);
  splay(0,l);root:=l;splay(root,r);
  ch(t[t[root].r].l);
end;
wri(root);
end.