题目链接POJ2352,HDU1541

题目大意:给n个星星的坐标,输入保证纵坐标y按非递减序输入,并且不会两个星星位置重复。如果某个星星左下角(包含边界)共包含k个星星,则成该星星的等级为k。分别输出0~n-1等级的星星数量

解题思路:虽说这是道树状数组的入门题,但仍没反应过来。个人理解是:c数组维护的是<=idx的前缀和,每次将横坐标为x加入的时候可以先查询一下目前小于等于x的个数,这个利用getsum求得,然后用hash数组+1,之后要将这个x单点更新一下,也就是x位置单点+1。(之前有个疑惑,前缀和和这个排名有什么关系呢?是这样子的,下标为k的前缀和由于我们每次单点更新+1,这样getsum求出来的前缀和一定<=k,每次add(idx,1)表示之后只要比idx大的,也就是横坐标比它大的都能得到我这个1的贡献。那么getsum也就转化成了取<=k的点的贡献,也就是我们要求得的东西。这和求那个逆序数的思路很像,但是比那个好理解,注意转化那边,二维其实就是一维的拓展)。本题注意横坐标从0开始,要+1,否则树状数组步骤会死循环。


AC代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <utility>

using namespace std;
const int maxn = (int)32e3+5;

int c[maxn],ans[maxn],n;

inline int lowbit (int x) {
	return x & (-x);
}

void add (int idx, int num) {
	while (idx <= maxn) {
		c[idx] += num;
		idx += lowbit(idx);
	}
}

int get_sum (int idx) {
	int k = 0;
	while (idx > 0) {
		k += c[idx];
		idx -= lowbit(idx);
// idx &= idx - 1;
	}
	return k;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int x,y;
	while (cin >> n) {
		memset(c,0,sizeof(c));
		memset(ans,0,sizeof(ans));
		for (int i = 1; i <= n; i++) {
			cin >> x >> y;
			x++;//x坐标从0开始
			add(x,1);
			ans[get_sum(x)]++;  //getsum的含义是横坐标<=n的星星个数之和,这个和在这里表示等级 ans表示每个等级的个数
			
		}
		for (int i = 1; i <= n; i++) {
			cout << ans[i] << '\n';
		}
	}

	return 0;
}