UVa 1322 Minimizing Maximizer

题目描述Chris Ltd.\texttt{Chris Ltd.}Chris Ltd.公司正在开发一种新的排序硬件Maximizer\texttt{Maximizer}Maximizer。该硬件有nnn个输入编号从111到nnn每个输入是一个整数。硬件只有一个输出表示当前输入中的最大值。Maximizer\texttt{Maximizer}Maximizer的实现方式是一个由mmm个排序器Sorter\texttt{Sorter}Sorter组成的管道。每个排序器Sorter(i,j)Sorter(i, j)Sorter(i,j)会对输入的第iii到第jjj个位置上的值进行非递减排序其他位置的值保持不变。所有排序器依次连接最后一个排序器的第nnn个输出就是Maximizer\texttt{Maximizer}Maximizer的输出。现在发现某些排序器可以从管道中移除而Maximizer\texttt{Maximizer}Maximizer仍然能够对所有可能的输入数据给出正确结果。问题是在保持正确性的前提下最短的排序器子序列的长度是多少输入第一行是测试用例数量ttt之后每个测试用例格式如下第一行两个整数nnn和mmm2≤n≤500002 \le n \le 500002≤n≤500001≤m≤5000001 \le m \le 5000001≤m≤500000接下来mmm行每行两个整数iki_kik​和jkj_kjk​1≤ikjk≤n1 \le i_k j_k \le n1≤ik​jk​≤n表示第kkk个排序器的参数。输出对每个测试用例输出一个整数表示最短子序列的长度。测试用例之间输出一个空行。题目分析我们需要选择排序器的一个子序列保持原有顺序使得对于所有可能的输入值组合最终第nnn个输出都是正确的最大值。问题转化考虑最大值从输入位置111出发最终到达输出位置nnn的过程。每个Sorter(i,j)Sorter(i, j)Sorter(i,j)的作用是如果最大值当前位于区间[i,j][i, j][i,j]内的某个位置那么经过这个排序器后最大值会被移到位置jjj因为排序后最大值在区间的最后。因此排序器可以看作是将最大值从某个小于等于jjj的位置“推送”到位置jjj的工具。更精确地如果我们定义状态dp[x]dp[x]dp[x]表示将最大值从位置111传递到位置xxx所需的最少排序器数量。那么对于每个Sorter(i,j)Sorter(i, j)Sorter(i,j)如果最大值已经到达某个位置p∈[i,j−1]p \in [i, j-1]p∈[i,j−1]那么通过这个排序器最大值就可以到达位置jjj。因此我们可以用dp[p]1dp[p] 1dp[p]1去更新dp[j]dp[j]dp[j]其中p∈[i,j−1]p \in [i, j-1]p∈[i,j−1]。由于我们要求的是最少数量所以应该取dp[i],dp[i1],…,dp[j−1]dp[i], dp[i1], \dots, dp[j-1]dp[i],dp[i1],…,dp[j−1]中的最小值再加111来更新dp[j]dp[j]dp[j]。动态规划方程初始化dp[1]0dp[1] 0dp[1]0最大值已经在位置111时不需要任何操作dp[2…n]∞dp[2 \dots n] \inftydp[2…n]∞对于每个排序器(i,j)(i, j)(i,j)dp[j]min⁡(dp[j], min⁡{dp[i],dp[i1],…,dp[j−1]}1) dp[j] \min(dp[j],\ \min\{dp[i], dp[i1], \dots, dp[j-1]\} 1)dp[j]min(dp[j],min{dp[i],dp[i1],…,dp[j−1]}1)我们需要按输入顺序依次处理排序器因为子序列必须保持原顺序。算法设计直接按照上述方程实现复杂度为O(m⋅(j−i))O(m \cdot (j-i))O(m⋅(j−i))在n,mn, mn,m很大时会超时。注意到我们需要频繁查询区间[i,j−1][i, j-1][i,j−1]内dpdpdp值的最小值因此可以使用线段树来维护dpdpdp数组将每次查询和更新的复杂度降到O(log⁡n)O(\log n)O(logn)。算法步骤初始化线段树将dp[1]dp[1]dp[1]设为000其余设为无穷大。依次读入每个排序器(i,j)(i, j)(i,j)在线段树上查询区间[i,j−1][i, j-1][i,j−1]的最小值minVal。如果minVal 1 dp[j]则更新dp[j]minVal1dp[j] minVal 1dp[j]minVal1并在线段树上更新位置jjj的值。最终dp[n]dp[n]dp[n]就是答案。注意由于排序器可能以任意顺序给出且iii可能大于jjj需要先确保iji jij。复杂度分析时间复杂度O(mlog⁡n)O(m \log n)O(mlogn)其中mmm是排序器数量nnn是输入数量。空间复杂度O(n)O(n)O(n)主要用于线段树和dpdpdp数组。代码实现// Minimizing Maximizer// UVa ID: 1322// Verdict: Accepted// Submission Date: 2026-01-02// UVa Run Time: 0.270s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF1e9;constintMAX_N50005;intdp[MAX_N];intsegTree[4*MAX_N];// 更新线段树将位置 idx 的值设为 valuevoidupdate(intnode,intleft,intright,intidx,intvalue){if(leftright){segTree[node]value;return;}intmid(leftright)/2;if(idxmid)update(node*2,left,mid,idx,value);elseupdate(node*21,mid1,right,idx,value);segTree[node]min(segTree[node*2],segTree[node*21]);}// 查询区间 [ql, qr] 的最小值intquery(intnode,intleft,intright,intql,intqr){if(qrleft||qlright)returnINF;if(qlleftrightqr)returnsegTree[node];intmid(leftright)/2;returnmin(query(node*2,left,mid,ql,qr),query(node*21,mid1,right,ql,qr));}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;while(t--){intn,m;cinnm;// 初始化 dp 数组for(inti1;in;i)dp[i]INF;dp[1]0;// 初始化线段树for(inti0;i4*MAX_N;i)segTree[i]INF;update(1,1,n,1,0);for(intk0;km;k){inti,j;cinij;if(ij)swap(i,j);// 确保 i j// 查询 dp[i] 到 dp[j-1] 的最小值intminValquery(1,1,n,i,j-1);if(minVal1dp[j]){dp[j]minVal1;update(1,1,n,j,dp[j]);}}coutdp[n]\n;if(t)cout\n;// 测试用例之间输出空行}return0;}总结本题的关键在于将硬件正确性问题转化为一个区间覆盖的动态规划问题并利用线段树高效维护区间最小值。通过维护dp[x]dp[x]dp[x]表示最大值到达位置xxx所需的最少排序器数量我们可以在O(mlog⁡n)O(m \log n)O(mlogn)时间内求出答案。注意处理输入顺序和边界条件以及测试用例之间的输出格式即可。