Flowers树状数组+离散化

本文主要是介绍Flowers树状数组+离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一些花，以及这些花开花的时间，问你在某一时间开花的总个数~~，很明显的树状数组题，插线问点。。

AC代码：

#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;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;
}

这篇关于Flowers树状数组+离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---