HDU3577 线段树(区间更新)

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3577 ，普通的线段树区间更新题目，较简单。

　　相当于一个区间覆盖问题，有一点要注意的就是叶子节点是一个长度为1的区间，而不是一个离散的点，两种叶子节点的具体区别我在这篇博客里提到过。

#include <iostream>

#include <cstdio>

#include <vector>

#include <cmath>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

#define LL __int64

#define eps 1e-8

#define INF INT_MAX

#define lson l , m , rt << 1

#define rson m , r , rt << 1 | 1

const int MOD = ;

const int maxn =  + ;

const int N =  + ;

int cnt[maxn << ] , col[maxn << ];

int ans[N];

void build()

{

    memset(cnt ,  , sizeof(cnt));

    memset(ans ,  , sizeof(ans));

    memset(col ,  , sizeof(col));

}

void PushUp(int rt)

{

    cnt[rt] = max(cnt[rt << ] , cnt[rt <<  | ]);

}

void PushDown(int rt)

{

    if(col[rt]) {

        col[rt << ] += col[rt];

        col[rt <<  | ] += col[rt];

        cnt[rt << ] += col[rt];

        cnt[rt <<  | ] += col[rt];

        col[rt] = ;

    }

}

void update(int L , int R , int l , int r , int rt)

{

    if(L <= l && R >= r) {

        cnt[rt]++;

        col[rt]++;

        return;

    }

    PushDown(rt);

    int m = (l + r) >> ;

    if(L >= m)

        update(L , R , rson);

    else if(R <= m)

        update(L , R , lson);

    else {

        update(L , R , lson);

        update(L , R , rson);

    }

    PushUp(rt);

}

bool query(int L , int R , int k , int l , int r , int rt)

{

    if(L <= l && R >= r) {

        return cnt[rt] < k;

    }

    PushDown(rt);

    int m = (l + r) >> ;

    if(L >= m)

        return query(L , R , k , rson);

    else if(R <= m)

        return query(L , R , k , lson);

    else

        return query(L , R , k , lson) && query(L , R , k , rson);

}

int main()

{

    int T , i , n , m , k , a , b;

    cin >> T;

    for(int j =  ; j <= T ; j++)

    {

        build();

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

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

            scanf("%d %d" , &a , &b);

            if(query(a , b , k ,  , maxn , )) {

                update(a , b ,  , maxn , );

                ans[i]++;

            }

        }

        printf("Case %d:\n" , j);

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

            if(ans[i])

                printf("%d " , i);

        printf("\n\n");

    }

    return ;

}

提供几组测试数据：

4
3 6
1 6
1 6
3 4
1 5
1 2
2 4

3 10
2 4
4 6
6 8
2 8
1 8
1 2
1 10
2 9
3 7
9 10

3 10
4 5
5 6
6 7
7 8
9 10
1 4
1 10
2 9
4 6
3 8

3 8
4 6
6 8
9 10
1 4
1 10
2 9
4 6
3 8

Case 1:
1 2 3 5

Case 2:
1 2 3 4 5 6 10

Case 3:
1 2 3 4 5 6 7 8

Case 4:
1 2 3 4 5 6

巴特西

HDU3577 线段树(区间更新)

最新文章

热门文章