「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）

2021-03-21 04:26

阅读：407

标签：https int names std efi 区间 ace turn ceil

https://loj.ac/problem/2074

我看到这个题的第一反应是做单调栈：
\(p[i]>=h[j]+\sqrt{|i-j|}-h[i]\)

就\(sqrt\)这函数吧，也是单调的，性质应该和直线差不多，所以单调队列维护交点单调的若干条曲线。

求交点可以用二分求，时间复杂度是\(O(n~log~n)\)

有理有据的做法是分块。

考虑\(\sqrt{|i-j|}\)只有\(2\sqrt n\)种取值，且对于每个每个取值，合法的\(j\)在一个区间里，预处理\(ST\)表以快速查询区间最大值最小值。

时间复杂度：\(O(n\sqrt n + n~log~n)\)

Code：

#include
#define fo(i, x, y) for(int i = x, _b = y; i = _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 1e5 + 5;

int n, h[N];

struct P {
	ll x, y;
};

#define db long double

ll jd(P a, P b) {
	ll as = 1e18;
	for(ll l = b.x, r = 1e18; l > 1;
		db v1 = a.y + sqrt(m - a.x), v2 = b.y + sqrt(m - b.x);
		if(v1 > 1;
		db v1 = a.y + sqrt(a.x - m), v2 = b.y + sqrt(b.x - m);
		if(v1 = jd(z[st], z[st + 1])) st ++;
		if(st = h[i]) continue;
		P a = (P) {i, h[i]};
		while(st  jd(z[en], a)) en --;
		z[++ en] = a;
	}
	st = 1, en = 0;
	fd(i, n, 1) {
		while(st = h[i]) continue;
		P a = (P) {i, h[i]};
		while(st

「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）

标签：https int names std efi 区间 ace turn ceil

原文地址：https://www.cnblogs.com/coldchair/p/12728520.html

上一篇：视频图文教学 - 用最快的速度把 DotNet Core Blazor 程序安装到树莓派中并且用网页控制 GPIO 闪灯

下一篇：[.net 面向对象编程基础] (19) LINQ使用

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）
文章链接：http://soscw.com/index.php/essay/67018.html

亲，登录后才可以留言！

「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）

评论

热门文章

推荐文章

最新文章

置顶文章