【hdu4325】【線段樹】Flowers 動态建樹

Flowers

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

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 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 Input

2

1 1

5 10

4

2 3

1 4

4 8

1

4

6

Sample Output

Case #1:

Case #2:

1

2

1

Author

BJTU

Source

2012 Multi-University Training Contest 3

Recommend

zhoujiaqi2010

線段樹基本操作，因為長度是 109 是以這裡要動态建樹

好像如果用數組寫線段樹可以用離散化來做

然後操作很基本，區間修改，單點查詢，查詢的時候如果沒有兒子節點說明那一片都是一樣的，直接傳回那一片就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define INF 2100000000
#define ll long long
#define clr(x)  memset(x,0,sizeof(x))
#define clrmax(x)  memset(x,127,sizeof(x))

using namespace std;

inline int read()
{
    char c;
    int ret=;
    while(!(c>='0'&&c<='9'))
        c=getchar();
    while(c>='0'&&c<='9')
    {
        ret=(c-'0')+(ret<<)+(ret<<);
        c=getchar();
    }
    return ret;
}

#define M 100005

struct tree2
{
    tree2 *lson,*rson;
    int n,lazy;
}*root,dizhi[M*];

int t,n,q;

void update(tree2 *tree)
{
    if(tree->lson==NULL)tree->lson=&dizhi[t++];
    if(tree->rson==NULL)tree->rson=&dizhi[t++];
    tree->lson->lazy+=tree->lazy;
    tree->rson->lazy+=tree->lazy;
    tree->lson->n+=tree->lazy;
    tree->rson->n+=tree->lazy;
    tree->lazy=;
}

void change(tree2 *tree,int l,int r,int x,int y)
{
    if(l==r||(x<=l&&y>=r))
    {
        tree->n++;
        tree->lazy++;
        return ;
    }
    if(tree->lazy)update(tree);
    int mid=(l+r)>>;
    if(x<=mid)
    {
        if(tree->lson==NULL)tree->lson=&dizhi[t++];
        change(tree->lson,l,mid,x,y);
    }
    if(y>mid)
    {
        if(tree->rson==NULL)tree->rson=&dizhi[t++];
        change(tree->rson,mid+,r,x,y);
    }
}

int find(tree2 *tree,int l,int r,int x)
{
    if(l==r||(tree->lazy&&tree->lson==NULL&&tree->rson==NULL))
        return tree->n;
    int mid=(l+r)>>;
    if(x<=mid)
        if(tree->lson==NULL)return tree->n;
        else 
        {
            if(tree->lazy)update(tree);
            return find(tree->lson,l,mid,x);
        }
    else if(tree->rson==NULL)return tree->n;
         else 
         {
            if(tree->lazy)update(tree);
            return find(tree->rson,mid+,r,x);
         }
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int T,ca=;
    T=read();
    while(T--)
    {
        ca++;
        clr(dizhi);
        t=;
        root=&dizhi[t++];
        n=read();q=read();
        for(int i=;i<=n;i++)
        {
            int a=read(),b=read();
            change(root,,,a,b);
        }
        printf("Case #%d:\n",ca);
        for(int i=;i<=q;i++)
        {
            int a=read();
            printf("%d\n",find(root,,,a));
        }
    }
    return ;
}
           

大概就是這個樣子，如果有什麼問題，或錯誤，請在評論區提出，謝謝。