265. 线段覆盖

★★☆ 输入文件：xdfg.in 输出文件：xdfg.out 简单对比
时间限制：2 s 内存限制：20 MB

【问题描述】

有一根长度为 L 的白色条状物。有两种操作：

用一条长度为 T 的黑布盖住条状物的 [a, a+T] 这个区间 (0<=a, T<=L) 。
把某条黑布拿走。

输入 L 和 n 次操作，要你输出每次操作之后：

条状物上有多少个黑区间。
条状物上黑区间的总长度。

【输入格式】

输入文件第一行两个整数L(1<=L<=200000), n(1<=n<=200000)

以下有n行,第2--n+1行每行有3个整数m,a,T，m表示操作类型,1表示放入黑布,2表示拿走黑布,a,T表示黑布在L上的起始位置与长度,拿走的黑布保证是原来已经存在的.

【输出格式】

输出有n行,每行两个整数x,y,x表示L上的黑区间个数,y表示黑区间的总长度.

【输入输出样例】

输入:

20 4
1 5 3
1 7 2
2 5 3
1 16 3

输出:

1 3
1 4
1 2
2 5

题解：

线段树的区间覆盖，因为这个题没有查询操作，所以可以不用pushdown。然后就是updata和insert操作了。updata中要判断tag的值，然后进行更新（是清成全黑，或者根据孩子更新）；add中对于找到的区间要看是否为单元素的，若为单元素的则直接更新，否则要判断tag的范围来进行。

AC代码：

#include<cstdio>

using namespace std;

#define N 200010

#define lc k<<1

#define rc k<<1|1

#define mid (l+r>>1)

struct node{

    int l,r,sum,len;

    bool flag;

}q[N<<];

int n,m,tag[N<<];

inline int read(){

    register int x=,f=;

    register char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void updata(int k,int l,int r){

    if(tag[k]>){

        q[k].l=q[k].r=q[k].sum=;q[k].len=r-l+;

    }

    else{

        q[k].l=q[lc].l;q[k].r=q[rc].r;

        q[k].sum=q[lc].sum+q[rc].sum;

        if(q[lc].r==q[rc].l&&q[lc].r==) q[k].sum--;

        q[k].len=q[lc].len+q[rc].len;

    }

    return ;

}

void add(int k,int l,int r,int x,int y,int v){

    if(x<=l&&r<=y){

        tag[k]+=v;

        if(l==r) q[k].l=q[k].r=q[k].sum=q[k].len=tag[k]>?:;

        else updata(k,l,r);

        return ;

    }

    if(y<=mid) add(lc,l,mid,x,y,v);

    else if(x>mid) add(rc,mid+,r,x,y,v);

    else add(lc,l,mid,x,mid,v),add(rc,mid+,r,mid+,y,v);

    updata(k,l,r);

}

int main(){

    freopen("xdfg.in","r",stdin);

    freopen("xdfg.out","w",stdout);

    n=read();m=read();

    for(int i=,x,y,z;i<=m;i++){

        z=read();x=read();y=read();

        if(z==)

            add(,,n,x,x+y-,);

        else

            add(,,n,x,x+y-,-);

        printf("%d %d\n",q[].sum,q[].len);

    }

    return ;

}

覆盖

COGS 265 线段覆盖

265. 线段覆盖