1. 首页
2. 树状数组
3. 本页

HDU 1541 Stars（树状数组）

QAQ明明记得之前都入过门，忘的真是快，，，，

统计下各个等级的星星数量，y是递增的，所以可以直接处理

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int MAXN = 320000+10;

int a[MAXN];
int level[MAXN];

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

void add(int x,int val)
{
    while(x<MAXN)
    {
        a[x]+=val;
        x+=lowbit(x);
    }
}

int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=a[x];
        x-=lowbit(x);
    }
    return ret;
}


int main()
{
    int n;
    while(cin>>n)
    {
        memset(a,0,sizeof(a));
        memset(level,0,sizeof(level));
        int x,y;
        for(int i=0; i<n; ++i)
        {
            cin>>x>>y;
            level[sum(++x)]++;
            add(x,1);
        }
        for(int i=0; i<n; ++i)
        {
            cout<<level[i]<<endl;
        }

    }


    return 0;
}