Ural 1028.Strs

1003 ワード

データ構造 ural

ツリー配列の授業を見た時にこの問題を見ました.星の座標を与えます.Y軸は小さいから大きいまで秩序があります.それではy軸の順番で樹状配列の値を修正して、1-xの区間と恒星の左下にある恒星の数を求めます.

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=15010;
const int maxm=32010;
int num[maxn],x[maxn];
int c[maxm],my;
int lowbit(int k)
{
    return k&(-k);
}
int query(int k)
{
    int sum=0;
    while(k>0)
    {
        sum+=c[k];
        k-=lowbit(k);
    }
    return sum;
}
void update(int k)
{
    while(k<=my)
    {
        c[k]+=1;
        k+=lowbit(k);
    }
}
int main()
{
    //freopen("data","r",stdin);
    int y,n;
    while(~scanf("%d",&n))
    {
        memset(num,0,sizeof(num));
        memset(c,0,sizeof(c));
        my=0;
        for(int i=0;imy)
             my=x[i];
        }
        my++;
        for(int i=0;i

linuxメモリ管理--パートナーシステムとメモリ分配器