[HOJ 251][IOI 2008] Pyramid Base

作法：

首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。

但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$

最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。

code :

#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
const int maxn=2000000+10 ;
 
struct node
{
    node *l,*r ;
    int tag,mi ;
    node(){l=r=NULL ; tag=mi=0 ;}
}pool[2*maxn];
int pcnt ;
 
node *newnode()
{
    node *u=&pool[pcnt++] ;
    u->l=u->r=NULL ;
    u->tag=u->mi=0 ;
    return u ;
}
 
node *build(int l,int r)
{
    if(l==r) return newnode() ;
    node *u=newnode() ;
    int mid=(l+r)/2 ;
    u->l=build(l,mid) ;
    u->r=build(mid+1,r) ;
    return u ;
}
 
inline void pull(node *u){u->mi=min(u->l->mi,u->r->mi);}
inline void push(node *u)
{
    if(!u->tag) return ;
    u->l->tag+=u->tag ; u->l->mi+=u->tag ;
    u->r->tag+=u->tag ; u->r->mi+=u->tag ;
    u->tag=0 ;
}
 
void modify(int l,int r,int L,int R,node *u,int val)
{
    if(l==L && r==R)
    {
        u->tag+=val ; u->mi+=val ;
        return ;
    }
    push(u) ;
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,u->l,val) ;
    else if(l>mid) modify(l,r,mid+1,R,u->r,val) ;
    else modify(l,mid,L,mid,u->l,val) ,
        modify(mid+1,r,mid+1,R,u->r,val) ;
    pull(u) ;
}
 
struct node2
{
    node2 *l,*r ;
    int ll,rl,len,tag ;
    node2(){l=r=0 ; ll=rl=len=1 ; tag=0 ;}
};
void pull(node2 *u,int l,int r)
{
    if(u->tag){u->ll=u->rl=u->len=0 ; return ;}
    if(!u->l){u->ll=u->rl=u->len=1 ; return ;}
    int mid=(l+r)/2 ;
    u->ll=(u->l->ll==mid-l+1 ? u->l->ll+u->r->ll : u->l->ll) ;
    u->rl=(u->r->rl==r-mid ? u->r->rl+u->l->rl : u->r->rl) ;
    u->len=max(max(u->l->len,u->r->len),u->l->rl+u->r->ll) ;
}
 
node2 *build2(int l,int r)
{
    if(l==r) return new node2 ;
    node2 *u=new node2 ;
    int mid=(l+r)/2 ;
    u->l=build2(l,mid) ;
    u->r=build2(mid+1,r) ;
    pull(u,l,r) ;
    return u ;
}
 
void modify2(int l,int r,int L,int R,node2 *u,int val)
{
    if(!(L<=l && l<=r && r<=R)){printf("7421\n") ; exit(0) ;}
    if(l==L && r==R){u->tag+=val ; pull(u,L,R) ; return ;}
    int mid=(L+R)/2 ;
    if(r<=mid) modify2(l,r,L,mid,u->l,val) ;
    else if(l>mid) modify2(l,r,mid+1,R,u->r,val) ;
    else modify2(l,mid,L,mid,u->l,val) ,
        modify2(mid+1,r,mid+1,R,u->r,val) ;
    pull(u,L,R) ;
}
 
int n,m,num ;
struct rec
{
    int x1,y1,x2,y2,val ;
    void scan(){scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val) ;}
}r[maxn];
 
struct event
{
    int y,x1,x2,val ;
    bool operator < (const event &rhs) const
    {
        return y<rhs.y ;
    }
}ev[maxn];
 
int cal(int x)
{
    pcnt=0 ;
    node *root=build(1,n-x+1) ;
    int ecnt=0 ;
    for(int i=0;i<num;i++)
    {
        int x1=max(r[i].x1-x+1,1),x2=min(r[i].x2,n-x+1) ;
        int y1=max(r[i].y1,x),y2=min(r[i].y2+x-1,m) ;
        ev[ecnt++]=(event){y1,x1,x2,r[i].val} ;
        ev[ecnt++]=(event){y2+1,x1,x2,-r[i].val} ;
    }
    sort(ev,ev+ecnt) ;
    int ret=INF ;
    for(int i=x,j=0;i<=m;i++)
    {
        for(;j<ecnt && ev[j].y<=i;j++)
            modify(ev[j].x1,ev[j].x2,1,n-x+1,root,ev[j].val) ;
        ret=min(ret,root->mi) ;
    }
    return ret ;
}
 
event add[maxn],sub[maxn] ;
main()
{
//    freopen("pbs14a.in","r",stdin) ;
    int B ; scanf("%d%d%d%d",&n,&m,&B,&num) ;
    for(int i=0;i<num;i++) r[i].scan() ;
    if(B)
    {
        int L=0,R=min(n,m)+1 ;
        while(R-L>1)
        {
            int mid=(L+R)/2 ;
            if(cal(mid)<=B) L=mid ;
            else R=mid ;
        }
        printf("%d\n",L) ;
        return 0 ;
    }
 
    for(int i=0;i<num;i++)
        add[i]=(event){r[i].y1,r[i].x1,r[i].x2,1} ,
        sub[i]=(event){r[i].y2,r[i].x1,r[i].x2,-1} ;
    sort(add,add+num) ; sort(sub,sub+num) ;
    node2 *root=build2(1,n) ;
    int ans=0 ;
    for(int le=1,ri=0,cnt1=0,cnt2=0;le<=m;le++)
    {
        for(;ri<m && root->len>=ri-le+1;)
        {
            ans=max(ans,ri-le+1) ;
            ri++ ;
            for(;cnt2<num && add[cnt2].y<=ri;cnt2++)
                modify2(add[cnt2].x1,add[cnt2].x2,1,n,root,1) ;
        }
        if(root->len>=ri-le+1) ans=max(ans,ri-le+1) ;
        for(;cnt1<num && sub[cnt1].y<=le;cnt1++)
            modify2(sub[cnt1].x1,sub[cnt1].x2,1,n,root,-1) ;
    }
    printf("%d\n",ans) ;
}