签到题

好久没刷题了，写个线段树要debug那么久，能过我也是觉得很神奇的。建立线段树维护每个节点上一个cover值，cover值如果大于0，代表这个节点代表的区间被覆盖了cover次，query 的时候统计cover值>0的区间的长度和。 当然，如果这个节点cover不大于0，两边的叶子都要查看。

其余的就是增加和删除的时候维护cover值，注意pushup,pushdown 即可

# include <cstdio>
# include <cstring>
# include <cctype>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;


const int debug = 1;
const int size  = 900000 + 10; 
const int INF = INT_MAX>>1;
typedef long long ll;

struct node{
    int cover;
} tree[size];

void pushdown(int no) {
    tree[no<<1].cover += tree[no].cover;
    tree[no<<1|1].cover += tree[no].cover;
    tree[no].cover = 0;
}

void pushup(int no) {
    int v = min(tree[no<<1].cover, tree[no<<1|1].cover);
    tree[no<<1].cover -= v;
    tree[no<<1|1].cover -= v;
    tree[no].cover += v;
}

void Build(int no,int lb,int rb){
    if (lb==rb){
        tree[no].cover = 0;
    }else {
        int mid = (lb + rb)>>1;
        Build(no<<1,lb,mid);
        Build(no<<1|1,mid+1,rb);
        tree[no].cover = 0;
    }
}

ll Query(int a,int b,int no,int lb,int rb){
    ll ret = 0;
    if (a<=lb&&rb<=b){
        if (tree[no].cover > 0){
            ret += rb - lb + 1;
            // cout << "rb lb " << lb << " " << rb  << endl;
        }else if (lb != rb){
            int mid = lb+rb>>1;    
            pushdown(no);
            ret += Query(a,b,no<<1,lb,mid);
            ret += Query(a,b,no<<1|1,mid+1,rb);
            pushup(no);
        }
    }
    return ret;
}

void Add(int a,int b,int c, int no,int lb,int rb){
    if (a<=lb&&rb<=b){
        tree[no].cover += c;
    }else {
        int mid = lb+rb>>1;
        pushdown(no);
        if (a <= mid)    Add(a,b,c, no<<1,lb,mid);
        if (b > mid)    Add(a,b,c, no<<1|1,mid+1,rb);
        pushup(no);
    }
}

typedef pair<int, int> pir;

int main(){
    int n,q;
    scanf("%d%d", &q, &n);
    n++;
    set<pir> st;
    Build(1, 1, n);
    while (q--){
        int op, a, b; scanf("%d%d%d", &op, &a, &b);
        a++, b++;
        // cout << op << endl;
        if (op==1){
            if (st.find(pir(a, b)) != st.end()) continue;
            st.insert(pir(a, b));
            // cout << "Insert" << a << " " << b << endl;
            Add(a, b, 1, 1, 1, n);
        }else if (op == 2){
            if (st.find(pir(a, b)) == st.end()) continue;
            // cout << "erase " << a << " " << b << endl;
            Add(a, b, -1, 1, 1, n);
        }else if (op == 3){
            printf("%d\n", Query(1, n, 1, 1, n));
        }
    }
    return 0;
}