校门外的树（增强版）

校门外的树（增强版）【线段树/模拟】

题目描述

校门外马路上本来从编号 $0$ 到 $L$，每一编号的位置都有一棵树。有砍树者每次从编号 $A$ 到 $B$ 处连续砍掉每一棵树，就连树苗也不放过（记 0 A B，含 $A$ 和 $B$）；幸运的是还有植树者每次从编号 $C$ 到 $D$ 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 C D，含 $C$ 和 $D$）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？

输入格式

第一行，两个正整数 $L$ 和 $N$，表示校园外原来有 $L + 1$ 棵树，并有 $N$ 次砍树或种树的操作。

以下 $N$ 行，每行三个整数，表示砍树或植树的标记和范围。

输出格式

共两行。第一行校门外留下的树苗数目，第二行种上又被拔掉的树苗数目。

样例输入

10 3
0 2 6
1 1 8
0 5 7

样例输出

3
2

提示

对于 $100 \%$ 的数据，$1 \le L \le 10000$，$1 \le N \le 100$。

思路

看数据范围，似乎是可以直接模拟的。不写了

线段树大法好√

注意：

① 树和树苗不是同一个概念

② 树坑的范围是从0 ~ n，需要转变为1 ~ n+1

维护两棵线段树，一棵只维护树的数量，另一棵维护树和树苗的数量。

每次砍树时，计算可砍数量。

每次种树时，计算需种数量。

可以得出： 树数量（n + 1） + 种数量 - 砍数量 = 剩数量

第一问：剩苗 = 剩数量 - 剩树（第一棵线段树最后的sum）

第二问：砍苗 = 砍数量 - （ 树数量 - 剩树）

CODE

template<class Info, class Laz>
struct SegTree
{
    int n;
    vector<int> arr;
    vector<Laz> laz;
    vector<Info> info;

    SegTree() : n(0) {}
    SegTree(int n_) : n(n_) 
    {
        init();
    }

    void init()
   {
        arr.resize(n + 5, 0);
        laz.resize(4 * n);
        info.resize(4 * n);
    }

    void build()
    {
        build(1, n, 1);
    }

    void build(int l, int r, int u)
    {
        if (l == r) 
        {
            info[u] = Info(arr[l]);
            return;
        }

        int mid = (l + r) >> 1;
        build(l, mid, u << 1);
        build(mid + 1, r, u << 1 | 1);
        push_up(u);
    }

    void apply(int u, Laz tag, int len)
    {
        laz[u].apply(tag);
        info[u].apply(tag, len);
    }

    void push_up(int u) 
    {
        info[u] = info[u << 1] + info[u << 1 | 1];
    }

    void push_down(int u, int llen, int rlen)
    {
        apply(u << 1, laz[u], llen);
        apply(u << 1 | 1, laz[u], rlen);
        laz[u] = Laz();
    }

    void modify(int l, int r, Laz tag) 
    {
        modify(l, r, tag, 1, n, 1);
    }

    void modify(int jobl, int jobr, Laz tag, int l, int r, int u) 
    {
        if (jobl <= l && jobr >= r) 
        {
            apply(u, tag, r - l + 1);
            return;
        }

        int mid = (l + r) >> 1;
        push_down(u, mid - l + 1, r - mid);
        if (jobl <= mid)
            modify(jobl, jobr, tag, l, mid, u << 1);
        if (jobr > mid)
            modify(jobl, jobr, tag, mid + 1, r, u << 1 | 1);
        push_up(u);
    }

    Info query(int l, int r) 
    {
        return query(l, r, 1, n, 1);
    }

    Info query(int jobl, int jobr, int l, int r, int u) 
    {
        if (jobl <= l && jobr >= r)
            return info[u];

        int mid = (l + r) >> 1;
        push_down(u, mid - l + 1, r - mid);
        Info ans = Info();
        if (job	l <= mid)
            ans = ans + query(jobl, jobr, l, mid, u << 1);
        if (jobr > mid)
            ans = ans + query(jobl, jobr, mid + 1, r, u << 1 | 1);
        return ans;
    }
};

struct Laz
{
    int change = inf;
    void apply(const Laz &tag)
    {
        if (tag.change != inf)
            change = tag.change;
    }
};

struct Info
{
    int sum = 0;
    Info() {}
    Info(int x) : sum(x) {}
    void apply(const Laz &tag, int len)
    {
        if (tag.change != inf)
            sum = tag.change * len;
    }

    Info operator+ (const Info &a) const
    {
       Info res;
       res.sum = sum + a.sum;
       return res;
    }
};

void solve()
{
    int n, m;   cin >> n >> m;
    SegTree<Info, Laz> seg1(n + 1), seg2(n + 1);
    for (int i=1;i<=n+1;i++)    seg1.arr[i] = 1, seg2.arr[i] = 1;
    seg1.build();
    seg2.build();

    int op, x, y, cut = 0, grow = 0;
    while (m --)
    {
        cin >> op >> x >> y;
        if (op == 0)
        {
            cut += seg2.query(x + 1, y + 1).sum;
            seg1.modify(x + 1, y + 1, {0});
            seg2.modify(x + 1, y + 1, {0});
        }
        else if (op == 1)
        {
            grow += y - x + 1 - seg2.query(x + 1, y + 1).sum;
            seg2.modify(x + 1, y + 1, {1});
        }
    }
    int stayTree = seg1.query(1, n + 1).sum;
    cout << n + 1 + grow - cut - stayTree << _endl << cut - (n + 1 - stayTree);
}