HDu 4325 Flowers線分ツリー+離散化(離散化の方法を習得する)

この问题は耻ずかしいforで循环して、それから配列の记录の下で过ごすことができます!!!理不尽だ~
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.
 
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 S
i
 and T
i
 (1 <= S
i
 <= T
i
 <= 10^9), means i-th flower will be blooming at time [S
i, T
i].
In the next M lines, each line contains an integer T
i, 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 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:
",++flag);
        for(int i=0;i<m;i++)
        {
            int k=bin(in[i],mm);
            printf("%d
",query(k,1));
        }
    }
    return 0;
}