【树状数组】数星星（POJ2352 star）
Time Limit:1000MS Memory Limit:65536K
Total Submit:23 Accepted:16
Description
天文学家经常观察星象图。
星象图中用平面上的点来表示一颗星星，每一颗星星都有一个笛卡尔坐标。
设定星星的等级为其左下角星星的总数。
天文学家们想知道星星等级的分布情况。
比如上图，5号星星的等级为3（其左下角有编号为1、2、4的星星共三颗）。
2号星星和4号星星的等级为1。
在上图中只有一颗星星等级为0，两颗星星等级为1，一颗星星等级为2，一颗星星等级为3。
给定一个星象图，请你写一个程序计算各个等级的星星数目。
Input
输入的第一行包含星星的总数N (1<=N<=15000)。
接下来N行，描述星星的坐标（X,Y）（X和Y用空格分开，0<=X,Y<=32000）。
星象图中的每个点处最多只有一颗星星。
所有星星按Y坐标升序排列。
Y坐标相等的星星按X坐标升序排列。
Output
输出包含N行，每行一个整数。
第一行包含等级0的星星数目，第二行包含等级1的星星数目，依此类推，最后一行包含等级为N-1的星星数目。
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
∙const maxn=60000;
∙var i,n,x,y,k:longint;
∙a:array[0..15000] of longint;
∙c,stars:array[0..60000] of longint; ∙procedure add(p,d:longint);
∙begin
∙ while p<=maxn do begin
∙ c[p]:=c[p]+d;
∙ p:=p+p and (-p);
∙ end;
∙end;
∙function sum(p:longint):longint;
∙var res:longint;
∙begin
∙ res:=0;
∙ while p>0 do begin
∙ res:=res+c[p]; p:=p-p and (-p); ∙ end;
∙ exit(res);
∙end;
∙begin
∙readln(n);
∙for i:=1 to n do begin
∙ readln(x,y);
∙ add(x+1,1);
∙ k:=sum(x+1)-1;
∙ stars[k]:=stars[k]+1;
∙end;
∙for i:=0 to n-1 do writeln(stars[i]); ∙end.
【树状数组】矩阵（POJ 2155）
Time Limit:3000MS Memory Limit:65536K
Total Submit:13 Accepted:8
Description
给你一个N*N的矩阵A，其元素为0或1。
A[i,j]代表在第i行第j列的数字。
最初A[i, j] = 0 (1 <= i, j <= N)。
我们按照如下规则改变矩阵。
给定一个矩形，其左上角为（x1, y1），其右下角为（x2，y2）。
我们对矩形内的所有元素执行“not”操作（也就是将“0”变为“1”，将“1”变为“0”）。
为了维护矩阵的信息，请你写一个程序接受并执行两种操作。
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n)对左上角为（x1，y1），右下角为（x2，y2）的矩形执行“not”操作。
2. Q x y (1 <= x, y <= n) 询问A[x, y]。
Input
第一行为一个整数X (X <= 10) 代表测试数据的组数。
接下来X块数据，每块数据代表一组测试数据。
每组测试数据的第一行包含两个数N和T (2 <= N <= 1000, 1 <= T <= 50000) 。
N 代表矩阵的大小。
接下来T行，每行有一条指令，按照格式“Q x y”或者“C x1 y1 x2 y2”。
Output
对于每个查询，输出一行代表A[x,y]。
注意连续两组测试数据的输出之间要有一个空行。
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
1
∙var
∙ n,k,i,j,t:longint;
∙ ch:char;
∙ c:array[0..1000,0..1000] of longint; ∙procedure add(x,y:longint);
∙var i,j:longint;
∙begin
∙ i:=x;
∙ while i<=n do begin
∙ j:=y;
∙ while j<=n do begin
∙ inc(c[i,j]);
∙ j:=j+j and (-j);
∙ end;
∙ i:=i+i and (-i);
∙ end;
∙end;
∙
∙procedure qc;
∙var x1,x2,y1,y2:longint;
∙begin
∙ readln(x1,y1,x2,y2);
∙ add(x1,y1);
∙ add(x1,y2+1);
∙ add(x2+1,y1);
∙ add(x2+1,y2+1);
∙end;
∙
∙function sum(x,y:longint):longint;
∙var v:longint; i,j:longint;
∙begin
∙ v:=0; i:=x;
∙ while i>0 do begin
∙ j:=y;
∙ while j>0 do begin
∙ v:=v+c[i,j];
∙ j:=j-j and (-j);
∙ end;
∙ i:=i-i and (-i);
∙ end;
∙ exit(v);
∙end;
∙
∙procedure qq;
∙var x,y:longint;
∙begin
∙ readln(x,y);
∙ writeln(sum(x,y) mod 2); ∙end;
∙begin
∙ readln(k);
∙ for i:=1 to k do begin
∙ fillchar(c,sizeof(c),0); ∙ readln(n,t);
∙ for j:=1 to t do begin ∙ read(ch);
∙ if ch='C' then qc
∙ else qq;
∙ end;
∙ writeln;
∙ end;
∙end.
∙。