程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Flowers&&樹狀數組+離散化

Flowers&&樹狀數組+離散化

編輯：C++入門知識

題意：給你一些花，以及這些花開花的時間，問你在某一時間開花的總個數~~，很明顯的樹狀數組題，插線問點。。
AC代碼：
[cpp]
#include<cstdio>
#include<string.h>
#include<string>
#include<algorithm>
#include<iostream>
#define N 1000005
using namespace std;
typedef struct node
{
    int num;
    int id;
}Node;
bool cmp(Node a,Node b)
{return a.num<b.num;}
int s[N];
Node s1[N];
int s2[N];
int lowbit(int x)
{return x&(-x);}
void add(int x,int y)
{
    while(x<N)
    {
        s[x]+=y;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
     ans+=s[x];
     x-=lowbit(x);
    }return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;++k)
    {
        memset(s,0,sizeof(s));
        int n,m;
        scanf("%d%d",&n,&m);
        int tot=n<<1;
        int res=tot+m;
        for(int i=0;i!=res;++i)
        {
            scanf("%d",&s1[i].num);
            s1[i].id=i;
        }
        sort(s1,s1+res,cmp);
        int ans=0; www.2cto.com
        s2[s1[0].id]=++ans;
        for(int i=1;i!=res;++i)
            if(s1[i].num!=s1[i-1].num) s2[s1[i].id]=++ans;
            else   s2[s1[i].id]=ans;
            for(int i=0;i!=tot;)
            {
                add(s2[i++],1);
                add(s2[i++]+1,-1);
            }
            printf("Case #%d:\n",k);
            for(int i=tot;i!=res;++i)
            {
                printf("%d\n",sum(s2[i]));
            }
    }return 0;
}