解题情况：成功 AC 了前三道，第四道假了，因为太困了就去睡觉了）
题意 给一个 1 1 1 到 n n n 的排列 p i p_i pi 和正整数 k k k，问对排列进行最少多少次的交换操作可以最小化排列的前 k k k 项和。
解答 容易发现，排列的前 k k k 项和最小时，前 k k k 项一定是一个 1 1 1 到 k k k 的排列，也就是我们最终的目标。所以，如果原排列前 k k k 个数中存在 > k > k >k 的数，那么就要把它和后 n − k n-k n−k 个数中某个 ≤ k \le k ≤k 的数互换位置。
最终答案为 ∑ i = 1 k [ p i > k ] \sum_{i=1}^k[p_i>k] ∑i=1k[pi>k].
提交记录，稍微写的有点麻烦，因为没看到是排列。
题意 给出 n n n，请构造一个 1 1 1 到 n n n 的排列 p i p_i pi，使得 ∑ i = 1 n lcm ( i , p i ) \sum_{i=1}^n\operatorname{lcm}(i, p_i) ∑i=1nlcm(i,pi) 最大。
解答 本题初看没什么思路，不过连蒙带猜构造还是容易的。
本题构造方法如下：
感觉上这样就很大。
下面用两种方法证明：
方法1 我的证明方法。
首先，当 n = 1 , 2 n=1, 2 n=1,2 时，容易证明这样的构造是不劣的。
其次，如果当 n = k − 2 ( k ≥ 3 ) n=k-2(k\ge 3) n=k−2(k≥3) 时，这样的构造是不劣的，我们下证明 n = k n=k n=k 时这样的构造是不劣的（即在原构造的基础上最后添加的是 k , k − 1 k, k-1 k,k−1）
无非有以下几种情况：
其实 3 4 可以这样理解；我多出了两个数 k − 1 , k k-1, k k−1,k，如果和之前的两个数 i , j i,j i,j 进行两两组合 成 ( a , b ) , ( c , d ) (a,b), (c,d) (a,b),(c,d)，贡献为 a b + c d ab+cd ab+cd（这里假设 a ⊥ b , c ⊥ d a\perp b, c\perp d a⊥b,c⊥d 为不劣情况），根据排序不等式， k − 1 k-1 k−1 和 k k k 组合会更优；同时由于 ( k − 1 ) ⊥ k (k-1)\perp k (k−1)⊥k，所以这种情况的最优性得到了确保。这样，再结合 1, 2，就可以得到构造的最优性。
方法2 是来自原题解的神乎其技！没看懂qwq。
提交记录。
题意 给一个长度为 n n n 的数列 a i ( 1 ≤ a i ≤ n ) a_i(1\le a_i\le n) ai(1≤ai≤n)。定义一个操作为：自己选一个 x x x，使得所有 a i = x a_i=x ai=x 的 a i a_i ai 变为 0。问最少需要几次操作使得数列变成单调不降。
解答 想象一下最后的情形，一定是一个：存在一个 t ∈ [ 0 , n ] t\in[0, n] t∈[0,n]，当 1 ≤ i ≤ t , a i = 0 1\le i\le t,\ a_i=0 1≤i≤t, ai=0，当 i > t i>t i>t， a i ≥ 1 a_i\ge 1 ai≥1 且不降。
所以我们从 n n n 往前扫描，确定这样一个 t t t。
如果找到一个
k
<
n
k
出现问题：因为操作要对所有 a i = x a_i=x ai=x 操作，所以对 a 1 … k a_{1\dots k} a1…k 操作时，有可能也会将 a k + 1 ⋯ n a_{k+1\cdots n} ak+1⋯n 中的一些值变成 0。
所以我们需要补充一个条件：扫到一个 a i a_i ai 时，如果存在 j < i jj<i 且 a j = a i a_j=a_i aj=ai，那么， ∀ k ∈ [ j , i ] \forall k\in[j,i] ∀k∈[j,i] 都应该有 a k = a i a_k=a_i ak=ai，否则就要从 i i i 开始往前赋值为 0 了。
实现过程中，只需记录每种 a i a_i ai 出现次数和最初位置，即可 O ( n ) O(n) O(n) 判断。
提交记录。
题意 给一个长度为 n n n 的数列 a n , ( 1 ≤ a i ≤ 1 0 9 ) a_n,(1\le a_i\le 10^9) an,(1≤ai≤109)，和一个正整数 k ( 1 ≤ k ≤ n ) k(1\le k\le n) k(1≤k≤n)，可以进行至多 k k k 次操作，每次操作将数列中的某一个数变为自己选的一个数 x ( 1 ≤ x ≤ 1 0 9 ) x(1\le x\le 10^9) x(1≤x≤109)。进行完操作后，建立 n n n 个点的完全图，且节点 x x x 和 y y y 之间连边为 e ( x , y ) = min x ≤ k ≤ y a k e(x,y)=\min_{x\le k\le y} a_k e(x,y)=minx≤k≤yak，设 d ( x , y ) d(x,y) d(x,y) 为 x , y x,y x,y 之间的最短路径，求对任意 u , v u,v u,v， d ( u , v ) d(u,v) d(u,v) 的最大值（也就是直径 d i a m e t e r diameter diameter）。
解答 考虑
d
(
x
,
y
)
,
x
<
y
d(x,y),x
d ( x , y ) = min ( min x ≤ i ≤ y a i , 2 ⋅ min 1 ≤ i ≤ n a i ) d(x,y)=\min(\min_{x\le i\le y} a_i,2\cdot\min_{1\le i\le n} a_i) d(x,y)=min(x≤i≤yminai,2⋅1≤i≤nminai)
前者是直接走过去，也就是 e ( u , v ) e(u,v) e(u,v)；后者是通过两条最小的边到达。
事实上，图中最小的边就是途径 a t a_t at（ a t a_t at 为最小值）的边。所以容易理解上面的式子的正确性。
于是直径
d
i
a
m
e
t
e
r
=
max
u
<
v
d
(
u
,
v
)
=
max
u
<
v
min
(
min
u
≤
i
≤
v
a
i
,
2
⋅
min
1
≤
i
≤
n
a
i
)
=
min
(
max
u
<
v
min
u
≤
i
≤
v
a
i
,
2
⋅
min
1
≤
i
≤
n
a
i
)
=
min
(
max
1
≤
k
<
n
min
(
a
k
,
a
k
+
1
)
,
2
⋅
min
1
≤
i
≤
n
a
i
)
（最后一步是因为， u , v u,v u,v 相距远的时候一定没有比 u , v u,v u,v 紧挨着的情况优）
我们要求的是 k k k 次操作后， d i a m e t e r diameter diameter 的最大值
于是有以下两种方法：
解法1 二分法
二分一个
d
d
d，看看是否满足
a
n
s
≥
d
ans \ge d
ans≥d。那么要求
max
1
≤
k
<
n
min
(
a
k
,
a
k
+
1
)
≥
d
\max_{1\le k
二分的区间为 [ 1 , 1 0 9 ] [1, 10^9] [1,109] 即可。
提交记录。
解法2 贪心法
将 k − 1 k-1 k−1 次操作用作将数列的前 k − 1 k-1 k−1 小值变为 1 0 9 10^9 109，最后一次操作用来枚举 1 1 1 到 n n n，这个位置再变成 1 0 9 10^9 109。取所有枚举的最大值。（事实证明枚举这一步是可以避免的，见下文）
下面简单证明一下。当 k = 1 k=1 k=1 是显然的；当 k ≥ 2 k\ge 2 k≥2 时：
我们要求所有的操作最大化
min ( max 1 ≤ k < n min ( a k , a k + 1 ) , 2 ⋅ min 1 ≤ i ≤ n a i ) \min(\max_{1\le k< n}\min(a_k,a_{k+1}), 2\cdot \min_{1\le i\le n}a_i) min(1≤k<nmaxmin(ak,ak+1),2⋅1≤i≤nminai)
那么我们的贪心不能杜绝达到最优的可能性。如果最后限制住的是 2 ⋅ min 1 ≤ i ≤ n a i 2\cdot \min_{1\le i\le n}a_i 2⋅min1≤i≤nai 的部分，那么我最后一次选取第 k k k 小值，则实质上选取了前 k k k 小值，尽全力提升了 2 ⋅ min 1 ≤ i ≤ n a i 2\cdot \min_{1\le i\le n}a_i 2⋅min1≤i≤nai；如果最后限制住的是 max 1 ≤ k < n min ( a k , a k + 1 ) \max_{1\le k< n}\min(a_k,a_{k+1}) max1≤k<nmin(ak,ak+1)，那么我们可以让两个 1 0 9 10^9 109 相邻，解除这个限制。
从上面的算法我们发现，我们其实不需要从 1 1 1 到 n n n 枚举（事实上就算枚举，也可以在不劣的复杂度下完成），只需要比较以下两处选取最大答案：
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)，瓶颈在排序。
提交记录。
题意 给出 l , r l,r l,r，求
∑
l
≤
i
<
j
<
k
≤
r
[
lcm
(
i
,
j
,
k
)
≥
i
+
j
+
k
]
\sum_{l\le i
解答 首先不考虑限制，这样的 ( i , j , k ) (i,j,k) (i,j,k) 三元组有 ( r − l + 1 3 ) \binom{r-l+1}{3} (3r−l+1) 个，那么原式即
(
r
−
l
+
1
3
)
−
∑
l
≤
i
<
j
<
k
≤
r
[
lcm
(
i
,
j
,
k
)
<
i
+
j
+
k
]
\binom{r-l+1}{3}-\sum_{l\le i
考虑后半部分（记为性质 Q）如何计数。
由于
k
∣
lcm
(
i
,
j
,
k
)
k\mid \operatorname{lcm}(i,j,k)
k∣lcm(i,j,k)，而
i
+
j
+
k
<
3
k
i+j+k<3k
i+j+k<3k，那么
lcm
(
i
,
j
,
k
)
=
k
或
2
k
\operatorname{lcm}(i,j,k)=k\ \textnormal{或}\ 2k
lcm(i,j,k)=k 或 2k。代入
lcm
(
i
,
j
,
k
)
<
i
+
j
+
k
\operatorname{lcm}(i,j,k)
lcm ( i , j , k ) = k \operatorname{lcm}(i,j,k)=k lcm(i,j,k)=k 或 （ lcm ( i , j , k ) = 2 k \operatorname{lcm}(i,j,k)=2k lcm(i,j,k)=2k 且 i + j > k i+j>k i+j>k）
两种情况下
i
,
j
i,j
i,j 都必须要是
2
k
2k
2k 的因数。我们先枚举
k
k
k 再枚举
i
∣
2
k
i\mid 2k
i∣2k，用
f
(
i
,
k
)
f(i,k)
f(i,k) 表示满足
i
<
j
<
k
i
这样我们就得到了若干个 f ( i , k ) f(i,k) f(i,k)。之后将询问离线，所有询问和贡献按 r r r 排序，维护 l l l 端点的答案，用树状数组维护即可。
时间复杂度为 O ( ∑ i = 1 n σ 0 ( 2 i ) ⋅ ( σ 0 ( 2 i ) + log n ) + T log n ) O(\sum_{i=1}^n\sigma_0(2i)\cdot (\sigma_0(2i)+\log n)+T\log n) O(∑i=1nσ0(2i)⋅(σ0(2i)+logn)+Tlogn)。
类比于 O ( ∑ i = 1 n σ 0 ( i ) ) = O ( ∑ i = 1 n ⌊ n / i ⌋ ) = O ( n log n ) O(\sum_{i=1}^n\sigma_0(i))=O(\sum_{i=1}^n\lfloor n / i\rfloor)=O(n\log n) O(∑i=1nσ0(i))=O(∑i=1n⌊n/i⌋)=O(nlogn)，上面那玩意大概是 O ( n log 2 n + T log n ) O(n\log^2 n+T\log n) O(nlog2n+Tlogn)。
提交记录。
暂时不会，待填。