感谢 \(\mathcal{AutumnKite}\) 神犇提供的思路！

CF1677E Tokitsukaze and Beautiful Subsegments

一个区间 \(l \sim r\) 是美丽的，当且仅当存在两个数 \(i, j\) 满足 \(l \leq i < j \leq r\) 且 \(a_i \cdot a_j = \max\limits^{k\leq r}_{k=l}a_k\)。

看到 \(\max\limits^{k\leq r}_{k=l}a_k\)，我们就能想到用一个单调栈来解决。

我们可以先用单调栈预处理处对于每一个 \(a_i\)，它后面第一个比它大的数的下标 \(R_i\) 和它前面第一个比它大的数的下标 \(L_i\)。

所以对于所有的区间 \(l \sim r\) 满足 \(L_i < l \leq r < R_i\)，都有 \(\max\limits^{k\leq r}_{k=l}a_k=a_i\)。

于是我们就能够直接得到一个区间的最大值。

接着我们先考虑如何求解整个数列的美丽区间个数。

可以先对于每个 \(a_i\) 暴力枚举，枚举区间的右端点 \(r\ (i\leq r < R_i)\)，确定左端点的范围，也可以枚举区间左端点 \(l \ (L_i < l \leq i)\)，确定右端点的范围。

我们这里以枚举右端点为例。

假设我们现在有一个区间：

\(1\ \ 3\ \ 4\ \ 2\ \ 12\ \ 8\ \ 6\)。

枚举到的 \(a_i = 12\)。

我们设区间左端点的范围为 \(L \sim R\)，明显 \(L = L_i + 1\)。

首先，我们初始化 \(R = L_i\)，也就是没有合法的区间。

接着，我们枚举 \(a_i\) 的因数，设两个因数分别为 \(x, y\ \ (x \ne y)\)，数的位置为 \(pos_x\) 和 \(pos_y\)（\(pos\) 数组可以预处理，因为这是一个 \(1 \sim n\) 的排列），判断是否 \(L_i < pos_x, pos_y \leq i\)，即在范围内，然后更新 \(R = \min(pos_x, pos_y)\)。

感性理解一下，例如在这里，我们可以枚举到 \(12\) 的因数有 \(3\) 和 \(4\)。

所以更新 \(R = \min(pos_3, pos_4) = 2\)，即只需左端点在 \(1 \sim 2\) 中，包含着 \(3\) 和 \(4\)，那么就有 \(3 \times 4 = 12\)，即这个区间是美丽的。

这样总时间复杂度为 \(\mathcal{O(\Sigma^{i\leq n}_{i=1}\sqrt a_i)}\)。

然后我们可以对于每一个枚举到的右端点，算出与它的乘积为 \(a_i\) 的那个数的位置，判断是否在范围内，如果在，则更新 \(R = \max(R, pos)\)，这里要注意，可能 \(pos > i\)，这是需要在更新 \(R = \min(R, i)\)。

例如枚举到 \(6\) 时，算出 \(\dfrac{12}{6}=2, pos_2 = 4\)，所以更新 \(R = 4\)，即右端点在 \(6\) 之后只需要左端点中包含 \(2\)，就有 \(2 \times 6 = 12\)，即这个区间是美丽的。

对于每一个这样的三元组 \((L,R,r)\) 表示右端点为 \(r\) 时左端点为 \(L \sim R\) 时区间时美丽的，我们都可以用一个 vector 把它记录下来。

具体地，我们可以这样操作：

vector < pair <int, int> > vec[MAXN];

// Insert operation.

vec[r].push_back(make_pair(L, R));

如果枚举左端点，三元组 \((L, R, l)\) 表示左端点为 \(l\) 时右端点为 \(L \sim R\) 时区间是美丽的，同理。

如果全局查询，我们只需要把每一个三元组的 \(R - L + 1\) 给加起来就是答案。

可是现在是区间查询。

所以我们可以参考扫描线的思想。

首先把询问离线，按照右端点从小到大排序，用 \(i\) 指针从 \(1\ sim n\) 枚举，每次把右端点为 \(i\) 的所有三元组给加到一个线段树中，就是把区间 \(L \sim R\) 加上 \(1\)，然后遇到对应的询问 \((l, r)\) 时，查询线段树上 \(l \sim r\) 的和就行了。

如果时枚举左端点，就按照左端点从大到小排序，用 \(i\) 指针逆序扫，其余同理。

这样我们可以完成区间查询了，但是时间复杂度却是可怜的 \(\mathcal{O(n^2)}\)。

我们会发现对于一个数 \(a_i\)，枚举左端点和右端点都可以，根据正常人的思维，哪一个短就枚举哪一个。

结果我们发现这过了。

其实这个是启发式分裂的思想，这样能够保证枚举的数量不超过 \(n \log n\) 个。

所以加上线段树查询的时间复杂度，总时间复杂度为 \(\mathcal{O(n \log^2 n + q \log n + \Sigma^{i\le n}_{i = 1}\sqrt a_i)}\)。

最后不要忘记开 long long。

并且这道题有一些神奇，不用快读快输过不去。

// Thanks for solution given from AutumnKite! Orz %%%
#include <bits/stdc++.h>

using namespace std;

#define int long long

static char buf[100010], *p1 = buf, *p2 = buf;
#define gc p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100010, stdin), p1 == p2)? EOF: *p1++

inline int read() {
	int res = 0, w = 0; char c = gc;
	while (!isdigit(c)) w |= c == '-', c = gc;
	while (isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = gc;
	return (w? -res : res);
}

inline void write(int x) {
	static int sta[50], top = 0;
	if (x < 0) putchar('-'), x = -x;
	do {
		sta[ top++ ] = x % 10, x /= 10;
	} while (x);
	while (top) putchar(sta[ --top ] + 48);
	putchar('\n');
}

#define ls (p << 1)
#define rs (p << 1 | 1)

const int MAXN = 2e5 + 10;

int n, Q, a[MAXN], pos[MAXN], L[MAXN], R[MAXN];
int sta[MAXN], top, Qnum;

vector < pair <int, int> > vec1[MAXN], vec2[MAXN];

struct Query {
	int l, r, id;
}q[ (int)(1e6 + 10) ];

int Ans[ (int)(1e6 + 10) ];

inline bool Comp1(Query a, Query b) {
	return a.r < b.r;
}

inline bool Comp2(Query a, Query b) {
	return a.l > b.l;
}

struct Node {
	int len, data, add;
	Node() = default;
	Node(const int Len, const int Data, const int Add) : len(Len), data(Data), add(Add) {}
}t[ MAXN << 2 ];

inline void build(int p, int l, int r) {
	t[p] = Node(r - l + 1, 0, 0);
	if (l == r) return ;
	int mid = l + r >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
}

inline void pushdown(int p) {
	t[ls] = Node(t[ls].len, t[ls].data + t[ls].len * t[p].add, t[p].add + t[ls].add);
	t[rs] = Node(t[rs].len, t[rs].data + t[rs].len * t[p].add, t[p].add + t[rs].add);
	t[p].add = 0;
}

inline void update(int p, int l, int r, int x, int y, int k) {
	if (l >= x && r <= y) {
		t[p] = Node(t[p].len, t[p].data + t[p].len * k, t[p].add + k);
		return ;
	}
	pushdown(p);
	int mid = l + r >> 1;
	if (x <= mid) update(ls, l, mid, x, y, k);
	if (mid < y) update(rs, mid + 1, r, x, y, k);
	t[p].data = t[ls].data + t[rs].data;
}

inline int query(int p, int l, int r, int x, int y) {
	if (l >= x && r <= y) return t[p].data;
	int ans = 0, mid = l + r >> 1;
	pushdown(p);
	if (x <= mid) ans += query(ls, l, mid, x, y);
	if (mid < y) ans += query(rs, mid + 1, r, x, y);
	return ans;
}

signed main() {
	n = read(); Q = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		pos[ a[i] ] = i;
	}
	
	top = 0;
	for (int i = 1; i <= n; i++) {
		while (top > 0 && a[ sta[top] ] < a[i]) top--;
		L[i] = sta[top];
		sta[ ++top ] = i;
	}
	
	top = 0;
	sta[0] = n + 1;
	for (int i = n; i >= 1; i--) {
		while (top > 0 && a[ sta[top] ] < a[i]) top--;
		R[i] = sta[top];
		sta[ ++top ] = i;
	}
	
	for (int i = 1; i <= Q; i++) {
		q[i].l = read(); q[i].r = read();
		q[i].id = i;
	}
	
	for (int i = 1; i <= n; i++) {
		int left, right;
		if (R[i] - i <= i - L[i]) {
			right = L[i];
			for (int j = 1; j * j <= a[i]; j++) {
				if (a[i] % j != 0) continue;
				int fx = pos[j], fy = pos[ a[i] / j ];
				if (fx == fy) continue;
				if (fx > fy) swap(fx, fy);
				if (fx > L[i] && fy <= i)
					right = max(right, fx);
			}
			for (int j = i; j < R[i]; j++) {
				if (a[i] % a[j] == 0) {
					int num = a[i] / a[j];
					if (pos[num] == j) continue;
					if (pos[num] > L[i] && pos[num] < j) {
						right = max(right, pos[num]);
						right = min(right, i); 
					}
				}
				if (L[i] < right)
					vec1[j].push_back(make_pair(L[i] + 1, right));
			}
		}
		else {
			left = R[i];
			for (int j = 1; j * j <= a[i]; j++) {
				if (a[i] % j != 0) continue;
				int fx = pos[j], fy = pos[ a[i] / j ];
				if (fx == fy) continue;
				if (fx > fy) swap(fx, fy);
				if (fy < R[i] && fx >= i)
					left = min(left, fy);
			}
			for (int j = i; j > L[i]; j--) {
				if (a[i] % a[j] == 0) {
					int num = a[i] / a[j];
					if (pos[num] == j) continue;
					if (pos[num] > j && pos[num] < R[i]) {
						left = min(left, pos[num]);
						left = max(left, i);
					}
				}
				if (left < R[i])
					vec2[j].push_back(make_pair(left, R[i] - 1));
			}
		}
	}

	sort(q + 1, q + Q + 1, Comp1);
	build(1, 1, n);
	
	Qnum = 1;
	for (int i = 1; i <= n; i++) {
		for (auto v : vec1[i]) {
			update(1, 1, n, v.first, v.second, 1);
		}
		for (; q[Qnum].r == i && Qnum <= Q; Qnum++) {
			Ans[ q[Qnum].id ] += query(1, 1, n, q[Qnum].l, q[Qnum].r);
		}
	}
	
	sort(q + 1, q + Q + 1, Comp2);
	build(1, 1, n);
	
	Qnum = 1;
	for (int i = n; i >= 1; i--) {
		for (auto v : vec2[i]) {
			update(1, 1, n, v.first, v.second, 1);
		}
		for (; q[Qnum].l == i && Qnum <= Q; Qnum++) {
			Ans[ q[Qnum].id ] += query(1, 1, n, q[Qnum].l, q[Qnum].r);
		}
	}
	
	for (int i = 1; i <= Q; i++) write(Ans[i]); 
	
	return 0;
}