ytez黄sir模拟赛

做法很简单直接维护单调队列,找到每个元素的前一个和后一个大于他的即可

考场上写了 $O(n)O(1)rmq$

我会推式子！(下文用 $(i,j)$ 代表 $\gcd(i,j)$ ，用 $[i,j]$ 代表 $lcm (i,j)$ ，默认 $n\leq m$ ，除法下取整)

\prod _{i=1}^n \prod_{j=1}^m [i,j]^{[i,j]} = \prod _{i=1}^n \prod_{j=1}^m(\frac{ij}{(i,j)}) ^{\frac{ij}{(i,j)}} =\prod_{g=1}^n \prod _{i=1}^n \prod_{j=1}^m(\frac{ij}{g^2}\times g) ^{\frac{ij}{g^2} \times g\times \epsilon((i,j)=g)}

令 $i = i/g,j=j/g$ ，变为枚举 $i,j$ 是 $g$ 的多少倍，再化掉元函数：

=\prod_{g=1}^n\prod_{i=1}^{n/g}\prod_{j=1}^{m/g} (ijg)^{(ijg)\epsilon((i,j)=1)} =\prod_{g=1}^n\prod_{i=1}^{n/g}\prod_{j=1}^{m/g} (ijg)^{(ijg)\sum_{k|(i,j)} \mu(k)} =\prod_{g=1}^n\prod_{i=1}^{n/g}\prod_{j=1}^{m/g}\prod_{k|(i,j)} (ijg)^{(ijg)\mu(k)}

注意说这个西格玛可以放下去

令现在的 $i = i/k,j=j/k$

=\prod_{g=1}^n\prod_{k =1} ^{n/g} \prod_{i=1}^{n/gk}\prod_{j=1}^{m/gk} (ijgk^2)^{(ijgk^2)\mu(k)} =\prod_{g=1}^n\prod_{k =1} ^{n/g} (\prod_{i=1}^{n/gk}\prod_{j=1}^{m/gk} {(ij)^{(ij)}})^{gk^2\mu(k)} \times \prod_{g=1}^n\prod_{k =1} ^{n/g}(gk^2)^{\mu(k)gk^2 \times \sum_{i=1}^{n/gk}\sum_{j=1}^{m/gk}ij}

是不是有些端倪了……我们令 $f(n,m)=\prod_{i=1}^n\prod_{j=1}^m (ij)^{ij} , S(n)=\sum_{i=1}^n i$ ，再令 $T=gk$ 枚举

左半边=\prod_{g=1}^n \prod_{k=1}^{n/g} f(n/gk,m/gk)^{gk^2\mu(k)} =\prod_{T=1}^n f(n/T,m/T)^{\sum_{k|T}k^2\mu(k)\frac{T}{k}} =\prod_{T=1}^n f(n/T,m/T)^{T\sum_{k|T}k\mu(k)}

右半边=\prod_{g=1}^n \prod_{k=1}^{n/g} (k^2)^{gk^2\mu(k)S(n/gk)S(m/gk)} \times \prod_{g=1}^n \prod_{k=1}^{n/g} (g^g)^{k^2\mu(k)S(n/gk)S(m/gk)} \\ =\prod_{T=1}^n\prod_{k|T} ((k)^{T2k\mu(k)})^{S(n/T)S(m/T)} \times \prod_{T=1}^n\prod_{k|T} ((\frac{T}{k})^{Tk\mu(k)})^{S(n/T)S(m/T)} \\ =\prod_{T=1}^n\prod_{k|T} (k^{Tk\mu(k)})^{S(n/T)S(m/T)} \times \prod_{T=1}^n\prod_{k|T} (T^{Tk\mu(k)})^{S(n/T)S(m/T)}

令 $L(T) =T\sum_{k|T}k\mu(k) ,G(T)=\prod_{k|T} k^{k\mu(k)}$ 其中第二个到第三个是把k乘过去了

左半边=\prod_{T=1}^n f(n/T,m/T)^{L(T)} ;右半边=\prod_{T=1}^n (T^{L(T)} \times G(T)^T)^{S(n/T)S(m/T)}

$f(n,m) = (\prod_{i=1}^n i^i)^{S(m)} (\prod_{i=1}^m i^i)^{S(n)}$ ，可通过 $O(n\log n)$ 预处理 $\prod_{i=1}^n i^i$ 再每次查询时做快速幂求得。

$L,G$ 都可以 $O(n \ln n)$ 枚举约数算得，然后再处理 $T^{L(T)} ,L(T)^T$ 的前缀积和 $L(T)$ 的前缀和，就可以数论分块解决啦。时间复杂度 $O(n\log n+T\sqrt n \log \bmod)$ ，期望得分 100pts

询问两个会有 $m-x_i-x_j-(i,j)$ , $(i,j)$ 表示i,j之间逆序对数

观察有

$\sum_{i}query(i,j)=2m+(n-3)x_i$

然后直接做就好了,有了 $x_i$ 就可以会知道 $(i,j)$ 是不是逆序对,就能得到i的排名了

但是我们也有一个叫做归并排序的方法,可以在 $nlogn$ 次逆序对关系得出答案

然后考虑优化,我们可以考虑怎么快速查询i位置的答案

先查询得到 $x_1,x_n$ 的取值,这里我们直接查询 $O(2n-2)$

然后可以直接得到每个的信息

询问1,i,n

你会发现

只有1,i为逆序对或者i,n为逆序对,或者1,i,n没有逆序对

两个信息求和有 $2x_i$

但是可能因为上述情况出现奇数,我们+1/2即可得到 $x_i$

然后我们就有每个 $x_i$

调用归并排序,就是类似得到每个位置逆序对,还原原来序列即可

夏晓光(loveJY)的博客