板刷计划:ARC068

传送门:https://atcoder.jp/contests/arc068

前言:智商不在线.

在说这道题之前,还是强调一个结论:调和级数:

\sum_{i=1}^n\frac{n}{i} \approx n\ln n \approx nlogn

.做这道题之前又突然失忆了,

题目大意:给你在线段

[1,m]上的n个

区间.对于每一个

d \in [1,m]

, 回答点集

\{d , 2d , ... , kd\} .k \leq \lfloor \frac{n}{d} \rfloor

覆盖了多少个区间.

题目思路:

不难发现:区间大小大于等于 d 的区间一定对答案有贡献.自然想到对区间大小排序.

考虑区间长度小于d的区间:它其中要么含有一个d的倍数.要么没有.所以我们自然可以将这些区间插入到树状数组中去.暴力每个点都查询一下即可.

注:这样一定是正确的.因为在暴力查询的过程中.每个区间最多贡献一次.所以每一个点的答案都一定来自于不同的区间贡献.

由于调和级数,暴力查询的复杂度为:

\Theta (nlog^2n)

两个推论:

1.一个长度为n的排列插入到双端队列中后产生

2^{n-1}

个本质不同的序列.且以

x

为开头的序列个数为:

2^{x - 2}

个.

*可以利用递推法:假设长度为n - 1 的排列产生X个方案,新增的n放在每个方案的两边将得到 2 * X 个方案.

2.一个长度为n的排列插入到双端队列中后值域的分布一定成"V"字形且最小值一定是1.