DEC
GOLD - A - Paired Up G
- 有 \(n\) 只奶牛，第 \(i\) 只在位置 \(x_i\)，有重量 \(y_i\)。
- 求在满足匹配要求的情况下，非匹配的奶牛的重量之和的 最大/最小 值。
- 两只奶牛能匹配，当且仅当 \(|x_i-x_j|\leq k\)。
- 匹配必须的极大的，也就是说，不能存在两只非匹配奶牛能匹配。
- \(n\leq 10^5,x_i\leq 10^9,y_i\leq 10^4\)。
将大小分开讨论，得到两种不同方法，同时均异常清晰。
首先问题可以独立的划分为几个子问题，每个子问题都是满足 \(x_i-x_{i-1}\leq k\) 的极长子链。
对于最小化，如果链长为偶数直接相邻匹配，答案为 \(0\)，否则枚举每个位置能否成为唯一一个非匹配的奶牛即可。
对于最大化，考虑一个简单的 DP，设 \(f(i,j)\) 表示考虑了前 \(i\) 只奶牛，有 \(j\) 只非匹配的奶牛时的最大值。
令 \(p\) 表示极右的满足 \(x_i-x_p>k\) 的奶牛，如果两者能够成为相邻两个被钦定为非匹配的奶牛的话，转移就是：
\[f(i,j)=\max(f(i-1,j),f(p,j-1)+y_i) \]否则只有 \(f(i,j)=f(i-1,j)\)。
判定能否被钦定，就是相邻两个匹配划分，可能会让 \(i-1\) 与 \(i+1\) 匹配。
容易注意到唯一影响判定的是 \(j\) 的奇偶性，所以第二维就可以优化成 \(0/1\) 了，问题迎刃而解。
GOLD - B - HILO G
- 给定一个 \(n\) 排列，以此为策略做猜数，会回答
LO（小了）或者HI（大了）。 - 要猜的数字为 \(x+0.5(x\in[0,n])\)，无用的猜测会跳过（例如猜 \(x\) 得到回答
LO，那就不会再猜 \(<x\) 的数）。 - 对于 \(n+1\) 个可能的 \(x\)，分别求出最终得到的回答序列中，
HILO的个数。 - \(n\leq 2\times 10^5\)。
看上去特别难想的题目，实际只要一个点。
这个过程可以类比二分的过程，如果顺序枚举排列，那么这个数会被猜的只会是一个区间。
并且，它会把这个区间劈成两半，一边是回答 HI，一边是 LO。
直接用 set 维护，劈 \(n\) 次就恰好得到了 \(n+1\) 个长度为 \(1\) 的区间，时间复杂度 \(O(n\log n)\)。
实际上，可以做的更好，观察猜测过程，实际就是在笛卡尔树上走的过程。
如果把序列后面拼 \(n+1\) 个 \(x+0.5\)，然后以 下标为堆，权值为 BST，建立笛卡尔树。
那么，每个答案点的询问序列就是它到根的路径，直接统计即可，时间复杂度 \(O(n)\)。
GOLD - C - Bracelet Crossings G
- 是用 \(m\) 条直线穿过平面内 \(n\) 个不同图形。
- 每个图形边界只出现 \(0/2\) 次，求是否有可能每个图形都是简单闭合图形，且边界均不相交。
- \(n,m\leq 50\)。
直接模拟判断即可，讨论起来不是很复杂：
- 每次的颜色序列是括号序列。
- 每种颜色的出现时刻是一个连续段。
- 每两种颜色的图形时刻只会是四种关系之一，不能改变：包含、被包含、上方、下方。
- 若 \(a\) 包含 \(b\)，那么 \(a\) 的出现时间不晚于 \(b\)，消失时间不早于 \(b\)。
最后一个比较难考虑到，代码不难写。
Platinum - A - Tickets P
- 有 \(n\) 个售票站，\(m\) 种票。
- 第 \(i\) 种票在 \(c_i\) 站售出，价格为 \(p_i\)，购买之后能够任意穿梭于 \([a_i,b_i]\) 售票站。
- 只有到一个售票站才能买那里的票，自此之后，可以任意时刻到达已买的票的区间。
- 对每个 \(i\in[1,n]\)，求从它出发，能到达 \(1\) 和 \(n\) 的最小代价，或判断无解。
- \(n,m\leq 10^5\)。
建图是比较自然的事情，显然是线段树优化建图。对于票 \(i\)，建有向边 \((c_i,\text{Id}_i,p_i),(\text{Id}_i,[a_i,b_i],0)\)。
要求能到达 \(1\) 和 \(n\)，那就将边全部反向，分别求从 \(1\) 和 \(n\) 出发的最短路。
但是直接相加显然得不到好处，可能会出现重复买票的情况。
处理也比较简单，就是将所有点赋值为两次最短路的和，然后再次用 Dijkstra 松弛。
最小的路径一定是没有重复买票的，也显然不可能不存在不重复买票的路径。
Platinum - B - Paired Up P
- 和 G 的 T1 类似。只是有两种牛，只有不同种的牛可以匹配。要求的东西和其它限制条件也是一样的。
- \(n\leq 5000\)。
此时可以接受 \(O(n^2)\) 的解。
对于最小化，转化成 总和 - 最大匹配和，同样的不会出现交叉匹配，所以直接 DP 即可，最大匹配一定是极大匹配，所以正确。
对于最大化，暴力思路很简单，设 \(f(i,j,k)\) 表示两种分别到了 \(i,j\)，最后一只未匹配的牛是 \(k\)。
想要新加入的牛不匹配，需要满足二者其一：\(k\) 与其同种，或 \(k\) 与它的距离大于限制。
想要优化，只能在 \(k\) 这一维下功夫，考虑钦定而非记录。
设 \(f(i,j,0/1)\) 表示考虑了第 \(1\) 种牛的前 \(i\) 只和第 \(2\) 种牛的前 \(j\) 只，当前钦定保留的是哪种牛。
有转移：
- \(f(i,j,0)\to f(i+1,j,0)+wx_{i+1}\)。
- \(f(i,j,1)\to f(i,j+1,1)+wy_{j+1}\)。
- 若 \((i+1,j+1)\) 能匹配，\(f(i,j,*)\to f(i+1,j+1,*)\)。
这是根据状态的定义可以直观得到的 3 种转移。
考虑钦定之间的替换，如果当前是 \(f(i,j,*)\)，那么转移必须是一路匹配。
直至 \(j'\) 到 \(i\) 的距离 \(>k\)，也就是没有能够与 \(i\) 匹配且被保留的不同种牛出现。
找到最近的 \((i',j')\) 和判断能否一路匹配都可以通过预处理求出。
Platinum - C - HILO P
- 和 G 的 T2 类似，但是变为已知 \(x+0.5\)，求所有排列出现的
HILO之和。 - \(n\leq 5000\)。
很妙的状态设计。
首先需要有一个积累，就是因为排列的高度对称和等可能性，这种问题等价于求期望再 \(\times n!\)。
往往期望是比计数好求的，这道题有十分直观的体现。
设 \(f(i,j,0/1)\) 表示，比 \(x\) 低的还有 \(i\) 个数可以问，比 \(x\) 高的还有 \(j\) 个可以问，上一次询问回答是 LO/HI 的答案。
答案显然就是 \(f(x,n-x,0)\)，DP 顺序实际上逆序了这个过程，有比较显然的转移方程：
\[\displaystyle f(i,j,0)=\frac{\displaystyle \sum_{0\leq i'<i} f(i',j,0)+\sum_{0\leq j'<j} f(i,j',1)}{i+j} \]\[\displaystyle f(i,j,1)=\frac{\displaystyle \sum_{0\leq i'<i} f(i',j,0)+\sum_{0\leq j'<j} f(i,j',1)}{i+j}+\frac{i}{i+j} \]可前缀和优化。
JAN
GOLD - A - Drought G
- 求满足条件的长度为 \(n\) 的序列的个数：
- 每个位置给定上届 \(h_i\)，即 \(a_i\in [0,h_i]\)。
- 可以通过任意次相邻两个数 \(-1\) 将序列变换为全部相同。
- \(n\leq 100, h_i\leq 1000\)。
思考方向全在充要条件上，完全没观察数据范围。
弄了半天，唯一有点用的结论是：
-
如果 \(N\) 为偶数，符合条件的序列得到的结果可以是任意 \(\leq \text{Mx}\) 的数字，\(\text{Mx}\) 指最大最终序列值。
-
如果 \(N\) 为奇数，且它符合条件，那么最终局面唯一。
实际上很简单，值域这么小就是要你过题的，直接考虑 \(O(NV^2)\) 的做法。
对于奇数枚举最终的 \(a\)，偶数钦定 \(0\) 即可。
然后把数字都 \(-a\)，\(f(i,j)\) 表示前 \(i\) 个，\(1\sim i-1\) 被消成了 \(0\)，第 \(i\) 个剩余为 \(j\)。
显然第 \(i\) 个的剩余数字必须全部被 \(i+1\) 消掉，所以就有：
\[\displaystyle f(i,j)=\sum_{j+k\leq h_i} f(i-1,k) \]前缀和优化即可，最终答案就是 \(f(n,0)\)，都是显然的。
GOLD - B - Farm Updates G
- 给定 \(n\) 个农场，初始时都是开放的，\(Q\) 个时间点有操作：
- 使一个农场不开放。
- 在两个开放的农场之间添加双向一条边。
- 删除之前添加的某一条边。
- 对每个农场，求它能到达至少一个不是它自己的开放的农场的最晚时刻。
- \(n\leq 10^5,q\leq 2\times 10^5\)。
一开始没看到第二个限制，想了一大堆线段树分治，LCT 什么的。
实际上直接倒序做，遇到操作二可以无视，因为完全不改变是否开放的状况。
相当于只加边不删边，直接维护连通块，拿 set 维护当前集合，启发式合并即可。
实际上这样很蠢，每干掉一个集合，它之中的数就用不到了。
直接 bfs 一边，把访问过的标记一下，就可以做到 \(O(n)\)，所以这是普及题 QwQ
GOLD - C - Tests for Haybales G
- 构造满足要求的序列：
- \(0\leq x_1\leq x_2\leq \cdots \leq x_N\)。
- 给定了 \(\text{Mx}_i\)，它是最大的满足 \(x_{j}\leq x_i+K\) 的下标 \(j\)。
- \(K\) 和序列都由你构造。
- \(n\leq 10^5,k,x_i\leq 10^{18}\)。
比较神的构造。发现 \(\leq\) 很不好用，将 \(\text{Mx}_i+1\) 并改成 \(<\)。
那么，考虑建边 \(\text{Mx}_i+1\to i\)，发现这是一棵以 \(N+1\) 为根，恰好 \(N\) 条边的连通树。
在树上，儿子节点 \(+K\) 需要严格 \(<\) 父亲。
而在同层，一定是编号连续的一段，且编号大的值也更大。
那么，考虑能否令每一层都有一个底数 \(K\times \text{dep}\)（这里的 \(\text{dep}\) 是从最底层开始的，即 \(n+1\) 的 \(\text{dep}\) 最大）。
然后每次层的树加上偏移量，发现确实可行。只需要满足：
- 同一层，编号大的偏移量大。
- 父亲的偏移量严格 \(>\) 儿子。
按照 bfs/dfs 序，每次先走最大编号的子节点，偏移量从大到小，都是可行的选择。
而 \(K\) 的取值只要严格大于偏移量的最大值即可，例如 \(N+1\)。
Platinum - A - Minimizing Haybales P
- 给定序列，每次可以交换其中大小相差不超过 \(K\) 的。
- 求能得到的序列中，字典序最小的。
- \(n\leq 10^5\)。
做法很多，这里说一个稍微科技一点的（LOJ 最劣解）。
实际上，这一类交换的题目，能得到的充要，都是不能交换的数对相对位置不变。
如果将所有点向它前面不能交换的点连边，相当于求最小字典序拓扑序。
这是一个熟悉的转化。
但是 它前面 和 不能交换 相当于二维偏序，普通的线段树优化建图不能支持。
这是后很自然的可以考虑到主席树优化建图，十分类似，唯一需要注意的点是 旧节点 要向 新建的节点 连边。
相当于是传递限制的方式。
最终拓扑排序的时候，\(>n\) 的主席树上虚节点优先即可。
Platinum - B - Counting Haybales P
- 给定一个序列，每次可以交换绝对值恰好为 \(1\) 的相邻位。
- 求可能的最终序列的方案数。
- \(n\leq 5000\)。
确实这种计数问题非常陌生。
实际上，还是可以图论建模（向相同 / 相差 > 1 的前面节点连边），得到一个 DAG。
相当于求不同拓扑排序数，对于一般 DAG 是无法统计的。
但观察性质，发现对奇偶分开讨论，同奇偶性的数字直接顺序固定，一定连出一条链。
那只需要和求最长公共子序列一样， 看每次连的边是否在另一个节点的前面即可，时间复杂度 \(O(N^2)\)。
Platinum - C - Multiple Choice Test P
- 给定 \(n\) 组向量，每组至少包含两个向量，由 \((x_i,y_i)\) 表示。
- 要求在每组中选择一个向量，使得向量总和距离原点最远。
- 向量总和 \(\leq 2\times 10^5\)。
科技题，对每组求凸包再启发式合并求闵可夫斯基和。
FEB
前置知识
高维前缀和，根据Oi Wiki的介绍。
设维度为 \(D\)，元素数为 \(U\)，那么支持在时间 \(O(DU)\)，空间 \(O(U)\) 下得到 \(f\) 的高维前缀/后缀和。
前缀和的伪代码，\(\text{state}'\) 表示在第 \(i\) 维比 \(\text{state}\) 少 \(1\) 的元素。
for state
sum[state] = f[state];
for i = 0 to D
for 从小到大枚举 state
if state 是第 i 维的极小元素 continue;
else sum[state] += sum[state']
后缀和是类似的，\(\text{state}'\) 表示在第 \(i\) 维比 \(\text{state}\) 多 \(1\) 的元素。
for state
sum[state] = f[state];
for i = 0 to D
for 从大到小枚举 state
if state 是第 i 维的极大元素 continue;
else sum[state] += sum[state']
GOLD - A - Redistributing Gifts G
- 有 \(n\) 个礼物，分给 \(n\) 个人，初始第 \(i\) 个人分得第 \(i\) 号礼物。
- 每个人有一个自己礼物排名（\(n\) 的排列），求有多少种重分礼物的方案，使得每个人得到的礼物不比原本的差。
- \(m\) 次询问，每次将人分成两组，要求此次询问同组之间才能交换。
- \(n\leq 18,m\leq 10^5\)。
每个人 \(i\) 向自己心目中排名在 \(i\) 前的连边，相当于求图环覆盖数量。
钦定环中编号最小的点为关键点，\(f(i,s)\) 表示当前在 \(i\)，已经经过了 \(s\) 集合，可以 \(O(n^22^n)\) 得到每个集合的成环方案数 \(g(s)\)。
再次钦定换中最小的点作为状态划分，可以 \(O(n^3)\) 得到每个集合的答案 \(h(s)\)。
GOLD - B - Cow Camp G
- 对一道题进行 \(k\) 次提交，这道题有 \(t\) 个测试点，除了第一个是样例必对外，其余点都有 \(1/2\) 的概率正确。
- 每次提交的得分为正确的测试点个数，求 \(k\) 次提交的得分最大值的期望。
- \(k\leq 10^9,t\leq 1000\)。
设 \(p_i\) 表示一次提交正确 \(i\) 个的概率，显然 \(\displaystyle p_0=0,p_1=1,p_i=\binom{t-1}{i-1}\times \frac{1}{2^{T-1}}\)。
设 \(f(i)\) 表示猜测 \(i\) 次的答案，有递推式：
\[\displaystyle f(i)=\sum_{j=1}^t p_i\times \max(i,f(i-1)) \]预处理 \(i\times p_i\) 的后缀和 \(g\)，以及 \(p_i\) 的前缀和 \(h\)，转移就是：\(f(i)=f(i-1)h(\lfloor f(i-1)\rfloor) + g(\lceil f(i-1)\rceil)\)。
发现 \(f\) 的值一定 \(<t\)，故转移系数只有 \(O(t)\) 次不同，二分 + 矩阵加速即可。
GOLD - C - Moo Network G
- 给定平面内 \(n\) 个点，两点间距离为欧几里得距离，求最小生成树。
- \(n\leq 10^5,x_i\leq 10^6,y_i\leq 10\)。
发现 \(y\) 这一维很小，同时发现考虑每个点对每一种 \(y\) 连边时，只需要考虑 \(x\) 的前驱和后继，于是暴力连 \(3n\) 条边即可。
Platinum - A - Paint by Rectangles P
- 给定平面内 \(n\) 个矩形，保证 \(x,y\) 均是 \(2n\) 的排列。
- 矩形的边界把平面划分成了多个区域，定义无穷大的区域为白色，然后将图黑白染色。
- 分别求出黑色区域和白色区域的数量。
感觉这种大胆设计算法的能力真的是天赋……
考虑扫描线，每次无论加入删除，均将区间内元素取反并均 \(+1\)。在删除时两端的颜色段会和外界合并，需要 \(-1\)。
多画几种情况，发现一个连通块最右侧结束时，最外侧的异色块会被多减恰好一次，需要加回来。
考虑用树状数组维护扫描线，用 set 维护同一连通块的补值。
Platinum - B - Sleeping in Class P
- 给定一个序列，每次可以：
- 合并相邻两个数，变成两者之和。
- 将一个数拆成两个正整数，它们的和为原数。
- \(m\) 次询问，求将序列变为全部是 \(q_i\) 的最小变换次数。
- \(n,m\leq 10^5,a_i,q_i\leq 10^{18}\)。
求一遍前缀和，有解的充要是 \(q_i|a_n\)。
再随便想个贪心结合样例，发现 \(\displaystyle Ans=n+\frac{a_n}{q_i}-2\sum_{i=1}^n[q_i|a_i]\)。
于是问题变为求序列中，是某个数倍数的数。
因为是 \(a_n\) 的约数，所以先 Pollard-Rho 把 \(a_n\) 分解。
然后变成了一个元素数和维数分别为 \(d(a_n)\) 与 \(\omega(a_n)\) 的高维前缀和，直接上科技就没了。
高维前缀和的严格 Hash 方法是将每一维看作一个进制位，每一位进制的上限可以不同。
Platinum - C - Phone Numbers P
- 有一个九键键盘，你为了快速输入可能会选择同时按下 \(1\times 2\) 或者 \(2\times2\) 的格子们。
- 但是你高估了自己的能力，同时按下的键会乱序排列。
- 给定最终得到的数字串，长度为 \(n\)，求可能的目标串个数。
- \(n\leq 10^5\)。
深刻理解，DP of DP 不仅需要 ”信仰状态跑不满“，更需要从各种角度出发寻找一些看似无用的剪枝，就像早期学习搜索一样。
考虑给定序列 \(a\) 如何判定 \(b\) 是否合法，设 \(f(i)\) 表示前缀 \(i\) 是否合法，它为 true 当且仅当：
- \(f(i-1)\) 合法，且 \(b_i=a_i\)。
- \(f(i-2)\) 合法，且 \(b_i,b_{i-1}\) 是 \(a_i,a_{i-1}\) 的排列，且数值上满足要求。
- \(f(i-4)\) 合法，且 \(b_{i-3}...b_i\) 是 \(a_{i-3}...a_i\) 的排列，且数值上满足要求。
看看压缩的状态，\(f(a,b,c,f_0,f_1,f_2,f_3)\) 总数 \(9^3\times 2^4\)……
发现可以直接用 \(f(a,b,c,d)\) 表示，如果对应不合法就记录特殊字符（例如 \(-1\)），降到 \(10^4\)……
当然显然合法状态数远小于这个值，但想通过还需要一个看似不起眼的可行性剪枝。
那就是如果仅考虑这 \(1/2/3\) 位与后面怎么结合都不合法就直接去掉，这样就能通过了，据说单位置状态峰值 \(\leq 50\)。
OPEN
GOLD - A - Apple Catching G
- 数轴上，某时刻某位置出现某数量 奶牛/苹果。
- 每只奶牛自出现开始，每时刻可以移动 \(1\) 单位长度。
- 苹果只能在出现时刻被接到，接到一个苹果的奶牛将离开，求最多能接到的苹果数。
- \(n\leq 2\times 10^5\)。
很巧妙的题目，赛时的思考是拆成两个不同的不等式分别贪心，但总找不到合理的贪心策略。
将题目可视化、平凡化的转换成几何模型是很有效的解题方法！
实际上，可以将 奶牛/苹果 表示成平面上 位置、时间的 \((x,t)\) 二元组。
奶牛 \(i\) 能接到苹果 \(j\) 的条件是：\(|x_i-x_j|\leq |t_i-t_j|,t_i\leq t_j\)。对应在平面上，就是 V 形的区域。
突发奇想，将每个点按照原点顺时针旋转 \(45\) 度， 坐标变为 \((\cfrac{t+x}{\sqrt 2},\cfrac{t-x}{\sqrt 2})\)。
好处是，区域变成了右上的矩形。同时将坐标 \(\times \sqrt 2\) 是不影响的，然后就是非常简单的贪心。
将所有苹果按照 \(x\) 升序排序，每次加入 $x\leq $ 它的奶牛，然后选择 \(y\) 最大的 $\leq $ 它的奶牛即可。
GOLD - B - Pair Programming G
- 定义表达式由两种运算构成：
- 乘法：\(\times d\)，其中 \(d\in[0,9]\)，是具体的数字。
- 加法：\(+s\)，其中 \(s\) 是一个从未出现过的变量名。
- 给定两个长度均为 \(n\) 的表达式，将它们归并，求本质不同的新表达式个数。
- \(n\leq 2000\)。
如果 \(\times 0\) 就把之前的运算清空，\(\times 1\) 直接忽略，剩下的不同种类运算顺序不同一定导致本质不同。
即唯一能导致重复的是相邻同级运算的交换。
考虑多记录 \(f(i,j,0/1)\) 表示上一次用的是 \(a_i\) 还是 \(b_j\)，钦定 \(0/1\) 转换的某个方向需要运算种类不同即可。
GOLD - C - Balancing a Tree G
- 每个点有权值范围，要求你钦定每个点的权值。
- 满足，全局的 \((i,j)\)（其中 \(i\) 是 \(j\) 的祖先）的 \(|a_i-a_j|\) 的最大值最小。
- \(n\leq 10^5,0\leq l_i\leq r_i\leq 10^9\)。
官方题解的做法很妙妙，再看这个解法感觉暴力多了。
先一手二分答案，设为 \(\lim\)。
然后想一个 naive 的贪心，考虑直接自底向上推，每次向上限制范围 \(|l-\lim,r+\lim|\)，每次求交，后再向上推。
但是，有可能当前值是由某一次的 \(l-\lim\) 扩展来的，此时再次 \(-\lim\) 扩展就出现了值域被错误的扩大的问题。
考虑这种情况出现的原因，是因为某个祖先和子孙的值域相差超过 \(\lim\)。
目的很明确，可以直接先从上往下收缩一次，把值域控制在较小的差中，再从下往上收缩一次即可。
输出方案也是类似的，在可选范围内任意钦定即可。
Platinum - A - 262144 Revisited P
- 给定序列，每次可以将相邻的两个数 \(x,y\) 合并成 \(\max(x,y)+1\)，求最终剩下的一个数最小是多少。
- 对给定序列的所有子区间均求答案。
- \(n\leq 2^{18}\)。
区间 DP 能轻松 \(O(n^3)\)，一手单调性就能做到 \(O(n^2)\)。
其余只能说待补吧。
Platinum - B - Hoof and Brain P
- 给定有向图，\(m\) 次询问，每次给出两个点 \(s,t\) 的初始位置。
- 每回合
B会指定一个点，H则需要选择它的一个出边并移动。 - 任意时刻如果两个点重合或被选择的点无法移动，那么
B胜利；反之如果游戏能无限进行下去，那么H胜利。 - 判断每次询问谁会胜利。
- \(n\leq 10^5,m\leq 2\times 10^5\)。
首先如果一个点不能走到某个环上那么是必输的，可以删除这些点。
然后考虑将出度为 \(1\) 的点和它出边指向的点合并，这样容易发现两个点会重合的充要条件是 \(s,t\) 属于同一点集。
洛谷题解区给出了 ”支配“ 的概念并引出了多个优美的性质，虽然感觉小题大做了但确实厉害（崇拜）。
只需要启发式合并 + map 就能做到两只 \(\log\)。
Platinum - C - Up Down Subsequence P
- 给定长度为 \(n\) 的排列和长度为 \(n-1\) 的要求序列。
- 要求为两个相邻位数字的大小关系。求选出一个子序列，使得能满足要求序列的某个前缀，求前缀的最长长度。
- \(n\leq 3\times 10^5\)。
容易设计一个 \(O(n^2)\) 的 DP，设 \(f(i,j)\) 表示考虑前 \(i\) 个位置，子序列长度为 \(j\)，最后一位的 最大/最小值。
如果要求是 U 就维护最小值，反之则是最大值。
考虑用两棵线段树分别动态维护 U 和 D 的序列，发现大小都是单调的，每次能更新的也都是对方的一个前缀，直接做就好了。