HDU 4325 Contest 3

很明显的区间加减单点查询。但由于规模大，于是离散化。在离散化的时候，可以把要查询的点也加入离散化的数组中。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define lowbit(x) ((x)&(-x))
#define LL __int64
using namespace std;

int tpoint[400010];
int save[100010];
int a[400020];

struct flower{
	int bgn,en;
}TF[100010];
int np,al;

int sum(int x){
  int s=0;
  for(;x;x-=lowbit(x))s+=a[x];
  return s;
}

void update(int x,int w){
  for(;x<=np;x+=lowbit(x))
  a[x]+=w;
}

int find(int p){
	int l=1,r=np;
	while(l<=r){
		int mid=(l+r)/2;
		if(tpoint[mid]==p)
		return mid;
		else if(tpoint[mid]<p)
		l=mid+1;
		else if(tpoint[mid]>p)
		r=mid-1;
	}
}

int main(){
	int T,n,m,p,su,kase=0; int pos;;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		np=1;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			scanf("%d%d",&TF[i].bgn,&TF[i].en);
			tpoint[np++]=TF[i].bgn; tpoint[np++]=TF[i].en;
		}
		for(int i=1;i<=m;i++){
			scanf("%d",&p);
			tpoint[np++]=p;
			save[i]=p;
		}
		sort(tpoint+1,tpoint+np);
		np=unique (tpoint+1, tpoint + np) - tpoint;
		for(int i=1;i<=n;i++){
			int f=find(TF[i].bgn);
			int b=find(TF[i].en);
			update(f,1);
			update(b+1,-1);
		}
		printf("Case #%d:
",++kase);
		for(int i=1;i<=m;i++){
			pos=find(save[i]);
			printf("%d
",sum(pos));
		}
	}
}