bzoj 2811: [Apio2012]Guard【线段树+贪心】

关于没有忍者的区间用线段树判就好啦

然后把剩下的区间改一改：l/r数组表示最左/最右没被删的点，然后删掉修改后的左边大于右边的；l升r降排个序，把包含完整区间的区间删掉；

然后设f/g数组表示i前/后的最少需要忍者数，这个贪心来转移即可，就是把忍者放在区间的最右/左位置

然后对于每个r判断。为什么是每个r而不是全部点，因为上一步的贪心。找到最右的r小于当前r-1的位置k1，最左的l大于当前r-1的位置k2，判断如果f[k1]+g[k2]+1>k，则说明此方案不合法，说明这个点必选

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=500005;

int n,k,m,tot,cnt,rl[N],l[N],r[N],con,f[N],g[N];

struct xds

{

    int l,r,tg;

}t[N<<1];

struct qwe

{

    int l,r,v;

    qwe(int L=0,int R=0)

    {

        l=L,r=R;

    }

}a[N],b[N];

bool cmp(const qwe &a,const qwe &b)

{

    return a.l<b.l||(a.l==b.l&&a.r>b.r);

}

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

void build(int ro,int l,int r)

{

    t[ro].l=l,t[ro].r=r;

    if(l==r)

        return;

    int mid=(l+r)>>1;

    build(ro<<1,l,mid);

    build(ro<<1|1,mid+1,r);

}

void update(int ro,int l,int r)

{

    if(t[ro].l==l&&t[ro].r==r)

    {

        t[ro].tg=1;

        return;

    }

    int mid=(t[ro].l+t[ro].r)>>1;

    if(r<=mid)

        update(ro<<1,l,r);

    else if(l>mid)

        update(ro<<1|1,l,r);

    else

    {

        update(ro<<1,l,mid);

        update(ro<<1|1,mid+1,r);

    }

}

int ques(int ro,int x)

{

    if(t[ro].tg)

        return t[ro].tg;

	if(t[ro].l==t[ro].r)

		return 0;

    int mid=(t[ro].l+t[ro].r)>>1;

    if(x<=mid)

        return ques(ro<<1,x);

    else

        return ques(ro<<1|1,x);

}

int main()

{

    n=read(),k=read(),m=read();

    build(1,1,n);

    for(int i=1;i<=m;i++)

    {

        int x=read(),y=read(),z=read();

        if(!z)

            update(1,x,y);

        else

            a[++tot]=qwe(x,y);

    }

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

        if(!ques(1,i))

            l[i]=r[i]=++cnt,rl[cnt]=i;

    if(cnt==k)

    {

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

            if(l[i])

                printf("%d\n",i);

        return 0;

    }

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

        if(!l[i])

            l[i]=l[i-1];

    r[n+1]=cnt+1;

    for(int i=n;i>=1;i--)

        if(!r[i])

            r[i]=r[i+1];

    for(int i=1;i<=tot;i++)

    {

        a[i].l=r[a[i].l],a[i].r=l[a[i].r];

        if(a[i].l<=a[i].r)

            a[++con]=a[i];

    }

    sort(a+1,a+1+con,cmp);

    tot=0;

    for(int i=1;i<=con;i++)

	{

		while(tot>=1&&b[tot].l<=a[i].l&&a[i].r<=b[tot].r)

			tot--;

		b[++tot]=a[i];

	}

	int mn=1e9,mx=0;

    for(int i=1;i<=tot;i++)

    {

 	    if(b[i].l>mx)

			f[i]=f[i-1]+1,mx=b[i].r;

		else

			f[i]=f[i-1];

	}

	for(int i=tot;i>=1;i--)

	{

		if(b[i].r<mn)

			g[i]=g[i+1]+1,mn=b[i].l;

		else

			g[i]=g[i+1];

	}

    bool fl=0;

    for(int i=1;i<=tot;i++)

    {

		if(f[i]!=f[i-1]+1)

			continue;

		if(b[i].l==b[i].r)

		{

			fl=1;

			printf("%d\n",rl[b[i].l]);

			continue;

		}

        int x=b[i].r-1,l=1,r=i-1,k1=0,k2=tot+1;

        while(l<=r)

        {

            int mid=(l+r)>>1;

            if(b[mid].r<x)

                k1=mid,l=mid+1;

            else

                r=mid-1;

        }

        l=i+1,r=tot;

        while(l<=r)

        {

            int mid=(l+r)>>1;

            if(b[mid].l>x)

                k2=mid,r=mid-1;

            else

                l=mid+1;

        }

        if(f[k1]+g[k2]+1>k)

            fl=1,printf("%d\n",rl[b[i].r]);

    }

    if(!fl)

        puts("-1");

    return 0;

}

巴特西

bzoj 2811: [Apio2012]Guard【线段树+贪心】

最新文章

热门文章