【POI2001】Goldmine
扫描线板子题,本质上这个题跟窗口的星星是一样的,只不过把权值 $k$ 都换成 $1$ 就行。但是需要注意的是这句话:
(若矿石位于这块地的边缘,我们同样认为他是属于这个区域的)
因此我们在处理矩形的时候就不需要进行缩小的操作。剩下的就都一样了,这个题 $x$ 和 $y$ 的范围到负数,我们可以先离散化一下,然后将每个“金矿”转化成矩形,排序横坐标,对纵坐标建立扫描线。
这边题解不一样的地方是扫描线使用分块维护,因为我们需要支持的操作包括区间加和区间最大值,分块同样可以做到,不一定非要用线段树。维护整块 $tag$ 加法标记,原始序列 $c$ 和整块 $maxx$ 数组,在整块直接取 $maxx$ 中的值,散块暴力找即可。
大常数选手跑得奇慢无比,喜提最劣解。
$Code$
#include<bits/stdc++.h>
#define int long long
#define MAX 100010
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1;c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
int n,w,h;
int ans,cnt;
struct scanline
{
int x,yup,ydown,k;
}a[MAX<<1];
inline bool cmp(scanline a,scanline b)
{
if (a.x!=b.x) return a.x<b.x;
else return a.k>b.k;
}
int d[MAX<<1];
int x,y;
inline void discrete()
{
w=read(),h=read();
n=read();
for(int i=1;i<=n;i++)
{
x=read(),y=read();
a[++cnt].x=x,a[cnt].yup=y+h,a[cnt].ydown=y,a[cnt].k=1; d[cnt]=y;
a[++cnt].x=x+w,a[cnt].yup=y+h,a[cnt].ydown=y,a[cnt].k=-1; d[cnt]=y+h;
}
sort(d+1,d+cnt+1);
cnt=unique(d+1,d+cnt+1)-d-1;
n<<=1;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
a[i].yup=lower_bound(d+1,d+cnt+1,a[i].yup)-d,
a[i].ydown=lower_bound(d+1,d+cnt+1,a[i].ydown)-d;
return;
}
int blo,bn;
int l[MAX],r[MAX],pos[MAX],c[MAX],tag[MAX],maxx[MAX];
inline void block()
{
blo=sqrt(cnt),bn=(cnt-1)/blo+1;
for(int i=1;i<=bn;i++)
l[i]=(i-1)*blo+1,r[i]=blo*i;
r[bn]=cnt;
for(int i=1;i<=bn;i++)
for(int j=l[i];j<=r[i];j++)
pos[j]=i;
return;
}
inline void check(int x)
{
maxx[x]=0;
for(int i=l[x];i<=r[x];i++)
maxx[x]=max(maxx[x],c[i]);
return;
}
inline void add(int L,int R,int k)
{
int p=pos[L],q=pos[R];
if(p==q)
{
for(int i=L;i<=R;i++)
c[i]+=k,maxx[p]=max(maxx[p],c[i]);
if(k==-1) check(p);
}
else
{
for(int i=p+1;i<=q-1;i++)
tag[i]+=k;
for(int i=L;i<=r[p];i++)
c[i]+=k,maxx[p]=max(maxx[p],c[i]);
if(k==-1) check(p);
for(int i=l[q];i<=R;i++)
c[i]+=k,maxx[q]=max(maxx[q],c[i]);
if(k==-1) check(q);
}
return;
}
inline int getmax(int L,int R)
{
int p=pos[L],q=pos[R],anss=0;
if(p==q)
{
for(int i=L;i<=R;i++)
anss=max(anss,c[i]+tag[q]);
}
else
{
for(int i=p+1;i<=q-1;i++)
anss=max(anss,maxx[i]+tag[i]);
for(int i=L;i<=r[p];i++)
anss=max(anss,c[i]+tag[p]);
for(int i=l[q];i<=R;i++)
anss=max(anss,c[i]+tag[q]);
}
return anss;
}
signed main()
{
discrete();
block();
for(int i=1;i<=n;i++)
{
add(a[i].ydown,a[i].yup,a[i].k);
ans=max(ans,getmax(1,cnt));
}
cout<<ans<<endl;
return (0-0);
}
标签:int,题解,POI2001,Goldmine,扫描线,整块
From: https://www.cnblogs.com/LittleTwoawa/p/16621113.html