Codeforces [Gym 102354B] Yet Another Convolution

> 给出两个长为 $n$ 的序列 $\{a_n\}$ 和 $\{b_n\}$ 。对于所有的 $k\in[1,n]\cap\mathbb Z_{+}$ ，求这样的 $c_k$： $$ c_k=\max_{\gcd(i,j)=k}\{a_i-b_j\} $$ > $1\leq n\leq 10^5$ 题目来源于 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 。 发现这题居然还是那一场通过人数最多的题目之一…深深地感觉到了自己的弱小。 然后正片部分。考虑这个式子可以怎么化，发现对于一个给定的 $k$ ，要找的 $a_i$ 和 $b_i$ 应该至少是这样的： $$ a_k,a_{2k},a_{3k}\cdots a_{pk} $$ $$ b_k,b_{2k},b_{3k}\cdots b_{pk} $$ 于是直接把这些拿出来重编号为 $1,2,3\cdots p$。那么为了保证 $\gcd(i,j)=k$，就需要满足取出的一个 `pair` 满足 $\gcd(i,j)=1$ 。也就是现在转化成了这么一个问题： $$ \max_{i=1}^p\{(a_i-b_j)[(i,j)=1]\} $$ 也就是 $$ \max_{i=1}^p\{a_i-\min_{j=1}^p\{b_j\cdot[(i,j)=1]\}\} $$ 然后似乎就没法做了。发现本题要求 $poly(\log)$ 的做法，但是本质上对于每个 $k$ ，都有 $O(\frac{n}{k})$ 组询问，这个询问量是十分巨大的。于是考虑有没有什么可以一起处理全部询问的方法。发现似乎整体二分可行。 首先把里面的 $\min$ 通过将 $b$ 全部取反变成 $\max$： $$ \max_{i=1}^p\{a_i+\min_{j=1}^p\{-b_j\cdot[(i,j)=1]\}\} $$ 之后考虑整体二分。具体的来讲，先考虑一组询问（即一个固定的 $i$）怎么二分。对于一个 $\min_{j=1}^p\{b_j\cdot[(i,j)=1]\}$ ，将其转化成判定性问题。假设当前二分到的值是 $ans$ ，那么考虑，如果 $\sum_{j=1}^p[ans<b_j][(i,j)=1] >0$，那就代表存在一个值比 $ans$ 大，符合二分性质。 那么对于这个 $\sum$ 而言，就可以变一下形了： $$ \sum_{j=1}^p[ans<b_j]\sum_{d|i\operatorname{and}d|j} \mu(d)>0 $$ 反演一下也就是 $$ \sum_{d|i} \mu(d)\sum_{d|j}^p[ans<b_j]>0 $$ 那么考虑整体二分的时候，对于每一层都可以把 $<vmid$ 的位置赋为 $1$ ，或者反过来，本质都一样。之后就只需要查询某个 $i$ 的上式值。发现这东西需要维护每个值的倍数处的值（后一个 $\sum$），并且不是很好清空。于是考虑一个有趣的做法。假设以把 $>vmid$ 的位置都赋值为 $1$ 做例子。每次手动将一个指针移动 $vmid+1$ 处，然后对于途径的所有 $b_j$，如果 $>vmid$ 的话就 $+1$ ，否则 $-1$ 。这样做之后，**直接把自己的标记下传给所有自己的约数**。这样最后去 $check(i)$ 的时候就可以直接枚举所有约数而不需要再去枚举约数的倍数。发现移动指针每层都是 $O(r-l)$ 的。 于是最后考虑算一下复杂度。大概是： $$ \sum _{i=1}^n(\frac{n}{i} \log \frac{n}{i} d(\frac{n}{i})) $$ 的复杂度。emmm，这大概是个什么复杂度呢…考虑 $d(n)<O(\sqrt[3]n)$ ，所以最后应该不会超过 $(n\log n)^{\frac{4}{3}}\log n$ 后面一个 $\log$ 是因为： $$ \int \frac{n}{x} \log \left(\frac{n}{x}\right) \mathrm{dx}=-\frac{n(\log x)^{2}-2 n \log n \log x+n(\log n)^{2}}{2} $$ 似乎是因为 $\log (\frac{n}{x})<0$ 的问题，所以需要忽略掉符号。最后大概也就是 $n\log^2 n$ 的级别。 然而实际积分出来也差不多？ $$ \int \frac{n^{\frac{4}{3}} \log \left(\frac{n}{x}\right)}{x^{\frac{4}{3}}} \mathrm{d x}=\frac{n^{\frac{1}{3}}(3 n \log x-3 n \log n+9 n)}{x^{\frac{1}{3}}} $$ 看上去就是 $(n\log n)^{\frac{4}{3}}\log n$ 的亚子。不过话说回来 $d(n)=O(\sqrt[3] n)$ 的近似误差有、大，所以还是 $O($能过$)$ 比较靠谱.jpg 。 ```cpp #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std ; const int N = 300010 ; #define p_b push_back #define upb upper_bound void debug(int *tp, int minn, int maxn, char c){ for (int i = minn ; i <= maxn ; ++ i) cout << tp[i] << " " ; cout << c ; } int n ; int xq ; int cnt ; int q[N] ; int A[N] ; int B[N] ; int lq[N] ; int rq[N] ; int pr[N] ; int ta[N] ; int tb[N] ; int Mu[N] ; int sum[N] ; int res[N] ; int ans[N] ; int tmp[N] ; int base[N] ; bool vis[N] ; vector <int> d[N] ; void add(int x, int y){ int p = d[x].size() ; for (int i = 0 ; i < p ; ++ i) sum[d[x][i]] += y ; return ; } void upd(int x){ while (xq > x) add(base[-- xq], 1) ; while (x > xq) add(base[xq ++], -1) ; //debug(sum, 1, 50, '\n') ; } int calc(int x){ int ret = 0 ; int p = d[x].size() ; for (int i = 0 ; i < p ; ++ i) ret += Mu[d[x][i]] * sum[d[x][i]] ; return ret ; } void do_it(int l, int r, int vl, int vr){ if (l > r) return ; if (vl == vr){ for (int i = l ; i <= r ; ++ i) ans[q[i]] = vl ; return void() ; } int vmid = (vl + vr) >> 1 ; int tl = 0, tr = 0 ; upd(vmid + 1) ; for (int i = l ; i <= r ; ++ i){ if (calc(q[i]) <= 0) lq[++ tl] = q[i] ; else rq[++ tr] = q[i] ; } //cout << tl << " " << tr << endl ; for (int i = 1 ; i <= tl ; ++ i) q[l + i - 1] = lq[i] ; for (int i = 1 ; i <= tr ; ++ i) q[l + tl + i - 1] = rq[i] ; do_it(l, l + tl - 1, vl, vmid) ; do_it(l + tl, r, vmid + 1, vr) ; } int do_do(int k){ for (int i = 1 ; i <= k ; ++ i) tmp[q[i] = i] = tb[i], sum[i] = 0 ; sort(tmp + 1, tmp + k + 1) ; int x ; xq = k + 1 ; for (int i = 1 ; i <= k ; ++ i){ x = upb(tmp + 1, tmp + k + 1, tb[i]) - tmp ; x -- ; base[x] = i ; tmp[x] ++ ; } int ret = -2333333 ; do_it(1, k, 1, k) ; //debug(q, 1, k, '\n') ; for (int i = 1 ; i <= k ; ++ i) ret = max(ret, ta[i] + tmp[ans[i]] - 1) ; return ret ; } void solve(){ for (int i = 1 ; i <= n ; ++ i){ for (int j = 1 ; i * j <= n ; ++ j) ta[j] = A[i * j], tb[j] = B[i * j] ; res[i] = max(res[i], do_do(n / i)) ; } } void sieve(int k){ vis[0] = vis[1] = Mu[1] = 1 ; for (int i = 2 ; i <= k ; ++ i){ if (!vis[i]) pr[++ cnt] = i, Mu[i] = -1 ; for (int j = 1 ; j <= cnt ; ++ j){ if (pr[j] * i > k) break ; vis[i * pr[j]] = 1 ; if (i % pr[j] == 0) break ; Mu[i * pr[j]] = - Mu[i] ; } } for (int i = 1 ; i <= k ; ++ i) for (int j = 1 ; i * j <= k ; ++ j) d[i * j].p_b(i) ; } int main(){ sieve(N - 10) ; ios :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ; cin >> n ; for (int i = 1 ; i <= n ; ++ i) cin >> A[i] ; for (int i = 1 ; i <= n ; ++ i) cin >> B[i] ; for (int i = 1 ; i <= n ; ++ i) B[i] = -B[i] ; solve() ; //for (int i = 1 ; i <= n ; ++ i) // cout << res[i] << " \n"[i == n] ; for (int i = 1 ; i <= n ; ++ i) A[i] = -A[i], B[i] = -B[i] ; solve() ; for (int i = 1 ; i <= n ; ++ i) cout << res[i] << " \n"[i == n] ; return 0 ; } ```