【JOISC2012】fish

Description

　　有 \(n\) 条鱼，第 \(i\) 条鱼的长度为 \(L_i\)，颜色是 \(C_i\)（\(C_i\) 只能是 'R','G','B'）。

　　你需要从中挑出至少一条鱼，要求挑出的鱼中不能存在两条鱼 \(x,y\) 满足 \(2L_x\le L_y\)。

　　求可以挑出 \(a\) 条红鱼、\(b\) 条绿鱼、\(c\) 条蓝鱼的三元组 \((a,b,c)\) 的个数。

　　\(n\le 5\times 10^5\)

Solution

　　将所有鱼按 \(L\) 从小到大排序。

　　枚举每条鱼 \(l\) 为 \(L\) 最小的鱼，求在此基础上能挑出的 \(L\) 最大的鱼 \(r\)。设第 \([l,r]\) 条鱼中有 \(a\) 条红鱼，\(b\) 条绿鱼，\(c\) 条蓝鱼，则 \((0,0,0)\) 到 \((a,b,c)\) 这个立方体空间中的所有三维点都是可以选的。问题转化成了求 \(n\) 个立方体的体积并。

　　\(n\) 个立方体的前左下端点都是 \((0,0,0)\)，这个性质很好，我们可以用扫描线倒序扫第一维，第二、三维组成的平面一定是一个包含左下角的凸包。不难发现我们要支持快速将一个前缀对一个参数取 max，以及整体求和，直接线段树就完了。时间 \(O(n\log n)\)。

　　当然也可以维护一个 set 记录第二、三维组成的平面上的凸包的每个顶点，区间更新 max 时暴力删掉中间所有被覆盖掉的顶点即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int rd(){

    char c=getchar();int x=0,flag=1;

    for(;c<'0'||c>'9';c=getchar())if(c=='-')flag=-1;

    for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

    return x*flag;

}

struct fish{

    int l,c;

    friend inline bool operator < (fish a,fish b){

        return a.l>b.l;

    }

}a[500010];

struct node{

    int x,y,z;

    friend inline bool operator < (node a,node b){

        return a.x>b.x;

    }

}p[500010];

struct seg_tree{

    ll sum;int tag,mx,mn;

}st[2000010]={0};

int n,sz[3]={0};

inline void pushdown(int s,int l,int r){

    if(!st[s].tag) return;

    int mid=(l+r)>>1,v=st[s].tag;

    st[s<<1].tag=st[s<<1].mx=st[s<<1].mn=v;

    st[s<<1].sum=(ll)v*(mid-l+1);

    st[s<<1|1].tag=st[s<<1|1].mx=st[s<<1|1].mn=v;

    st[s<<1|1].sum=(ll)v*(r-mid);

    return (void)(st[s].tag=0);

}

inline void pushup(int s){

    st[s].sum=st[s<<1].sum+st[s<<1|1].sum;

    st[s].mx=max(st[s<<1].mx,st[s<<1|1].mx);

    st[s].mn=min(st[s<<1].mn,st[s<<1|1].mn);

    return;

}

inline void upd(int s,int l,int r,int x,int y,int v){

    if(st[s].mn>=v) return;

    if(x<=l&&r<=y&&st[s].mx<=v){

        st[s].tag=st[s].mx=st[s].mn=v;

        st[s].sum=(ll)v*(r-l+1);

        return;

    }

    int mid=(l+r)>>1;pushdown(s,l,r);

    if(x<=mid) upd(s<<1,l,mid,x,y,v);

    if(mid<y) upd(s<<1|1,mid+1,r,x,y,v);

    return pushup(s);

}

int main(){

    n=rd();

    for(int i=1;i<=n;i++){

        int l=rd();char c[2];scanf("%s",c);

        a[i]=(fish){l,(c[0]=='R')?0:(c[0]=='G')?1:2};

    }

    sort(a+1,a+n+1);

    for(int i=1,j=1;i<=n;i++){

        for(;j<=n&&(a[j].l<<1)>a[i].l;j++)

            sz[a[j].c]++;

        p[i]=(node){sz[0]+1,sz[1]+1,sz[2]+1};

        sz[a[i].c]--;

    }

    sort(p+1,p+n+1);

    ll ans=0;

    for(int i=n+1,j=1;i;i--){

        for(;j<=n&&p[j].x==i;j++)

            upd(1,1,n+1,1,p[j].y,p[j].z);

        ans+=st[1].sum;

    }

    return printf("%lld\n",ans-1),0;

}

巴特西

【JOISC2012】fish

Description

Solution

最新文章

热门文章