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)$。由于常数很小所以可以通过。此外还存在一些复杂度相同但是常数更小的做法。

A

原本两维息息相关，相当麻烦，容易想到转$45$度坐标，可以使得两维独立。

那么原本$x^ny^m$会变成$(\frac{x+y}{2})^n(\frac{x-y}{2})^m$。

可以用二项式展开真正使得两维独立，接下来需要解决的是求$E(a^k)$。

可以简单设一个dp。

用$F_{i,j}$表示$i$步后$E(a^j)$是多少，同样用二项式展开可以得到转移式。

把转移写成矩阵，可以使用矩阵乘法。

复杂度$O((n+m)^3\ log\ t)$。

计算$F_{i,j}$的过程可以不用矩阵乘法。

注意到转移过程中$j$减少的次数不超过$n$次，那么记$g_{i,j}$表示经过$i$次减少量至少为$1$的转移，总的变化是$j$的所有转移的系数乘积和。

对于减少量为$0$的转移，$F_{i,j}$会对$F_{i+1,j}$产生$2F_{i,j}$的贡献。

所以，最终的和就是$\sum \limits_{i=0}^n\binom t i \times \sum\limits_{j=0}^n g_{i,j}\times x^j\times 2^{t-i}$。

复杂度$O((n+m)^3)$。

B

不妨让我们先换一种方式描述积和式。

一个边权二分图，一个完美匹配的贡献为匹配边边权的乘积。

求所有完美匹配贡献的和。

接下来我们认为矩阵上不为$1$的位置对应的就是一条关键边。

假设$S$是一个关键边集,任意两条属于边集的边没有相同的端点。

令$f(S)$表示有多少种完美匹配方案恰好只包含边集$S$，也就是不包含多余的关建边。

令$g(S)$表示有多少种完美匹配方案包含边集$S$，显然$g(S)=(n-|S|)!$。

定义$v(S)$表示边集$S$内所有边边权的乘积。$w_e$来表示边$e$的权值。

首先显然$g(S)=\sum_{S\subset T}f(T)$

则显然有$f(S)=\sum_{S\subset T}g(T)*(-1)^{|T|-|S|}$

我们再来写出答案的式子。

$\sum_{S}v(S)*f(S)$

$\sum_{S}v(S)\sum_{S\subset T}g(T)*(-1)^{|T|-|S|}$

$\sum_{T}g(T)\sum_{S\subset T}v(S)*(-1)^{|T|-|S|}$

整理一下式子可以发现答案的表达。

$\sum_{S}(n-|S|)!\prod_{e\in S}(w_e-1)$。

因此我们可以把所有边权减一，那么问题变成计算对于每个$k$，任选$k$条不相交的关键边边权乘积和是多少。

首先显然可以将联通块分开独立来做，最后再背包在一起。

假设一个联通块点数为$n$，边数为$m$，因为是二分图，其中一边一定有不超过$\frac{n}{2}$个点。

可以将小的一边状压，假设小的一边是Y部。

设$f_{i,s}$表示做到X部的第$i$个点，目前对于一端在X部的前$i$个点的关键边，我们选择了一些，它们没有相同的另一端并覆盖了$s$这个状态，边权积的和是多少。

转移只需要枚举当前点的一条边即可。

复杂度为$O(m*2^{\frac{n}{2}})$，即$O(n^2*2^{\frac{n}{2}})$。

考虑对图做出任意一颗生成树。

对于非树边，我们暴力枚举其选或不选。

对于生成树的部分，我们设$dp_{x,i,0/1}$表示$x$子树内已经做完，一共选了$i$条关键边，目前$x$的匹配状态是什么。

合并时需要枚举两个子树的第二维，枚举上界显然不会超过子树的大小。

如果这样枚举，复杂度实际只有$n^2$，可以发现任意两个点都会在lca处被计算一次。

那么我们的复杂度为$O(n^2*2^{m-n+1})$

对于每个联通块，我们只需要选择复杂度小的算法即可。

最终复杂度为$O(n^2*2^{\frac{m}{3}})$。

C

首先$A$与$B$两维顺序没有关系，我们默认$A\geq B$。

我们来尝试写出一个式子。首先肯定开始飞了之后就不会正常驾驶，容易想到枚举起飞位置。接下来是简单的鸽笼原理。

$\sum_{a=0}^A\sum_{b=0}^B\binom{a+b}{a}\sum_{x=1}^{min(A-a,B-b,C)}\binom{A-a-1}{x-1}\binom{B-b-1}{x-1}\binom{C-1}{x-1}$

$\sum_{i=0}^n\binom{a}{i}\binom{b}{n-i}=\binom{a+b}{n}$

从组合意义去理解，有$a+b$个格子，要求给$n$个格子染上黑色，求方案数。两个式子都能表达。

$\sum_{i=0}^n\binom{i}{a}\binom{n-i}{b}=\binom{n+1}{a+b+1}$

从组合意义去理解，有$n$个格子，要求给$a$个格子染上红色，给$b$个格子染上绿色，最后一个红色格子严格在最前一个绿色格子之前，同时还要选择一条分界线$i$，使得前$i$个格子只有红格子，后面只有绿格子。

不妨额外添加一个格子，同样要求给$a$个格子染红，$b$个格子染绿，还需要给一个格子染黄，规定一个格子只能染一种颜色。

要求黄格子前只有红格子，黄格子后只有绿格子。显然每一种新问题的染色方案对应原问题一种方案。

根据我们得出的答案的表达式，不妨先将$A,B,C$都减一，接下来设$up$表示$min(A,B,C)$。

为了方便对比，先贴出答案表达式。

$\sum_{a=0}^A\sum_{b=0}^B\binom{a+b}{a}\sum_{x=1}^{min(A-a,B-b,C)}\binom{A-a-1}{x-1}\binom{B-b-1}{x-1}\binom{C-1}{x-1}$

接下来用$x$代替原来的$x-1$，$a$代替原来的$A-a$，$b$代替原来的$B-b$，同时我们已将$A,B,C$减一。

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\sum_{b=0}^B\binom{b}{x}\binom{A+B-a-b}{A-a}$

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\sum_{b=0}^B\binom{b}{x}\binom{A+B-a-b}{A-a}$

注意到$b>B$会让$\binom{A+B-a-b}{A-a}$值为$0$，因此我们可以抬高上界。

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\sum_{b=0}^{A+B-a}\binom{b}{x}\binom{A+B-a-b}{A-a}$

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\binom{A+B-a+1}{A-a+x+1}$

使用之前基础知识提到的可以变换成这条式子。

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\binom{A+B-a+1}{A-a+x+1}$

$\sum_{x=0}^{up}\binom{C}{x}(\sum_{a=0}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{A-a+x+1}-\sum_{a=A+1}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{A-a+x+1})$

$\sum_{x=0}^{up}\binom{C}{x}(\sum_{a=0}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{B-x}-\sum_{a=A+1}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{A-a+x+1})$

前面部分可以使用基础知识提到的等式，后面部分我们改枚举$a-(A+1)$。

$\sum_{x=0}^{up}\binom{C}{x}(\binom{A+B+2}{B+1}-\sum_{a=0}^{B}\binom{a+A+1}{x}\binom{B-a}{x-a})$

容易发现$up,B\leq 10^6$，因此前面部分已经可以快速计算，接下来我们只考虑后面部分。

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^{B}\binom{a+A+1}{x}\binom{B-a}{x-a}$

我们用基础知识介绍的等式拆开组合数。

$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^{B}\binom{B-a}{x-a}\sum_{i=0}^x\binom{A+1}{i}\binom{a}{x-i}$

$\sum_{x=0}^{up}\binom{C}{x}\sum_{i=0}^x\binom{A+1}{i}\sum_{a=0}^{B}\binom{B-a}{x-a}\binom{a}{x-i}$

$\sum_{x=0}^{up}\binom{C}{x}\sum_{i=0}^x\binom{A+1}{i}\sum_{a=0}^{B}\binom{B-a}{B-x}\binom{a}{x-i}$

$\sum_{x=0}^{up}\binom{C}{x}\sum_{i=0}^x\binom{A+1}{i}\binom{B+1}{B-i+1}$

$\sum_{i=0}^{up}\binom{A+1}{i}\binom{B+1}{B-i+1}\sum_{x=i}^{up}\binom{C}{x}$

后面部分可以预处理后缀和，那么这个式子也可以快速计算。

环

我们不妨考虑按$0-n$顺序的前缀和，记作数组$D$。于是$D[i]$就表示环上按顺时针方向从$0$号车站到$i$号车站的距离总和。为了后面方便的推导，我们再假设环的总长度（也就是答案）为X，于是便可得到如下的不等式约束（箭头后方是差分约束的标准形式）：

由于相邻车站之间的距离是正整数，所以有：

$$ D[i]+1\le D[i+1] \rightarrow D[i]-D[i+1]\le -1 $$

不难发现$D[0]=0,D[n]=X$，所以我们又可以得到以下式子：

$$ D[0]+X=D[n] \rightarrow D[0]-D[n]<=-X,D[n]-D[0]<=X $$

对于题目给的第一种条件，我们根据按照顺时针方向是否跨越过0号车站，分类讨论一下，也不难建立不等式关系：

$$ 1.S < T,D[T]-D[S]\ge L \rightarrow D[S]-D[T]\le -L $$

$$ 2.S>T,X+D[T]-D[S]\ge L \rightarrow D[S]-D[T]\le X-L $$

同理对于第二种条件，也可以获得以下不等式关系：

$$ 1.S < T,D[T]-D[S]\le L \rightarrow D[T]-D[S]\le L $$

$$ 2.S>T,X+D[T]-D[S]\le L \rightarrow D[T]-D[S]\le -X+L $$

这是一个经典的差分约束模型。所有不等式约束可以转化为图论中最短路的模型，如果出现负环则说明该不等式组无解。

在这道题中，我们由于设了一个未知数$X$，所以似乎无法直接求解。但是我们不难发现给定一个答案$X$，我们可以在转化的图上跑$bellman-ford$或者$spfa$来判断是否存在负环，从而判断该答案是否可行。但显然答案的范围可能很大，枚举验证的方法效率不高，我们不妨采用以下两种思路来解决问题。

不难发现最终的答案其实是在一个区间范围之内。于是我们如果设计出一个算法来判断一个不合法的X是低于下界还是高于上界，便可以进行二分求解出最终答案的区间。

对于一个不可行的答案，我们必然是可以在转化的图中找到一个负环的。于是我们不妨在求最短路的时候对于每一个值都记录下$X$的系数，那当我们找到一个负环的时候，我们也可以得到该负环数值中的X的系数。如果$X$的系数是正的话，那么显然我们只有将$X$调大，才能使该负环变成非负环，所以该X的值是低于答案的下界。同理，如果$X$的系数为负，可以得到该$X$高于答案的上界。值得注意的是，如果存在一个负环$X$的系数为$0$便会无解。

至此，我们可以使用二分算法，对上界和下界分别进行二分便可获得答案区间。时间复杂度为$O(nmlogn)$。

塔

我们注意到，一个方块的具体颜色对转移并没有太大影响，只要处理相邻颜色相同的就可以了（也可以理解为相对颜色）。

我们定义状态$dp_{i,k,a}$为高度为$i$，已经有$k$对相邻方块颜色相同，顶面相对颜色序列为$a$的方案数。

对于这里的序列$a$，我们以如下方法构造。先为顶层的方块编号，编号为$1$的方块的相对颜色定义为$1$。

然后以编号从小到大顺序枚举，如果当前方块的颜色在之前没有出现过，便将其编号为之前所有编号的最大值$+1$如果当前方块的具体颜色在以前出现过，就用以前出现的编号。

枚举最上面一层以及第二层的相对颜色，计算并更新相邻方块颜色相同的个数，直接叠加即可。

由于$H$过大，上文的算法显然会超时，因此我们要挖掘一些性质。

我们发现，转移方程是线性的，且$i$不会影响转移方程的形式。因此我们使用矩阵乘法+快速幂优化。

设$m=a的种类数\times(K+1)+1$。

我们可以构造$1\times m$矩阵$a$为每种状态初始的方案数，再定义$m\times m$矩阵$b$为动态规划中任意两种状态转移的常数，并用最后一个位置记录每一种高度的方案的和。

答案显然为$a\times b^h$的最后一项。

数

我们可以将题目中的要求转化为求$[1, T]$中满足$F(x) \equiv 0 \pmod{m}$的$x$个数。不难发现，$F(x) \mod{m}$仅与$x \mod{m}$和$k$的最大值有关，且假如$F(x) \equiv 0 \mod{m}$，那么就有$F(x + m) \equiv 0 \mod{m}$。因此，我们可以对所有的$x$按模$m$的余数进行分类，并计算出每一类$x$中满足条件的下界是多少，就能得到答案了。设这个下界为$A_m[]$。

此外，对于一组满足$(x, y) = 1$的$x$和$y$，不难利用$A_x[]$及$A_y[]$在$O(xy)$时间内构造出正确的$A_{xy}[]$。因此，现在的问题是，给定某个质数幂$p^c$，求出$A_{p^c}[]$的值。

考虑最直接的做法。对于每个$[0, p^c)$中的$i$，我们枚举$k$，计算出$i-k^2$中$p$的数量并累加，直到不少于$c$；$A_{p^c}[i]$就等于此时的$k^2 + 1$。由于$k$是$O(\sqrt{x})$的，总复杂度$O(m \sqrt{hi})$。

这样做的复杂度太高了，需要优化。注意到$c$的范围非常小，因此假如我们只枚举$i-k^2$中包含至少一个$p$的$i$和$k$，复杂度就会降低许多。因此，我们先枚举$k$，并维护一个$cnt[i]$表示到目前为止所有$i-k^2$中$p$的总个数；然后再枚举满足$i \equiv k^2 \mod{p}$的所有$i$，这样的$i$就只有$p^{c-1}$个了，单次求解的复杂度降至$O(p^{c-1} \sqrt{hi})$。

我们发现，每个$k$所影响的$i$以$p$为周期循环，$k$与$k+p$所影响的$i$是相同的；而每次每个受影响的$i$的$cnt[i]$至少会加一，因此有用的$k$只有$p*c$个。与算法二结合后，复杂度降至$O(p^{c-1} * p * c) = O(p^c * c)$，由于$c=O(\log m)$，总复杂度$O(m \log m)$，可以通过本题。

来自多校的测试包。

A

$1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=\frac{1}{3}+\frac{1}{3}+\frac{1}{3}=\frac{1}{2}+\frac{1}{4}+\frac{1}{4}$.

B

对于一个括号序列，令$n$是长度，$m$是前缀最小值('(' +1，')'-1)，$sum$是最后的和，那么答案就是$m-sum+2m$。现在这个$n$和sum都是定值，只要最大化$m$就好了。 每个串，把匹配后的搞掉之后，会得到一个pair ($a, b$)，表示$a$个左括号接上$b$个右括号，把($a,b$)按照一定顺序排一排依次接起来就知道$m$的最大值了。

C

求个凸包，然后选择凸包一条边$AB$，然后找个和$AB$夹角最小的点$C$，把$ABC$当做一个三角形删掉即可。这样做个$n$次，显然这样求出来的三角形们是合法的。

D

显然可以从左往右贪心，问题转化成求一个区间里的mex，由于区间左右端点都是递增的，用个set维护下即可。

E

一个显而易见的观察是：按照操作来可以很容易进行dp。于是只要还原出操作序列即可：每次选个度数为2的点删掉，然后加入一条虚边。 $dp(edge, x, y)$表示处理到$edge$这条边，这条边左端点匹配状态是$x$，右端点匹配状态是$y$的最大匹配和方案数。碰到重边的时候merge下即可。

F

考虑这个无限长的序列中相等的数$s_{i_1}, s_{i_2}, ..., s_{i_k}$，考虑$i_1 \bmod n, i_2 \bmod n, ..., i_k \bmod n$，这些构成了一条链。相邻两个位置有个$delta$，表示下一个相同位置在$delta$后。

然后考虑这些链，肯定是$s_i \bmod n$一样的数组成的。不妨$O(n^2)$枚举这个链的一部分，统计它的贡献。设距离上一个位置是$prev$，距离下一个位置是$next$，这时候会分成4种情况： + 这个prev and next都在$[a,b]$内：贡献是一个等差数列乘以若干常数 + prev部分在$[a,b]$里，next全在$[a,b]$内：贡献是两个等差数列相乘，然后乘以若干常数 + prev完全在$[a,b]$内，next部分在$[a,b]$内：贡献是两个等差数列相乘，然后乘以若干常数 + prev和next都部分在$[a,b]$内：贡献是三个等差数列相乘，然后乘以若干常数

具体等差数列就不列出来了，有std的参考std，没有的找有std的人要。

G

考虑这个数列的差分数列，除了个别项，本质就是：$1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0,...$。

可以观测到，这个序列可以这么生成：一开始只有一个$1$，$1$变成$110$，$0$保持不变。迭代无穷多次后就是这个差分序列。

知道差分序列，可以应用阿贝尔变换，把$a$的前缀和搞成差分序列相关。不妨令差分序列是$da$，那么$a$的前缀和$$s(n)=(n-1)\sum_{i=0}^{n-2}da(i) - \sum_{i=0}^{n-2}da(i)i + 1$$。

利用$da$的分形结构，很容易算出$s(n)$。

H

RMQ-Similar实际上就是$A$和$B$的笛卡尔树一样，这样我们就有了一个二叉树，然后可以在树上分析了。

考虑到$B$中有元素相同的概率是$0$，于是可以假设$B$里面元素互不相同，也就是说可以假定是一个排列。

显然，符合笛卡尔树的排列就是这个树的拓扑序列个数，就是$\frac{n!}{\prod size_i}$。然后显然每个排列期望的和是$\frac{n}{2}$，于是答案就是$\frac{n}{2\prod size_i}$。

I

这边有个简单的结论，考虑$s=w_1w_2...w_n$是$s$的lyndon factorization，那么$|w_i|$的最大值就是$s$的最长lyndon substring。证明略，想知道的私信我。

于是你只要会合并两个lyndon factorization就好了。这个是个经典问题，利用lyndon factorization的单调性，只要两个二分就搞定了。

J

考虑只有一个起点的时候应该怎么做。令起点在$p$，最左边的$1$在位置$s$，最右边的$1$在$t$，显然$p \to s \to t$或者$p \to t \to s$都是可以的，不妨只考虑$p \to s \to t$。

显然，先走到$s$，中间该取反的就取反，然后从$s$走到$t$，该取反的也取反，这些是要走的必要步数。考虑剩下来那些位置中$1$所在的位置为$i_1,i_2,...,i_m$.我们要把这些位置的状态搞对，那么考虑相邻两两配对，来回一趟就可以把这两个都搞定。如果位置是奇数个，最后还需要和$t$搞一下。可以证明这样是最优的。

这个过程很容易就可以推广到起点不定的情况，考虑起点$p$和$s$和$t$的位置关系。 + 如果$p \le s$，那么$p$和$s$之间每个位置在过完$p \to s \to t$后都是$1$，剩下部分是个定值，可以直接维护。 + 如果$s \le p \le t$，显然在$p$从$s$慢慢增加到$t$的时候，$1$位置的变换也是很好维护的 + 如果$p > t$，这个时候显然不如走$p \to t \to s$逻辑，所以可以在另一种情况下做。

K

转换成分钟，然后随便算算就好了。

RT

The European Commission has just announced an agreement whereby English will be the official language of the European Union rather than German, which was the other possibility.

As part of the negotiations, the British Government conceded that English spelling had some room for improvement and has accepted a 5- year phase-in plan that would become known as "Euro-English".

In the first year, "s" will replace the soft "c". Sertainly, this will make the sivil servants jump with joy. The hard "c" will be dropped in favour of "k". This should klear up konfusion, and keyboards kan have one less letter.

There will be growing publik enthusiasm in the sekond year when the troublesome "ph" will be replaced with "f". This will make words like fotograf 20% shorter.

In the 3rd year, publik akseptanse of the new spelling kan be expekted to reach the stage where more komplikated changes are possible.

Governments will enkourage the removal of double letters which have always ben a deterent to akurate speling.

Also, al wil agre that the horibl mes of the silent "e" in the languag is disgrasful and it should go away.

By the 4th yer people wil be reseptiv to steps such as replasing "th" with "z" and "w" with "v".

During ze fifz yer, ze unesesary "o" kan be dropd from vords kontaining "ou" and after ziz fifz yer, ve vil hav a reil sensi bl riten styl.

Zer vil be no mor trubl or difikultis and evrivun vil find it ezi TU understand ech oza. Ze drem of a united urop vil finali kum tru.