P2434 [SDOI2005] 区间题解

lhz2022 · 2024-09-06 20:30:14 · 题解

拿到的第一反应就是线段树。

感觉题目中有一个地方比较坑，就是：

相邻的区间如样例，当两个区间 [1,4] 和 [5,10] 反映到数组上面时，就会发现它变成了 [1,10] 一个区间。

解决方法：超级加倍具体来说，在输入的 2 到 n-1 行中，每一个 [a_i,b_i] 都变成 [2\times a_i,2\times b_i] 这样相邻的区间中会至少相隔一个数字。

最后只需要从 1 枚举到 2000001 得到这个点是否被覆盖基本上就搞定了

然后我们就可以赶制出这坨代码。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 2000007
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fll
int n,m,a[N];
struct tree{
    int val,lazy;
}tr[N<<2];
void push_up(int rt){
    tr[rt].val=min(tr[rt<<1].val,tr[rt<<1|1].val);
}
void push_down(int rt){
    if(tr[rt].lazy!=0){
        tr[rt<<1].lazy=tr[rt].lazy;
        tr[rt<<1|1].lazy=tr[rt].lazy;
        tr[rt<<1].val=tr[rt].lazy;
        tr[rt<<1|1].val=tr[rt].lazy;
        tr[rt].lazy=0;
    }
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r) return tr[rt].val;
    push_down(rt);
    int mid=(l+r)>>1;
    if(qr<=mid) return query(rt<<1,l,mid,ql,qr);
    if(ql>mid) return query((rt<<1)|1,mid+1,r,ql,qr);
    return min(query(rt<<1,l,mid,ql,qr),query((rt<<1)|1,mid+1,r,ql,qr));
}

void update(int rt,int l,int r,int ul,int ur,int add){
    if(ul<=l&&ur>=r){
        tr[rt].val=add;
        tr[rt].lazy=add;
        return;
    }
    push_down(rt);
    int mid=(l+r)>>1;
    if(ul<=mid) update(rt<<1,l,mid,ul,ur,add);
    if(ur>mid) update((rt<<1)|1,mid+1,r,ul,ur,add);
    push_up(rt);
}
signed main(){
    cin>>n;
    for(int i=1,x,y;i<=n;++i){
        cin>>x>>y;
        update(1,1,2000001,x*2,y*2,1);
    }
    int sg=0;
    for(int i=1;i<=2000001;++i){//显然这样一个一个搜就可以保证输出按照字典序排列
        int ss=query(1,1,2000001,i,i);//得到数组的第i为
        if(ss==1&&ss!=sg) cout<<(i+1)/2<<' ';//是区间的开头
        if(ss==0&&ss!=sg) cout<<(i+1)/2-1<<'\n';//是区间的结尾 因为要输出的区间是要包括结尾的，所以要 -1
        sg=ss;
    }
    return 0;
}

最后提醒：这份代码常数略大，如果 [a_i,b_i] 是 10^{9} 级别的，就需要离散化了。

AC记录

P2434 [SDOI2005] 区间 题解

P2434 [SDOI2005] 区间题解