题解 P4687 【[IOI2008] Pyramid Base 金字塔基】

· · 题解

经 典 二 合 一

首先，我们看到三档部分分：B=0 时，最多障碍数是 4\times10^5；而 B\neq0 时，最多障碍数仅有 3\times10^4。

这启示我们对于要对于两种情形分开写一个算法。

B=0

此种情形意味着无法消除任何障碍。若我们把障碍看作是矩形赋 1 的话，问题就转换为最大全零正方形。

同用单调栈解决的最大全零矩形不同，最大全零正方形可以使用two-pointers+扫描线+线段树解决。

具体而言，我们考虑固定一个指针 i，再设另一个指针 j<i。则，我们想知道所有以 i,j 为两边的矩形中，另一维最长的那一个。因为随着 j 的增加，i-j 这一维的长度会不断减小，而另一维的长度会不断增加，所以当正方形边长最大时，一定有两维差最小。于是我们不断增加 j，直到另一维的长度大于 i-j 这一维。

现在问题就变成了仅需维护 i,j 间没有任何障碍物的最大子段。因为我们仍然可以把一坨障碍物看作是区间加一，所以问题变为区间加、全局最大全零子段。子段问题只需在线段树上维护左端点、右端点、全局等一大坨玩意然后合并即可，不再赘述。

时间复杂度 O(n\log n)。

B\neq 0

此种情形意味着可以消除障碍。但是，因为数据范围明显减少，我们可以思考复杂度更高的算法。

明显金字塔边长具有可二分性。于是我们二分边长。二分边长以后，我们考虑在金字塔的右上角位置储存该金字塔需要消除的障碍的代价和。考虑一个障碍，则其会对其内部，以及其右方上方一定距离（准确说，二分的边长再减一）的位置的金字塔造成影响。于是问题就变成了最小矩形覆盖问题。直接上扫描线维护即可。

时间复杂度 O(n\log^2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define y1 __17680321
int n,m,c,q,xx,yy;
vector<int>X,Y;
struct edge{
    int y1,y2,val;
    edge(int a,int b,int c){y1=a,y2=b,val=c;}
};
vector<edge>v[800100];
struct rect{
    int x1,y1,x2,y2,cost;
    void input(){scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&cost),x1--,y1--;}
    void isput(){X.push_back(x1),X.push_back(x2),Y.push_back(y1),Y.push_back(y2);}
    void reput(){
        x1=lower_bound(X.begin(),X.end(),x1)-X.begin();
        x2=lower_bound(X.begin(),X.end(),x2)-X.begin();
        y1=lower_bound(Y.begin(),Y.end(),y1)-Y.begin();
        y2=lower_bound(Y.begin(),Y.end(),y2)-Y.begin();
    }
}r[400100],t[30100];
void discrete(vector<int>&v,int&vv){sort(v.begin(),v.end()),v.resize(vv=unique(v.begin(),v.end())-v.begin()-1);}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
namespace S1{
    struct SegTree{int tag,mn,len,lval,lln,rval,rln;}seg[3200100];
    void ADD(int x,int y){seg[x].tag+=y,seg[x].mn+=y,seg[x].lval+=y,seg[x].rval+=y;}
    void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
    void pushup(int x,int l,int r){
        seg[x].lval=seg[lson].lval,seg[x].rval=seg[rson].rval;
        if(seg[lson].lln==Y[mid]-Y[l]&&seg[lson].rval==seg[rson].lval)seg[x].lln=seg[lson].lln+seg[rson].lln;
        else seg[x].lln=seg[lson].lln;
        if(seg[rson].rln==Y[r]-Y[mid]&&seg[lson].rval==seg[rson].lval)seg[x].rln=seg[rson].rln+seg[lson].rln;
        else seg[x].rln=seg[rson].rln;
        seg[x].mn=min(seg[lson].mn,seg[rson].mn),seg[x].len=0;
        if(seg[x].mn==seg[lson].mn)seg[x].len=max(seg[x].len,seg[lson].len);
        if(seg[x].mn==seg[rson].mn)seg[x].len=max(seg[x].len,seg[rson].len);
        if(seg[lson].rval==seg[x].mn&&seg[rson].lval==seg[x].mn)seg[x].len=max(seg[x].len,seg[lson].rln+seg[rson].lln);
    }
    void build(int x,int l,int r){
        if(l+1==r){seg[x].lln=seg[x].rln=seg[x].len=Y[r]-Y[l];return;}
        build(lson,l,mid),build(rson,mid,r),pushup(x,l,r);
    }
    void modify(int x,int l,int r,int L,int R,int val){
//      printf("%d %d %d %d %d %d\n",x,l,r,L,R,val);
        if(l>=R||r<=L)return;
        if(L<=l&&r<=R){ADD(x,val);return;}
        pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid,r,L,R,val),pushup(x,l,r);
    }
//  void iterate(int x,int l,int r){
//      printf("%d(%d,%d]:MN:%d LN:%d LV:%d LL:%d RV:%d RL:%d\n",x,l,r,seg[x].mn,seg[x].len,seg[x].lval,seg[x].lln,seg[x].rval,seg[x].rln);
//      if(l+1!=r)pushdown(x),iterate(lson,l,mid),iterate(rson,mid,r),pushup(x,l,r);
//  }
    int calc(){
        X.push_back(0),X.push_back(n),Y.push_back(0),Y.push_back(m);
        for(int i=1;i<=q;i++)r[i].isput();
        discrete(X,xx),discrete(Y,yy);
        for(int i=1;i<=q;i++)r[i].reput();
        for(int i=1;i<=q;i++)v[r[i].x1].push_back(edge(r[i].y1,r[i].y2,1)),v[r[i].x2].push_back(edge(r[i].y1,r[i].y2,-1));
        build(1,0,yy);
        int res=0;
        for(int i=0,j=0;i<=xx;i++){
//          printf("%d:%d\n",i,j);
//          iterate(1,0,yy);
//          for(auto k:v[i])printf("(%d,%d,%d)",k.y1,k.y2,k.val);puts("");
            if(!seg[1].mn)res=max(res,min(X[i]-X[j],seg[1].len));
//          printf("SQR:%d %d\n",X[i]-X[j],seg[1].len);
            while(j<i&&(seg[1].mn||seg[1].len<=X[i]-X[j])){
                j++;
                for(auto k:v[j])if(k.val<0)modify(1,0,yy,k.y1,k.y2,k.val);
                res=max(res,min(X[i]-X[j],seg[1].len));
            }
//          puts("IN");
            for(auto k:v[i])if(k.val>0)modify(1,0,yy,k.y1,k.y2,k.val);
        }
        return res;
    }
}
namespace S2{
    struct SegTree{int tag,mn;}seg[240100];
    void ADD(int x,int y){seg[x].tag+=y,seg[x].mn+=y;}
    void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;}
    void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);}
    void modify(int x,int l,int r,int L,int R,int val){
        if(l>=R||r<=L)return;
        if(L<=l&&r<=R){ADD(x,val);return;}
        pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid,r,L,R,val),pushup(x);
    }
    bool che(int ip){
        X.push_back(0),X.push_back(n),Y.push_back(0),Y.push_back(m);
        for(int i=1;i<=q;i++)t[i]=r[i],t[i].x2=min(n,t[i].x2+ip-1),t[i].y2=min(m,t[i].y2+ip-1),t[i].isput();
        discrete(X,xx),discrete(Y,yy);
        for(int i=1;i<=q;i++)t[i].reput();
        for(int i=1;i<=q;i++)v[t[i].x1].push_back(edge(t[i].y1,t[i].y2,t[i].cost)),v[t[i].x2].push_back(edge(t[i].y1,t[i].y2,-t[i].cost));
        int lim=lower_bound(Y.begin(),Y.end(),ip)-Y.begin()-1;
        int mn=0x7f7f7f7f;
        memset(seg,0,sizeof(seg));
        for(int i=0;i<=xx;i++){
            if(X[i]>=ip)mn=min(mn,seg[1].mn);
            for(auto j:v[i])modify(1,lim,yy,j.y1,j.y2,j.val);
        }
        X.clear(),Y.clear();for(int i=0;i<=xx;i++)v[i].clear();
        return mn<=c;
    }
    int calc(){
        int l=0,r=min(n,m);
        while(l<r){
            int md=(l+r+1)>>1;
            if(che(md))l=md;
            else r=md-1;
        }
        return l;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&c,&q);
    for(int i=1;i<=q;i++)r[i].input();
//  for(int i=0;i<=xx;i++)printf("%d ",X[i]);puts("");
//  for(int i=0;i<=yy;i++)printf("%d ",Y[i]);puts("");
//  for(int i=1;i<=q;i++)printf("%d %d %d %d\n",r[i].x1,r[i].x2,r[i].y1,r[i].y2);
    if(!c)printf("%d\n",S1::calc());
    else printf("%d\n",S2::calc());
    return 0;
}