线段树……

Program p2777;
const
   maxl=100000;
   maxt=30;
   maxo=100000;
var
   l,t,o,i,j,k:longint;
   col:array[1..maxl*10] of longint;
   c:char;
   x,y,color:longint;
   visit:array[1..maxt] of boolean;
procedure build(l,r,root:longint);
var
   mid:longint;
begin
   if l=r then
   begin
      col[root]:=1;
      exit;
   end;
   mid:=(l+r) shr 1;
   build(l,mid,root shl  1);
   build(mid+1,r,root shl 1+1);
   col[root]:=1;
end;
procedure swap(var a,b:longint);
var
   p:longint;
begin
   p:=a;a:=b;b:=p;
end;
procedure detate(l,r,sonl,sonr,root,color:longint);
var
   i,j,mid:longint;
begin
   mid:=(l+r) shr 1;
   if l=r then
   begin
      col[root]:=color;
      exit;
   end;

   if (sonl<=l) and (r<=sonr) then
   begin
      col[root]:=color;
      exit;
   end;

   if col[root]>0 then
   begin
      col[root*2]:=col[root];
      col[root*2+1]:=col[root];
      col[root]:=-1;


   end;

   if not((mid<sonl) or (sonr<l)) then detate(l,mid,sonl,sonr,root shl 1,color);
   if not((r<sonl) or (sonr<mid+1)) then detate(mid+1,r,sonl,sonr,root shl 1+1,color);



end;
function quere(l,r,sonl,sonr,root:longint):longint;
var
   mid,i,j:longint;
begin
   quere:=0;
   mid:=(l+r) shr 1;

   if col[root]>0 then
   begin
      if not(visit[col[root]]) then
      begin
         visit[col[root]]:=true;
         exit(1);
      end;
      exit(0);
   end;


   if not((mid<sonl) or (sonr<l)) then inc(quere,quere(l,mid,sonl,sonr,root shl 1));
   if not((r<sonl) or (sonr<mid+1)) then inc(quere,quere(mid+1,r,sonl,sonr,root shl 1+1));


end;

begin
   readln(l,t,o);
   build(1,l,1);
   for i:=1 to o do
   begin
      read(c);
      if c='C' then
      begin
         readln(x,y,color);
         if x>y then swap(x,y);
         detate(1,l,x,y,1,color);
      end
      else
      begin
         readln(x,y);
         if x>y then swap(x,y);
         fillchar(visit,sizeof(visit),false);
         writeln(quere(1,l,x,y,1));
      end;
   end;
end.

本题乍一看链表，实际上肯定超时%……

故用线段树 LogN查找……

Program P2828;
const
   maxn=200000;
var
   n,i,j:longint;
   pos,val:array[1..maxn] of longint;
   sum:array[1..maxn*10] of longint;
   ans:array[1..maxn] of longint;
procedure pushup(root:longint);
begin
   sum[root]:=sum[root*2]+sum[root*2+1];
end;
procedure build(l,r,root:longint);
var
   mid:longint;
begin
   if l=r then
   begin
      sum[root]:=1;
      exit;
   end;
   mid:=(l+r) shr 1;
   build(l,mid,root*2);
   build(mid+1,r,root*2+1);
   pushup(root);
end;
procedure decr(l,r,root,node:longint);
var
   mid:longint;
begin
   if l=r then
   begin
      dec(sum[root]);
      exit;
   end;
   mid:=(l+r) shr 1;
   if (node<=mid) then decr(l,mid,root shl 1,node)
   else decr(mid+1,r,root shl 1+1,node);
   pushup(root);
end;
function find(l,r,root,value:longint):longint;
var
   mid:longint;
begin
   mid:=(l+r) shr 1;
   if l=r then
   begin
      decr(1,n,1,l);
      exit(l);
   end;
   if (sum[root shl 1]>=value) then exit(find(l,mid,root shl 1,value))
   else exit(find(mid+1,r,root shl 1+1,value-sum[root shl 1]));
end;
begin
   while not seekeof do
   begin
      read(n);
      for i:=1 to n do read(pos[i],val[i]);
      build(1,n,1);
      for i:=n downto 1 do
      begin
         ans[find(1,n,1,pos[i]+1)]:=val[i];

      end;
      for i:=1 to n-1 do write(ans[i],' ');
      writeln(ans[n]);
   end;
end.

此题数据有误……

是我英文太差，还是答案出错……

Program P2528;
const
   maxn=10000;
   maxr=10000000;
var
   t,n,i,j,k:longint;
   a,b,v:array[1..maxn*2] of longint;
   h:array[1..maxr] of longint;
   col:array[1..maxn*100] of longint;
   visit:array[1..maxn*2] of boolean;


procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=v[(l+r) div 2];
   repeat
      while v[i]<m do inc(i);
      while v[j]>m do dec(j);
      if i<=j then
      begin
         p:=v[i];
         v[i]:=v[j];
         v[j]:=p;
         inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
procedure update(l,r,sonl,sonr,root,color:longint);
var
   i,j,k,mid:longint;
begin
   mid:=(l+r) shr 1;
   if (sonl<=l) and (r<=sonr) then
   begin
      col[root]:=color;
      exit;
   end;

   if (col[root]>=0) then
   begin
      col[root*2]:=col[root];
      col[root*2+1]:=col[root];
      col[root]:=-1;
   end;
   if not((mid<sonl) or (sonr<l)) then update(l,mid,sonl,sonr,root*2,color);
   if not((r<sonl) or (sonr<mid+1)) then update(mid+1,r,sonl,sonr,root*2+1,color);



end;
function dfs(l,r,root:longint):longint;
var
   i,j,mid:longint;
begin
   mid:=(l+r) shr 1;
   if col[root]=0 then exit(0);
   if col[root]>0 then
   begin
      if not(visit[col[root]]) then
      begin
         visit[col[root]]:=true;
         exit(1);
      end
      else exit(0);
   end;

   exit(dfs(l,mid,root*2)+dfs(mid+1,r,root*2+1));

end;
begin
   read(t);
   while t>0 do
   begin
      dec(t);
      read(n);
      for i:=1 to n do
      begin
         read(a[i],b[i]);
         v[i]:=a[i];
         v[n+i]:=b[i];
      end;
      qsort(1,2*n);
      j:=1;
      for i:=2 to 2*n do
         if v[i]<>v[i-1] then
         begin
            inc(j);
            v[j]:=v[i];
         end;
      for i:=1 to j do h[v[i]]:=i;

      fillchar(col,sizeof(col),0);

      for i:=1 to n do
      begin
        update(1,j,h[a[i]],h[b[i]],1,i);
      end;
      fillchar(visit,sizeof(visit),false);
      writeln(dfs(1,j,1));

   end;
end.

PushUp（root） 维护

          sum[root]=sum[root/2]+sum[root/2+1] 

Build     建树 （当前区间，序号（当前区间的root））

         维护目前结点

l=r   return

    更新左右子树

Update   更新子节点 （当前区间，所求区间，Root）

l=r    更新   return

更新结点在左子树    更新左子树

否则更新右子树

PushUp 当前结点

Query 区间求和 （当前区间，所求区间，Root）

包含   直接返回当前值

否则考察左右结点是否包含   求和