「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）
2021-03-21 04:26
阅读：488
标签：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
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）
文章链接：http://soscw.com/index.php/essay/67018.html
文章标题：「JSOI2016」灯塔（数论分块+ST做RMQ或单调栈）
文章链接：http://soscw.com/index.php/essay/67018.html
评论
亲，登录后才可以留言！