脚本宝典收集整理的这篇文章主要介绍了CF765F Souvenirs，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

描述：

给出 (n) 以及一个长为 (n) 的序列 (a)。

给出 (m)，接下来 (m) 组询问。

每组询问给出一个 (l,r)，你需要求出，对于 (i,j in [l,r])，且满足 (i neq j)，(|a_i-a_j|) 的最小值。

(1 leq n leq 10^5)，(1 leq m leq 3times 10^5)，(0 leq a_i leq 10^9)。

思路：

考虑将询问离线，按照右端点依次处理询问。套路：考虑将操作分类，同类一起处理。（如：右端点分类）

考虑加入元素 (i) 对答案产生的影响。

含有绝对值的条件不好处理，可以分两次，每次只处理 (a_jge a_i) 的影响。

发现直接枚举左端点不可行，那么考虑元素 (i) 什么时候会对答案产生影响。

首先，我们先确定如何执行影响：对于左端点 (j) ，将 (1) 至 (j) 为左端点的答案更新 (|a_i - a_j|) 。

我们发现要使每个左端点可能有影响，那么左端点位置递增，(|a_i-a_j|) 递减，可这枚举还是 (O(n^2)) 的。

这个思路可以用线段树维护每个位置最后出现次数，每次找到 (j<i,a_j>a_j) 的最大位置，一个个往前跳即可。

我们发现要对答案产生影响，还需要更加严格的条件，以减少枚举次数：

对于当前找到的位置为 (j) ，下次跳的位置为 (j') ，有：

(a_j'-a_i<a_j'-a_j) ，这样可以保证 (i) 可以对 (j') 产生贡献，可以发现这样跳至多跳 (LOG n) 次，复杂度为 (O(nlog^2n))

代码：

#include <bITs/stdc++.h>

#define LL long long
#define DB double
#define PR pair <int, int>
#define MK make_pair
#define pb push_back
#define fi First
#define se second
#define RI register int
#define Low(x) (x &amp; (-x))

using namespace std;

const int kN = 6e6 + 5, kInf = 1e9 + 5;

int n, m, a[kN], b[kN], ans[kN], len = kInf, cnt, rt;
PR q[kN];
vector <int> id[kN];

struct Smt {
  int mx[kN], ls[kN], rs[kN];
#define ls(p) ls[p]
#define rs(p) rs[p]

  void Pushup(int p) {mx[p] = max(mx[ls(p)], mx[rs(p)]);}

  void Build() {
    memset(mx, 0, sizeof mx);
    memset(ls, 0, sizeof ls);
    memset(rs, 0, sizeof rs);
  }
  
  void Modify(int l, int r, int pos, int k, int &p) {
    if (!p) p = ++cnt;
    if (l == r) {mx[p] = max(mx[p], k); return;}
    int mid = (l + r) >> 1;
    if (pos <= mid) Modify(l, mid, pos, k, ls(p));
    else Modify(mid + 1, r, pos, k, rs(p));
    Pushup(p);
  }

  int Query(int l, int r, int L, int R, int p) {
    if (!p) return 0;
    if (l >= L && r <= R) return mx[p];
    int mid = (l + r) >> 1, res = 0;
    if (L <= mid) res = max(res, Query(l, mid, L, R, ls(p)));
    if (R > mid) res = max(res, Query(mid + 1, r, L, R, rs(p)));
    return res;
  }
} T;

struct BIT {
  int c[kN];

  void Build() {
    for (int i = 0; i <= n; ++i) c[i] = len;
  }

  void Add(int x, int k) {
    for (; x; x -= Low(x)) c[x] = min(c[x], k);
  }

  int Ask(int x) {
    int res = kInf;
    for (; x <= n; x += Low(x)) res = min(res, c[x]);
    return res;
  }
} T2;

void Solve() {
  T.Build(), T2.Build();
  rt = cnt = 0;
  for (int i = 1; i <= n; ++i) {
    //    cout << i << endl;
    int p = T.Query(1, len, a[i], len, rt);
    //    cout << i << endl;
    while (p) {
      T2.Add(p, a[p] - a[i]);
      p = T.Query(1, len, a[i], (a[i] + a[p]) / 2 - (1 - ((a[i] + a[p]) & 1)), rt);
      //      cout << i << endl;
    }
    //    cout << i << endl;
    T.Modify(1, len, a[i], i, rt);
    //    cout << i << endl;
    for (int j = 0; j < id[i].size(); ++j)
      ans[id[i][j]] = min(ans[id[i][j]], T2.Ask(q[id[i][j]].fi));
  }
}

signed 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) scanf("%d%d", &q[i].fi, &q[i].se), id[q[i].se].pb(i), ans[i] = kInf;
  Solve();
  for (int i = 1; i <= n; ++i) a[i] = len - a[i] + 1;
  Solve();
  for (int i = 1; i <= m; ++i) printf("%dn", ans[i]);
  return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的CF765F Souvenirs全部内容，希望文章能够帮你解决CF765F Souvenirs所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。