[atARC126F]Affine Sort
记$g(k)$为$c$恰为$k$的合法三元组数，显然$f(k)=\sum_{i=1}^{k}g(i)$
结论：若$\lim_{k\rightarrow \infty}\frac{g(k)}{k^{2}}$存在，记其为$s$，则$\lim_{k\rightarrow \infty}\frac{f(k)}{k^{3}}=\frac{1}{3}s$
任取正实数$\epsilon$，根据极限的定义$\exists k_{0}\ge 1$，满足$\forall k\ge k_{0},s-\epsilon\le \frac{g(k)}{k^{2}}\le s+\epsilon$
对其求和并简单变形，不难得到$s-\epsilon\le \frac{\sum_{i=k_{0}}^{k}g(i)}{\sum_{i=k_{0}}^{k}i^2}\le s+\epsilon$
当$k\rightarrow\infty$时，显然中间的式子可以看作$\frac{f(k)}{\frac{1}{3}k^{3}}$，即得证
由此，不妨考虑如何求出$s$，进行如下构造：
定义$[x]$为$x$的小数部分，即$[x]=x-\lfloor x\rfloor$（这里$\lfloor x\rfloor$为小于等于$x$的最大整数）
注意到$x\ mod\ c 考虑$\alpha$和$\beta$，由于$c(=k)\rightarrow \infty$，因此$a,b\in [0,c)$可以看作$\alpha$和$\beta$在$[0,1)$内均匀分布 记$D=\{(\alpha,\beta)\mid \alpha,\beta\in [0,1)$且$[\alpha X_{1}+\beta]<[\alpha X_{2}+\beta]<...<[\alpha X_{n}+\beta]\}$，不妨考虑将$D$中的点都染上黑色，此时问题即求黑色部分的面积 将$[0,1)$看成一个圆（顺时针方向为增大），并定义$f_{i}(\alpha)$为$[\alpha X_{i}]$到$[\alpha X_{i+1}]$在圆上顺时针方向的距离，那么不难得到$f_{i}(\alpha)=[(X_{i+1}-X_{i})\alpha]$（特别的，定义$X_{n+1}=X_{1}$） 对于$\alpha\in [0,1)$，$\exists \beta\in [0,1),(\alpha,\beta)\in D$的必要条件为$\sum_{i=1}^{n}f_{i}(\alpha)=1$（感性理解，即至多只能转一圈） 进一步的，若$\alpha$满足此条件，那么$(\alpha,\beta)\in D$当且仅当$[\alpha X_{1}+\beta]<[\alpha X_{n}+\beta]$（结合前者显然），进而不难得到$\alpha$所在列上黑色部分的长度即为$[(X_{1}-X_{n})\alpha]$ 事实上，这里并没有考虑$[\alpha X_{i}+\beta]=[\alpha X_{i+1}+\beta]$的情况，但显然线段并不影响面积 枚举$\lfloor (X_{i+1}-X_{i})\alpha\rfloor$，即将$[0,1)$划分为$o(|X_{i+1}-X_{i}|)$段，每一段的$f_{i}(\alpha)$都是关于$\alpha$的一次函数，那么考虑$\sum_{i=1}^{n}f_{i}(\alpha)$即是一个$o(\sum_{i=1}^{n}|X_{i+1}-X_{i}|)$段的一次函数 对于其中一段，若其截距为1（不难发现斜率必然为0），那么即对$[(X_{1}-X_{n})\alpha]$求一个区间定积分，将其的端点也加入后同样变为一次函数，直接计算即可 时间复杂度为$o(S\log S)$（其中$S=\sum_{i=1}^{n}X_{i}$），可以通过 1 #include