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

 

Sample Output

 

Author

BJTU

 

Source

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<queue>

using namespace std;

#define N 110000

#define MOD 100000007

#define Lson r<<1

#define Rson r<<1|1

struct node

{

    int L, R, e;

    int Mid()

    {

        return (L+R)/;

    }

}a[N<<];

void BuildTree(int r, int L, int R)

{

    a[r].L=L, a[r].R=R, a[r].e=;

    if(L==R)

        return ;

    BuildTree(Lson, L, a[r].Mid());

    BuildTree(Rson, a[r].Mid()+, R);

}

void Update(int r, int L, int R)

{

    if(a[r].L==L && a[r].R==R)

    {

        a[r].e++;

        return ;

    }

    if(R<=a[r].Mid())

        return Update(Lson, L, R);

    else if(L>a[r].Mid())

        return Update(Rson, L, R);

    else

    {

        Update(Lson, L, a[r].Mid());

        Update(Rson, a[r].Mid()+, R);

    }

}

void UP(int r, int L, int R)

{

    if(L==R)

        return ;

    if(a[r].L==L && a[r].R==R )

    {

        a[Lson].e += a[r].e;

        a[Rson].e += a[r].e;

    }

    if(R<=a[r].Mid())

         UP(Lson, L, R);

    else if(L>a[r].Mid())

         UP(Rson, L, R);

    else

    {

         UP(Lson, L, a[r].Mid());

         UP(Rson, a[r].Mid()+, R);

    }

}

int Query(int r, int x)

{

    if(a[r].L==a[r].R && a[r].L==x)

       return a[r].e;

    if(x<=a[r].Mid())

        return Query(Lson, x);

    else

        return Query(Rson, x);

}

int main()

{

    int T, iCase=;

    scanf("%d", &T);

    while(T--)

    {

        int n, m, i, L, R, x;

        scanf("%d%d", &n, &m);

        BuildTree(, , );

        for(i=; i<n; i++)

        {

            scanf("%d%d", &L, &R);

            Update(, L, R);

        }

        UP(, , );

        printf("Case #%d:\n", iCase++);

        for(i=; i<m; i++)

        {

            scanf("%d", &x);

            printf("%d\n", Query(, x));

        }

    }

    return ;

}