2021 牛客多校第二场 训练记录 暨 补题

太弱小了! 没有力量! FFT 慢慢学叭先补题写记录, 不然要被大大骂惨了嘤嘤嘤.

我和蒋叶桢迟到了大概半小时, 期间张炀杰在疯狂输出, 18min 签到 C, 然后发现另一个签到题 WA 了. 我到后一看, 两个点这不直接比较写什么排序. 重写一发 43min 签到D. 我翻译了 K 和 F, 蒋叶桢 K 有思路, 然后去写了. 我一看 F 计算几何, 又来莽了. 一通计算, 结果 WA 了. 然后蒋叶桢那边 K 也出现了点问题, 后来发现了, 2h +2 过了 K. 蒋叶桢去写 I 了, 是个搜索题. 我这边找了半天没有找到为什么 WA, 很奇怪明明测试过两个球包含的情况是能跑的, 后来张炀杰改了两个特判, 终于 2h53min +2 过了 F. 蒋叶桢 I 发现路径不太对, 原来是张炀杰翻译错了方向. 重新读题后 3h05min 过了. 然后去搞之前没做出来的 G, G 好像是拿出来再丢进去就做完了, 但是 WA 了. 蒋叶桢去看 J 数学题, 他说是个缝合板题, 然后写了一大堆, 出了点大问题, P 不是质数, 然后取模不会整, 我说了个 ex 卢卡斯, 蒋叶桢说不会, 然后去找了模板题的题解, 由于没看清复杂度是 $O(P\log P)$ (主要是题解里写了个 $O(\log P)$), T了. 然后蒋叶桢灵光一闪, 骂了我一顿, 说, 直接 exCRT 就行了, 但是已经来不及打了.

  1. 计算几何在不确定的情况下最好特判, 注意细节
  2. 学习数学, 别乱给蒋叶桢瞎说算法(别骂了别骂了)

$a$ 是一个大小为 $n$ 的排列, 按照下面的算法算出数组 $b$

Stk is an empty stack
for i = 1 to n :
  while ( Stk is not empty ) and ( Stk's top > a[i] ) :
    pop Stk
  push a[i]
  b[i]=Stk's size

给出 $k$ 个 $b$ 中的数, 构造一组 $a$, 或判断无解.

$n \le 10^6$

考场上蒋叶桢写了个树状数组的, 我看了一个晚上看不懂…

易知题目的算法是维护一个单调栈.

首先无解很好判断, 就是两位置之差不能小于数值之差, 否则即使一个个填过去, 还是到不了.

通过上述分析, 可以知道, 一种合法情况是一个一个填, 那么对于 $b$ 来说, 就是没有给出的地方是上一个数$+1$. 不要放在脑子里空想, 写出来.

现在有了完整的 $b$ 如何构造 $a$.

手玩可以发现, $b$ 的最后一个数是 $x$, 那么 $a$ 的最后一个数一定是 $x$. 这是因为单调栈, $[1, x-1]$ 都在前面出现, 而到这个数 $x$ 的时候, 正好栈大小是 $x$. 按照这个思路, 先把最后一个考虑完, 那么倒过来做试一试. 下一个应该是什么呢? 假设倒数第二个数是 $y, y < x$, 那显然是 $y$; 如果 $y > x$ 呢? 由于 $x$ 被用过了, 不会出现在前面, 所以 $y$ 会更大一点.

可以用栈来维护出现在前面的数. 设当前数 $cur$, 当栈中的数小于 $b_i$ 时, 以此把 $cur, cur+1, \dots$ 入栈, 表示这些数在 $a_i$ 的前面, 直到当前栈大小等于 $b_i$. 然后栈顶就是 $a_i$ 的值, 用过了, 弹出.

也不知道怎么想到这个的, 可能是逆向思维和对称思想? 那下次碰到题想想逆过来做和对称做.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n, k, a[MAXN], b[MAXN];
vector<PII> v;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k; i++) {
    int p, x;
    scanf("%d%d", &p, &x);
    v.emplace_back(p, x);
    b[p] = x;
  }
  int last_p = 0, last_x = 0;
  for (auto[p, x] : v) {
    if (p - last_p < x - last_x) {
      puts("-1");
      return 0;
    }
    last_p = p, last_x = x;
  }
  for (int i = 1; i <= n; i++)
    if (!b[i])
      b[i] = b[i-1] + 1;
  VI stk;
  int cur = 1;
  for (int i = n; i; i--) {
    while(stk.size() < b[i])
      stk.push_back(cur++);
    a[i] = stk.back();
    stk.pop_back();
  }
  for (int i = 1; i <= n; i++)
    printf("%d%c", a[i], " \n"[i==n]);
  return 0;
}

$n$ 个区间 $[l_i, r_i)$, 分成 $m$ 组, 要求一组里的区间交集不为空. 一组的贡献是这组里区间交集的大小. 问最大贡献.

$1 \le m \le n \le 5000, 0 \le l_i < r_i \le 10^5$

贪心是错的, 又难写又过不了, 自闭了

首先把包含了其他区间的区间提出来, 这些区间只要不独立成组, 那么组的贡献就和它没有关系了.

既然不是贪心, 那么考虑 dp, 对剩下来的区间做dp. 设 $dp(i, j)$ 为前 $i$ 个分成 $j$ 组的最大总贡献, 转移如下:

$$dp(i, j) = \max_{k < i} \{ dp(k, j-1) + \min_{k < x \le i} \{r_x\} - \max_{k < y \le i} \{ l_y \} \}$$

且需要满足 $\min_{k < x \le i} \{r_x\} > \max_{k < y \le i} \{ l_y \}$

把剩下来的区间按先 $l$ 后 $r$ 排个序, 会发现这些区间的 $l$ 和 $r$ 分别递增, 式中的 $\min_{k < x \le i} \{r_x\} = r_{k+1}, \max_{k < y \le i} \{ l_y \} = l_i$. 方程变为:

$$dp(i, j) = \max_{k < i} \{ dp(k, j-1) + r_{k+1} - l_i \}$$

$l_i$ 提出来:

$$dp(i, j) = \max_{k < i} \{ dp(k, j-1) + r_{k+1} \} - l_i$$

朴素转移 $O(n^3)$, $\max_{k < i} \{ dp(k, j-1) + r_{k+1} \}$ 这个东西可以用单调队列来优化, 而且是常见的限制转移且限制单调, 即 $r_{k+1}$ 需要大于 $l_i$, 而限制 $l_i$ 和条件 $r_{i+1}$ 都是递增的. 那么对每个 $j-1$, 维护一个 $dp(k, j-1) + r_{k+1}$ 单调递减的双端单调队列, 从队头开始判断是否满足限制, 不满足就弹出, 否则就是满足限制的最优决策. 注意维护的是 $j-1$ 的队列, 和当前转移的 $j$ 的没有关系, 只不过是因为做到了 $i$, 以后的都可以考虑 $i$, 所以要把 $dp(i, j-1)$ 放进去. 从队首放, 先判断队首 $dp(k, j-1) + r_{k+1}$ 和 $dp(i, j-1), r_{i+1}$ 的大小, 如果前者小, 说明它一定不会是最优决策点, 弹出. 继续判断, 直到不满足, 再压入 $i$ 决策点.

还有一点细节, 当 $i < j$ 时 $dp(i, j)$ 不存在, 可以设为负无穷, 转移的时候也不要用它转移, 双重保险. 也就是说, 先枚举 $j$ 再枚举 $i$ 时, 直接从 $j$ 开始就行了, 再小的是不存在的状态. 需要注意, $j-1$ 队列中是有 $j-1$ 的, 这应该是第一个点, 往后加入的决策点因为这样的枚举, 都是不小于 $j$ 的, 要注意在开头压入 $j-1$.

大概总结一下关于多个区间的题

  1. 如果区间都是包含关系而没有相交关系, 那么区间的包含关系是一棵树, 按先 $l$ 递增后 $r$ 递减排序后是树的前序遍历, 可维护栈来构造这棵树. (见OpenCup某题)
  2. 如果把包含的大区间去掉, 剩下的区间按先 $l$ 后 $r$ 排序, 那么 $l$, $r$ 分别递增(本题)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
int n, k, L[MAXN], R[MAXN];
vector<PII> a, b, c;
bool big[MAXN];
LL dp[MAXN][MAXN], w[MAXN];

bool cmp(PII &p, PII q) {
  auto[lp, rp] = p;
  auto[lq, rq] = q;
  return rp - lp > rq - lq;
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    a.emplace_back(l, r);
  }

  for (int i = 0; i < n; i++) if (!big[i]) {
    auto[li, ri] = a[i];
    for (int j = 0; j < n; j++) if (j != i && !big[j]) {
      auto[lj, rj] = a[j];
      if (li == lj && ri == rj)
        big[j] = 1;
    }
  }

  for (int i = 0; i < n; i++) if (!big[i]) {
    auto[li, ri] = a[i];
    for (int j = i+1; j < n; j++) if (!big[j]) {
      auto[lj, rj] = a[j];
      if (lj <= li && ri <= rj)
        big[j] = 1;
      if (li <= lj && rj <= ri)
        big[i] = 1;
    }
  }

  for (int i = 0; i < n; i++) {
    if (big[i])
      b.push_back(a[i]);
    else
      c.push_back(a[i]);
  }

  int m = c.size();
  c.emplace_back(0, 0);
  sort(c.begin(), c.end());
  for (int i = 1; i <= m; i++) {
    auto[l, r] = c[i];
    L[i] = l, R[i] = r;
  }

  sort(b.begin(), b.end(), cmp);
  for (int i = 1; i <= n-m; i++) {
    auto[l, r] = b[i-1];
    w[i] = w[i-1] + r - l;
  }

  for (int i = 0; i <= m; i++)
    for (int j = 0; j <= k; j++)
      dp[i][j] = -INF;

  dp[0][0] = 0;
  deque<int> Q;
  for (int j = 1; j <= min(m, k); j++) {
    Q.clear();
    Q.push_back(j-1);
    for (int i = j; i <= m; i++) {
      while (Q.size() && R[Q.front()+1] <= L[i])
        Q.pop_front();
      if (Q.size())
        dp[i][j] = dp[Q.front()][j-1] + R[Q.front()+1] - L[i];
      while (Q.size() && dp[Q.back()][j-1] + R[Q.back()+1] <= dp[i][j-1] + R[i+1])
        Q.pop_back();
      Q.push_back(i);
    }
  }
  LL ans = -INF;
  for (int i = 1; i <= min(m, k); i++)
    ans = max(ans, dp[m][i] + w[k-i]);

  printf("%lld\n", max(0ll, ans));

  return 0;
}

$n$ 个人 $m$ 个关系组成图, 一个点的邻居是它的好友. 在接下来 $q$ 个单位时间内, 每次会有一个人走 $w$ 步, 当一个人是好友中步数最多的, 他是冠军. 问每个人当冠军的总时间.

$n, m, q \le 2 \cdot 10^5$, 每个人的步数不会超过 $10^4$

不好维护, 不好修改, 数据较大, 又是相邻点信息和, 那么肯定就是图论分块了.

不解释什么是图论分块.

首先维护一个数组 $last_i$ 表示最近一次成为冠军的时间(如果是冠军), 当他下一次不是冠军时, 就用不是冠军的时间减去 $last_i$ 更新答案即可. 不是冠军的话就设一个最大值或者-1表示不是冠军.

一个点更新的时候, 需要考虑邻居会不会失去冠军, 这个点会不会成为冠军.

轻点暴力, 下面考虑重点:

  1. 邻居会不会失去冠军:

重点连的重点不超过 $\sqrt{2m}$ 个, 直接暴力重点, 考虑轻点:

当一个点更新时, 避免不了要考虑所有邻居会不会失去冠军. 由于步数最多不超过 $10^4$, 那么可以考虑对每个重点开 $10^4$ 个桶, 存"步数为x的轻点邻居". 这样当一个轻点更新后, 更新所有重点邻居的桶. 当重点更新时, 假设之前是步数为 $x$, 现在加了 $w$, 那么只有在 $(x, x+w]$ 桶内的轻点才可能因为这个点变大了而失去冠军. 为什么说可能呢? 因为如果一个点更新了两次, 那么这两次都会被丢在桶里, 我们没有删除操作. 不过步数是即时更新的, 可以通过步数信息来确定这个点是不是需要失去冠军.

  1. 自己会不会成为冠军

更新轻点时可以维护重点的轻点邻居最大值, 重点邻居暴力找最大值.

一些小细节, nw的数组开不下, 但是只需要对重点开, 可以先算出$\sqrt {2m}$, 开这么多个, 记得对重点离散化.

复杂度很奇妙, 我不会算. 一次重点修改可能就是 $O(m)$ 的, 但一定不是每次都是 $O(m)$, 大概均摊 $O(qw\sqrt m)$? 很迷.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
int T, n, m, q, deg[MAXN], S, step[MAXN], heavy[MAXN], idx = 0;
int is_champion[MAXN], light_neighbor_max[MAXN], ans[MAXN], last[MAXN];
VI G[MAXN], E[MAXN], candidate[MAXM][MAXW];

void build() {
  for (int u = 1; u <= n; u++)
    for (int v : G[u]) if (deg[v] > S) {
      if (!heavy[v])
        heavy[v] = ++idx;
      E[u].push_back(v);
    }
}

void becomeChampion(int u, int t) {
  last[u] = t;
  is_champion[u] = 1;
}

void loseChampion(int u, int t) {
  ans[u] += t - last[u];
  is_champion[u] = 0;
  last[u] = q;
}

void update(int u, int w, int t) {
  step[u] += w;
  if (heavy[u]) {
    bool flag_champion_heavy = 1;
    for (int v : E[u]) {
      if (step[v] <= step[u] && is_champion[v])
        loseChampion(v, t);
      if (step[u] <= step[v])
        flag_champion_heavy = 0;
    }
    bool flag_champion_light = step[u] > light_neighbor_max[u];
    for (int i = step[u] - w + 1; i <= step[u]; i++)
      for (int v : candidate[heavy[u]][i])
        // 可能轻点被更新掉变大了, 但是没有在vector里删除
        if (is_champion[v] && step[v] <= step[u])
          loseChampion(v, t);
    if (flag_champion_heavy && flag_champion_light && !is_champion[u])
      becomeChampion(u, t);
  }
  else {
    bool flag_champion = 1;
    for (int v : G[u]) {
      if (step[v] <= step[u] && is_champion[v])
        loseChampion(v, t);
      if (step[u] <= step[v])
        flag_champion = 0;
    }
    for (int v : E[u]) {
      light_neighbor_max[v] = max(light_neighbor_max[v], step[u]);
      candidate[heavy[v]][step[u]].push_back(u);
    }
    if (flag_champion && !is_champion[u])
      becomeChampion(u, t);
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
    deg[u]++, deg[v]++;
  }
  S = sqrt(2 * m);
  for (int u = 1; u <= n; u++)
    last[u] = q;
  build();
  for (int t = 1; t <= q; t++) {
    int u, x;
    scanf("%d%d", &u, &x);
    update(u, x, t);
  }
  for (int u = 1; u <= n; u++)
    if (is_champion[u])
      loseChampion(u, q);

  for (int i = 1; i <= n; i++)
    printf("%d\n", ans[i]);
  return 0;
}

长度为 $n$ 的序列 $a$, 求有多少个连续子序列, 满足排序以后是一个等差数列.

经典枚举 $r$, 用数据结构维护 $l$, 统计有多少个 $l$ 满足条件. 但是我不会😁.

首先这里有一个很巧妙的转换, 一个数列如果能够排成等差数列, 设公差为 $d$, 有序的话, 相邻两个数的差就是 $d$, 乱序的时候, 根据欧几里得算法, 两两之差的 $gcd = d$, 即 $gcd(|a_2 - a_1|, |a_3 - a_2|, \dots) = d$. 当然有可能过程中某两个 $gcd(|a_{i+1} - a_i|, |a_{i+2} - a_{i+1}|) \ne d$, 但是一定有上述 $d | gcd$. 根据这个性质, 如果一个序列排列后是等差数列, 就有 $\max \{a_i\} - \min \{a_i\} = (r - l) \cdot gcd$, 其中, $gcd$ 表示相邻两两之差的 $gcd$, 共 $r - l$ 个. 如果这个序列排序后不是等差数列, 那么相邻两两差值不相等, 可能有 gcd 不变, 比如 2 4 6 8 12, 但是这样最大值减最小值就会比 $r-l$ 个 gcd 大; 或者 gcd 变小, 比如 2 4 6 8 9, 这样最大值减最小值还是比 $r-l$ 个 gcd 大. 严格证明? 不会! 然后把上面那个等式变型, 有 $\max \{a_i\} - \min \{a_i\} - (r - l) \cdot gcd \ge 0$. 而等于 $0$ 的点, 则是对答案有贡献的点.

枚举$r$, 每个点 $l$ 代表的是区间 $[l, r]$, 在这个点中维护 $[l, r]$ 区间的信息. 主要维护 $\max{a_i} - \min{a_i} - (r - l) \cdot gcd$. 然后对 $[1, r]$ 这些点, 开线段树维护区间信息, 主要是区间最小值(因为最小值为 0, 判断是不是 0 就知道这个区间有没有贡献了), 区间里点值为 $0$ 的个数. 那么每次枚举 $r$, 更新了以后, 答案就加上询问区间 $[1, r]$ 的贡献即可.

现在考虑如何维护. 当 $a_r$ 进来时, 考虑它会不会影响前面的某些 $[l, r]$ 中的最大值或者最小值, 这个用单调队列就可以确定需要更新的区间了. 仔细想想就能出来, 不详细解释了. 更新的话就是去掉原来的贡献, 加上现在的贡献. 然后考虑 $d = |a_r - a_{r-1}|$ 对 gcd 的贡献. 这里显然前面的每个点的 gcd 都要对这个东西再取 gcd, 但是注意到, 如果一段线段树上的区间, 即一些连续的 $[l, r]$ 区间的 gcd 都是一个数(显然这些区间是都是等差数列), 并且 $gcd | d$, 这样这些区间在加上 $a_r$ 后, gcd 不变, 不需要更新了. 只需要在值里减去一个 gcd 即可(即维护 $\max{a_i} - \min{a_i} - (r - l) \cdot gcd$). 如果线段树上区间的 gcd 有不同的, 那么就继续向下递归求解. 所以线段树上还需要记录一个 $gcd$. 当向下做到线段树上一个点时, 也即一个区间 $[l, r]$, 需要更新一下 gcd, 同时也需要维护值(详见代码). 而一次更新的 gcd 是呈平方次递减的, 所以一个线段树上的区间总共更新不会超过 $\log a$ 次. 复杂度可接受.

这里维护的 gcd, 如果对线段树上的区间来说, 左右两边的 gcd 不一样, 那么它就必须更新下去; 换句话说, 只有一样的 gcd, 才可以同时更新, 所以这里还需要一个标记, 可以直接用 $gcd = 0$ 来做标记.

pushup 需要维护的除了最小值外, 还需要有多少个点是最小值, 设为 cnt. 可以先对左区间取最小值, 然后判断左右是不是最小值, 是的话就加上这个子区间的 cnt. 两个都不是就是 0. 当然叶子节点最小值是自己, 所以 $cnt = 1$. 不需要担心叶子节点的值是不是0, 因为可以在查询的时候判断, 如果是0, 才加上cnt, 不是就不加. 同理对线段树上的区间也是一样的. 当然也可以维护 cnt 表示是 0 的有多少个, 这样就可以不用判断直接调用.

说的话好像也说不太明白,,, 还是具体看代码比较好, 复杂度大概是 $O(n \log n + n \log a)$? 有个 gcd 在那我也不知道怎么算.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
struct Node {
  int l, r, mid;
  LL mn, tag, d, cnt;
} t[MAXN << 2];

int T, n, topmn, topmx, stkmn[MAXN], stkmx[MAXN];
LL ans, a[MAXN];

/* 更新一条完整的线段 */
void updateNode(int u, LL d) {
  t[u].mn += d;
  t[u].tag += d;   //打上标记, 不再往下
}
/* 将标记下放 */
void pushDown(int u) {
  updateNode(LCH(u), t[u].tag);
  updateNode(RCH(u), t[u].tag);
  t[u].tag = 0;    //取消标记
}
/* 由左右儿子线段合并更新当前线段 */
void pushUp(int u) {
  t[u].cnt = 0;
  t[u].mn = min(t[LCH(u)].mn, t[RCH(u)].mn);
  if (t[u].mn == t[LCH(u)].mn)
    t[u].cnt += t[LCH(u)].cnt;
  if (t[u].mn == t[RCH(u)].mn)
    t[u].cnt += t[RCH(u)].cnt;
  t[u].d = t[LCH(u)].d && t[RCH(u)].d && t[LCH(u)].d == t[RCH(u)].d ? t[LCH(u)].d : 0;
}
/* 递归建树 */
void build(int l, int r, int u) {
  t[u] = Node{l, r, (l+r)>>1, 0ll, 0ll, 0ll, 0ll};
  if (l == r) t[u].cnt = 1;
  else {                             //分成左右两边递归求和
    build(l, t[u].mid, LCH(u));
    build(t[u].mid+1, t[u].r, RCH(u));
    pushUp(u);
  }
}

/* 区间修改 */
void updateVal(int l, int r, LL d, int u = 1) {
  if (t[u].l == l && t[u].r == r)
    updateNode(u, d); // 找到对应线段更新
  else {
    pushDown(u);  // 访问u的儿子线段, 需要先下放标记更新
    if (l > t[u].mid)
      updateVal(l, r, d, RCH(u)); //更新的线段全在该区间右边
    else if (r <= t[u].mid)
      updateVal(l, r, d, LCH(u)); // 全在左边
    else { // 跨越了左右两边
      updateVal(l, t[u].mid, d, LCH(u));
      updateVal(t[u].mid+1, r, d, RCH(u));
    }
    pushUp(u);  // 由儿子线段的更新后的值计算当前线段值
  }
}

void updateGcd(int R, int l, int r, LL d, int u = 1) {
  if (t[u].l == l && t[u].r == r && t[u].d && d % t[u].d == 0)
    updateNode(u, -t[u].d);
  else if (t[u].l == t[u].r) {
    updateNode(u, (R - t[u].l - 1) * t[u].d);
    t[u].d = __gcd(t[u].d, d);
    updateNode(u, -(R - t[u].l) * t[u].d);
  }
  else {
    pushDown(u);  // 访问u的儿子线段, 需要先下放标记更新
    if (l > t[u].mid)
      updateGcd(R, l, r, d, RCH(u)); //更新的线段全在该区间右边
    else if (r <= t[u].mid)
      updateGcd(R, l, r, d, LCH(u)); // 全在左边
    else { // 跨越了左右两边
      updateGcd(R, l, t[u].mid, d, LCH(u));
      updateGcd(R, t[u].mid+1, r, d, RCH(u));
    }
    pushUp(u);  // 由儿子线段的更新后的值计算当前线段值
  }
}

LL query(int l, int r, int u = 1) {
  if (t[u].l == l && t[u].r == r)
    return t[u].mn == 0 ? t[u].cnt : 0;
  pushDown(u);
  if (l > t[u].mid) return query(l, r, RCH(u));
  if (r <= t[u].mid) return query(l, r, LCH(u));
  else return query(l, t[u].mid, LCH(u)) +
        query(t[u].mid+1, r, RCH(u));
}

void init() {
  topmn = topmx = ans = 0;
  build(1, n, 1);
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++)
      scanf("%lld", a + i);
    for (int r = 1; r <= n; r++) {
      while (topmn && a[stkmn[topmn]] > a[r]) {
        updateVal(stkmn[topmn-1]+1, stkmn[topmn], a[stkmn[topmn]]);
        topmn--;
      }
      updateVal(stkmn[topmn]+1, r, -a[r]);
      stkmn[++topmn] = r;
      while (topmx && a[stkmx[topmx]] < a[r]) {
        updateVal(stkmx[topmx-1]+1, stkmx[topmx], -a[stkmx[topmx]]);
        topmx--;
      }
      updateVal(stkmx[topmx]+1, r, a[r]);
      stkmx[++topmx] = r;
      if (r > 1)
        updateGcd(r, 1, r-1, abs(a[r] - a[r-1]));
      ans += query(1, r);
    }
    printf("%lld\n", ans);
  }
  return 0;
}