题解 | #签到题#

签到题 (nowcoder.com)

问题描述：添加、删除线段，并求总的线段并。

思路：线段树。

pushup(int u)函数用来将以u为根的两个儿子的的最小区间并的长度合并到结点u，对儿子的区间并长度减去获得到的最小区间并长度。

void pushup(int u) {
    int mi = min(tr[ls(u)].cover, tr[rs(u)].cover);
    tr[ls(u)].cover -= mi; tr[rs(u)].cover -= mi;
    tr[u].cover += mi;
}

pushdown(int u)函数进行lazy标记的向下覆盖。

void pushdown(int u) {
    auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];
    if(root.cover) {
        left.cover += root.cover;
        right.cover += root.cover;
        root.cover = 0;
    }
}

modify(int u, int l, int r, int k)函数对区间的覆盖次数进行加减。

void modify(int u, int l, int r, int k) {
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].cover += k;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(ls(u), l, r, k);
    if(r > mid) modify(rs(u), l, r, k);
    pushup(u);
}

query(int u, int l, int r)函数查询。

int query(int u, int l, int r) {
    LL res = 0;
    if(tr[u].l >= l && tr[u].r <= r) {
        if(tr[u].cover > 0) {
            res += tr[u].r - tr[u].l + 1;
        } else if(l != r) {
            int mid = tr[u].l + tr[u].r >> 1;
            pushdown(u);
            if(l <= mid) res += query(ls(u),l,mid);
            if(r > mid) res += query(rs(u),mid+1,r);
        }
        return res;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if(l <= mid) res += query(ls(u),l,r);
        if(r > mid) res += query(rs(u),l,r);
        return res;
    }
}

AC代码：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;
struct SegTree {
    int l,r,cover; // cover统计该区间的覆盖次数
}tr[N << 2];
inline int ls(int u) { return u << 1; }
inline int rs(int u) { return u << 1 | 1; }
void pushup(int u) {
    int mi = min(tr[ls(u)].cover, tr[rs(u)].cover);
    tr[ls(u)].cover -= mi; tr[rs(u)].cover -= mi;
    tr[u].cover += mi;
}
void pushdown(int u) {
    auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];
    if(root.cover) {
        left.cover += root.cover;
        right.cover += root.cover;
        root.cover = 0;
    }
}
void build(int u, int l, int r) {
    if(l == r) tr[u] = {l,r,0};
    else {
        int mid = l + r >> 1;
        tr[u] = {l,r};
        build(ls(u), l, mid), build(rs(u), mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int l, int r, int k) {
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].cover += k;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(ls(u), l, r, k);
    if(r > mid) modify(rs(u), l, r, k);
    pushup(u);
}
int query(int u, int l, int r) {
    LL res = 0;
    if(tr[u].l >= l && tr[u].r <= r) {
        if(tr[u].cover > 0) {
            res += tr[u].r - tr[u].l + 1;
        } else if(l != r) {
            int mid = tr[u].l + tr[u].r >> 1;
            pushdown(u);
            if(l <= mid) res += query(ls(u),l,mid);
            if(r > mid) res += query(rs(u),mid+1,r);
        }
        return res;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if(l <= mid) res += query(ls(u),l,r);
        if(r > mid) res += query(rs(u),l,r);
        return res;
    }
}
void inpfile();
void solve() {
    int n,L; cin>>n>>L;
    build(1,1,L);
    set<PII> s;
    while(n--) {
        int opt,l,r; cin>>opt>>l>>r;
        if(opt == 1) {
            if(s.find({l,r}) != s.end()) continue;
            s.insert({l,r});
            modify(1,l,r,1);
        } else if(opt == 2) {
            if(s.find({l,r}) == s.end()) continue;
            s.erase({l,r});
            modify(1,l,r,-1);
        } else if(opt == 3) {
            cout<<query(1,1,L)<<endl;
        }
    }
}
int main()
{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}