首页 > 代码库 > COGS 265线段覆盖[线段树]
COGS 265线段覆盖[线段树]
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
需要维护的是区间个数和总长度
保存区间cnt,len，区间处理需要lazy标记，考虑合并需要知道左右断点是否覆盖，lcov和rcov
本题只需要考虑更新就可以了，没有查询操作
merge时考虑lazy标记
注意叶子节点直接处理
//// main.cpp// cogs265//// Created by Candy on 10/9/16.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define m (l+r)/2#define lson o<<1,l,m#define rson o<<1|1,m+1,r#define lc o<<1#define rc o<<1|1const int N=2e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int L,n,op,a,T;struct node{ int cnt,len,lcov,rcov; int lazy;}t[N<<2];void merge(int o,int l,int r){ if(t[o].lazy>0){ t[o].cnt=t[o].lcov=t[o].rcov=1;t[o].len=r-l+1; }else{ t[o].lcov=t[lc].lcov; t[o].rcov=t[rc].rcov; t[o].cnt=t[lc].cnt+t[rc].cnt; if(t[lc].rcov==1&&t[rc].lcov==1) t[o].cnt--; t[o].len=t[lc].len+t[rc].len; }}void add(int o,int l,int r,int ql,int qr,int v){//printf("add %d %d %d\n",o,l,r); if(ql<=l&&r<=qr){ t[o].lazy+=v; if(l==r) t[o].len=t[o].cnt=t[o].lcov=t[o].rcov=t[o].lazy>0?1:0; else merge(o,l,r); }else{ if(ql<=m) add(lson,ql,qr,v); if(m<qr) add(rson,ql,qr,v); merge(o,l,r); }}int main(int argc, const char * argv[]){ //freopen("xdfg.in","r",stdin); //freopen("xdfg.out","w",stdout); L=read();n=read(); for(int i=1;i<=n;i++){ op=read();a=read();T=read(); if(op==1) add(1,1,L,a,a+T-1,1); else add(1,1,L,a,a+T-1,-1); printf("%d %d\n",t[1].cnt,t[1].len); } return 0;}
COGS 265线段覆盖[线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。