POJ - 2352 Stars

思路

考虑到是从左往右，从下往上给点的，所以可以遍历这个顺序把点插入到树状数组中，每次插入前，看当前树状数组中有多少个x是小于此时的X的，就算是这个点的level了。

代码

模板大于代码系列

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int tr[maxn];
int ans[maxn];

int lowbit(int x){
    return x&-x;
}
void add(int idx,int v){
    for(int i = idx;i<=32001;i += lowbit(i)) tr[i] += v;
}
int query(int r){
    int sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int main(){
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++){
        int x,y;cin>>x>>y; x += 1;
        ans[query(x)] += 1;
        add(x,1);
    }
    for(int i = 0;i<=N-1;i++) cout<<ans[i]<<'\n';
    return 0;
}