首页 > 代码库 > cogs265.线段覆盖

cogs265.线段覆盖

2024-10-20 23:18:02   211人阅读

265. 线段覆盖

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

【问题描述】

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

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

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

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

【输入格式】

输入文件第一行两个整数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

[题解]

线段树维护区间被覆盖长度  段数  被覆盖层数  "左融合"  "右融合";由此可以实现每次O(1)查询;

解释:所谓左右融合其实就是判断用的,左右融合就是字面意思,能否与左边右边的黑布融合,用于数据上传;

本题难在两点:

1.数据上传的时候,通过"左融合"  "右融合"现实处理计算区间段数:

由儿子上传数据时,当前区间的段数等于左儿子的段数加右儿子的段数,

难点在于:如果左儿子最右边是被黑布盖着,右儿子左边是被黑布盖着,显然段数多算了1,

而左右融合此时的作用体现了,若左儿子右融合等于1,右儿子左融合等于1,那么此节点段数需要减1,正确性,,很显然啊....

2.(我之前就一直卡在这里)

本来我想用lazy下传黑布,后来发现不可做...必须每次操作具体到叶子,于是T了很多点,

后来发现这个题有个特点,  撤走的黑布一定存在! 

那么就不需要lazy下传了,只需要维护区间被盖了几次

撤走黑布就把盖的次数-1;

当被覆盖0次那么所有数据清空;

否则保留.

于是,A了.

[代码]

#include <cstdio>
#include <algorithm>
using namespace std;
int n,t;
struct d
{
    int len,s;
    int zr,yr;
    int c;
};
d node[400000];
inline void gengxin(int o,int l,int r)
{
    if(node[o].c>0)
    {
        node[o].zr=node[o].yr=node[o].s=1;
        node[o].len=r-l+1;
        return;
    }
    else
    {
        node[o].zr=node[o*2].zr;
        node[o].yr=node[o*2+1].yr;
        node[o].len=node[o*2].len+node[o*2+1].len;
        node[o].s=node[o*2].s+node[o*2+1].s;
        if(node[o*2].yr==1&&node[o*2+1].zr==1)node[o].s--;
        return ;
    }
}
inline void add(int o,int l,int r,int nl,int nr,int v)
{
    if(l>=nl&&r<=nr)
    {
        node[o].c+=v;
        if(l==r)
        {
            if(node[o].c>0)
            {
                node[o].len=node[o].zr=node[o].yr=node[o].s=1;
                return;
            }
            else
            {
                node[o].len=node[o].zr=node[o].yr=node[o].s=0;
                return;
            }
        }
        else
        {
            gengxin(o,l,r);
            return;
        }
    }
    int m=(l+r)>>1;
    if(m>=nl)
    {
        add(o*2,l,m,nl,nr,v);
    }
    if(m<nr)
    {
        add(o*2+1,m+1,r,nl,nr,v);
    }
    gengxin(o,l,r);
}
int main()
{
    freopen("xdfg.in","r",stdin);
    freopen("xdfg.out","w",stdout);
    scanf("%d%d",&n,&t);
    while(t--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x==1)
        {
            add(1,1,n,y,y+z-1,1);
        }
        else
        {
            add(1,1,n,y,y+z-1,-1);
        }
        printf("%d %d\n",node[1].s,node[1].len);
    }
    return 0;
}

 

cogs265.线段覆盖


联系
我们