头文字 D
题目链接：ybtoj高效进阶 21262
题目大意
给你一个排列，问你有多少个长度大于 1 的区间，满足这个区间的所有长度大于 1 的子区间的 gcd 和的最大值为 x。
对于每个 x 都要求解。
思路
首先我们考虑从 (n) 到 (1) 求每个答案。
那如果能有这个答案，它一定是由两个 (x)（的倍数）或以上组成的。
但它不一定是，可能答案是这个 (x) 的倍数。
那我们先不管，我们先找到位置，记为 (pl_i)。
（(pl_0=0)）
那对于任意一个 (i(1leqslant i<m))，会有 ([pl_{i-1}+1,pl_i]) 中的左端点和 ([pl_{i+1},n]) 中的右端点组成的右区间就一定包含至少两个 (x) 的倍数。
然后接下来处理答案不是 (x) 而是 (x) 的倍数的，那因为我们是从大到小枚举的，这个时候这些位置都会被碰过。
那我们再搞一个数组 (pos_i) 表示 (i) 为左端点，右端点最多能移动到哪里，使得这个区间都没有被碰过。
显然 (pos_i) 单调递增。
那我们考虑用线段树维护，对于前面我们枚举的每个区间，我们先找到 ([pl_{i-1}+1,pl_i]) 中第一个 (pos_i) 大于 (pl_{i+1}) 的位置 (l)。
那这些位置都可以有，就是 ([l,pl_i]) 的 (pos) 值都变成 (pl_{i+1}-1)。
不难发现每次能算出来的结果就是 (pos) 值改变的位置数，其实就是线段树全局和的差值。
然后就好了。
枚举哪个答案 (O(n))，枚举它的倍数 (O(logn))，线段树 (O(logn))，所以是 (O(nlog^2n)) 可以过。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, a[100001], pl[100001];
ll ans[100001], lst, now;
int b[100001], bn;
struct node {//线段树（维护和，最大值）
ll sum[400001], maxn[400001];
ll lzy[400001];
void up(int now) {
sum[now] = sum[now << 1] + sum[now << 1 | 1];
maxn[now] = max(maxn[now << 1], maxn[now << 1 | 1]);
}
void down(int now, int l, int r) {
if (!lzy[now]) return ;
int mid = (l + r) >> 1, ls = mid - l + 1, rs = r - mid;
sum[now << 1] = 1ll * lzy[now] * ls;
sum[now << 1 | 1] = 1ll * lzy[now] * rs;
maxn[now << 1] = maxn[now << 1 | 1] = lzy[now];
lzy[now << 1] = lzy[now << 1 | 1] = lzy[now];
lzy[now] = 0;
}
void insert(int now, int l, int r, int L, int R, int val) {
if (L <= l && r <= R) {
sum[now] = 1ll * val * (r - l + 1);
maxn[now] = val; lzy[now] = val;
return ;
}
down(now, l, r);
int mid = (l + r) >> 1;
if (L <= mid) insert(now << 1, l, mid, L, R, val);
if (mid < R) insert(now << 1 | 1, mid + 1, r, L, R, val);
up(now);
}
ll query_sum(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) return sum[now];
down(now, l, r);
int mid = (l + r) >> 1;
ll re = 0;
if (L <= mid) re += query_sum(now << 1, l, mid, L, R);
if (mid < R) re += query_sum(now << 1 | 1, mid + 1, r, L, R);
return re;
}
ll query_big(int now, int l, int r, int L, int R, int k) {
if (l == r) return l;
down(now, l, r);
int mid = (l + r) >> 1;
if (L <= mid && maxn[now << 1] > k) return query_big(now << 1, l, mid, L, R, k);
if (mid < R && maxn[now << 1 | 1] > k) return query_big(now << 1 | 1, mid + 1, r, L, R, k);
return -1;
}
}T;
int main() {
// freopen("gcd.in", "r", stdin);
// freopen("gcd.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]); pl[a[i]] = i;
}
T.insert(1, 1, n, 1, n, n);
lst = T.query_sum(1, 1, n, 1, n);
for (int i = n; i >= 1; i--) {
int j = i; bn = 0;
b[0] = 0;
while (j <= n) {//找到每个它的倍数在原数组中的位置
b[++bn] = pl[j];
j += i;
}
sort(b + 1, b + bn + 1);//排序
for (int j = 1; j < bn; j++) {//操作
int l = T.query_big(1, 1, n, b[j - 1] + 1, b[j], b[j + 1] - 1);
if (l != -1) T.insert(1, 1, n, l, b[j], b[j + 1] - 1);
}
now = T.query_sum(1, 1, n, 1, n);
ans[i] = lst - now;//答案为线段树的和的变化
lst = now;
}
for (int i = 1; i <= n; i++)
printf("%lld
", ans[i]);
return 0;
}