首页 > 其他分享 >题解:【POI2001】Goldmine

题解:【POI2001】Goldmine

时间:2022-08-24 18:14:47浏览次数:96  
标签:int 题解 POI2001 Goldmine 扫描线 整块

【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

相关文章

  • 数的划分 题解
    \(0.\)写在前面1.3【例题1】数的划分-TuringEDUP2706数的划分-TopsCoding这题可以有两种写法:(至少两种)深搜计数\(\text{DP}\)接下来将会依次讲解\(1.\)......
  • 题解:【WC2005】双面棋盘
    【WC2005】双面棋盘题目链接这天做双面棋盘这道题,发现题解里面大多都是LCT,对于线段树套并查集的写法思路讲评很少而且不大清晰,因此有了这一篇题解。维护联通块的数量,......
  • has been blocked by CORS policy跨域问题解决
    title:hasbeenblockedbyCORSpolicy跨域问题解决我们在前端调用接口时,浏览器有时候会报错:XXXXformXXXXXhasbeenblockedbyCORSpolicy:No'Access-Control-......
  • CF1715F Crop Squares 题解
    CF1715FCropSquaressolution有一个\(n\timesm\)的长方形,四个角的坐标分别为$(0,0)$,$(0,m)$,$(n,0)$,$(n,m)$。在长方形里面有一个\(1\time......
  • CF838D题解
    很厉害的题。考虑将原本的座位串成一个环,然后加一个节点在\(1\)的前面\(n\)的后面。原问题等价为新节点不被座到的方案数。容易发现所有节点被座到和不被座到的方案......
  • 关于npm ERR! ERESOLVE could not resolve 问题解决
    1、问题描述从代码仓库拉取代码到本地,执行npminstall命令安装项目依赖,提示如下图错误  问题出现的原因由于npm版本问题,npm不同版本库之间命令不兼容。解决办法:执......
  • App 自动化测试实战技巧与经典面试题解析
    ⬇️点击“下方链接”,提升测试核心竞争力!>>更多技术文章分享和免费资料领取移动互联网时代,为了高效应对App多端发布、多版本发布、多机型发布等质量挑战,App自动化测试......
  • [题解]轮流拿牌问题_一道博弈论笔试题(C++)
    题目A和B轮流从一个数组左右两端取数,A先B后,每次取一个数,最终取数总和大者获胜,两人每次都会选择最有利的策略,求获胜者取数的和。思路笔试时遇到的一道算法题,也是博弈论中......
  • ARC099F题解
    被杀了,记录一下好了。对于他那个数组是否相等,直接判断复杂度很高,考虑通过哈希映射之后判断是否相等。对数组的Hash可以类似字符串Hash那样去做。于是判断一个区间是......
  • laravel+mews/captcha 打开页面后的首次验证码总是验证失败的问题解决
    出现问题的原因验证码获取后,还有其他的接口请求,导致验证码的缓存被覆盖(参考文章:LaravelSession遇到的坑)解决办法修改vendor/mews/captcha/src/Captcha.php源码,将......