题目链接

• 时间限制: 1 s
• 空间限制: 128000 KB
• 题目等级 : 大师 Master

题目描述 Description

简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量

数据已重新装配，不会出现OLE错误

时限和数据范围适当修改，避免数据包过大而浪费空间资源

输入描述 Input Description

第1行共包括2个正整数，分别为N,M。

接下来m行每行两个正整数L,R

输出描述 Output Description

一共输出M行,每行输出切完之后剩下水果数量

样例输入 Sample Input

10 3

3 5

2 8

1 5

样例输出 Sample Output

7

3

2

数据范围及提示 Data Size & Hint

30% 的数据满足N,M<=5000

60% 的数据满足N,M<=100000

100% 的数据满足1<=L<=R<=N<=500000,1<=M<=500000

线段树实现。

#include <cstdio>

using namespace std;

struct node_type

{

    int l, r, lc, rc, sum; // l: 左区间, r: 右区间, lc: 左子树, rc: 右子树, sum: 该树有几个水果未删除。

    bool del; //删除标记

};

node_type node[1000010];

int tot = 0, root, n, m;

void update(int now) //更新 now 节点的 sum 值

{

    node[now].sum = node[node[now].rc].sum + node[node[now].lc].sum;

}

int make_tree(int l, int r) //建树

{

    int now = ++tot;

    node[now].l = l;

    node[now].r = r;

    node[now].del = false;

    if (l == r)

    {

        node[now].lc = node[now].rc = 0;

        node[now].sum = 1;

        return now;

    }

    int mid = (l + r) / 2;

    node[now].lc = make_tree(l, mid);

    node[now].rc = make_tree(mid + 1, r);

    update(now);

    return now;

}

void cut_fruit(int l, int r, int now) //切水果（删除 [l, r] ）

{

    if (node[now].del)

        return;

    if (l <= node[now].l && node[now].r <= r)

    {

        node[now].del = true;

        node[now].sum = 0;

        return;

    }

    int mid = (node[now].l + node[now].r) / 2;

    if (l <= mid && node[now].lc)

        cut_fruit(l, r, node[now].lc);

    if (r > mid && node[now].rc)

        cut_fruit(l, r, node[now].rc);

    update(now);

}

int main()

{

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

    int l, r;

    root = make_tree(1, n);

    node[0].sum = 0;

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

    {

        scanf("%d%d", &l, &r);

        cut_fruit(l, r, root);

        printf("%d\n", node[root].sum);

    }

    return 0;

}