悲，昨天存本地忘发了，今天又不想写模拟 5 的。
考了四道 ARC 就离谱。
A. LIS to Original Sequence
首先考虑 \(k = 1\)，唯一的方案就是倒序输出 \(1\) 到 \(n\)。
我们可以想到，这道题的方法是向已经确定的序列 \(A\) 中插入其他数。
对于一个数 \(x(x < A_i)\)，是不能把它放在 \(A_i\) 前的，不然会使最长上升子序列的长度变大。
为了保证字典序最小，我们得把能放在 \(A_i\) 后的最小的数放它后边。
最后要特殊处理 \(A_k\)，把剩下没有加入答案序列的部分倒序输出。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200500;
int n,k;
int a[N],t[N];
int main() {
cin >> n >> k;
for(int i = 1;i <= k; i++) {
cin >> a[i];
t[a[i]] ++;
}
if(k == 1) {
for(int i = n;i >= 1; i--)
cout << i << " ";
return 0;
}
int cur = 1;
while(cur <= n && t[cur])
cur ++;
for(int i = 1;i < k; i++) {
cout << a[i] << " ";
if(cur < a[i]) {
t[cur] ++;
cout << cur << " ";
cur ++;
}
while(cur <= n && t[cur])
cur ++;
}
for(int i = n; i >= 1; i--) {
if(!t[i] || i == a[k])
cout << i << " ";
}
return 0;
}
B. Unique Subsequence
设 \(pre_i\) 表示在 \(i\) 之前最后一个和 \(i\) 相同的数的位置，\(dp_i\) 表示第 \(i\) 个数为结尾的序列的合法方案数。
对于 \(pre_i = 0\)，即在 \(i\) 之前不存在与 \(i\) 相同的数，\(dp_i\) 由 \(\left[ 1,i - 1 \right]\) 转移过来。由于这个数还没有在之前出现过，它本身也是一个合法序列，所以要加 \(1\)。
\[dp_i= \sum_{j=1}^{i-1}dp_j + 1 \]对于 \(pre_i \neq 0\)，即在 \(i\) 之前存在与 \(i\) 相同的数，那么我们考虑 \(\left[ 1,pre_i - 1 \right]\) 这部分，由于 \(i\) 已经在之前出现过了，这部分序列加上 \(i\) 的部分在 \(pre_i\) 已经处理过了，再加的话会导致重复。
考虑 \(\left[ pre_i,i - 1 \right]\) 这部分，对于之前加过的单独的 \(i\)，这时候要 \(-1\)，但是又因为产生了新序列 \(\left\{ pre_i,i \right\}\)，这里要 \(+1\)，所以最终不加不减。
\[dp_i=\sum^{i-1}_{j=pre_i}dp_j \]最后我们用树状数组对区间求和进行优化。
C. Maximize GCD
设 \(a_{max}\) 表示 \(max \left\{ a_1,\dots,a_n \right\}\)，\(sum\) 表示 \(a_1 + a_2 + \dots + a_n\)。
一般来说，与其处理 \(x | \gcd(A_1,\dots,A_N)\) ，处理 \(x = \gcd(A_1,\dots,A_N)\) 更加容易。这是因为后者能够被分解为各个元素：\(\forall i,x | A_i\)。
因此，我们将解决下面这个问题而不是原来的问题。
寻找 \(x\) 的最大值，这样就有可能在运算后得到 \(x | \gcd(A_1,\dots,A_N)\)。
假设 \(K\) 足够大，能够使得序列中每一个值都加到 \(a_{max}\)，那我们就先把每个值都加到 \(a_{max}\)，剩下的操作数再平均分配到每一个元素。
如果 \(K\) 不能使得序列中每一个值都加到 \(a_{max}\)，我们能够发现，答案的最大值不超过 \(a_{max}\)，也就是不超过 \(3 \times 10^5\)。
这个范围我们完全可以从大到小枚举 \(x\) 的值。
如何枚举 \(x\) 的值？
设 \(k\) 为一个整数，并且计算出对于所有 \(A_i\) 能够满足 \((k - 1)x < A_i \leq kx\) 的操作数。
我们可以计算出一个值域 \(\left(kx - x,kx \right]\) 内 \(A_i\) 的个数和 \(A_i\) 的和。由于是静态的，直接前缀和统计就可以。
这样枚举中找到满足需要的操作次数不大于 \(K\) 的 \(x\) 的最大值。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
const int N = 114514 * 6;
int n,K;
int a[N];
int num[N];
// 桶
int sum1[N],sum2[N];
long long sum = 0;
int max_num = -114514;
void Input() {
cin >> n >> K;
for(int i = 1;i <= n; i++) {
cin >> a[i];
num[a[i]] ++;
max_num = max(max_num,a[i]);
}
return ;
}
void Ready() {
for(int i = 1;i <= 2 * max_num; i++) {// 枚举值域
sum1[i] = sum1[i - 1] + num[i];
sum2[i] = sum2[i - 1] + num[i] * i;
}
return ;
}
void Work_0() {
for(int i = 1;i <= n; ++i)
sum += (max_num - a[i]);
return ;
}
signed main() {
Input();
Ready();
Work_0();
if(sum <= K) {
cout << max_num + (K - sum) / n;
return 0;
}
for(int x = max_num;x >= 1; x--) {
sum = 0;
for(int k = 1;(k - 1) * x <= max_num; k++) {
// 最后一个区间可能只有一小部分
// 所以使左区间小于 max_num
int tmp = sum1[x * k - 1] - sum1[x * (k - 1)];
sum += tmp * x * k;
sum -= sum2[x * k - 1] - sum2[x * (k - 1)];
}
if(sum <= K) {
cout << x;
return 0;
}
}
return 0;
}