题目链接
题目概述
给输入星星的坐标（y递增，若y相等，x递增），每个星星都有一个等级，规定它的等级就是在它左下方的星星的个数。输入所有星星后，依次输出等级为0到n-1的星星的个数。
题目分析
乍一看很茫然，仔细观察输入规律就能发现，是在x的维度上求逆元数。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=32005;
int tree[MAXN];
int level[MAXN],n;
#define lowbit(x) x&-(x)
void add(int x, int d){
while(x<=MAXN){
tree[x]+=d;
x+=lowbit(x);
}
}
int getsum(int x){
int sum=0;
while(x>0){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
int main(){
int x,y;
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d%d", &x, &y);
x++;
level[getsum(x)]++;
add(x, 1);
}
for(int i=0; i<n; i++)
printf("%d\n", level[i]);
return 0;
}
|
自我总结
一开始题目还读错了，没看懂输入的规律（逃，虽然已经接触了一段时间树状数组了，但不能把思维固定在最基础的题型上，要加强举一反三的能力。