题解 CF377D 【Developing Game】

· · 题解

题目链接

题目大意：

有 n 个人，每人有属性 l_i,v_i,r_i(l_i\leq v_i\leq r_i)，要求选出最大的人的集合 S 使得 \forall x,y\in S 有 l_y\leq v_x\leq r_y

题解：

简单分析一下这些不等式可以发现题目的要求可以转化为：\max\limits_{i\in S} l_i\leq \min\limits_{i\in S} v_i\leq \max\limits_{i\in S} v_i\leq\min\limits_{i\in S} r_i

进一步地，我们将要求转化为找到 L,R，使得 \max\limits_{i\in S} l_i\leq L\leq \min\limits_{i\in S} v_i,\max\limits_{i\in S} v_i\leq R\leq\min\limits_{i\in S} r_i

我们将 (L,R) 看作二维平面上的一个点，一个人就对应着一个矩形。集合中选出多个人，对 (L,R) 的限制就是这些矩形的交。选出最多的人，就是要找到一个点被尽可能多的矩形覆盖。

以样例为例

4
2 8 9
1 4 7
3 6 8
5 8 10

找到这个点可以用扫描线+线段树。记录最优的点的位置，输出方案时挨个判断矩形是否包含该点。

#include<bits/stdc++.h>
using namespace std;
inline int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}

const int N=200100,M=600300;
int a[M<<2],tag[M<<2],pos[M<<2];
inline void pushup(int x){
    if(a[x<<1]>a[x<<1|1]){
        pos[x]=pos[x<<1];
        a[x]=a[x<<1];
    }else{
        pos[x]=pos[x<<1|1];
        a[x]=a[x<<1|1];
    }
}
inline void pushdown(int x){
    tag[x<<1]+=tag[x];
    a[x<<1]+=tag[x];
    tag[x<<1|1]+=tag[x];
    a[x<<1|1]+=tag[x];
    tag[x]=0;
}
void modify(int l,int r,int val,int x,int nl,int nr){
    pushdown(x);
    if(l<=nl&&nr<=r){
        a[x]+=val;
        tag[x]+=val;
        return;
    }
    int mid=nl+nr>>1;
    if(nl<=r&&mid>=l)modify(l,r,val,x<<1,nl,mid);
    if(mid+1<=r&&nr>=l)modify(l,r,val,x<<1|1,mid+1,nr);
    pushup(x);
}
inline int query(){
    return a[1];
}
void build(int x,int l,int r){
    if(l==r){
        pos[x]=l;
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pos[x]=pos[x<<1];
}
int l[N],r[N],v[N];
struct seg{
    int x,u,d;
    bool b;
};
seg s[N];
bool cmp(seg a,seg b){
    if(a.x!=b.x)return a.x<b.x;
    else return a.b<b.b;
}
int main(){
    int n=getint();
    for(int i=0;i<n;i++){
        l[i]=getint();
        v[i]=getint();
        r[i]=getint();
        s[i*2].x=l[i];   s[i*2].u=r[i];   s[i*2].d=v[i];   s[i*2].b=0;
        s[i*2+1].x=v[i]; s[i*2+1].u=r[i]; s[i*2+1].d=v[i]; s[i*2+1].b=1;
    }
    build(1,1,3e5+1);
    sort(s,s+n*2,cmp);
    int ans=0,ansp=0,ansx=0;
    for(int i=0;i<n*2;i++){
        modify(s[i].d,s[i].u,s[i].b?-1:1,1,1,3e5+1);
        if(query()>ans){
            ans=query();
            ansp=pos[1];
            ansx=s[i].x;
        }
    }
    cout<<ans<<endl;
    for(int i=0;i<n;i++){
        if(l[i]<=ansx&&ansx<=v[i]&&v[i]<=ansp&&ansp<=r[i])cout<<i+1<<" ";
    }
    return 0;
}