首页 > 其他 > 详细

BZOJ1135: [POI2009]Lyz

时间:2018-04-22 20:49:21      阅读:207      评论:0      收藏:0      [点我收藏+]

【传送门:BZOJ1135


简要题意:

  给出1到n号的鞋子,每对鞋子有k对

  已知x号脚的人可以穿x到x+d号的鞋子

  给出m个操作,每个操作输入r,x,说明来了x个r号脚的人(如果x为负数,则说明走了x个)

  判断k对鞋子是否能够满足任何时刻所有人都有鞋穿


题解:

  二分图匹配显然会超时

  这时。。就应该膜题解

  Hall定理????wtf,膜一波


参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
struct trnode
{
    int l,r,lc,rc;LL c,lm,rm,mx;
}tr[410000];int trlen;
void bt(int l,int r)
{
    trlen++;int now=trlen;
    tr[now].l=l;tr[now].r=r;tr[now].c=tr[now].lm=tr[now].rm=tr[now].mx=0;
    tr[now].lc=tr[now].rc=-1;
    if(l<r)
    {
        int mid=(l+r)/2;
        tr[now].lc=trlen+1;bt(l,mid);
        tr[now].rc=trlen+1;bt(mid+1,r);
    }
}
void follow(int now)
{
    int lc=tr[now].lc,rc=tr[now].rc;
    tr[now].c=tr[lc].c+tr[rc].c;
    tr[now].lm=max(tr[lc].lm,tr[lc].c+tr[rc].lm);
    tr[now].rm=max(tr[rc].rm,tr[rc].c+tr[lc].rm);
    tr[now].mx=max(tr[lc].rm+tr[rc].lm,max(tr[lc].mx,tr[rc].mx));
}
void change(int now,int x,LL c)
{
    if(tr[now].l==tr[now].r)
    {
        tr[now].c=tr[now].mx=tr[now].lm=tr[now].rm+=c;
        return ;
    }
    int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
    if(x<=mid) change(lc,x,c);
    else change(rc,x,c);
    follow(now);
}
int main()
{
    int n,m;LL k,d;
    scanf("%d%d%lld%lld",&n,&m,&k,&d);
    trlen=0;bt(1,n);
    for(int i=1;i<=n;i++) change(1,i,-k);
    for(int i=1;i<=m;i++)
    {
        int r;LL x;
        scanf("%d%lld",&r,&x);
        change(1,r,x);
        if(tr[1].mx<=d*k) printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}

 

BZOJ1135: [POI2009]Lyz

原文:https://www.cnblogs.com/Never-mind/p/8909105.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!