Codeforces Round #700 (Div.1)

上红成功。

A.Searching Local Minimum

题意：交互题，事先确定一个长度为$n$的排列，可以询问不超过$100$次某位置的值，最终给出一个位置，满足两边相邻的元素值（如果存在）都大于这一位置的元素。 $n\le {10}^5$

题解：小范围暴力。否则考虑询问$1,2,n-1,n$的位置，判断$1$和$n$位置是否满足条件。

如果都不满足条件，可以证明可以从中选出三个数$x,y,z$满足$x<y<z$且$a_x>a_y,a_z>a_y$。考虑不断缩小三元组的值的距离。迭代，取$y-x$和$z-y$中较大者，假设为$y-x$，那么询问$t=\lfloor \frac{x+y}{2}\rfloor$处的值，比较其和$a_y$的大小，$a_t<a_y$则$(x,y,z)\to (x,t,y)$，否则$(x,y,z)\to (t,y,z)$，可以证明这样迭代会以$O(\log n)$的复杂度得到符合条件的一个位置。

B1/B2.Painting the Array

题意：将长度为$n$的数组划分为两个数组，满足归并后为原数组，且两数组不同颜色连续段个数之和最大/最小。 $1\le n\le {10}^5$

题解：其实有一个统一的做法：暴力dp，设考虑前$i$个位置，两段末尾的颜色分别为$a$和$b$的答案的最大/最小值为$f_{i,a,b}$。由于第$i$个元素一定在某一个数组的末尾，因此其实颜色$a$是确定的，可以用一棵线段树维护以$b$为下标的$f_i$数组，转移到$i+1$，分为加入$a$之后和加入$b$之后讨论：如果加入$a$之后，$b$下标不变，若$i$与$i+1$颜色不同，数组全体增加$1$；如果加入$b$之后，一定更新下标为$i$的颜色的位置，讨论之前的$b$的颜色和$i+1$是否相同，分区间查询线段树的最值即可更新答案。总复杂度$O(n\log n)$。

C.Continuous City

题意：构造一张不超过$32$个点的正边权简单DAG，满足$1$到$n$长度为$x$的路径恰好有一条，$x=L,L+1,\dots ,R$。

$L,R\le {10}^6$

题解：考虑递归，$L=R$直接连边，否则令$mid=\lfloor \frac{L+R+1}{2}\rfloor -1$，先构造关于$[L,mid]$的图，设终点为$t$，新建一个复制点$t^{\prime }$，将$t$的入边复制一遍，再由$t^{\prime }$向$t$连一条长度为$mid+1-L$的边，此时，点$t$已经对区间$[L,R-((R-L+1)mod2)]$满足题目条件，若$R-L+1$是奇数，则额外新建一个工具点$t^{″}$，构造一条$1\to t^{″}\to t$的长度为$R$的路径即可。可以证明点数是$O(\log R)$的。

D.Odd Mineral Resource

考场上最后一分钟交题被卡常了...不爽

题意：一棵大小为$n$的带点权的树，$q$次询问，每次问$u$到$v$的路径上，是否存在$[l,r]$中的权值，在路径上出现奇数次，如果有输出任意一个。

$n,q\le 3\ast {10}^5$

题解： 考虑判断一个询问是否存在$[l,r]$之间的答案：对$[l,r]$中的每个数随机分配一个权值，计算$u$到$v$的路径点权值异或和是否为$0$即可。 因此类似于整体二分，先将$q$个询问用线段树规则拆分成$O(\log n)$个询问插入二分过程中。现在询问的答案在$[l,r]$之间，队列中有权值为$[l,r]$的点和待回答的答案在这个区间内的询问。由于有中途插入的询问，先判断一遍是否在$[l,r]$有解。接下来取$mid=\lfloor \frac{l+r}{2}\rfloor$，判断每个有解询问是否在$[l,mid]$中仍然有解，如有分在左半部分，否则在右半部分，点则按照权值分在两部分，递归进行即可。

分析复杂度，假设某一过程有$k$个操作，利用树状数组+lca统计路径异或和，复杂度为$O(k\log n)$，每个点操作会被执行$O(\log n)$次，每个询问会先被拆分为$O(\log n)$个，拆分后每个询问又最多递归$O(\log n)$次。但这里有一个优化：初步拆分的$O(\log n)$个询问，可以先判断一遍是否有解，选取一个有解的继续递归$O(\log n)$次寻找答案即可。于是总复杂度是$O(n{\log }^{2}n)$。

E.School Clubs

题意：有$n$个人，每个人恰好属于$m$个俱乐部中的一个，每轮随机选一个人，$\frac{1}{2}$的概率令其单独成立一个新俱乐部（只有一个人），$\frac{1}{2}$的概率从已有俱乐部中随机选一个加入，对于此人离开前人数为$a$的俱乐部，其被选择的概率为$\frac{a}{n}$。求所有人都在一个俱乐部内的期望时间。

题解：这是一个期望停时问题，可以通过建立一个势函数来解决。解决方法见出题人的blog (opens new window)。 假设现在的俱乐部人数可以用一个可重集$A$表示，根据信仰，我们认为存在一个合法的势函数可以写成如下形式：

$$\varphi (A)=\sum _{a\in A}f(a)$$

那么由停时定理，问题转化为求$\sum _{i}f(a_i)-f(n)$，其中$a_i$表示初始时刻第$i$个俱乐部的人数。现在关注如何求解$f$。

首先，由于添加若干个人数为$0$的俱乐部没有影响，一定有$f(0)=0$。

那么为了满足$\mathbb{E}[\varphi (A_{t+1})-\varphi (A_t)\mid A_t,A_{t-1},\dots ,A_1,A_0]=\mathbb{E}[\varphi (A_{t+1})-\varphi (A_t)\mid A_t]=-1$，根据题目的转移规律有：

$$\mathbb{E}[\varphi (A_{t+1})-\varphi (A_t)\mid A_t]$$$$=\sum _{a\in A}\frac{a}{n}(\frac{1}{2}(\varphi (A_k)-f(a)+f(a-1)+f(1))+\frac{a}{2n}\varphi (A_k)+\frac{1}{2}\sum _{b\in A,b\not\equiv a}\frac{b}{n}(\varphi (A_k)-f(a)+f(a-1)-f(b)+f(b+1)))-\varphi (A_t)$$$$=\frac{1}{2}(f(1)+\sum _{a\in A}\frac{a}{n}((2-\frac{a}{n})(f(a-1)-f(a))+(1-\frac{a}{n})(f(a+1)-f(a))))$$$$=-1$$

由$A$的任意性，可得$\frac{1}{2}f(1)=-1$，于是$f(1)=-2$ ，于是：

$$(2-\frac{a}{n})(f(a-1)-f(a))+(1-\frac{a}{n})(f(a+1)-f(a))=0$$

令$g(a)=\mathrm{\Delta }f(a)=f(a+1)-f(a)$，转化得：

$$\frac{g(a)}{g(a-1)}=\frac{2n-a}{n-a}$$$$g(a)=g(0)\prod _{i=1}^a\frac{g(i)}{g(i-1)}=-2\prod _{i=1}^a\frac{2n-i}{n-i}$$

可以验证：

$$f(a)=f(0)+\sum _{i=0}^{a-1}g(i)=-2\sum _{i=0}^{a-1}\prod _{j=1}^i\frac{2n-j}{n-j}=-2\frac{n}{n-1}(\prod _{i=1}^a\frac{2n-i}{n+1-i}-1)$$

于是：

$$\begin{array}{}\text{(1)}& f(a)=-2\frac{n}{n-1}(\prod _{i=1}^a\frac{2n-i}{n+1-i}-1)\end{array}$$$$\begin{array}{}\text{(2)}& =-2\frac{n}{n-1}(\frac{(2n-1)!(n-a)!}{(2n-a-1)!n!}-1)\end{array}$$

接下来的处理和鬼牌 (opens new window)类似，设阈值$T$，对于$a_1,a_2,\dots ,a_m$，分为$\le T$和$>T$两部分。$\le T$的部分，由$(1)$式通过$O(T+m\log \mathrm{M}\mathrm{O}\mathrm{D})$的复杂度递推求解；$>T$的部分不超过$\frac{n}{T}$个，利用$(2)$式配合分段打表求阶乘解决，假设打表间隔为$T^{\prime }$，这一部分的复杂度就是$O(\frac{n}{T}{T}^{\prime })$。

综上所述，解决问题的时间复杂度为$O(T+\frac{n}{T}{T}^{\prime }+m\log \mathrm{M}\mathrm{O}\mathrm{D})$，考虑到打表，空间复杂度为$O(m+\frac{n}{T^{\prime }})$。可以取$T={10}^7,T^{\prime }=2\ast {10}^5$（CF的代码长度限制为65535B）。