【CF765F】Souvenirs

【CF765F】Souvenirs

题面

洛谷

题解

我们可以发现,对于某个右端点\(i\),左端点\(j\)在由\(i\rightarrow 1\)的过程中,每一段的答案是单调不增的,由这个性质,我们想办法维护出加入右端点\(i\)后的答案。

我们只考虑形如\(j<i,a_i<a_j\)的答案,因为其他的情况我们只需要将值域翻转即可得到答案。

根据我们上面的说法,你首先需要找到一个\(j\),使得\(a_j>a_i\)且\(j\)最大,这个可以用值域线段树维护。然后我们又要找到一个一个\(j'\),使得\(a_{j'}-a_i<a_j-a_i\),那么我们可以令\(j=j'\),继续更新答案。

如果仅仅是这样的话,我们的复杂度还是不满足要求的,但是限制\(a_{j'}-a_i<a_j-a_i\)可以转化为\(a_{j'}-a_i<a_j-a_{j'}\),因为大于的情况之前肯定以及更新过了,那么我们没必要再次更新,而这个限制又可以变为\(a_{j'}-a_i<\frac 12(a_j-a_i)\),这样子每次值域减半的话复杂度可以保证。

而维护某个左端点的话可以用树状数组维护后缀取\(\min\)即可。

复杂度\(O(n\log ^2 10^9)\)。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm>
#include <vector> 
using namespace std; 
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
} 
const int INF = 1e9; 
const int MAX_N = 3e5 + 5; 
vector<pair<int, int> > vec[MAX_N]; 
int N, M, a[MAX_N], ans[MAX_N]; 
int c[MAX_N]; 
inline int lb(int x) { return x & -x; } 
void Add(int x, int v) { while (x) c[x] = min(c[x], v), x -= lb(x); } 
int Min(int x) { int res = INF; while (x <= N) res = min(res, c[x]), x += lb(x); return res; } 
struct Node { int ls, rs, v; } t[MAX_N << 5]; 
int rt[MAX_N], tot; 
void modify(int &o, int p, int l, int r, int pos, int v) { 
    o = ++tot, t[o] = t[p], t[o].v = max(t[o].v, v); 
    if (l == r) return ; 
    int mid = (l + r) >> 1; 
    if (pos <= mid) modify(t[o].ls, t[p].ls, l, mid, pos, v); 
    else modify(t[o].rs, t[p].rs, mid + 1, r, pos, v); 
} 
int query(int o, int l, int r, int ql, int qr) { 
    if (!o || l > r) return 0; 
    if (ql <= l && r <= qr) return t[o].v; 
    int mid = (l + r) >> 1, res = 0; 
    if (ql <= mid) res = max(res, query(t[o].ls, l, mid, ql, qr)); 
    if (qr > mid) res = max(res, query(t[o].rs, mid + 1, r, ql, qr)); 
    return res; 
} 
void solve() { 
    for (int i = 1; i <= N; i++) c[i] = INF; 
    for (int i = 1; i <= tot; i++) t[i] = (Node){0, 0, 0}; 
    tot = 0, memset(rt, 0, sizeof(rt)); 
    for (int i = 1; i <= N; i++) modify(rt[i], rt[i - 1], 0, INF, a[i], i); 
    for (int i = 1; i <= N; i++) { 
        int j = query(rt[i - 1], 0, INF, a[i], INF); 
        while (j) { 
            Add(j, a[j] - a[i]); 
            j = query(rt[j - 1], 0, INF, a[i], ((a[i] + a[j]) >> 1) - (~(a[i] + a[j]) & 1)); 
        } 
        for (auto it : vec[i]) ans[it.second] = min(ans[it.second], Min(it.first)); 
    } 
} 
int main () { 
#ifndef ONLINE_JUDGE 
    freopen("cpp.in", "r", stdin); 
#endif 
    N = gi(); 
    for (int i = 1; i <= N; i++) a[i] = gi(); 
    M = gi(); 
    for (int i = 1; i <= M; i++) { 
        int l = gi(), r = gi(); 
        vec[r].push_back(make_pair(l, i)); 
        ans[i] = INF; 
    } 
    solve(); 
    for (int i = 1; i <= N; i++) a[i] = INF - a[i]; 
    solve(); 
    for (int i = 1; i <= M; i++) printf("%d\n", ans[i]); 
    return 0; 
} 
上一篇:CF765F Souvenirs


下一篇:github编程指南