Solution. Codeforces Round #830
补题拖了很久，还好最近的 Div.2 做的不错，不会留太多题，但是 1+2 就很难受了。
D. Balance
其实 $\operatorname{mex}$ 这种东西通常没有什么花里胡哨的处理方式，一般来说还是要根据题目的具体操作找一些特殊的性质。
对于这道题，我们的做法是，每次暴力找 $\operatorname{mex}$，只不过将答案存下来，下次查询时从上次的答案处继续跳。
如果加上了删除操作，我们考虑对于每一个 $k$ 维护被删除且不大于当前答案的数的集合，每次查询时假如集合不为空就取最小值，否则和之前一样继续跳 $\operatorname{mex}$。
其实基本上就是暴力的做法。
复杂度的核心在于一个数会被计算多少次，我的想法是，对于 $x$，假如它在 $\operatorname{k-mex}$ 中被计算了一次，那么就意味着还有 $\dfrac xk$ 个数已经被加入了，于是我们知道 $\dfrac xk\le q=5\times10^5$，即 $k\geq \dfrac{x}{5\times10^5}$，另外我们知道 $k\mid x$，假如 $x$ 有约数 $d$，则 $x$ 也有约数 $\dfrac xd$，于是 $k$ 的个数不会超过 $x$ 在 $[1,5\times10^5]$ 中的约数个数，我认为这个数应该不会特别大，但是这玩意不太好验证的样子，但感性上差不多是正确的，而且这个上界非常松。
另一种说法是加入 $1,2,3,\dots$ 是最劣的情况，然后断言这个题的复杂度是 $O(n\log^2 n)$，我不是很懂。
说实话这个题我没有找到非常严谨的证明，目前只能到这个程度。
Code
#define int long long
namespace Main{
const int N = 200005;
int q, cnt;
map<int, bool> vis;
map<int, int> ans;
map<int, set<int>> app, del;
void Main(){
vis[0] = true;
input(q);
while(q--){
char ch; ll x;
cin >> ch, input(x);
if(ch == '+'){
vis[x] = true;
for(int i: app[x]) del[i].erase(x);
}
else if(ch == '-'){
vis[x] = false;
for(int i: app[x]) del[i].insert(x);
}
else{
if(del[x].size()){
write(*del[x].begin());
puts("");
continue;
}
int &res = ans[x];
while(vis[res*x]) res++, app[res*x].insert(x);
write(res * x);
puts("");
}
}
return;
}
} // namespace
#undef intE. Location
分块，设块长为 $B$，块数为 $\dfrac nB$。
散块的可以暴力求答案暴力更新，这个不必多说，问题在于如何实现整块的 $O(1)$ 修改与查询。
值域很小，我们考虑对整块预处理出 $ans_x$ 表示将 $a_i$ 推平为 $x$ 时的答案，$x$ 取遍值域。
$\dfrac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}$ 可以被写成 $\dfrac{a_i\times b_i}{\gcd^2(a_i, b_i)}$，$\gcd$ 枚举起来很困难，但是假如我们只是枚举 $a_i,b_i$ 的公因数，这样同样能够求出正确答案，因为非 $\gcd$ 的公因数会让答案更劣。
于是，对于每个 $x$，我们枚举 $x$ 的约数 $d$，接下来只需要找满足 $d\mid b_i$ 最小的 $b_i$ 即可，我们可以提前预处理 $mn_d$ 表示这个值。
$mn_d$ 的预处理类似刷表法，复杂度为 $O(\sum d(b_i))$，这个东西的上界是 $O(B\sqrt V)$。
接下来计算 $ans_x$，我们会遍历值域枚举每个数的约数，经过计算，所有数的约数个数总和大概是 $5\times10^5$。
预处理部分的总复杂度可以粗略看作是 $O(n\sqrt V)$。
剩下的，每次修改和查询如何处理整块与散块就很常规了，不必多说。
如果忽略 $\gcd$，我们的总复杂度是 $O\left(n\sqrt V+q\left(B+\dfrac nB\right)\right)$，$B=\sqrt n$ 时最优。
如果你实现优秀可以通过本题，如果你像我一样常数巨大，那么就需要 $O(1) \gcd$ 的科技，这样可以稳过本题，完全不需要卡常。
Code
namespace Main{
const int N = 50005;
const int B = 300;
const int inf = UINT32_MAX;
int n, q, a[N], b[N], bel[N], blocks, L[B], R[B], mn[N], ans[B][N], val[B], tag[B];
vector<int> d[N];
void fac(){
for(int i = 1; i < N; i++){
for(int j = 1; j * j <= i; j++){
if(i % j == 0){
d[i].push_back(j);
if(j * j != i) d[i].push_back(i / j);
}
}
}
}
void pre(){
for(int i = 0; i < blocks; i++){
for(int j = 1; j < N; j++) mn[j] = inf;
for(int j = L[i]; j <= R[i]; j++){
for(int x: d[b[j]]) mn[x] = min(mn[x], b[j]);
}
for(int j = 1; j < N; j++){
ans[i][j] = inf;
for(int x: d[j]){
if(mn[x] != inf) ans[i][j] = min(ans[i][j], j * mn[x] / x / x);
}
}
}
}
void pushdown(int p){
if(tag[p]){
for(int i = L[p]; i <= R[p]; i++) a[i] = tag[p];
tag[p] = 0;
}
}
int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x % y);
}
int getval(int x, int y){
int t = GCD::gcd(x, y); // O(1) gcd
return x * y / t / t;
}
void modify(int l, int r, int x){
assert(bel[l] == bel[r]);
pushdown(bel[l]);
for(int i = l; i <= r; i++) a[i] = x;
val[bel[l]] = inf;
for(int i = L[bel[l]]; i <= R[bel[l]]; i++) val[bel[l]] = min(val[bel[l]], getval(a[i], b[i]));
}
void Main(){
input(n, q);
for(int i = 1; i <= n; i++) input(a[i]);
for(int i = 1; i <= n; i++) input(b[i]);
blocks = (n - 1) / B + 1;
for(int i = 0; i < blocks; i++){
L[i] = i * B + 1;
R[i] = min(n, (i + 1) * B);
for(int j = L[i]; j <= R[i]; j++){
bel[j] = i;
}
}
fac(); pre();
for(int i = 0; i < blocks; i++) val[i] = inf;
for(int i = 1; i <= n; i++) val[bel[i]] = min(val[bel[i]], getval(a[i], b[i]));
while(q--){
int op;
input(op);
if(op == 1){
int l, r, x;
input(l, r, x);
if(bel[l] == bel[r]) modify(l, r, x);
else{
modify(l, R[bel[l]], x);
modify(L[bel[r]], r, x);
for(int i = bel[l] + 1; i < bel[r]; i++){
tag[i] = x;
val[i] = ans[i][x];
}
}
}
else{
int l, r, res = inf;
input(l, r);
if(bel[l] == bel[r]){
pushdown(bel[l]);
for(int i = l; i <= r; i++) res = min(res, getval(a[i], b[i]));
}
else{
pushdown(bel[l]), pushdown(bel[r]);
for(int i = l; i <= R[bel[l]]; i++) res = min(res, getval(a[i], b[i]));
for(int i = L[bel[r]]; i <= r; i++) res = min(res, getval(a[i], b[i]));
for(int i = bel[l] + 1; i < bel[r]; i++){
res = min(res, val[i]);
}
}
write(res), puts("");
}
}
return;
}
} // namespace
Data Generator
import random
with open("in", "w") as file:
file.write("50000 50000\n")
for i in range(0, 50000):
file.write(str(random.randint(1, 50000)) + " ")
file.write("\n")
for i in range(0, 50000):
file.write(str(random.randint(1, 50000)) + " ")
file.write("\n")
for i in range(0, 50000):
l = random.randint(1, 50000)
r = random.randint(l, 50000)
if random.randint(1, 2) == 1:
file.write("1 " + str(l) + " " + str(r) + " " + str(random.randint(1, 50000)))
else:
file.write("2 " + str(l) + " " + str(r))
file.write("\n")本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
