数星星 Stars

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 751 字

树状数组二维偏序

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1536
// 题意：N 个点，每个点等级=其左下方（含正左、正下）的点数。输出 0 级到 N-1 级各有多少个点。点按 y 增序、同 y 按 x 增序给出。
// 思路：按 y 升序（输入已满足）逐个处理：点 (x,y) 的等级 = 当前已处理点中 x'≤x 的个数，用树状数组统计 x 坐标。再把该点计入 x 处。
// 复杂度：O(N log C) 时间 / O(C) 空间（C 为坐标上限 32000）
// 易错点：坐标含 0，树状数组下标从 1 起故 x+1；等级从 0 开始，最多 N-1 级。
#include <bits/stdc++.h>
using namespace std;
const int MAXC = 32005;
int bit[MAXC];
int n;
void add(int i){ for(;i<MAXC;i+=i&-i) bit[i]++; }
int sum(int i){ int s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }
int main(){
    if(!(cin>>n)) return 0;
    vector<int> ans(n,0);
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        int lv=sum(x+1);
        ans[lv]++;
        add(x+1);
    }
    for(int i=0;i<n;i++) cout<<ans[i]<<"\n";
    return 0;
}

数星星 Stars

正文

一本通·提高篇的其它内容