SD 三轮省队集训

· · 个人记录

Day 1

其实 T1 交了个假的东西上去，T2 交了 $O(n^{1.75})$ 多过了一点分。 ### A 考虑两个 $\log$ 咋做，直接树剖之后颜色段均摊，用线段树维护二元组的第二个值即可。所以你可以选择直接写 LCT 跑单 $\log$ 颜色段均摊，但是我不会。 还是有其他单 $\log$ 做法的，因为修改是到根的，所以有个常见的思路是转成单点修改子树查询。这里赛时编了个不能合并的标记但是数据太水没卡掉，但是可以改成每个点直接开一棵以时间为轴的线段树，然后发现线段树合并是正确的，就能做了。 ### B 扫描线后问题形如区间加减 $1$ 若干次查询值为 $x$ 的个数，由矩阵乘法规约这个不能低于根号。考虑直接分块，设块长为 $B$，暴力做的话有 $n$ 次修改和 $\frac{n^2}{m}$ 次查询，平衡一下可以得到一个 $O(\frac{n^2}{\sqrt m})$，也就是 $O(n^{1.75})$ 的做法。 考虑发掘一些性质，一个块内的极差在一次修改后增大 $1$ 只会在它是一个散块的情况发生，而散块修改一共就 $2n$ 个，所以每个块的极差之和是 $O(n)$ 的。考虑在上述过程中额外维护出来每个块当前的最大最小值，只要保证每个块查一次的复杂度是极差除以 $m$，就可以做到 $O(\frac{n^2}{m}+n\sqrt n)$ 了。能想到这个的真是神人了。 ### C 其实听懂这题好像并不难啊，但是缝在一起还是太逆天了点。 ## Day 2 $100+20+8=128$，啥都不会。 T2 疯狂冲刺旋转扫描线，写了三个半小时没过大样例。 ### A 糖丸了的题。显然具有一个双指针的结构在，直接做的问题在于复杂度不太对：一个点可以被多个限制覆盖。但是你发现两个限制对应的点要么包含要么不交，包含显然没用，线段树合并删掉包含的情况即可保证每个点只被覆盖一次，然后每种限制覆盖的点拉出来双指针即可 $O(n\log n)$。 ### B 先考虑只有一个颜色怎么做，也就是半平面数点问题。 考虑分块，设块长为 $B$，每个块内跑一个叫旋转扫描线的东西，也就是想象一根直线的斜率从负无穷到正无穷转动，对于任意两个点 $i,j$ 设 $x_i<x_j$，则这条线斜率 $k\le k_{ij}$ 时 $i$ 更可能在下方，否则 $j$ 更可能在下方。每个块内共发生 $B^2$ 次交换，维护出排名后查询可以在每个块内二分，取 $B=\sqrt q$ 可以做到 $O(n\sqrt q\log q)$。 对于本题，考虑对颜色出现次数根号分治，出现次数多的颜色直接跑上面的做法即可。对于次数少的颜色，考虑设计一个分块方式使得每个块大小为 $[B,2B)$ 且每种颜色都在一个块内，这个显然能够实现。因为查询的是平方和，我们可以考虑对块内每个数维护块内它前面有多少和它同色的，维护排名的过程中在交换时使用树状数组更新即可，复杂度不变。 ### C 诗人我吃。 ## Day 3 $10+60+100=170$，得分单调递增了🤡🤡。 开场觉得 T1 很不可做（事实上确实），T2 其实之前讲过但是当时在睡觉，T3 比较有感觉大战之后通过了。 ### A 这也太难了。 ### B 先考虑一个比较重要的部分分：修改都是全局。 首先考虑全局操作了若干次后每个 $a_i$ 应该是什么。考虑一张网格图，第 $i$ 行 $j$ 列表示第 $i$ 次操作后 $a_j$ 的值，用连边 $(i,j)\to(i+1,j)$ 和 $(i,j)\to(i,j+1)$ 表示连向的两个位置的值要异或上 $(i,j)$ 的值，则发现 $a_{x,i}$ 对 $a_{y,j}$ 有贡献当且仅当在这张图上 $(x,i)$ 到 $(y,j)$ 的路径个数为奇数。 考虑在这张网格图上 $(x,i)$ 走到 $(y,j)$ 的方案数其实是 $\binom{y-x}{j-i}$，组合数的奇偶性肯定考虑 Lucas 定理，也就是当 $j-i$ 是 $y-x$ 的子集时会有贡献。所以假设当前全局被操作了 $t$ 次，则 $a_i=\bigoplus\limits_{x\subseteq t}a_{i-x}$。容易想到定期重构，设阈值 $B=2^k$（方便重构序列），每进行 $B$ 次修改之后就直接重构整个序列，每次查询直接枚举当前修改次数的子集复杂度至多为 $O(B)$，取 $B=512$ 即可做到 $O(n\sqrt n)$。 尝试扩展到一般情况，我们同时以 $B$ 为块长对序列进行分块，则我们需要对每个块求出 $B$ 次修改后块内的每个数，还要回答所有跨过这个块的询问。注意因为我们最多攒了 $B$ 次修改操作，所以每个位置的值只会与这个位置所在的块与上一个块内的值有关。因此我们每次考虑两个相邻的块处理，下面是具体的处理过程。 - 如果有一个修改操作完全跨过两个块，维护一个整体标记 $tag$ 并将 $tag$ 加上 $1$。 - 如果有一个修改操作与两个块有交但不是完全跨过，将 $tag$ 下放清空并暴力做一遍。注意这里下放 $tag$ 的方式是类似高维前缀和的逐位处理，这样清空一次 $tag$ 的复杂度是 $O(B\log B)$。 - 如果有一次块内的询问操作，直接枚举当前 $tag$ 的子集暴力即可。 看上去第二种情况复杂度很高，但是这相当于只会在散块的位置发生，所以复杂度还是对的。认为 $B=\sqrt n$ 且 $n,q$ 同阶的话复杂度是 $O(n\sqrt n\log n)$，代码无敌好写而且跑得飞快。 ### C 大战四小时通过了，我觉得这题真不难啊。 先考虑调整一下操作顺序，可以发现区间减只会在区间加前执行。证明也不难，分讨一下加法区间和减法区间的位置关系即可。 思考下操作次数的刻画，考虑如果确定了每个数被减和加的次数 $s_i,t_i$，根据积木大赛的经典结论答案就是 $\sum_{i>1}(\max(s_i-s_{i-1},0)+\max(t_i-t_{i-1},0))$。发现对于不存在 $b_i=0$ 的情况，如果确定了一个位置的 $s_i$ 则可以直接确定 $t_i=b_i-a_i+s_i$，所以可以直接 dp，设 $f_{i,j}$ 表示考虑了前 $i$ 个数且 $s_i=j$ 的答案，直接转移就能做到 $O(nV^2)$，可能也可以稍加优化做到 $O(nV)$，或许还可以说明第二维能离散化之类的，反正用不到。 考虑带上 $b_i=0$ 的情况，发现问题就是此时 $t_i$ 可以为任意值而不好确定。继续调整下操作，发现对于一个极长的 $b_i=0$ 的连续段，如果前面有伸进来的区间减操作则肯定会跨过整段，且整个段至少要被减去段内 $a_i$ 的最大值次。更进一步地，可以发现段内的 $t_i$ 直接取和前一个 $b_i\not=0$ 的数相同的值一定不劣。根据上面的观察可以考虑将序列里 $b_i=0$ 的极长段缩起来，新缩出来的 $a_i$ 为原来段内 $a_i$ 的最大值。 沿用上面的 dp 状态，考虑先跳过 $b_i=0$ 的位置，即认为 $b_i>0$。如果 $b_{i-1}>0$ 则和不存在 $b_{i}=0$ 的转移一致，这种情况平凡。否则因为缩过序列，考虑枚举 $s_{i-2}$ 的值，这样就能得到 $t_{i-2}$ 的值和 $s_{i-1}=\max(s_{i-2},a_{i-1})$，根据上面性质还有 $t_{i-1}=t_{i-2}$，所以 $s_{i/i-1}$ 和 $t_{i/i-1}$ 的值都可以确定下来，于是能直接转移，同样直接实现可以做到 $O(nV^2)$。 尝试继续优化这个 dp，打表后可以发现这个 dp 数组固定 $i$ 这一维后关于 $j$ 是凸的，且斜率只有 $0,1,2$ 三种，于是可以考虑每一维直接维护图像长什么样，也就是记一下最小值和两个斜率拐点，分类讨论容易做到 $O(n)$，于是就做完了。 赛时觉得这个好像一点道理都没有，发现其实很好证啊！首先说明差分不超过 $2$，显然一个位置如果被多减了一次一定存在一个多用了不超过 $2$ 次的方案补救回来。接下来只需要说明凸性，上面 $O(nV^2)$ 的暴力 dp 中转移代价由减法和加法的操作次数两部分构成，每一部分都是一条分段的折线，且只有斜率为 $0,1$ 的两段，因此也可以归纳说明 $f_i$ 满足凸性。 ## Day 4 $100+30+1=131$，太神秘的场，一点都不懂。 ### A 容易发现我们只需要枚举 $a$ 序列中的一个极长上升子段来 check，然后考虑把 $b$ 序列里的数分为 $[1,a_l-1),[a_l,a_r],(a_r,n]$ 三个区间。然后考虑大力贪心，发现中间的数如果有的话就一定会取，对于两侧发现策略就两种，一定是不断先取左边或者不断先取右边。大力分类讨论并精细实现可以做到 $O(1)$ check 一次，这样最后就能做到 $O(n)$，写起来虽然不长但是很像是在吃史。 ### B 计算几何爬。 ### C 首先把询问按照 $S$ 的区间猫树分治掉，只考虑 $S$ 区间跨过当前分治区间中点的询问。 考虑如何回答询问，不妨枚举询问的 $T$ 的区间中的一条分割线，分割线左边和 $S$ 的左区间匹配，右边和 $S$ 的右区间匹配，每个分割线把两侧的匹配长度加起来求最大值就是答案。把 $S$ 的左右区间看成是两个串，这样相当于要快速查询 $T$ 的一个区间和一个串的前缀的 $\text{LCS}$ 的长度。所以在每个分治区间上要解决的问题就形如，给定两个串 $X,Y$，多次查询 $\text{LCS}(X[l,r],Y[1,k])$。 设 $dp(i,j,k)=\text{LCS}(X[l,r],Y[1,k])$，考察 $dp(i,j,k)$ 有什么性质，比较重要的有： - 如果 $dp(i,j,k)>dp(i,j-1,k)$，那么一定有 $dp(i+1,j,k)>dp(i+1,j-1,k)$。 - 如果 $dp(i,j,k)>dp(i,j,k-1)$，那么一定有 $dp(i-1,j,k)>dp(i-1,j,k-1)$。 这两个性质能带来的结论是： - 当 $j\to j+1$ 时，固定 $k$ 后 dp 值会加 $1$ 的 $i$ 是一段后缀。 - 当 $k\to k+1$ 时，固定 $j$ 后 dp 值会加 $1$ 的 $i$ 是一段前缀。 设 $p(j,k)$ 表示，$j-1\to j$ 之后 $i\ge p(j,k)$ 的位置都被 $+1$；同理设 $q(j,k)$ 表示，$k-1\to k$ 之后 $i<q(j,k)$ 的位置都被 $+1$。设 $F_i=dp(i,j-1,k-1)$，发现要求 $p,q$ 只需要观察下 $dp(*,j-1,k),dp(*,j,k-1)$ 和 $dp(*,j,k)$ 里每个 $i$ 对应的取值是什么（显然只应该是 $F_i$ 或 $F_i+1$ 两者其一），最后的结论是： $$ (p(j,k),q(j,k))=\begin{cases} (p(j,k-1),q(j-1,k)),&X_j=T_k\land p(j,k-1)\ge q(j-1,k)\\ (q(j-1,k),p(j,k-1)),&\text{otherwise} \end{cases} $$ 边界为 $p(i,0)=i+1$ 和 $q(0,i)=1$。 对于每个分治区间我们都可以 $O(len\times m)$ 递推出所有 $p(j,k)$ 和 $q(j,k)$，处理询问的时候可以直接根据 $p,q$ 差分求出要用到的 dp 值，所以回答一个询问的复杂度是 $O(m)$，最后本题的总复杂度是 $O(nm\log n+qm)$。 这里提到的所有性质的证明都可以在 [do_while_true 的题解](https://www.luogu.com.cn/article/t52d39ri) 中找到详细的证明，这里不再赘述。事实上这好像是一道论文题，解题的思路看上去也相当不自然，我也不太懂该怎么做出来这题，只能先抄一下做法了。 ## Day 5 $40+100+0=140$。 T1 开场读错题比较红温，而且发现确实不太会做，所以转战了 T2 并蒙过了。 ### A 考虑设 $dp_u$ 表示经过 $u$ 的点中最晚离开 $u$ 的时刻。加入一个点 $x$ 的影响其实就是，首先令 $dp_{R}$ 加上 $1$，然后顺次取出 $R$ 到 $x$ 路径上的点 $p_1,p_2,\ldots,p_k$，发现其实就是对 $1\le i<k$ 顺次做 $dp_{p_i}\leftarrow\max(dp_{p_i},dp_{p_{i+1}})$ 和 $dp_{p_{i+1}}=dp_{p_i}+1$，最后给 $dp_x$ 加上 $a_x$。如果树是一条链，发现当前的 dp 数组形如若干个斜率为 $1$ 的一次函数，而那个 chkmax 的操作其实就是要我们支持把一次函数左移，然后还需要将一些一次函数整体上移，所有过程均可以使用平衡树维护做到 $O(n\log n)$。 那对于树上问题，考虑直接先上个树剖，发现每条重链相当于要对前缀做类似链上的操作。考虑对每一条重链开一棵平衡树维护，就可以做到 $O(n\log ^2 n)$ 了。具体来说你只需要维护一个点到重链顶部每个点对应的一次函数的变化，然后查询出自己的新 dp 值返回即可，注意这是个从上往下的过程。 ### B 前面忘了，总之是可以注意到查询的式子可以化简为： $$ \sum_{i=l}^ra_i(i-l+1)\sum_{j=l}^ra_j(r-j+1) $$ 前后两个求和号显然还是独立的，于是发现只需要支持区间加，查询区间 $a_i$ 和 $i\times a_i$ 的和就能快速计算了，使用线段树维护略微卡常后可以通过，使用树状数组维护三阶差分可以稳定通过，时间复杂度均为 $O(n\log n)$。 至于如何得到这个最简形式，场上的我是先在纸上推了两页得到了个略微复杂的形式，然后在暴力验证时输出了系数发现很多项好像都被消去了，结合题目名称开始大力注释暴力代码并最终得到最简形式。 ### C 还没看，to be done。 ## Day 6 $100+0+0=100$，T1 因为奇怪原因卡了好久，小丑完了。 ### A 一个简单的想法是记录后 $k-1$ 个位置的字符等价类，但是这样状态数很难不是满的 $bell(k-1)$。 考虑容斥，钦定若干个位置出现了长度为 $k$ 的回文子串。容斥之后的好处就是，如果你不钦定一个位置出现的回文子串，那么后缀里不同的字符等价类你也就不再需要要求它们的字符不能相同了。此时的决策就是，要么钦定下一个位置结尾形成回文子串，此时需要根据回文的限制合并若干个等价类，如果不钦定则在末尾新开一个等价类。而等价类填字符的方案数可以认为就是 $\sigma$，在合并两个等价类时把方案除以 $\sigma$ 即可。此时发现状态数好像就不是太满了，爆搜一下发现可以接受，于是就可以通过了，复杂度为 $O(nS)$。 ### B 先考虑如何计算一个确定序列的价值。对于一个二进制位 $w$，设这一位为 $1$ 的位置有 $c$ 个，那么这一位能产生的贡献其实就是 $2^w\times2^{n-c}\times\sum_{i\text{ is odd}}\binom{c}{i}$，后面的组合数杨辉三角展开掉发现就是上一行求和，所以贡献就是 $2^w\times 2^{n-c}$。那对于整个序列来说，设所有元素按位或的结果为 $v$，价值其实就是 $v\times 2^{n-1}$。 现在设价值 $w=2^{n-1}\times v$，考虑如果确定了 $v$，如何计算对应的序列个数。对于 $v$ 非 $0$ 的二进制位方案数就是 $(2^n-1)$，所以设 $t=\text{popcount}(v)$，方案数就是 $(2^n-1)^t$。因为方案数只和 $\text{popcount}(v)$ 有关，所以如果确定的是 $t$，那么最优的 $v$ 肯定是把这 $t$ 个 $1$ 填在最低位上，也就是取 $v=2^t-1$ 即可。现在的问题就是求最小的 $t$ 使得 $(2^n-1)^t\equiv x\pmod m$，发现就是 exBSGS 板子，直接套上去做即可，复杂度 $O(T\sqrt m)$。 当然这只是一般情况，实际上需要对 $x=0$ 和 $m=1$ 之类的情况特判，注意快速幂需要扩展欧拉定理算，细节很烦人。 ### C 其实就是树上分糖果，先照搬下序列的做法，套个树上差分线段树合并掉即可上树，询问的时候只需要二分一下就是 $O(n\log^2 n)$ 的了。 ### Day 7 $32+15+25=72$，超级大坠机，打完玉玉了一天。 主要问题在于 T1 完全想歪了，T2 啥都没想到。 ### A 观察倒水的过程，发现除了最后一次一定都是往右倒，否则右边的杯子会一直都是空的。更进一步，设 $b_i$ 表示第 $i$ 个杯子目前里面有多少体积的水，从右边的杯子 $y$ 倒向左边的杯子 $x$ 时倒掉的水量显然为 $\min(a_x,b_y)$。 设 $f_{i,j}$ 表示当前从左向右倒到第 $i$ 个杯子且这个杯子里当前有 $j$ 体积的水的概率，转移可以是向后倒到杯子 $p$ 转移到 $f_{p,\min(a_p,j)}$，也可以是向前倒水计入答案里。直接实现可以做到 $O(n^3)$。稍加优化，维护 $s_x=\sum_{j\le i}f_{j,x}$，即可做到 $O(1)$ 转移，此时复杂度降到 $O(n^2)$。 继续优化的方向也很明显，考虑把 $s$ 直接拍到线段树上，观察发现 $i\to i+1$ 时只需要支持区间乘和单点加，求答案也只需要查询一些带系数的区间和，直接大力上线段树维护就好了，复杂度 $O(n\log n)$。 很难想象赛时我的状态到底是什么。 ### B 大家好像都觉得这题不难，但是我一点都不会/ll/ll 先感性理解下题意，把 $S$ 看成一个 $01$ 串，由于 $S$ 里面有 $1$ 所以 $T$ 里面必须有 $0$，这相当于把 $S$ 平放一遍，然后 $T$ 里面每加入一个数就相当于把 $S$ 整体向右平移若干位然后复制，我们需要恰好覆盖 $1\sim nm$ 这些位置。 cxm：你先想一下你是这个串 $S$ 你会怎么填满。首先考虑你可以把 $S$ 划分为若干个相同的部分，这样你做完了第一部分其它部分可以直接抄作业。除此之外还有一个想法就是把 $S$ 切为若干等长的段，满足除了第一段剩下的段都是全 $0$，这样你做完第一个段可以平移填充其它的段。猜测所有合法的串都可以通过这两种方式缩到单独一个 $1$，可以发现是正确的。 但是这里还有个问题是一个串 $S$ 可能有多个方案缩到 $1$，解决办法是你可以钦定上面的两种操作要交替进行，这样就可以保证一种操作唯一对应一种串了。倒着看这个过程，发现可以描述为：初始有 $n=m=1$，可以交替进行下面的操作：将 $n$ 变为 $n$ 的倍数（对应了前面的第一种操作，倒着看相当于把自己复制若干份），将 $m$ 变为 $m$ 的倍数（对应了前面的第二种操作），问将 $n,m$ 变为输入的值的不同操作序列个数。 因为是交替进行的，所以 $n,m$ 可以分开看，当作两个相同的子问题。现在要解决的问题相当于是，给定一个数 $n$，对所有的 $x$ 求恰好进行了 $x$ 次乘法把 $1$ 乘到 $n$ 的方案数（不能乘 $1$）。考虑变成自己的倍数相当于是选若干个质因子过来，所以还可以看成是，有 $L$ 种小球，每种小球有 $a_i$ 个且同种球之间不区分，对每个 $x$ 求将这些小球装到 $x$ 个盒子里且没有盒子为空的方案数。考虑容斥，计算钦定 $i$ 个盒子为空的方案数 $g_i$，则可以二项式反演得到恰好使用 $i$ 个盒子的方案数 $f_i$，求 $g_i$ 只需要对每种小球分别隔板法乘起来即可，令 $N=\sum a_i$ 则这样最后的时间复杂度为 $O(N^2)$。 考虑进一步优化，首先不同的 $a_i$ 只有 $O(\sqrt N)$ 种，于是每个 $g_i$ 可以直接算 $O(\sqrt N)$ 次组合数的快速幂乘起来得到。其次二项式反演的过程显然可以 NTT 加速，也就是看成两个 EGF 乘起来。可以证明最后的总复杂度为 $O(N\sqrt N)$。 ### C Ad-hoc 交互题，不做。 ## Day 8 哈哈哈又坠机了，做了一整场 T1 不会，后两题没看。 听讲题发现我的思路其实和 dX 是高度一致的啊，看上去他想到的我也都在想，但是我真的没编出来最后一步/ll/ll。 ### A 考虑先把 $a,b$ 排序，这样如果确定了赢的人集合 $S$，则一定是这 $|S|$ 个人和 $b$ 的前 $|S|$ 小去匹配，剩下的再从小往大匹配。 于是枚举 $|S|$ 后就可以直接设计出一个 dp：$f_{i,j}$ 表示前 $i$ 个数已经有 $j$ 个人加入了 $S$ 的方案数。转移枚举 $i$ 是否加入 $S$ 即可做到 $O(1)$，所以说我们能 $O(n^2)$ 算一个 $|S|$，最后的复杂度是 $O(n^3)$。 考虑优化，上面的做法复杂度高的原因是 dp 转移的时候需要知道 $|S|$（否则如果 $i$ 不加入 $S$ 不知道和谁匹配），导致每个 $|S|$ 都需要重新跑一遍 dp。这时候容易想到的是尝试倒着 dp，设 $g_{i,j}$ 表示考虑了后 $i$ 个人有 $j$ 个人没有加入 $S$，发现这时候 $i$ 不加入 $S$ 确实知道该和谁匹配了，但是如果加入 $S$ 又什么都不知道了，问题棘手了起来。 最后是怎么解决的呢？同样还是枚举 $|S|=x$，我们找到最大的 $p$ 使得 $a_p<b_x$，以 $p$ 为分界线将序列分为 $[1,p]$ 和 $[p+1,n]$，我们发现 $[p+1,n]$ 内的 $a_i$ 可以自由地打过 $[1,p]$ 内的 $b_j$，同理 $[1,p]$ 内的 $a_i$ 可以自由地打不过 $[p+1,n]$ 内的 $b_j$，这样可以考虑上面对前后缀 dp 时如果 $i$ 选择不加入/加入 $S$ 则不再考虑是否合法，将 $p$ 两侧的 dp 拼起来卷积即可统计答案，复杂度优化到 $O(n^2)$。 这真是人能想到的？？ ### B 神秘构造题，不做。 ### C 如果确定了最终的 $x$ 是啥，首先我们要求 $x$ 二进制下必须有区间最大值的最高位，区间内 $\le x$ 的数一定可以通过一次操作解决，$>x$ 的数则需要两次解决，所以我们只需要最小化 $\min(x+\sum[a_i>x])$ 即可。于是这里就有了一些魔怔莫队做法，使用回滚莫队好像可以直接做到单根号，但是正解无关。 形式有点像二分图匹配，考虑变成最大化 $\max(\sum[a_i\le x]-x)$，这样就变成了类似 Hall 定理的式子。Hall 定理告诉我们左部点最小失配数是 $\max(|S|-|N(S)|)$，考虑构建一张左部点为序列右部点为值域的二分图，左边的 $i$ 向右部的 $j$ 连边当且仅当 $j\le a_i$，则可以发现上面的式子正好就是左部点最小失配数，因为确定 $|N(S)|$ 为 $x$ 后 $\le x$ 的 $a_i$ 全选上并不会扩大 $N(S)$。 因为这张二分图左部点只会连向右部点的一个前缀，所以我们可以按照任意顺序贪心匹配，也就是找最大的能匹配的点。不妨假设我们贪心的顺序是从右往左，那我们按相反方向从左往右对 $r$ 扫描线，加入 $r$ 时根据上面贪心优先给 $r$ 匹配一定是对的。考虑再重新利用 Hall 定理维护匹配，如果加入 $r$ 后有 $\min(x-\sum[a_i\le x])\ge 0$ 则说明 $r$ 能找到一组没用过的匹配，直接加入即可。否则说明此时直接加入 $r$ 没得匹配，为了让 $r$ 匹配我们肯定要删去之前的一组匹配，找到最小的 $l$ 满足删去 $l$ 后 $\min(x-\sum[a_i\le x])\ge 0$ 即可，这个可以线段树简单维护。 如何在线回答询问？在加入 $r$ 时删除 $l$ 会对满足 $L\le l\land r\le R$ 的询问 $[L,R]$ 的失配数产生 $+1$ 的贡献，也就是矩形加单点查的形式，直接主席树做就好了，复杂度 $O(n\log n)$。实现时要注意因为我们要求 $x$ 包含区间内的最高位，我们要对每一位分开做。