UVa 12384 Span

题目描述给定一个包含nnn个整数的数组X1≤i≤nX_{1 \leq i \leq n}X1≤i≤n​定义数组XXX的spanSSS为一个长度为nnn的整数数组其中SiS_iSi​表示在XiX_iXi​之前包括XiX_iXi​自身连续满足所有元素都≤Xi\leq X_i≤Xi​的最大元素个数。数学表示如下Si∣Ai∣,Ai{j≤i∣∀k(j≤k≤i) (Xk≤Xi)}. S_i |A_i|, \quad A_i \{j \leq i \mid \forall k (j \leq k \leq i) \ (X_k \leq X_i)\}.Si​∣Ai​∣,Ai​{j≤i∣∀k(j≤k≤i)(Xk​≤Xi​)}.例如X[40,2,10,50,30,15]X [40,2,10,50,30,15]X[40,2,10,50,30,15]的span为S[1,1,2,4,1,1]S [1,1,2,4,1,1]S[1,1,2,4,1,1]。本题的特殊设定是XiPi mod mX_i P_i \bmod mXi​Pi​modm其中PiP_iPi​是第iii个素数。我们需要计算SSS的所有元素之和模mmm的结果。输入格式第一行一个整数TTT表示测试用例个数。接下来TTT行每行两个整数n,mn, mn,m满足1≤n,m≤1051 \leq n, m \leq 10^51≤n,m≤105。输出格式对于每个测试用例输出一行一个整数(∑i1nSi) mod m\left(\sum_{i1}^n S_i\right) \bmod m(∑i1n​Si​)modm。样例输入3 7 10 10 16 10 7实际格式应为每行两个数这里只是紧凑写法样例输出0 5 6题目分析1. 直接计算的复杂度若直接按照定义计算SiS_iSi​需要向前扫描直到遇到一个大于XiX_iXi​的数时间复杂度O(n2)O(n^2)O(n2)当nnn达到10510^5105时不可接受。2. 素数的获取我们需要前nnn个素数。第10510^5105个素数大约是1.3×1061.3 \times 10^61.3×106因此可以预先用埃氏筛Sieve of Eratosthenes\texttt{Sieve of Eratosthenes}Sieve of Eratosthenes生成2×1062 \times 10^62×106以内的所有素数并存储到全局数组中。由于TTT最多可能为10510^5105必须只预处理一次。3.Span的计算优化观察SiS_iSi​的含义它等于从iii向左数直到遇到第一个大于XiX_iXi​的元素为止这中间的元素个数包括XiX_iXi​自己。这是一个经典的左边第一个更大元素问题可以用单调栈在O(n)O(n)O(n)时间内解决。具体方法维护一个单调递减栈栈内元素的值从栈底到栈顶严格递减。遍历i0…n−1i 0 \dots n-1i0…n−1当栈非空且栈顶元素的值≤Xi\leq X_i≤Xi​时弹出栈顶因为这些元素无法成为比XiX_iXi​大的左边界。如果栈为空说明左边所有元素都≤Xi\leq X_i≤Xi​则Sii1S_i i 1Si​i1。否则栈顶元素的下标jjj是左边第一个大于XiX_iXi​的元素则Sii−jS_i i - jSi​i−j。将iii入栈。这个过程保证了每个元素最多入栈和出栈一次因此总复杂度O(n)O(n)O(n)。4. 模运算的注意点最终需要输出totalSum mod mtotalSum \bmod mtotalSummodm。注意totalSumtotalSumtotalSum可能很大最大约n2n^2n2级别应使用646464位整数如long long\texttt{long long}long long累加避免溢出。解题思路整体流程预处理素数使用埃氏筛生成2×1062 \times 10^62×106以内的所有素数存入全局数组primes\texttt{primes}primes。对每个测试用例读取n,mn, mn,m。取前nnn个素数对mmm取模得到数组XXX。使用单调栈计算SiS_iSi​并累加求和。输出sum mod msum \bmod msummodm。为什么素数范围取2×1062 \times 10^62×106第10510^5105个素数约为129970912997091299709因此2×1062 \times 10^62×106足够生成前10510^5105个素数且不会造成过多的时间开销。时间复杂度筛法O(Llog⁡log⁡L)O(L \log \log L)O(LloglogL)其中L2×106L 2 \times 10^6L2×106。每个测试用例O(n)O(n)O(n)。总复杂度O(Llog⁡log⁡L∑n)O(L \log \log L \sum n)O(LloglogL∑n)在10510^5105级别内可接受。空间复杂度素数列表约10510^5105个整数。每个测试用例临时数组XXX和SSSO(n)O(n)O(n)。实现细节使用vectorbool\texttt{vectorbool}vectorbool进行布尔标记以节省内存。使用stackint\texttt{stackint}stackint存储下标维护单调性。输入输出使用scanf\texttt{scanf}scanf/printf\texttt{printf}printf提高效率。累加和用long long\texttt{long long}long long类型。代码实现// Span// UVa ID: 12384// Verdict: Accepted// Submission Date: 2026-05-25// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 全局素数列表vectorintprimes;// 埃氏筛生成所有不超过 limit 的素数voidsieve(intlimit){vectorboolisPrime(limit1,true);isPrime[0]isPrime[1]false;for(inti2;ilimit;i){if(isPrime[i]){primes.push_back(i);if((longlong)i*ilimit){for(intji*i;jlimit;ji)isPrime[j]false;}}}}intmain(){// 预先生成足够多的素数第 100000 个素数约 1299709取 2e6 安全constintMAX_PRIME_LIMIT2000000;sieve(MAX_PRIME_LIMIT);intT;scanf(%d,T);while(T--){intn,m;scanf(%d %d,n,m);// 步骤1生成 X 数组vectorintX(n);for(inti0;in;i)X[i]primes[i]%m;// 步骤2单调栈计算 spanvectorintS(n);stackintst;// 存下标维护 X[st] 递减longlongtotalSum0;for(inti0;in;i){while(!st.empty()X[st.top()]X[i])st.pop();if(st.empty())S[i]i1;elseS[i]i-st.top();st.push(i);totalSumS[i];}// 输出 sum % mprintf(%lld\n,totalSum%m);}return0;}总结本题综合了素数筛法与单调栈两个经典算法。关键在于一次性预处理素数避免重复计算。利用单调栈将span的计算从O(n2)O(n^2)O(n2)优化到O(n)O(n)O(n)。注意累加和的数据范围防止溢出。掌握这些技巧后不仅能解决本题也能应对许多与 “左边第一个更大 / 更小元素” 相关的题目。