启动。
DEGwer's Doctoral Dissertation Cheering Contest
好魔怔的比赛。
E. Half Palindromes
先考虑单个 \(f(l,r)\) 的计算，有结论：我们一定会不断删最小的长度为 \(k\) 的前缀，满足前 \(2k+1\) 个字符是回文的。直到没有这样的 \(k\) 为止。
证明也很容易，假设我们某一步删了长度为 \(q\) 的前缀，而不是长度为 \(p\) 的前缀（其中 \(p\lt q\)），那么我们可以先删长度为 \(p\) 的，再删长度为 \(q-p\) 的。
现在考虑对每个 \(l\)，求出最小的 \(p\gt l\)，令 \(len=p-l\)，则满足 \([l,p)\) 和 \((p,p+len]\) 对称。那么当我们的 \(r\ge p+len\) 的时候，就会从 \(l\) 跳到 \(p\)。
注意到一共有 \(O(n)\) 个这样的条件，我们可以考虑结合扫描线的过程：从小到大扫描 \(r\)，对每个 \(l\)，维护 \(f_l\) 表示 \(l\) 开始删，会删到哪里。那么上面的条件就等价于：当我们扫到 \(r=p+len\) 的时候，就会把所有 \(f=l\) 的位置指向为 \(f=p\)。而我们显然只关注 \(\sum f\)。因此就可以维护 \(f\) 的桶，然后每次修改对应的 \(f=l\) 的位置，直接在桶上修改即可。需要注意的一个点是，由于 \(f=p\) 的人可能在之前也已经指向了新的位置，那么我们 \(f=l\rightarrow f=p\) 的时候，就应该把 \(f=l\) 的人，指向 \(f=p\) 的人所指向的位置，需要用并查集来维护一下。
那么显然除了预处理所有 \(p\) 以外，剩余的部分可以看作线性；而 \(p\) 的处理可以考虑：预处理出每个中心能拓展出的最长长度，然后就是利用 dsu 做一个离线的区间 chkmin 的事情，那么如果用 manacher 的话，这部分也能线性。当然其实是带了一个 dsu 的复杂度的。
F. K-Medians Clustering
我趣，这不是我们 XXII OpenCup XiAn 的 E 题吗？怎么变成计数出出来了？
那么直接快进到：我们对把 \(c_i\) 排序后（\(c_0=0,c_{k+1}=m+1\)）排序后，分别来考虑每个 \((c_i,c_{i+1})\) 之间的段。
然后不妨来算不合法的情况，因为它是一个类似绝对众数状物的东西：就是有一段 \((c_i,c_{i+1})\) ，这里面的数的出现次数 \(cnt\)，减去剩下的 \((n-k-cnt)\)，依旧大于 \(i\)。显然这样的 \(i\) 若存在，则唯一。
那么不妨先来枚举它在哪一段 \((c_i,c_{i+1})\) 内，然后一个常规的想法是，枚举这一段内所有数的出现总次数 \(x\)，\(x\) 应当有一个可以计算的下界 \(m\)。然后把剩下的 \(n-k-cnt\) 分配给这一段以外的所有数。那么就是两个插板的组合数相乘的一个东西。发现我们要做 \(k\) 次，每次是 \(O(n)\) 的，这样我们得到的是一个 \(O(nk)\) 的做法。
注意到这个其实是范德蒙德卷积，带了一个下指标的情况。它看起来给人一种很难优化的感觉。
事实上这一部分没有什么简洁的通项了，但是我们有一个类似于“转置”的手法，把这个 \(O(n)\) 的式子变成一个 \(O(c_{i+1}-c_{i})\) 的式子，然后再利用 \(\sum (c_{i+1}-c_{i})=O(m)\) 的事实把这个题在 \(O(n+m+k)\) 的时间内解决。
大体思路就是，我们并不枚举出现次数 \(x\ge m\)，而是说，我们因为不关注多重集内数的顺序，所以可以把多重集看作一个递增的序列，然后我们不妨枚举 \((c_i,c_{i+1})\) 内的数里，第 \(m\) 个数的值 \(y\)，那么也就相当于，前 \(m-1\) 个数可以是 \((ci,y]\) 里的，剩下的 \(n-m-k\) 个数，既可以是 \([y,c_{i+1})\) 里的，也可以是 \((ci,c_{i+1})\) 区间以外的。那么这次还是插板，但是枚举量就讲到了 \(c_{i+1}-c_{i}\) 级别。
然后就在 \(O(n+m+k)\) 的时间内解决了，所以 \(k\) 可以做到 \(10^7\) 的。
ICPC 合肥
D. Balanced Array
首先需要注意到：我们存在 \(O(1)\) 判断一个长度为 \(n\) 的序列在某个 \(k\) 下是否合法的方法，直接使用字符串哈希，令 \(base\) 是一个大于 \(2a\) 的数：
- \(h[1,n-2k]+h[2k+1,n]=2h[k+1,n-k]\)
然后，注意到对于一个 \(k\)，不考虑 \(2k+1\le l\) 的限制的话，那么合法的 \(l\) 是一个前缀。加上 \(2k+1\le l\) 的话就是一段区间，所以可以直接对每个 \(k\) 先二分算出这个区间，然后跑区间覆盖，这样是 \(O(n\log n)\) 的。
考虑换一个角度：从小到大枚举 \(k\)，然后我们假设之前已经让 \(p\) 这个前缀平衡了，且没有成功让 \(p+1\) 这个前缀平衡。对于此时的 \(k\)，如果 \(p+1\lt 2k+1\) 了，那么 \(p+1\) 就永远没有机会平衡了，所以我们直接令 \(p\) 来到 \(2k\)。然后我们不断检查 \(p+1\) 在 \(k\) 下是否是平衡的，如果是，我们就继续向后尝试，否则根据单调性我们直接停在这里，考虑更大的 \(k\) 即可。这样的话就在 \(O(n)\) 的时间内解决了这个问题。
K.Campus Partition
首先注意到：对于一个连通块，我们设最大点为 \(x\)，次大点为 \(y\)，则只需要保留 \(x\sim y\) 路径上的所有点。
因此连通块划分变成了路径划分。然后一条路径的权值（非退化）应该就是路径端点里边权较小的那个。
然后考虑设计树形 dp：令 \(f(u)\) 是 \(u\) 子树内的答案，\(g(u,x)\) 是 \(u\) 子树内的答案，但是 \(x\rightarrow u\) 被占据，且这条路径只确定了一端点是 \(x\)，另一端点在 \(u\) 子树外，还未确定，此时的一个答案。
转移比较显然：当我们加入一个儿子 \(v\) 的时候，首先原始的 \(f(u)\) 会加上 \(f(v)\)，然后我们用 \(g(u,x)+g(v,y)+\min\{a_x,a_y\}\) 来更新此时的 \(f(v)\)，这是 \(f\) 的变化；至于 \(g(u)\) 就应该是，原本的所有 \(g(u,x)\) 都会加上 \(f(v)\)，而 \(g(v,x)\) 会加上之前的 \(\sum f(v)\)，然后更新给 \(g(u,x)\)。
这个过程显然可以用线段树合并维护，然后就做到了 \(O(n\log n)\)。
L. Information Spread
考虑根据题意建出 dfs 树，则一条可能的传播路径一定是沿着树边走的，只有最后一条边可以是非树边。
证明是这样的：如果我们走了一条非树边，那么说明 \(label_u\gt label_v\)，其中 \(label\) 是一个点什么时候 \(vis=1\)。那么你就不可能从 \(v\) 往后走了，因为它已经传递过一次自身信息了。
这样的话，对于一个点 \(v\)，考虑所有非树边 \(u\rightarrow v(pr=w)\)，所有这样的 \((v,w)\)，再加上 \((u,1)\)，相当于是这样一个事件：
- \((x,y)\) 表示：如果 \(1\rightarrow x\) 的路径上每条边都生效，那么有 \(y\) 的概率让 \(v\) 被传递到信息。
显然因为有多个事件，所以考虑容斥：计算每一个事件都失效的概率。
那么这就是一个比较套路的问题了：直接建出关于 \(x\) 的虚树，然后 \(dp(u,0/1)\) 表示计算完 \(u\) 子树内的情况，且我们是否强制要求 \(1\rightarrow u\) 的路径上至少有一条边失效，这样的概率。
然后本题在 \(O((n+m)\log n)\) 的时间内解决。
The 1st Universal Cup. Stage 18: Shenzhen
M. Canvas
很好的构造题。但是有点难写。
对于 \(1-1\) 和 \(2-2\) 两种类型的操作，前者我们可以全放最前面，后者我们可以全放最后面。
当我们把一下 \(2-2\) 放在最后面的时候，对于剩下的 \(1-2\) 操作，如果它的 \(1\) 会在后面被染成 \(2\)，那么我们也能放心地做这个 \(1-2\) 操作（应该在所有 \(2-2\) 之前，其余 \(1-2\) 之后），然后可以把这个操作也视为 \(2-2\).... 重复这个过程以后，可以化简成一个只有 \(1-2\) 类型操作的问题。
考虑从 \(2\) 的那个点连有向边到 \(1\) 的那个点，然后问题变成我们需要按顺序考虑激活每条边，使得有尽可能多的店，和它相关的边最后一次被激活的时候，是它的出边。
如果这张图是个 DAG，那么很明显答案就是 \(n\) 减去无出度点数 \(x\)：显然这是上界，也很容易构造：我们随便跑出一组拓扑序，然后对于所有有出度点 \(u\)，随意选择一条 \(u\rightarrow v\) ，最后按照 \(u\) 的拓扑序，从前往后枚举每个 \(u\)，点亮这条 \(u\rightarrow v\)。除去这 \(n-x\) 条关键边，剩下的边就直接全放最前面即可。
现在考虑这张图是一个 scc 的情况：显然，不可能所有点最后都合法，因为让一个点变成 \(2\) 总意味着一个点会变成 \(1\)：所以答案上界是 \(n-1\)，并且很容易发现是一定能取到的：我们随意选择一个点，那么它一定能被所有点走到，因此在反图上 dfs 建出 dfs 树的一个树形结构，然后从叶子开始激活向父亲的边，这样就只会有根节点最后不合法。
结合上面的两个构造，很容易导出一般情况的结论：答案就是 \(n\) 减去缩点后的无出度点数 \(x\)：这个值是答案的上界同样容易证明。并且容易给出构造：对于所有 scc，若其有出度，则我们令关键点为某个有连向 scc 外的连边的点，否则随意钦定其中一个点为关键点。然后对于每个 scc，以关键点为根，跑出内部 dfs 树的树形结构。对于每个有出度的 scc 的关键点，随意连向一个另外的 scc。显然此时这些保留的连边形成一个 DAG，按照拓扑序的顺序激活即可。
此时我们就在 \(O(n+m)\) 的时间内解决了这个问题。
杂题
ARC112F Die Siedler
神题！
首先注意到，如果没有卡包，我们的策略可以是从前往后考虑（考虑完 \(n\) 就回来考虑 \(1\)），然后看是否有 \(2i\) 张卡牌 \(i\)，有的话就升级。还注意到一个事情是，我们不需要严格按这个 \(1\sim n\) 的顺序考虑也是对的：也就是我们不断地任意选择一个 \(2i\) 张 \(i\) 然后升级，直到无法进行任何操作为止，这也是不影响答案的。
这启发我们初始把一张 \(i\) 号牌替换成 \((2i-2)!!\) 张 \(1\) 号牌，然后整个牌堆就只有 \(1\) 号牌了。还有一点是，我们可以从 \(n\) 换到 \(1\)，所以我们可以把 \((2n)!!\) 张 \(1\) 号牌换成一张。那么令 \(S=(2n)!!-1\) 我们的这个 \(1\) 号牌数就可以认为是在 \([1,S]\) 意义下（注意不是 \(\bmod S\) 意义下）的东西。
然后令卡包的数是 \(b_i\)，那么我们令初始的数是 \(a\)，能得到的所有数就是 \(a\) 加上 \((b,...,S)\) 的一个线性组合，其中 \(b\) 的系数只能是非负数，而 \(S\) 的系数是非正数。根据 bezout 定理，此时我们能加上的就是 \(\gcd(b,...,S)\) 的任意非负倍数。也就是 \(a+kg\)（在 \([1,S]\) 意义下）都能被表出。
那么不妨令 \(a:=a\bmod g\)，则我们可以直接枚举 \(k\lt \frac{S}{g}\)，然后再暴力计算每个 \(a+kg\) 最后会剩下的卡牌张数。但是当 \(\frac{S}{g}\) 的时候这就会出问题。需要注意到的一个，非常重要的事情是，在 \(n\le 16\) 的情况下，\((2n)!!-1\) 的因子非常有规律：要么极大，要么极小。事实上最接近的一对 \(x\times y=S(x\le y)\)，\(x\) 是一个 \(10^6\) 左右的数，所以 \(g\) 和 \(\frac{S}{g}\) 总有一个是在我们可以接受的范围内的，刚才我们已经得到了一个 \(O(\frac{S}{g})\) 的算法，现在我们只需要得到一个 \(O(g)\) 的算法就够了。
此时我们不再从确定 \(a+kg\) 后计算局面的概率考虑，而是从，每次往局面里加入一张任意卡，然后更新 \(a+kg\) 的局面来考虑。也就是我们令 \(dis(x)\) 是所有 \(\equiv x\pmod g\) 的状态的里面，张数最小的。转移的时候，直接枚举 \(1\sim n\) 的一张卡牌加入即可。那么这就是在跑同余最短路，容易做到 \(O(gm)\)。
然后两部分拼一下，就解决了本题。