p2352szsz.cpp

来自「大概POJ上50道比较难的题的代码」· C++ 代码 · 共 33 行

#include <iostream>
using namespace std;
const int MAXN = 32010;
int c[MAXN],ans[MAXN];
inline int lowbit(int x){
    return x & (-x);
}
void change(int x){
    while(x <= MAXN){
        ++c[x];
        x += lowbit(x);
    }
}
int sum(int x){
    int res(0);
    while(x > 0){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main (){
    int N,x,y;
    cin >> N;
    for(int i = 0;i < N;++i){
        scanf("%d%d",&x,&y);
        ++ans[sum(x+1)];
        change(x+1);
    }
    for(int i = 0;i < N;++i)
        printf("%d\n",ans[i]);
}