企业官网建设流程全解析

题目描述

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和mmm（2≤n≤500002 \le n \le 500002≤n≤50000，1≤m≤5000001 \le m \le 5000001≤m≤500000）
• 接下来mmm行：每行两个整数iki_kik​和jkj_kjk​（1≤ik<jk≤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[i+1],…,dp[j−1]dp[i], dp[i+1], \dots, dp[j-1]dp[i],dp[i+1],…,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[i+1],…,dp[j−1]}+1) dp[j] = \min(dp[j],\ \min\{dp[i], dp[i+1], \dots, dp[j-1]\} + 1)dp[j]=min(dp[j],min{dp[i],dp[i+1],…,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)。

算法步骤

1. 初始化线段树，将dp[1]dp[1]dp[1]设为000，其余设为无穷大。
2. 依次读入每个排序器(i,j)(i, j)(i,j)：
   • 在线段树上查询区间[i,j−1][i, j-1][i,j−1]的最小值minVal。
   • 如果minVal + 1 < dp[j]，则更新dp[j]=minVal+1dp[j] = minVal + 1dp[j]=minVal+1，并在线段树上更新位置jjj的值。
3. 最终dp[n]dp[n]dp[n]就是答案。

注意：由于排序器可能以任意顺序给出，且iii可能大于jjj，需要先确保i<ji < ji<j。

复杂度分析

• 时间复杂度：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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintINF=1e9;constintMAX_N=50005;intdp[MAX_N];intsegTree[4*MAX_N];// 更新线段树：将位置 idx 的值设为 valuevoidupdate(intnode,intleft,intright,intidx,intvalue){if(left==right){segTree[node]=value;return;}intmid=(left+right)/2;if(idx<=mid)update(node*2,left,mid,idx,value);elseupdate(node*2+1,mid+1,right,idx,value);segTree[node]=min(segTree[node*2],segTree[node*2+1]);}// 查询区间 [ql, qr] 的最小值intquery(intnode,intleft,intright,intql,intqr){if(qr<left||ql>right)returnINF;if(ql<=left&&right<=qr)returnsegTree[node];intmid=(left+right)/2;returnmin(query(node*2,left,mid,ql,qr),query(node*2+1,mid+1,right,ql,qr));}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cin>>t;while(t--){intn,m;cin>>n>>m;// 初始化 dp 数组for(inti=1;i<=n;i++)dp[i]=INF;dp[1]=0;// 初始化线段树for(inti=0;i<4*MAX_N;i++)segTree[i]=INF;update(1,1,n,1,0);for(intk=0;k<m;k++){inti,j;cin>>i>>j;if(i>j)swap(i,j);// 确保 i < j// 查询 dp[i] 到 dp[j-1] 的最小值intminVal=query(1,1,n,i,j-1);if(minVal+1<dp[j]){dp[j]=minVal+1;update(1,1,n,j,dp[j]);}}cout<<dp[n]<<"\n";if(t)cout<<"\n";// 测试用例之间输出空行}return0;}

总结

本题的关键在于将硬件正确性问题转化为一个区间覆盖的动态规划问题，并利用线段树高效维护区间最小值。
通过维护dp[x]dp[x]dp[x]表示最大值到达位置xxx所需的最少排序器数量，我们可以在O(mlog⁡n)O(m \log n)O(mlogn)时间内求出答案。
注意处理输入顺序和边界条件，以及测试用例之间的输出格式即可。