数星星 Stars LibreOJ
题目描述
原题来自：Ural 1028
天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下）有 k 级的。
例如，上图中星星 3 级的星星。
给定星星的位置，输出各级星星的数目。
一句话题意 n 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。
输入格式
第一行一个整数 x 坐标增序给出。
输出格式
N−1 级的星星的数目。
样例
| Input | Output |
|---|---|
5 1 1 5 1 7 1 3 3 5 5 |
1 2 1 1 0 |
数据范围与提示
对于全部数据，1≤N≤1.5×104,0≤x,y≤3.2×104。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10; ll Case, n, m, i, j; ll a[1500010],ans[1500010]; inline void add(ll x, ll y) { for (ll i = x; i <= 1500010; i += i & (-i)) { a[i] += y; } } inline ll getsum(ll x) { ll sum = 0; for (ll i = x; i; i -= i & (-i)) { sum += a[i]; } return sum; } int main() { scanf("%lld", &n); for (i = 1; i <= n; i++) { ll x,y; scanf("%lld%lld", &x,&y); ll t = getsum(x + 1); ans[t]++; add(x + 1, 1); } for (i = 0; i < n; i++) { printf("%lld ", ans[i]); } }