题解 P4687 【[IOI2008] Pyramid Base 金字塔基】
miaokehao
·
·
题解
首先考虑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);
}
}