洛谷 P2161 [SHOI2009]会场预约

• 题意: 维护一个区间，A操作表示把l，r区间上的所有线段清空，加入一条新的线段，并输入删除了多少条线段。B操作输出当前还剩多少条线段
• 思路: 线段树维护区间染色，因为后面的颜色不可能跟前面的颜色相同，线段树的操作就只有下放没有push_up,且维护del数组记录这个颜色是否被删除了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef  pair<int,int> pii;
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
int n,m;
int ans,era;
struct node{
    int l,r;
    int lazy,col; // 被那条线段覆盖，区间是否完全被覆盖
}sgt[N*4];
int del[N*4];   // 线段是否被删除
void push_down(int rt){
    if(!sgt[rt].lazy) sgt[rt].col = 0;// 没有被覆盖
    else{
        sgt[rt*2].lazy = sgt[rt*2+1].lazy = sgt[rt].lazy;   // 左右子树都被覆盖
        sgt[rt].lazy = sgt[rt].col = 0;                     // 清空自身信息
    }
}

void build(int l,int r,int rt){
    sgt[rt].l = l ; sgt[rt].r = r;
    sgt[rt].col = 1;            // 一开始为空，被覆盖
    if(l==r)    return ;
    int mid = (l+r)>>1;
    if(l<=mid)  build(l,mid,rt*2);
    if(r>mid)   build(mid+1,r,rt*2+1);
}
void find(int rt,int col){
    if(sgt[rt].col){           // 已经被覆盖
        if(!del[sgt[rt].lazy] && sgt[rt].lazy)      // 当前被覆盖的线段存在
            --ans,++era;       // 更新答案
        del[sgt[rt].lazy] = 1; // 将其删去
        sgt[rt].lazy = col;    // 被新的线段覆盖
        return ;
    }
    find(rt*2,col);            // 删除左右子树
    find(rt*2+1,col);
    sgt[rt].lazy = col;         // 被覆盖
    sgt[rt].col = 1;            // 被覆盖
}
void update(int l,int r,int rt,int col){
    if(sgt[rt].l >= l && sgt[rt].r <= r){
        find(rt,col); return ;      // 递归到当前区间，进行删除
    }
    push_down(rt);
    int mid =(sgt[rt].l + sgt[rt].r) >> 1;
    if(l <= mid)    update(l,r,rt*2,col);
    if(r > mid)     update(l,r,rt*2+1,col);
}

int main(){
    int n;
    build(1,100000,1);
    char op[3];
    int l,r,cnt = 0 ;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",op);
        if(op[0]=='B'){
            printf("%d\n",ans);
        }else{
            scanf("%d%d",&l,&r);
            ++ans,era = 0;  // ans代表当前还剩多少条线段，era代表当前操作删去了多少线段
            update(l,r,1,i);
            printf("%d\n",era);
        }
    }
    return 0;
}