11247: 【原1247】老鹿召唤树人

题目

题目描述

author: Xingdong Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1247

Description

玩过魔兽争霸3的同学们都知道暗夜精灵有一个英雄叫老鹿，他有一个技能是召唤树人。在这个过程中，他会把一定范围内的树变成树人。现在我们假设老鹿面前有一排树，他们的编号是0,1,2,...,L。假设技能覆盖的范围由两个整数给出，在这个范围内的树会全部变成树人。我们现在要知道在老鹿释放了M次召唤树人的技能后还剩下几棵树。

Input Format

第一行：输入两个整数L，M。L代表树木最大的编号，M代表老鹿释放召唤树人技能的次数。L和M之间用一个空格隔开。

接下来的M行：每行都有两个整数，这两个整数由一个空格隔开，表示老鹿技能的释放范围（两端的树也在范围内）。

Output Format

输出一行，这一行只有一个整数，表示在释放技能之后还剩余的树的数目。

Sample Input

500 2
150 200
180 210

Sample Output

440

Hint

对于20%的数据，技能覆盖的范围没有重合的部分；对于其他的数据，范围有重合的情况。

L的大小范围：\( 1 \leq L \leq 10000 \)

M的大小范围：\( 1 \leq M \leq 100 \)

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

class node {
public:
    int left = 0, right = 0;
    int val = 0;
    bool flag = false;
};

node smt[100009];

void build_tree(int l, int r, int root) {
    smt[root].left = l;
    smt[root].right = r;
    if (l == r - 1) {
        smt[root].val = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(l, mid, root * 2);
    build_tree(mid, r, root * 2 + 1);

    smt[root].val = smt[root * 2].val + smt[root * 2 + 1].val;
}

void push_down(int root) {
    if (smt[root].flag) {
        smt[root].flag = false;
        smt[root * 2].val = 0;
        smt[root * 2 + 1].val = 0;
        smt[root * 2].flag = true;
        smt[root * 2 + 1].flag = true;
    }
}

void update(int l, int r, int root) {
    if (l <= smt[root].left && smt[root].right <= r) {
        smt[root].val = 0;
        smt[root].flag = true;
        return;
    }
    int mid = (smt[root].left + smt[root].right) >> 1;
    push_down(root);
    if (l < mid)
        update(l, r, root * 2);
    if (r > mid)
        update(l, r, root * 2 + 1);
    smt[root].val = smt[root * 2].val + smt[root * 2 + 1].val;
}

int query(int l, int r, int root) {
    if (l <= smt[root].val && smt[root].val <= r) {
        return smt[root].val;
    }
    int mid = (smt[root].left + smt[root].right) >> 1;
    push_down(root);
    int ans = 0;
    if (l < mid) {
        ans += query(l, r, root * 2);
    }
    if (r > mid) {
        ans += query(l, r, root * 2 + 1);
    }
    return ans;
}

int main() {
    int M, L;
    scanf("%d %d", &L, &M);

    build_tree(0, L + 1, 1);

    for (; M > 0; --M) {
        int a, b;
        scanf("%d %d", &a, &b);

        update(a, b + 1, 1);
    }

    printf("%d", query(0, L + 1, 1));

    return 0;
}

yyong119's solution

#include <iostream>
#define MAX_N 10000
using namespace std;

int tree[MAX_N << 2];
int n, m;

void update(int d, int dl, int dr, int l, int r) {
    if (dl == dr) tree[d] = 1;
    else {
        int mid = (dl + dr) >> 1;
        if (r <= mid) update(d << 1, dl, mid, l, r);
        else if (l > mid) update(d << 1 | 1, mid + 1, dr, l, r);
        else {
            update(d << 1, dl, mid, l, mid);
            update(d << 1 | 1, mid + 1, dr, mid + 1, r);
        }
        tree[d] = tree[d << 1] + tree[d << 1 | 1];
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin >> n >> m;
    while(m--) {
        int l, r;
        cin >> l >> r;
        update(1, 1, n + 1, l + 1, r + 1);
    }
    cout << n + 1 - tree[1] << endl;
    return 0;
}