https://www.luogu.com.cn/problem/CF765F
挺不错的一道题,首先考虑扫描线,对于每个\(i\),找\(j<i,a[j]>a[i], j\)最大的
用权值线段树可以轻易维护
假设找到一个\(j\),然后再找\((a[i],a[j])\)之间的
时间复杂度不优
考虑再找到的一个是\(j'\)
发现必须要满足\(a[j']-a[i]<a[j]-a[i]\) 且 \(a[j']-a[i]<a[j]-a[j']\)
综合一下如果\(j'\)能贡献答案的话就必须满足第二条式子
移动一下项可以得到
\(2a[j']<a[j]+a[i] \\ a[j']<\frac{a[j]+a[i]}{2}\)
直接找即可
然后再用一个树状数组维护后缀最大值
code:
#include<bits/stdc++.h>
#define N 300050
#define pii pair<int, int>
#define ls ch[rt][0]
#define rs ch[rt][1]
#define fi first
#define se second
using namespace std;
const int lim = 1e9;
int ma[N << 5], ch[N << 5][2], tot, root;
void add(int &rt, int l, int r, int x, int o) {
if(!rt) rt = ++ tot;
ma[rt] = max(ma[rt], o);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) add(ls, l, mid, x, o);
else add(rs, mid + 1, r, x, o);
}
int query(int rt, int l, int r, int L, int R) {
if(L > R) return 0;
if(!rt) return 0;
if(L <= l && r <= R) return ma[rt];
int mid = (l + r) >> 1, ret = 0;
if(L <= mid) ret = query(ls, l, mid, L, R);
if(R > mid) ret = max(ret, query(rs, mid + 1, r, L, R));
return ret;
}
#define lowbit(x) (x & - x)
int t[N], n, a[N];
void update(int x, int y) {
for(; x; x -= lowbit(x)) t[x] = min(t[x], y);
}
int ask(int x) {
int ret = lim;
for(; x <= n; x += lowbit(x)) ret = min(ret, t[x]);
return ret;
}
void clr() {
for(int i = 0; i <= n; i ++) t[i] = lim;
for(int i = 0; i <= tot; i ++) ch[i][0] = ch[i][1] = ma[i] = 0;
tot = root = 0;
}
vector<pii > q[N];
int ans[N], m;
void solve() {
clr();
for(int i = 1; i <= n; i ++) {
int pos = query(root, 0, lim, a[i], lim);
while(pos) {
update(pos, a[pos] - a[i]);
pos = query(root, 0, lim, a[i], (a[i] + a[pos] + 1) / 2 - 1);
}
add(root, 0, lim, a[i], i);
for(auto it : q[i]) {
ans[it.se] = min(ans[it.se], ask(it.fi));
}
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = 1; i <= m; i ++) {
int l, r;
scanf("%d%d", &l, &r);
q[r].push_back(make_pair(l, i));
}
for(int i = 1; i <= m; i ++) ans[i] = lim;
solve();
for(int i = 1; i <= n; i ++) a[i] = lim - a[i];
solve();
for(int i = 1; i <= m; i ++) printf("%d\n", ans[i]);
return 0;
}