poj 树状数组入门 2352

浏览数：19 / 时间：2015年06月08日

#include <bits/stdc++.h>

using namespace std;

#define maxn 32005
int N;
int sum[maxn] , level[maxn];

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

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

void update(int x)
{
    while(x < maxn)
    {
        sum[x]++;
        x += lowbit(x);
    }
}

int main()
{
    while(~scanf("%d" , &N))
    {
        memset(sum, 0, sizeof(sum));
        memset(level, 0, sizeof(level));
        int x , y;
        int t = N;
        while(N--)
        {
            cin>>x>>y;
            x++;
            level[get_sum(x)]++;
            update(x);
        }
        for(int i=0; i<t; i++)
        cout<<level[i]<<endl;
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

poj 树状数组入门 2352