这是我的第一篇题解呢

点我传送

题目大意

题目描述

在一条数轴上有N个点，分别是1—N。一开始所有的点都被染成黑色。接着我们进行M次操作，第i次操作将[Li，Ri]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。

输入格式

输入一行为N和M。下面M行每行两个数Li、Ri。

输出格式

输出M行，为每次操作后剩余黑色点的个数。

题解

思考

我们要对一段区间进行处理，每次把l～r染黑，我们可以考虑用线段树维护区间内有多少黑色，lazytag标记将l～r全部染白。

接下来就是板子了。

code

#include <iostream>

using namespace std;

#define root 1, n, 1
#define lson l, m, rt * 2
#define rson m + 1, r, rt * 2 + 1
#define now_node l, r, rt

const int maxn = 200005;
long long m, n, z[maxn * 4] = {0}, flag[maxn * 4] = {0};

void update(int rt)
{
    z[rt] = z[rt * 2] + z[rt * 2 + 1]; 
}

void build(int l, int r, int rt) //建立一棵线段树
{
    if (l == r) //当左端点=右端点时，就表示它是一个叶子节点，这时我们就给它赋值
    {
        z[rt] = 1;
        return;
    }
    int m = (l + r) / 2; //二分当前区间
    build(lson);         //左边一段作为左子树，递归建立左子树
    build(rson);         //右边一段作为右子树，递归建立右子树
    update(rt);          //将左右子树的修改应用于当前节点
}

void add(int l, int r, int rt) 
{
    z[rt] = 0;
    flag[rt] = 1;
}

void push_down(int l, int r, int rt) //在询问时，把标记下放
{
    if (flag[rt] != 0)
    {
        int m = (l + r) / 2;
        add(lson); //打左儿子
        add(rson); //打右儿子 233
        flag[rt] = 0;        //标记清零
    }
}

void modify(int l, int r, int rt, int findl, int findr) //修改findl~findr区间的值，把它们都加上v
{
    if (findl == l && r == findr) //将区间的修改应用于它的每一个子节点
    {
        add(now_node);
        return;
    }
    push_down(now_node);
    int m = (l + r) / 2; //二分当前区间
    if (findl <= m)      //要修改的区间在左子树上
    {
        if (m < findr) //特判：要改的区间贯穿左右子树
        {
            modify(lson, findl, m);     //在左子树上改findl~m这段
            modify(rson, m + 1, findr); //在右子树上改m+1~findr这段
        }
        else
            modify(lson, findl, findr);
    }
    else
        modify(rson, findl, findr); //要找的区间在右子树上
    update(rt);
}

long long query(int l, int r, int rt, int findl, int findr) //询问某段区间的和 findl表示要询问的区间的左端点，findr表示要询问的区间的右端点
{
    if (findl == l && r == findr)
        return z[rt]; //当前端点等于要找的端点时 返回
    push_down(now_node);
    int m = (l + r) / 2; //二分当前区间
    if (findl <= m)      //要找的区间在左子树上
    {
        if (m < findr)
            return query(lson, findl, m) + query(rson, m + 1, findr); //特判：要找的区间贯穿左右子树
        else
            return query(lson, findl, findr);
    }
    else
        return query(rson, findl, findr); //要找的区间在右子树上
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m; //线段树区间的长度为n，有次操作
    build(root);   //从根结点开始建立线段树

    for (register int i = 1; i <= m; i++)
    {
        int l,r;
        cin >> l>>r;
        modify(root, l, r);
        cout << query(root, 1, n)<<endl;
    }
    return 0;
}