这道题无耻就无耻在用for循环，然后数组记录下也可以过！！！没天理了~
Problem Description
Problem Description
As is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many flowers will bloom in the garden in a specific time.
But there are too many flowers in the garden, so he wants you to help him.
But there are too many flowers in the garden, so he wants you to help him.
Input
The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times.
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times.
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.
Output
For each case, output the case number as shown and then print M lines. Each line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.
Sample outputs are available for more details.
Sample Input
2 1 1 5 10 4 2 3 1 4 4 8 1 4 6
Sample Output
Case #1: 0 Case #2: 1 2 1
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxx 100002
struct node
{
int left,right,count;
}nodes[maxx<<2];
int n,m;
int li[maxx],ri[maxx];
int x[maxx<<4],in[maxx];
void build(int left,int right,int id)
{
nodes[id].left=left;
nodes[id].right=right;
nodes[id].count=0;
if(left==right)
return ;
int mid=(left+right)>>1;
build(left,mid,id<<1);
build(mid+1,right,id<<1|1);
}
void update(int left,int right,int id)
{
if(nodes[id].left>=left&&nodes[id].right<=right)
{
nodes[id].count++;
return;
}
if(nodes[id].count>0)
{
nodes[id<<1].count+=nodes[id].count;
nodes[id<<1|1].count+=nodes[id].count;
nodes[id].count=0;
}
int mid=(nodes[id].left+nodes[id].right)>>1;
if(mid>=right)
update(left,right,id<<1);
else if(mid<left)
update(left,right,id<<1|1);
else
{
update(left,mid,id<<1);
update(mid+1,right,id<<1|1);
}
}
int query(int k,int id)
{
if(nodes[id].left==nodes[id].right)
return nodes[id].count;
if(nodes[id].count>0)
{
nodes[id<<1].count+=nodes[id].count;
nodes[id<<1|1].count+=nodes[id].count;
nodes[id].count=0;
}
int mid=(nodes[id].left+nodes[id].right)>>1;
if(k<=mid)
return query(k,id<<1);
else
return query(k,id<<1|1);
}
int bin(int key,int n)
{
int l=0,r=n-1;
while(l<=r)
{
int m=(l+r)>>1;
if(x[m]==key) return m;
if(x[m]<key) l=m+1;
else r=m-1;
}
}
int main()
{
int cases,c,flag=0;
scanf("%d",&cases);
while(cases--)
{
scanf("%d%d",&n,&m);
memset(x,0,sizeof(x));
memset(in,0,sizeof(in));
int nn=0;
//数组x用于离散化，注意，应该将所有的输入值都进行记录，第二个for语句不可以省，否则没有离散化的点会输出0
for(int i=0;i<n;i++)
{
scanf("%d%d",&li[i],&ri[i]);
x[nn++]=li[i];
x[nn++]=ri[i];
}
for(int i=0;i<m;i++)
{
scanf("%d",&in[i]);
x[nn++]=in[i];
}
sort(x,x+nn);
int mm=1;
for(int i=1;i<nn;i++)
{
if(x[i]!=x[i-1])
x[mm++]=x[i];
}
for(int i=mm-1;i>0;i--)
{
if(x[i]!=x[i-1]+1)
x[mm++]=x[i-1]+1;
}
sort(x,x+mm);
build(0,mm,1);
//注意，因为下面二分查找是从0开始，所以建树的时候应该从0开始
for(int i=0;i<n;i++)
{
int l=bin(li[i],mm);
int r=bin(ri[i],mm);
update(l,r,1);
}
printf("Case #%d:\n",++flag);
for(int i=0;i<m;i++)
{
int k=bin(in[i],mm);
printf("%d\n",query(k,1));
}
}
return 0;
}