2019/5/21 day6 解题日志

2019-05-21

字数统计: 777字 | 阅读时长: 4分

2019年山东省赛H题，题源ZOJ。

给$n$个线段$[l,r]$，可以在这$n$条线段上放置小球，但限制同一位置$pos$只能在$1$条线段上放球，问最多可以有多少线段被至少$1$个小球覆盖。
$n \le 10^5,1\le l \le r \le 10^9$

day6

思路

首先由于$[l,r]$的范围很大，却不能离散化处理，所以不妨想到用动态开点的线段树维护哪些位置被放过小球了。

首先对$n$条线段进行排序，按照”$r$小，$r$相同$l$小”的方式排序，原因是：

r小的情况下，剩余的[r+1,inf]更多，能够给出更多空间；
l小的情况下，可以充分利用[1,l]的空间，从而给[l+1,r]留出更多空间。

然后显然要每次对线段进行查询，查询的是区间内最靠左的未被覆盖过的位置，通过动态开点线段树实现，时间复杂度为$O(nlogn)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n;
pair<int,int> p[maxn];
bool cmp(pair<int,int >a,pair<int,int> b){
    if(a.second==b.second)return a.first<b.first;
    return a.second<b.second;
}
struct node{
    int l,r,v,ls,rs;
    node(int l=0,int r=0,int v=0,int ls=0,int rs=0):l(l),r(r),v(v),ls(ls),rs(rs){}
}seg[maxn<<2];
int cnt,ans;
int f;
void solve(int L,int R,int rt){
    if(L<=seg[rt].l && R>=seg[rt].r){
        if(seg[rt].r-seg[rt].l==0){seg[rt].v=1;f=1;ans++;return;}
        if(!seg[rt].ls){
            seg[rt].ls=++cnt;
            seg[cnt]=node(seg[rt].l,seg[rt].l+seg[rt].r>>1);
        }
        if(seg[seg[rt].ls].r - seg[seg[rt].ls].l + 1 > seg[seg[rt].ls].v)solve(L,R,seg[rt].ls);
        else{
            if(!seg[rt].rs){
                seg[rt].rs=++cnt;
                seg[cnt]=node((seg[rt].l+seg[rt].r)/2+1,seg[rt].r);
            }
            if(seg[seg[rt].rs].r - seg[seg[rt].rs].l + 1 > seg[seg[rt].rs].v)solve(L,R,seg[rt].rs);
        }
        seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;
        return;
    }seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;if(f)return;
    if(L<=(seg[rt].l+seg[rt].r)/2){
        if(!seg[rt].ls){
            seg[rt].ls=++cnt;
            seg[cnt]=node(seg[rt].l,seg[rt].l+seg[rt].r>>1);
        }
        if(seg[seg[rt].ls].r - seg[seg[rt].ls].l + 1 > seg[seg[rt].ls].v){
            solve(L,R,seg[rt].ls);
            seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;
            if(f)return;
        }
    }
    if(R>(seg[rt].l+seg[rt].r)/2){
        if(!seg[rt].rs){
            seg[rt].rs=++cnt;
            seg[cnt]=node((seg[rt].l+seg[rt].r)/2+1,seg[rt].r);
        }if(seg[seg[rt].rs].r - seg[seg[rt].rs].l + 1 > seg[seg[rt].rs].v)solve(L,R,seg[rt].rs);
    }seg[rt].v=seg[seg[rt].ls].v + seg[seg[rt].rs].v;
}
int main(){
    int t;cin>>t;
    while(t--){
        seg[1]=node(1,1e9);
        cnt=1;ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second);
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++){
            f=0;solve(p[i].first,p[i].second,1);
        }cout<<ans<<endl;
    }return 0;
}