自动搬运

查看原文

来自洛谷，原作者为

	miaokehao **

搬运于2025-08-24 22:02:38，当前版本为作者最后更新于2018-11-24 16:44:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑B=0的情况

B=0时数据要求一个nlogn的算法，用扫描线维护第i列到第j列的最大空出的距离，若大于j-i+1，那么说明什么呢？我们可以右移j。当我们改变i时，又可以发现如果i到j是满足要求的，那么i+1到j也是满足要求的。于是尺取法+线段树成功得到65分

namespace Subtask1
{
  vector<pi > st[N],ed[N];
  namespace T
  {
#define ls (now<<1)
#define rs (now<<1|1)
    struct papa
    {
      int maxn,lmax,rmax,tag,len;
      papa():tag(0) {};
    } tr[N<<2];
    inline void pushup(res now)
    {
      if(tr[now].tag)
      {
        tr[now].lmax=tr[now].rmax=tr[now].maxn=0;
        return;
      }
      if(tr[now].len==1)
      {
        tr[now].lmax=tr[now].rmax=tr[now].maxn=1;
        return;
      }
      if(tr[ls].lmax==tr[ls].len)
        tr[now].lmax=tr[ls].lmax+tr[rs].lmax;
      else
        tr[now].lmax=tr[ls].lmax;
      if(tr[rs].rmax==tr[rs].len)
        tr[now].rmax=tr[rs].rmax+tr[ls].rmax;
      else
        tr[now].rmax=tr[rs].rmax;
      tr[now].maxn=max(tr[ls].rmax+tr[rs].lmax,max(tr[ls].maxn,tr[rs].maxn));
    }
    void build_up(res now,res l,res r)
    {
      tr[now].maxn=tr[now].lmax=tr[now].rmax=tr[now].len=r-l+1;
      if(l==r)
        return;
      res mid=l+r>>1;
      build_up(ls,l,mid);
      build_up(rs,mid+1,r);
    }
    void update(res now,res l,res r,res ql,res qr,res c)
    {
      if(ql<=l&&r<=qr)
      {
        tr[now].tag+=c;
        pushup(now);
        return;
      }
      res mid=l+r>>1;
      if(mid>=ql) update(ls,l,mid,ql,qr,c);
      if(mid<qr) update(rs,mid+1,r,ql,qr,c);
      pushup(now);
    }
  }
  inline void MAIN()
  {
    for(res i=1; i<=p; i++)
    {
      res A=read(),B=read(),C=read(),D=read(),k=read();
      st[A].push_back(make_pair(B,D));
      ed[C].push_back(make_pair(B,D));
    }
    T::build_up(1,1,m);
    res j=0;
    for(res i=1; i<=n; i++)
    {
      for(; T::tr[1].maxn>=j-i+1&&j<=n;)
      {
        j++;
        for(res k=0; k<st[j].size(); k++)
          T::update(1,1,m,st[j][k].fi,st[j][k].se,1);
      }
      for(res j=0; j<ed[i].size(); j++)
        T::update(1,1,m,ed[i][j].fi,ed[i][j].se,-1);
      ans=max(ans,j-i);
    }
    printf("%d\n",ans);
  }
}

现在考虑B>0的情况，二分答案是显然的。

之后我们可以再次使用扫描线，枚举每一列，用线段树维护每一行作为左上角的最小代价，则第一个节点就可以表示这一列的最小代价。每次一个矩形的覆盖，我们可以看成两次区间覆盖，{(x1,y1),(x2,y2)}影响的范围是{（x1-l+1,x2）,(y1-l+1),y2}(l为二分的长度)

namespace Subtask2
{
  int ans;
  struct papa1
  {
    int A,B,C,D,k;
  } a[N];
  struct papa
  {
    int l,r,w;
    papa():w(0) {};
    papa(int l0,int r0,int w0):l(l0),r(r0),w(w0) {};
  };
  vector<papa> st[N],ed[N];
  namespace T
  {
#define lson (now<<1)
#define rson (now<<1|1)
    int tr[N<<2],tag[N<<2];
    inline void build_up(res now,res l,res r)
    {
      tag[now]=tr[now]=0;
      if(l==r) return;
      res mid=l+r>>1;
      build_up(lson,l,mid);
      build_up(rson,mid+1,r);
    }
    inline void pushdown(res now)
    {
      if(!tag[now]) return;
      tag[lson]+=tag[now];
      tag[rson]+=tag[now];
      tr[lson]+=tag[now];
      tr[rson]+=tag[now];
      tag[now]=0;
    }
    inline void pushup(res now)
    {
      tr[now]=min(tr[lson],tr[rson]);
    }
    inline void update(res now,res l,res r,res ql,res qr,res c)
    {
      if(ql<=l&&r<=qr)
      {
        tag[now]+=c;
        tr[now]+=c;
        return;
      }
      pushdown(now);
      res mid=l+r>>1;
      if(mid>=ql) update(lson,l,mid,ql,qr,c);
      if(mid<qr) update(rson,mid+1,r,ql,qr,c);
      pushup(now);
    }
  }
  inline bool check(res l)
  {
    for(res i=1; i<=n-l+1; i++)
      st[i].clear(),ed[i].clear();
    T::build_up(1,1,m-l+1);
    for(res i=1; i<=p; i++)
    {
      res A=a[i].A-l+1,B=a[i].B-l+1,C=a[i].C,D=a[i].D,k=a[i].k;
      A=max(A,1),B=max(B,1);
      C=min(C,n-l+1),D=min(D,m-l+1);
      if(A>C||B>D) continue;
      st[A].push_back(papa(B,D,k));
      ed[C].push_back(papa(B,D,-k));
    }
    for(res i=1; i<=n-l+1; i++)
    {
      for(res j=0; j<st[i].size(); j++)
        T::update(1,1,m-l+1,st[i][j].l,st[i][j].r,st[i][j].w);
      if(T::tr[1]<=b)
      {
        //printf("%d %d\n",i,l);
        return 1;
      }
      for(res j=0; j<ed[i].size(); j++)
        T::update(1,1,m-l+1,ed[i][j].l,ed[i][j].r,ed[i][j].w);
    }
    return 0;
  }
  inline void MAIN()
  {
    for(res i=1; i<=p; i++)
      a[i].A=read(),a[i].B=read(),a[i].C=read(),a[i].D=read(),a[i].k=read();
    res l=1,r=min(n,m);
    while(l<=r)
    {
      res mid=l+r>>1;
      if(check(mid)) ans=mid,l=mid+1;
      else r=mid-1;
    }
    printf("%d\n",ans);
  }
}