RT

请各位医务人员以国家利益、人民健康为重，错峰感染、有序阳性。

尊敬的国际社会朋友：

我们注意到近期 QOJ 平台尚未上传CTT 2022的题目，对此我们表示深切关切并强烈谴责。

CTT，作为全球影响力极大的竞赛，其题目的发布与分享在推动全球计算机科技领域的发展、增进各国间的科技交流、以及提升全球公众对此领域的理解与认知等方面，起着至关重要的作用。我们坚决支持全球公开、透明、公平的科技竞赛环境，反对任何形式的不公平、非透明行为。

我们注意到，QOJ 平台尚未上传 CTT 2022 题目，这一行为严重损害了国际计算科学领域的公平竞争环境，制约了全球计算机科技领域的进步，也伤害了广大计算机科学爱好者的学习和交流权益。

对此，我们强烈谴责 QOJ 平台此次行为，并正式要求 QOJ 平台立即纠正错误，尽快上传 CTT 2022 题目，恢复全球计算机科技领域的公平、开放和合作。

我们呼吁全球各界人士一同关注并促进全球计算机科学领域的发展，共同维护公开、公正的竞赛环境。我们坚信，只有每一个科技爱好者都能公平参与到科技竞赛中，全球的科技发展才能更加健康、公正、和谐。

QOJ 博客必须开始魔怔！！

T1

额外数据范围：另外20%的数据，n,q<=100000。

题意：给一个数列a[i]，每时每刻在[0,1]，要求支持区间乘法，询问区间(1-a[i])之积。

对于a[i]<=0.4，我们可以考虑询问区间ln(1-a[i])之和，然后再exp一下。

把ln(1-x)在x=0处泰勒展开，可以发现$ln(1-x)=-\sum_{i=1}^{\infty} x^i/i$。

对于x<=0.4这个精度还是很好的，大概展开24项左右就可以达到1e-11的精度。

对于a[i]>0.4，我们考虑把区间里所有>0.4的a[i]拎出来，把1-a[i]暴力乘到答案上。$0.6^{28} < 10^{-6}$，所以如果有28个这样的a[i]我们直接输出0即可。

实际维护的时候需要拿个线段树维护<=0.4的1次幂到24次幂之和以及大于0.4的最小a[i]。每次乘上一个数之后如果有原来大于0.4的现在小于了就维护一下。

T2

额外数据范围：对70%的数据，n<=1000，字符串随机。

题意：给两个随机的字符集为4的序列A和B，求最长公共循环同构子序列。

这是一个很正常的序列题。

正经平方做法1：把A扩展成A[1]A[2]…A[n]A[1]A[2]…A[n]，你要求的就是A的每个长度为n的子串与B的LCS的最大值。大力跑个all-substring-lcs即可，参见51nod 1825。

正经平方做法2：类似做法1，但是每次取LCS字典序最小的转移序列，然后每次扩展一下，参见lcs2.cpp和https://arxiv.org/pdf/1208.0396v3.pdf。

还有一种常数比较小的三方乱搞做法也可以通过，大概就是LCS的时候忽略|i-j|>200的下标，然后找分割点的时候可以用当前答案剪枝，见lcs3.cpp。

T3

额外数据范围：对50%的数据，s<=1000。对70%的数据，s<=10000。对80%的数据，s<=100000。

首先，合法区间长度的级别是啥？

我们考虑一个长度为$10^p$的区间的后p位一定是$000000$到$999999$，和是$45p*10^{p-1}$。

p=5时这个值为2250000，那么区间长度就不超过$10^5$。

假设长度不超过$10^p$，那么最高位只有两种可能对吧。

考虑枚举左右端点在$\bmod10^p$ 意义下的值。那么长度已然确定，不同的就是前面位的那个bound。

先考虑左$\bmod 10^p=L$ ，右$\bmod~10^p=R$，$L \leq R$，那么设$ n \bmod 10^p=Q$。

那么如果$R \leq Q$，那么设每个数/10^p=a，只要$a \leq n/10^p$且$sd(a)(R-L+1)+\sum_{i=L}^R sd(i) \leq lim$即可。

目测一下枚举了sd(a)之后枚举R一下就可以two-pointer了。

如果$R >Q$，要求变成了$a < n/10^p$，其他不变。

如果$L>R$，$R \leq Q$，那么设前一半的数/10^p=a，只要$a+1 \leq n/10^p$且$sd(a)(10^p-L)+sd(a+1)(R+1)+\sum_{i=L}^{10^p-1} sd(i)+\sum_{i=0}^R sd(i) \leq lim$。$(sd(a),sd(a+1))$的个数是$O(log^2)$的（只与$sd(a)$和进了几位有关）。我们从小到大枚举R之后two-pointer即可。由于这部分复杂度比较大，可以加上适当的剪枝。

$R>Q$也是变成了$a+1 < n/10^p$。

一开始我们需要求出对于$a \leq $ 某个值，每个$sd(a)$和每个$(sd(a),sd(a+1))$的出现次数，sd(a)直接数位dp的时候记就行，$(sd(a),sd(a+1))$的话，记一下a的最后有几个9即可。这部分dp复杂度是$O(\log^3(n))$的。

最后的复杂度是$O(\log^2(n)s)$。由于常数很小所以可以通过。此外还存在一些复杂度相同但是常数更小的做法。