题解：P14316 [Aboi Round 2] 礎の花冠
j23wuyifan
·
·
题解
感觉挺牛的数据结构题，至少我不会。。
先将询问离线下来，按照 r 做扫描线。维护一个数组 num_i 表示商为 i 的最大的 l。答案就是 num_i \ge l 的 i 的个数。商为 0 的需要特判一下。考虑从 r-1 到 r 对 num 数组的影响。
对于 a_x \le a_r，不难想到用整除分块维护。查询所有与 a_r 的商相同的 a_x 最大的 x 更新 num 数组。我们需要一个支持 O(1) 查询区间最大值，O(\sqrt{n}) 单点修改的数据结构。O(1) 修改 O(\sqrt{n}) 查询只能分块，又要查询最大值，不难想到对于每个块维护一个 st 表。修改会被影响的点，时间是
对于整块查询直接暴力查询整块最大值即可，因为查询合起来是 $1$ 到 $V$ 的，总共只有 $O(\sqrt{n})$ 个整块，所以均摊是 $O(1)$ 的。
对于 $a_x > a_r$ 的，对 $a_r$ 根号分治。若 $a_r > B$，直接暴力枚举 ${\left \lfloor \frac{a_x}{a_r} \right \rfloor}$ 的商更新答案。若 $a_r \le B$，只需要枚举上一个 $a_r$ 出现的位置到 $r$ 的数都除以 $a_r$ 更新答案。
最后就是对于 $num$ 数组求答案：当 $num$ 数组有变化时，再开个值域分块维护一下，$O(\sqrt{n})$ 查询可以接受。
卡常的话主要是跟官方题解一样把整除分块的常数卡一卡。代码应该不难写，还是放一下吧。
```cpp
inline int qrymx(int id, int l, int r) {
const int len = lg[r - l + 1];
return max(st[id][len][l], st[id][len][r - (1 << len) + 1]);
}
inline int qry(int l, int r) {
const int bl = pos[l], br = pos[r];
if (bl == br)return qrymx(bl, l - L[bl] + 1, r - L[bl] + 1);
int ans = max(qrymx(bl, l - L[bl] + 1, R[bl] - L[bl] + 1), qrymx(br, 1, r - L[br] + 1));
for (int i = pos[l] + 1; i < pos[r]; i ++) ans = max(ans, mx[i]);
return ans;
}
inline void updmx(int x, int v) {
//更新st表
const int bl = pos[x], y = x - L[bl] + 1, len = R[bl] - L[bl] + 1;
st[bl][0][y] = v;
for (int i = 1; i <= lg[len]; i ++) {
for (int j = max(y - (1 << i) + 1, 0), lim = min(y, len - (1 << i) + 1); j <= lim; j ++)
st[bl][i][j] = max(st[bl][i - 1][j], st[bl][i - 1][j + (1 << i - 1)]);
}
mx[bl] = qrymx(bl, 1, len);
}
int mn[N], sum1[N], sum2[N];
int pos2[N], block2, tot2, L2[N], R2[N];
inline void updsum(int x, int v) {
if (mn[x] < v) sum1[mn[x]] --, sum2[pos2[mn[x]]] --, mn[x] = v, sum1[v] ++, sum2[pos2[v]] ++;
}
inline int qrysum(int r) {
int ans = 0;
for (int i = r; i <= R2[pos2[r]]; i ++)ans += sum1[i];
for (int i = pos2[r] + 1; i <= tot2; i ++)ans += sum2[i];
return ans;
}
int ql[N], qr[N], ans[N];
vector<int> vec[N];
signed main() {
read(n), read(m);
int mx = 0;
for (int i = 1; i <= n; i ++)read(a[i]), mx = max(mx, a[i]);
block = sqrt(mx);
tot = (mx + block - 1) / block;
L[1] = 1, R[tot] = mx;
for (int i = 2; i <= tot; i ++)L[i] = min(L[i - 1] + block, mx);
for (int i = 1; i < tot; i ++) R[i] = L[i + 1] - 1;
for (int i = 1; i <= tot; i ++)
for (int j = L[i]; j <= R[i]; j ++)pos[j] = i;
block2 = sqrt(n);
tot2 = (n + block2 - 1) / block2;
L2[1] = 1, R2[tot2] = n;
for (int i = 2; i <= tot2; i ++)L2[i] = min(L2[i - 1] + block2, n);
for (int i = 1; i < tot2; i ++) R2[i] = L2[i + 1] - 1;
for (int i = 1; i <= tot2; i ++)
for (int j = L2[i]; j <= R2[i]; j ++)pos2[j] = i;
lg[1] = 0;
for (int i = 2; i < N; i ++)lg[i] = lg[i >> 1] + 1;
nxt[n] = n;
for (int i = n - 1; i >= 1; i --)nxt[i] = a[i] == a[i + 1] ? nxt[i + 1] : i;
for (int i = 1; i <= m; i ++) {
read(ql[i]), read(qr[i]);
vec[qr[i]].push_back(i);
ans[i] = nxt[ql[i]] < qr[i];
}
for (int i = 1; i <= n; i ++) {
const int v = a[i], sq = sqrt(v);
updmx(v, i);
for (int j = 1, pre = v, now; j <= sq; j ++)
updsum(j, qry(now = v / (j + 1) + 1, pre)), pre = now - 1;
for (int j = 1; j <= sq; j ++)
updsum(v / j, st[pos[j]][0][j - L[pos[j]] + 1]);
if (v > block) for (int j = v, k = 1; j <= mx; j += v, k ++)updsum(k, qry(j, min(j + v - 1, mx)));
else {
for (int j = lst[v] + 1; j <= i; j ++)if (a[j] >= v)updsum(a[j] / v, j);
lst[v] = i;
}
for (int x : vec[i])ans[x] += qrysum(ql[x]);
}
```