【ybtoj高效进阶 21262】头文字 D(线段树)(数学)
头文字 D
题目链接:ybtoj高效进阶 21262
题目大意
给你一个排列,问你有多少个长度大于 1 的区间,满足这个区间的所有长度大于 1 的子区间的 gcd 和的最大值为 x。
对于每个 x 都要求解。
思路
首先我们考虑从 n n n 到 1 1 1 求每个答案。
那如果能有这个答案,它一定是由两个
x
x
x(的倍数)或以上组成的。
但它不一定是,可能答案是这个
x
x
x 的倍数。
那我们先不管,我们先找到位置,记为
p
l
i
pl_i
pli。
(
p
l
0
=
0
pl_0=0
pl0=0)
那对于任意一个 i ( 1 ⩽ i < m ) i(1\leqslant i<m) i(1⩽i<m),会有 [ p l i − 1 + 1 , p l i ] [pl_{i-1}+1,pl_i] [pli−1+1,pli] 中的左端点和 [ p l i + 1 , n ] [pl_{i+1},n] [pli+1,n] 中的右端点组成的右区间就一定包含至少两个 x x x 的倍数。
然后接下来处理答案不是
x
x
x 而是
x
x
x 的倍数的,那因为我们是从大到小枚举的,这个时候这些位置都会被碰过。
那我们再搞一个数组
p
o
s
i
pos_i
posi 表示
i
i
i 为左端点,右端点最多能移动到哪里,使得这个区间都没有被碰过。
显然
p
o
s
i
pos_i
posi 单调递增。
那我们考虑用线段树维护,对于前面我们枚举的每个区间,我们先找到
[
p
l
i
−
1
+
1
,
p
l
i
]
[pl_{i-1}+1,pl_i]
[pli−1+1,pli] 中第一个
p
o
s
i
pos_i
posi 大于
p
l
i
+
1
pl_{i+1}
pli+1 的位置
l
l
l。
那这些位置都可以有,就是
[
l
,
p
l
i
]
[l,pl_i]
[l,pli] 的
p
o
s
pos
pos 值都变成
p
l
i
+
1
−
1
pl_{i+1}-1
pli+1−1。
不难发现每次能算出来的结果就是 p o s pos pos 值改变的位置数,其实就是线段树全局和的差值。
然后就好了。
枚举哪个答案
O
(
n
)
O(n)
O(n),枚举它的倍数
O
(
l
o
g
n
)
O(logn)
O(logn),线段树
O
(
l
o
g
n
)
O(logn)
O(logn),所以是
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n) 可以过。
代码
#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\n", ans[i]);
return 0;
}