题意：给出n个星星的位置，一个星星的level定义为其左下角（不严格）星星的数量。
要求统计0到n-1 level的星星各有多少个。
下面是一年前写的树状数组的题解：
依然想不通，智商是硬伤，绝望的想哭，真的想哭。
更新于2015年08月04日01:47:18：
好像有点明白了…..详情看注释
树状数组ac代码：
代码实现
1/*************************************************************************
2 > File Name: code/poj/2352.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月04日 星期二 00时33分52秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=4E4+7;
32int a[N];
33int t[N];
34int x,y;
35int n;
36int lowbit (int x)
37{
38 return x&(-x);
39}
40void update(int x,int c)
41{
42 int i;
43 for ( int i = x ; i <= 32001 ; i = i + lowbit(i))
44 {
45 t[i] = t[i] + c;
46 }
47}
48int sum( int x)
49{
50 int i;
51 int res = 0;
52 for ( int i = x ; i >= 1 ; i = i-lowbit(i))
53 {
54 res = res + t[i];
55 }
56 // cout<<"x:"<<x<<" res:"<<res<<endl;
57 return res;
58}
59int main()
60{
61 scanf("%d",&n);
62 for ( int i = 0 ; i < n ; i ++ )
63 {
64 scanf("%d %d",&x,&y);
65 a[sum(++x)]++; // ++x是因为坐标是从0 开始，而树状数组的下标一定是从1开始，不然会TLE
66 // sum(++x)是求 ++x 的level
67 //
68 //
69 update(x,1); //向上更新，对于每一个比x大的位置，由于x的存在，那些位置的点的level都会增加1
70 //比如对于星3，因为星1的读入，我向上更新了星2,星3,星4,星5，这时候他们的level都是1
71 //之后读入星2，更新了星3和星5，星3的level是2，星5的level也是2，之后由于星4，星5的level又加1，为5.
72 }
73 for ( int i = 0 ; i < n ; i ++ )
74 {
75 printf("%d\n",a[i]); //数组a存的是level 为i的点有多少个，即为题目所求。
76 }
77 return 0;
78}当然用线段树也是可以的。 思路同poj 2481 poj 2481 解题报告
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年09月04日 星期日 14时31分12秒
4File Name :code/poj/r2352.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=32005;
32int tree[N<<2];//tree的N写成了区间个数的15000，wa了一发。
33int ans[N];
34int n;
35pi a[N];
36void PushUp( int rt)
37{
38 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
39}
40void update(int p,int l,int r,int rt)
41{
42 if (l==r)
43 {
44 tree[rt]++;
45 return;
46 }
47 int m = (l+r)>>1;
48 if (p<=m) update(p,lson);
49 else update(p,rson);
50 PushUp(rt);
51}
52int query(int L,int R,int l,int r,int rt)
53{
54 if (L<=l&&r<=R) return tree[rt];
55 int m = (l+r)>>1;
56 int ret = 0 ;
57 if (L<=m)
58 {
59 int res =query(L,R,lson);
60 ret = ret + res;
61 }
62 if (R>=m+1)
63 {
64 int res = query(L,R,rson);
65 ret = ret + res;
66 }
67 return ret;
68}
69int main()
70{
71#ifndef ONLINE_JUDGE
72 freopen("code/in.txt","r",stdin);
73#endif
74 scanf("%d",&n);
75 ms(ans,0);
76 for ( int i = 1 ;i <= n ; i++) scanf("%d%d",&a[i].fst,&a[i].sec),a[i].fst++,a[i].sec++;
77 for ( int i = 1 ; i <= n ; i++)
78 {
79 int tmp = query(1,a[i].fst,1,32001,1);
80 ans[tmp]++;
81 update(a[i].fst,1,32001,1);
82 }
83 for ( int i = 0 ; i <= n-1 ; i++)
84 printf("%d\n",ans[i]);
85#ifndef ONLINE_JUDGE
86 fclose(stdin);
87#endif
88 return 0;
89}