$H$ 的数据范围暗示，需要高效的算法来确定分界值 $u^*$。由于分界值 $u^*$ 和划分出的席位数（即 $u_i/2^j \ge u^*$ 的 $(i,j)$ 对数）之间具有良好的单调关系，可以用二分 $u^*$ 的办法求解。

每次二分 $u^*$，对每个 $u_i$ 判断可以分得多少席位。整理不等式可得

$$j \le \log\frac{u_i}{u^*}$$

故可以分得 $\left\lfloor\log(u_i/u^*)\right\rfloor$ 个席位。对每个 $u_i$ 可以 $O(1)$ 求解（假设忽略运算复杂度），则总复杂度为 $O(T\log H)$，可以通过本题。

直接对 $u^*$ 二分，可能会出现很大的精度问题：每个 $u_i$ 最少分得 $H/T$ 个席位，故

$$u^* \approx \frac{u_i}{2^{H/T}} \rightarrow 0$$

一种解决办法是，对 $v^*=\log u^*$ 进行二分，则可以转化为 $j = \left\lfloor\log u_i − v^*\right\rfloor$，相对而言精度问题不大。

更进一步地，可以对 $v^*$ 的整数部分和小数部分分开求解。整数部分需要根据是否大于 $\left\lfloor\max\log u_i\right\rfloor$ 简单讨论，小数部分直接排序即可。这样可以完全避免精度问题。

给定三种记号：

• $s_i\text{#}s_{i+1}$ 表示读完 $s_i$ 后应紧跟 $s_{i+1}$，且优先级高于其它两种符号；
• $s_i\text{*}s_{i+1}$ 表示读完 $s_{i+1}$ 后再读 $s_i$；
• $s_i\text{p-q}$ 表示（在不考虑的情况下）（如果有则）先读对应的 $\text{p-(q-1)}$ 前的文字，读完 $s_i$，再读对应的 $\text{p-(q+1)}$ 前的文字。

给出一个排列 $p_i$，求一组记号使得阅读 $p_i$ 的顺序恰好将其还原为 $1 \sim K$ 的排列。

$1 \le K \le 10^6$

先考虑只有最复杂的 \text{p-q} 时应该怎么处理。

可以想到用栈来保存当前的遥远跳转结构，如果碰到可以直接阅读的则将栈清空。

如果有多个遥远跳转结构怎么办？栈套栈！每弹出一个栈，更新新栈顶的栈的嵌套层数。

在此基础上可以实现另外两种符号，其中 $\text{*}$（及其连续段）需要根据头尾情况简单分类讨论一下。想清楚了实现起来并不复杂。

复杂度 $O(K)$

题目简述

给定正整数 $n$ 和长为 $n$ 的正整数序列 $a$。对于正整数 $x$，定义$\newcommand{dfrac}[2]{\displaystyle\frac{#1}{#2}}$

$$f(x)=\begin{cases}0&(x>n)\\f(x+\gcd(x,a_x))+a_x&(x\leq n)\end{cases}$$

现有 $q$ 次操作，分为两类：

• 1 l r c：将所有满足 $l\leq i\leq r$ 的 $a_i$ 的值乘以 $c$。
• 2 x：查询 $f(x)$ 对 $998244353$ 取模的值。

做法解析

做法的核心是分块。将序列分为长度为 $B$ 的一些块，并维护块内每个位置不断向后跳时第一次跳出块时对应的位置和这个过程中 $a_x$ 的总和，则可以 $O\left(\dfrac{n}{B}\right)$ 的处理一次查询。修改虽然是区间修改，但维护新的跳到的位置时，$\gcd(x,a_x)$ 的改变次数最多是 $x$ 质因子分解后对应幂次的总和，可以说明总的改变次数是 $O(n\log\log n)$ 的，因此可以用 set 对每个质数维护还可能被修改的位置，每次修改时暴力重构整个块；而对于维护一路上的权值和，可以对整块的修改打标记、散块的修改直接暴力，复杂度为 $O\left(B+\dfrac{n}{B}\right)$。因此总的复杂度大致为 $O\left(q\left(B+\dfrac{n}{B}\right)+n\log\log n\cdot (B+\log n)\right)$，综合分析常数和理论结果，大致取 $B=300$ （差不多是 $\dfrac{n}{\sqrt3}$）时最优。

时限给了 $4\text{s}$，实际上 std 取 $B=300$ 需要跑大约 $1.3\text{s}$，取 $B=500$ 也只需要大约 $2\text{s}$，所以应该是完全不卡常的。

题意

$n$ 只猫娘，每只猫娘每天要么自己举行了排队，要么会追随自己最好的朋友去参加她要去的派对。

举办的派对有 $3$ 种类型，在每一天晚上都会有一只猫娘举办了某种类型的派对，这只猫娘会一直举行下去直到自己换类型，问每天晚上这三种类型的派对都几只猫娘参加。

思路

首先把猫 $i$ 与自己的朋友连一条有向边，那么整张图就是一个内向基环树。每当一只猫娘举行了派对，这个结点相当于把自己和父亲结点的连边断开了，我们就需要统计每个举办派对的结点子树大小。

如果我们直接对着每一天的修改一个一个做，那么要处理分裂的问题，也能做但是不是很好写，所以我们考虑倒着做。

具体来说，每一天把当前猫娘举办的派对的答案回溯到这只猫娘举办的上一个派对那里（因为这只猫娘从上一个派对到举行当前派对这段时间一直都没变），但是如果这是这只猫娘举办的第一个派对了，那么来她排队里的猫娘和她自己都会跟随她的父亲结点，相当于连上了一条边，可以直接用dsu做，假如当前父亲节点追随的结点举办了派对，那么我们需要把当前结点子树的大小统计进这个派对的类型中。

差点忘了，我们既然从后往前做了，那需要初始化每种类型在最后时刻的人数，可以直接把一直都没举行派对的猫娘直接和她们的父亲节点连起来，然后对于有派对的把对应类型类加上自己子树的大小，然后从后往前一步一步更新当前答案这题做完了。

有一个注意的点在于并查集合并方向要写对，不然只能得 $4$ pts（也可能是我写法问题）。

这题洛谷评蓝是不是太夸张了（

题目很明显是一个最小割问题。对于题目描述中的“通知一个分部，在其所有下辖的铁路上设立检查站”操作，我们需要对如下问题进行网络流建模：给定网络流图以及对其边的划分，一次可以以 $1$ 的代价割掉一个划分集合中的所有边。特别地，在同一个划分集合中的所有边都与某个点相邻。

考虑某个形如 $A_i \to x_i \to B_i$ 的划分集合，其中 $A_i$ 和 $B_i$ 为任意点集。考虑如下建模：

• 建立虚点 $p_i, q_i$；
• 有边 $(p_i,q_i,1)$、$(A_i, p_i, 1)$、$(x_i, p_i, 1)$、$(q_i,x_i,1)$、$(q_i,B_i,1)$。

注意到在这个建模中，若所有边都不被割掉，其连通关系恰好为 $A_i \to x \to B_i$，而割掉 $p_i \to q_i$ 之后这个连通关系就消失了，符合我们的需求。

再注意到网络流图上的所有边边权均为 1，直接运行 dinic 算法求解最大流的复杂度为 $O(n \sqrt{m})$，足以通过本题。

CRT或是简单枚举即可得到答案 $83$