POJ3225 (Pascal)

poj3225.pas

const
  maxn=132000;

type
  segment=record
            left,right,cov,res:longint;
            //cov:cover
            //res:reverse
          end;

var
  a:array [0..maxn shl 2] of segment;
  f:array [0..maxn+10] of longint;
  order,tmp,l_char,r_char:char;
  l,r,i:longint;
  flag:boolean;

procedure change(p:longint);
begin
  if a[p].res=1 then a[p].res:=0 else
    if a[p].cov<>-1 then a[p].cov:=1-a[p].cov else
      a[p].res:=1;
end;

function getint(var p:longint):char;
var
  ch:char;

begin
  p:=0;
  repeat
    read(ch);
    if ch in ['0'..'9'] then p:=p*10+ord(ch)-48 else exit(ch);
  until false;
end;

procedure tr_create(p,l,r:longint);
var
  m:longint;

begin
  a[p].left:=l;
  a[p].right:=r;
  if l=r then exit;
  m:=(l+r) shr 1;
  tr_create(p shl 1,l,m);
  tr_create(p shl 1+1,m+1,r);
end;

procedure tr_update(p:longint);
begin
  if a[p].cov<>-1 then
    begin
      a[p shl 1].cov:=a[p].cov;
      a[p shl 1+1].cov:=a[p].cov;
      a[p shl 1].res:=0;
      a[p shl 1+1].res:=0;
      a[p].cov:=-1;
    end;
  if a[p].res=1 then
    begin
      a[p].res:=0;
      change(p shl 1);
      change(p shl 1+1);
    end;
end;

procedure tr_insert(p,l,r,c:longint);
begin
  if (l<=a[p].left) and (r>=a[p].right) then
    begin
      a[p].res:=0;
      a[p].cov:=c;
      exit;
    end;
  if a[p].left=a[p].right then exit;
  tr_update(p);
  if l<=a[p shl 1].right then tr_insert(p shl 1,l,r,c);
  if r>=a[p shl 1+1].left then tr_insert(p shl 1+1,l,r,c);
end;

procedure tr_xor(p,l,r:longint);
begin
  if (l<=a[p].left) and (r>=a[p].right) then
    begin
      if a[p].res=1 then a[p].res:=0 else
        if a[p].cov=-1 then a[p].res:=1 else
          a[p].cov:=1-a[p].cov;
      exit;
    end;
  if a[p].left=a[p].right then exit;
  tr_update(p);
  if l<=a[p shl 1].right then tr_xor(p shl 1,l,r);
  if r>=a[p shl 1+1].left then tr_xor(p shl 1+1,l,r);
end;

procedure tr_query(p:longint);
begin
  if a[p].left=a[p].right then
    begin
      if a[p].res=1 then a[p].cov:=1-a[p].cov;
      f[a[p].left]:=a[p].cov;
      exit;
    end;
  tr_update(p);
  tr_query(p shl 1);
  tr_query(p shl 1+1);
end;

procedure print(l,r:longint);
var
  l_char,r_char:char;

begin
  if odd(l) then begin dec(l); l_char:='('; end else l_char:='[';
  if odd(r) then begin inc(r); r_char:=')'; end else r_char:=']';
  write(l_char,l shr 1,',',r shr 1,r_char);
end;

procedure print_state;
var
  l,r,i:longint;
  flag:boolean;

begin
  fillchar(f,sizeof(f),0);
  tr_query(1);
  flag:=false;
  i:=0;
  while i<=maxn do
    begin
      if f[i]=1 then
        begin
          l:=i;
          while f[i]=1 do inc(i);
          r:=i-1;
          if flag then write(' ');
          flag:=true;
          if odd(l) then write('(',l shr 1) else write('[',l shr 1);
          write(',');
          if odd(r) then write(r shr 1+1,')') else write(r shr 1,']');
        end;
      inc(i);
    end;
  if not flag then write('empty set');
  writeln;
end;

begin
  tr_create(1,0,maxn);
  while not eof do
    begin
      read(order,tmp,l_char);
      tmp:=getint(l);
      r_char:=getint(r);
      readln;
      l:=l shl 1+ord(l_char='(');
      r:=r shl 1-ord(r_char=')');
      case order of
        'U':tr_insert(1,l,r,1);
        'I':begin tr_insert(1,0,l-1,0); tr_insert(1,r+1,maxn,0); end;
        'D':tr_insert(1,l,r,0);
        'C':begin tr_insert(1,0,l-1,0); tr_insert(1,r+1,maxn,0); tr_xor(1,l,r); end;
        'S':tr_xor(1,l,r);
      end;
    end;
  print_state;
end.