{Memory:7192K
Time:297MS
Language:Pascal
Code Length:1995B}
program count;

type
  TTree=^Node;
  Node=record
    L,R,col:longint;
    lc,rc:TTree;
    same:boolean;  //same的意义在于，same为true则区间为纯色，为false则为混色
  end;

var
  long,O,i,a,b,c:longint;
  T:TTree;
  ch:char;

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

procedure build(var T:TTree;L,R:longint);
var mid:longint;
begin
  new(T);
  T^.L:=L; T^.R:=R;
  T^.lc:=nil; T^.rc:=nil;
  T^.col:=1; T^.same:=true;
  if L<R then
  begin
    mid:=(L+R) shr 1;
    build(T^.lc,L,mid);
    build(T^.rc,mid+1,R);
  end;
end;

procedure paint(var T:TTree;L,R,c:longint);
var mid:longint;
begin
  if (T^.L=L) and (T^.R=R) then
  begin
    T^.same:=true;
    T^.col:=c;
    exit;
  end;
  if T^.same then
  begin
    T^.same:=false;
    T^.lc^.col:=T^.col;
    T^.lc^.same:=true;
    T^.rc^.col:=T^.col;
    T^.rc^.same:=true;
  end;
  mid:=(T^.L+T^.R) shr 1;
  if R<=mid then paint(T^.lc,L,R,c)
  else if L>mid then paint(T^.rc,L,R,c)
  else
  begin
    paint(T^.lc,L,mid,c);
    paint(T^.rc,mid+1,R,c);
  end;
  T^.col:=T^.lc^.col or T^.rc^.col;
end;

function query(T:TTree;L,R:longint):longint;
var mid:longint;
begin
  if T^.same then exit(T^.col);
  if (T^.L=L) and (T^.R=R) then exit(T^.col);
  mid:=(T^.L+T^.R) shr 1;
  if R<=mid then exit(query(T^.lc,L,R))
  else if L>mid then exit(query(T^.rc,L,R))
  else exit(query(T^.lc,L,mid) or query(T^.rc,mid+1,R));
end;

function count(c:longint):integer;
var i,x:longint;
begin
  count:=0;
  x:=1;
  for i:= 1 to 30 do
  begin
    if x and c>0 then inc(count);
    x:=x shl 1;
  end;
end;

begin
  readln(long,O,O);
  build(T,1,long);
  for i:= 1 to O do
  begin
    read(ch);
    case ch of
      'C':
      begin
        readln(a,b,c);
        if a>b then swap(a,b);  //注意题目说"A may be larger than B"
        paint(T,a,b,1 shl (c-1));
      end;
      'P':
      begin
        readln(a,b);
        if a>b then swap(a,b);
        writeln(count(query(T,a,b)));
      end;
    end;
  end;
end.

• Re:AC代码 (2358) renyanyu345 2015-04-05 16:21:15