E.签到题

题目描述
恭喜你找到了本场比赛的签到题！
为了让大家都有抽奖的机会，只需要复制粘贴以下代码（并且稍微填下空）即可 AC：
（我超良心的）

#include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <climits>
 #include <cstdio>
 #include <vector>
 #include <cstdlib>
 #include <ctime>
 #include <cmath>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set>
 #define fi first
 #define lc (x<<1)
 #define se second
 #define U unsigned
 #define rc (x<<1|1)
 #define Re register
 #define LL long long
 #define MP std::make_pair
 #define CLR(i,a) memset(i,a,sizeof(i))
 #define FOR(i,a,b) for(Re int i = a;i <= b;++i)
 #define ROF(i,a,b) for(Re int i = a;i >= b;--i)
 #define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
 #define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
 #define DEBUG(x) std::cerr << #x << '=' << x << std::endl
 const int MAXN = 1000000+5;
 int N,maxL;
 std::set<std::pair<int,int> > L;
 inline int calc(){
     // 返回 set 中所有线段的并长度。(每个 pair 表示一个线段[first,second]
 }
 int main(){
     scanf("%d%d",&N,&maxL);
     while(N--){
         int opt,x,y;
         scanf("%d%d%d",&opt,&x,&y);
         if(opt == 1){
             if(L.find(MP(x,y)) != L.end()) continue;
             L.insert(MP(x,y));
         }
         if(opt == 2){
             if(L.find(MP(x,y)) == L.end()) continue;
             L.erase(MP(x,y));
         }
         if(opt == 3){
             printf("%d\n",calc());
         }
     }
     return 0;
 }

输入描述:
第一行两个整数 N,L，意义如代码所述。
接下来 N 行，每行三个整数 opt,l,r，意义如代码所述。

输出描述:
对于每一组 opt=3 的询问输出一个答案。

题解
这里我们考虑用线段树的做，我们用a[N]表示节点表示的线段的覆盖次数（ 不是和），b[N]表示节点表示的线段的答案，在添加时只需要将该线段在线段树中表示的线段标记加1，在删除的时候只需要将该线段在线段数中表示的线段标记减1，这样，如果要删去的线段为某一线段的子线段，那么删除后肯定能保证原线段在线段树中对应的线段标记至少为1，应为删除的线段在之前肯定添加过，这样就能保证答案的正确性。
附代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e7+5;
int a[N<<2],b[N<<2];
set<pii>s;
void updata(int x,int y,int z,int l,int r,int rat){
    if(x<=l&&r<=y){
        a[rat]+=z;
        if(a[rat])b[rat]=r-l+1;
        else if(l!=r)b[rat]=b[rat<<1]+b[rat<<1|1];
        else b[rat]=0;//单点情况
        return ;
    }
    int mid=(r+l)>>1;
    if(mid>=x)
        updata(x,y,z,l,mid,rat<<1);
    if(mid<y)
        updata(x,y,z,mid+1,r,rat<<1|1);
    if(a[rat])b[rat]=r-l+1;
    else if(l!=r)b[rat]=b[rat<<1]+b[rat<<1|1];
    else b[rat]=0;//单点情况
}
int main(){
    int n,m;
    cin>>n>>m;
    while(n--){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt == 1){
            if(s.find((pii){x,y}) != s.end()) continue;
            s.insert((pii){x,y});
            updata(x,y,1,1,m,1);
        }
        if(opt == 2){
            if(s.find((pii){x,y}) == s.end()) continue;
            s.erase((pii){x,y});
            updata(x,y,-1,1,m,1);
        }
        if(opt == 3){
            cout<<b[1]<<'\n';
        }
    }
    return 0;
}