题解 | #Arithmetic Progression#

Arithmetic Progression

给定每个元素互不相同的序列 $a_n$ ，求排序后能构成等差数列的区间个数。

$1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$

结论：对于元素互不相同的序列 $b_n$ ，其排序后是公差为 $d$ 等差数列的充要条件是 $d=\gcd(|b_2-b_1|,|b_3-b_2|,\dots)$ 且 $\max b_i - \min b_i = (n-1)d$ 。

证明：

必要性：

设 $b_i = k_id + b_1$ 且 $b_n$ 排序后为等差数列，则 $k_i$ 是 $0, 1, \dots n-1$ 的一个排列，所以 $\max b_i - \min b_i= (n-1)d$ 。

根据辗转相减法：

$\gcd(|b_2-b_1|,|b_3-b_2|,\dots)\ = \gcd(|b_2-b_1|, |b_3 - b_1|, \dots) = \gcd(d, 2d, \dots) = d$ 。

充分性：

不妨设 $b_1 < b_2 <\dots < b_n$ ， $\gcd(|b_2-b_1|,|b_3-b_2|,\dots)\ = \gcd(|b_2-b_1|, |b_3 - b_1|, \dots) = d = \frac{b_n - b_1}{n-1}$ 。

设 $b_i = k_id + b_1$ ，则 $k_1 = 0 < k_2 \dots < k_n = n - 1$ ，所以 $k_i = i - 1,b_i = (i-1)d+b_1$ ，为等差数列。

于是问题转化为求 $\max a_i - \min a_i = (r-l)\gcd(|a_{l+1}-a_l|, |a_{l+2} - a_{l+1}|, \dots)$ 的区间个数。

由上面的证明不难发现 $\max a_i - \min a_i - (r-l)\gcd(|a_{l+1}-a_l|, |a_{l+2} - a_{l+1}|, \dots) \geq 0$ ，所以用线段树维护这个值的最小值以及最小值的个数。

每次移动右端点时，极差只需修改一个区间，但每个点的 $\gcd$ 都可能被修改。

考虑一个点作为左端点的区间 $\gcd$ 被修改的次数，发现每次修改至少会折半，所以最多修改 $\log$ 次，于是在线段树上暴力修改即可。

不需要 zkw 跑得也很快！

// Author:  HolyK
// Created: Wed Jul 21 12:59:35 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(1e5 + 5);
int n, a[N];
#define ls o << 1
#define rs o << 1 | 1
LL min[N << 2], tag[N << 2];
int cnt[N << 2], gcd[N << 2];
void pushup(int o) {
  min[o] = std::min(min[ls], min[rs]);
  cnt[o] = (min[ls] == min[o] ? cnt[ls] : 0) + (min[rs] == min[o] ? cnt[rs] : 0);
  min[o] += tag[o];
  gcd[o] = gcd[ls] == gcd[rs] ? gcd[ls] : -1;
}
void update(int o, int l, int r, int x, int y, int z) {
  if (gcd[o] > 0 && z % gcd[o] == 0) {
    min[o] -= gcd[o];
    tag[o] -= gcd[o];
    return;
  }
  if (l == r) {
    int t = gcd[o];
    gcd[o] = std::gcd(gcd[o], z);
    min[o] -= LL(gcd[o] - t) * (y - l) + gcd[o];
    cnt[o] = 1;
    return;
  }
  int m = l + r >> 1;
  if (x <= m) update(ls, l, m, x, y, z);
  if (y > m) update(rs, m + 1, r, x, y, z);
  pushup(o);
}
void add(int o, int l, int r, int x, int y, int z) {
  if (x <= l && r <= y) {
    min[o] += z;
    tag[o] += z;
    return;
  }
  int m = l + r >> 1;
  if (x <= m) add(ls, l, m, x, y, z);
  if (y > m) add(rs, m + 1, r, x, y, z);
  pushup(o);
}
int ask(int o, int l, int r, int x, int y, int z) {
  if (y < l || r < x) return 0;
  if (x <= l && r <= y) return min[o] + z == 0 ? cnt[o] : 0;
  int m = l + r >> 1;
  z += tag[o];
  return ask(ls, l, m, x, y, z) + ask(rs, m + 1, r, x, y, z);
}
int s1[N], s2[N], t1, t2; // min, max
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  while (t--) {
    std::cin >> n;
    memset(min, 0, n + 1 << 5);
    memset(tag, 0, n + 1 << 5);
    memset(cnt, 0, n + 1 << 4);
    memset(gcd, 0, n + 1 << 4);
    for (int i = 1; i <= n; i++) {
      std::cin >> a[i];
    }
    LL ans = n;
    t1 = t2 = s1[1] = s2[1] = 1;
    for (int i = 2; i <= n; i++) {
      while (t1 && a[s1[t1]] > a[i]) {
        add(1, 1, n, s1[t1 - 1] + 1, s1[t1], a[s1[t1]]);
        t1--;
      }
      while (t2 && a[s2[t2]] < a[i]) {
        add(1, 1, n, s2[t2 - 1] + 1, s2[t2], -a[s2[t2]]);
        t2--;
      }
      add(1, 1, n, s1[t1] + 1, i, -a[i]);
      add(1, 1, n, s2[t2] + 1, i, a[i]);
      s1[++t1] = s2[++t2] = i;
      update(1, 1, n, 1, i - 1, a[i] - a[i - 1]);
      ans += ask(1, 1, n, 1, i - 1, 0);
    }
    std::cout << ans << "\n";
  }
  return 0;
}