P9681 幽默的世界。 题解

· · 题解

前置知识

二分法

题意简述

给定一个长度为 n 的序列 a。q 次询问，每次询问给定 l,r，求满足以下条件的数对 (l',r') 个数。

数据范围

子任务 0

#### 子任务 1 $1\leqslant n,q\leqslant 50$，$1\leqslant l\leqslant r\leqslant n$，$-10^9\leqslant a_i\leqslant 10^9$。 #### 子任务 2 $1\leqslant n,q\leqslant 3000$，$1\leqslant l\leqslant r\leqslant n$，$-10^9\leqslant a_i\leqslant 10^9$。 #### 子任务 3 $1\leqslant n,q\leqslant 2\times 10^5$，$1\leqslant l\leqslant r=n$，$-10^9\leqslant a_i\leqslant 10^9$。 #### 子任务 4 $1\leqslant n,q\leqslant 2\times 10^5$，$1=l\leqslant r\leqslant n$，$-10^9\leqslant a_i\leqslant 10^9$。 #### 子任务 5 $1\leqslant n,q\leqslant 2\times 10^5$，$1\leqslant l\leqslant r\leqslant n$，$-10^9\leqslant a_i\leqslant 10^9$。 # 解题思路 ## 子任务 0 ### 做法 若 $n=4,q=3$，则答案分别为 $1,2,3$；若 $n=7,q=6$，则答案分别为 $1,2,4,0,2,1$。 ### 正确性证明 $n=4,q=3$ 的答案在 **样例输出 #1** 中给出，分别为 $1,2,3$；$n=7,q=6$ 的答案在 **样例输出 #2** 中给出，分别为 $1,2,4,0,2,1$。 ### 具体实现 判断 $n,q$ 的值。若 $n=4,q=3$，则输出三行三个整数，分别为 $1,2,3$；若 $n=7,q=6$，则输出六行六个整数，分别为 $1,2,4,0,2,1$。 ### 时间复杂度分析 输出一次，复杂度为 $O(1)$，可以通过 **子任务 0**。 ### 参考核心代码 ```cpp if(n==4&&q==3) printf("1\n2\n3"); if(n==7&&q==6) printf("1\n2\n4\n0\n2\n1"); ``` ### 期望得分 $0$ 分。 ## 子任务 1 ### 做法 对于每次询问，枚举所有可能的 $(l',r')$。根据定义，检查 $\displaystyle\sum_{i=l'}^{r'}a_i$ 是否大于 $0$。若 $\displaystyle\sum_{i=l'}^{r'}a_i\leqslant0$，则该 $(l',r')$ 不符合题意。并枚举该区间内所有可能的 $x$ 和 $y$，判断是否有 $l'\leqslant x\leqslant y\lt r',\displaystyle\sum_{i=x}^ya_i\leqslant0$。若存在一个 $(x,y)$，满足 $\displaystyle\sum_{i=x}^ya_i\gt0$，则该 $(l',r')$ 不符合题意。 最后可以求出所有符合题意的 $(l',r')$ 个数。 ### 正确性证明 由于我们每次枚举了 **所有可能的 $(l',r')$**，并**按照定义**，逐一检查了 $(l',r')$ 是否符合题意，因此该思路是正确的。 ### 具体实现 对于每次询问，使用两重循环枚举所有 $l\leqslant l'\leqslant r'\leqslant r$，并用一重循环计算 $\displaystyle\sum_{i=l'}^{r'}a_i$。若 $\displaystyle\sum_{i=l'}^{r'}a_i\leqslant0$，则该 $(l',r')$ 一定不合题意，跳过。再使用两重循环枚举所有 $l'\leqslant x\leqslant y\lt r'$，其中再使用一重循环，计算 $\displaystyle\sum_{i=x}^ya_i$，并判断是否存在 $\displaystyle\sum_{i=x}^ya_i\gt0$。若存在，则该 $(l',r')$ 一定不合题意。计算出符合题意的 $(l',r')$ 数量，并输出。 ### 时间复杂度分析 外层两重循环，内层分别有一重循环，以及两重循环嵌套一重循环，总共最多嵌套五重循环。每个循环复杂度为 $O(n)$，则回答一次询问，时间复杂度为 $O(n^5)$。 总时间复杂度 $O(qn^5)$，实测可以通过 **子任务 0** 和 **子任务 1**。 ### 参考核心代码 ```cpp for(i=l;i<=r;i++) for(j=i;j<=r;j++){//枚举所有(l',r') long long summ=0; for(k=i;k<=j;k++) summ+=a[k]; if(summ<=0)//求和，若小于0不合题意 continue; bool flg=true; for(x=i;x<j;x++) for(y=x;y<j;y++){//枚举区间内所有(x,y) summ=0; for(m=x;m<=y;m++) summ+=a[m]; if(summ>0){//若存在[x,y]区间和大于0，则不合题意 flg=false; break; } } if(flg) ans++;//若符合题意答案加1 ... printf("%d\n",ans); ``` ### 期望得分 $15$ 分。 ## 子任务 2 ### 做法 对于每次询问，枚举 **所有可能的 $r'$**。若 $a_{r'}\leqslant0$，则对于所有 $(l',r')$，该数对均 **不符合题意**。否则，我们 **二分** 出一个整数位置 $p\in[1,r']$，满足 $\displaystyle\sum_{i=p}^{r'}a_i\gt0\land\forall x\in \{p,p+1,p+2,\dots,r'-1\},a_x\leqslant 0$，且 $\displaystyle\sum_{i=p-1}^{r'}a_i\leqslant0\lor\exists x\in\{p-1,p,p+1,\dots,r'-1\},a_x\gt0$。此时得到的位置 $p$ 即为以 $r'$ 为右端点的所有数对 $(l',r')$ 中，**最小的 $l'$**。我们将 $\min(r'-p+1,r'-l+1)$ 加入答案。 枚举完所有 $r'\in[l,r]$，即可求出符合题意的 $(l',r')$ 个数。 ### 正确性证明 根据题意，符合题意的 $(l',r')$ 必须满足：$\forall l'\leqslant x\leqslant y\lt r'$，都有 $\displaystyle\sum_{i=x}^ya_i\leqslant0\implies\displaystyle\sum_{i=l'}^{r'-1}a_i\leqslant0$。 又知 $\displaystyle\sum_{i=l'}^{r'}a_i\gt0$，因此 $a_{r'}=\displaystyle\sum_{i=l'}^{r'}a_i-\displaystyle\sum_{i=l'}^{r'-1}a_i\gt0$。 所以，**$(l',r')$ 符合题意 $\implies a_{r'}\gt0$**。 故其逆否命题成立： **$a_{r'}\leqslant0\implies (l',r')$ 不符合题意**。 回到定义：$\forall l'\leqslant x\leqslant y\lt r'$，都有 $\displaystyle\sum_{i=x}^ya_i\leqslant0\implies\forall l'\leqslant x\lt r'$，都有 $a_x\leqslant0$。 所以，**$(l',r')$ 符合题意 $\implies\forall l'\leqslant x\lt r',a_x\leqslant0$**。 又根据定义，可以得到：**$(l',r')$ 符合题意 $\iff\displaystyle\sum_{i=l'}^{r'}a_i\gt0$**。 若 $\forall l'\leqslant x\lt r'$，都有 $a_x\leqslant 0$，则 $\forall l'\leqslant x\leqslant y\lt r'$，有 $\displaystyle\sum_{i=x}^ya_i=a_x+a_{x+1}+a_{x+2}+\cdots+a_y\leqslant0$。 综上所述： - **一个数对 $(l',r')$ 符合题意 $\iff$ $\forall l'\leqslant x\lt r',a_x\leqslant0$ $\land$ $\displaystyle\sum_{i=l'}^{r'}a_i\gt0$**。 - **$a_{r'}\gt0$ 是数对 $(l',r')$ 符合题意的必要条件**。 对于一个确定的 $r'$，记 $f(x)=\displaystyle\sum_{i=x}^{r'-1}[a_i\gt0],x\in\{1,2,\dots,r'-1\}$，则： $\forall x_1,x_2\in\{1,2,\dots,r'-1\},x_1\lt x_2$，都有 $$\begin{aligned} f(x_1)-f(x_2)&=\displaystyle\sum_{i=x_1}^{r'-1}[a_i\gt0]-\displaystyle\sum_{i=x_2}^{r'-1}[a_i\gt0]\\ &=\displaystyle\sum_{i=x_1}^{x_2-1}[a_i\gt0]\geqslant0 \end{aligned}$$ 即 $f(x_1)\geqslant f(x_2)$，因此 $f(x)$ 是 **非严格单调递减** 函数。 根据上述推理，$f(l')=0\implies$ 数对 $(l',r')$ 符合题意。由上述 **单调性** 证明，我们可以通过二分，找到满足 $f(l')=0$ 的最小的 $l'$。我们记这个位置为 $pos$。 对于一个确定的 $r'$ 及其对应的 $pos$，记 $g(x)=\displaystyle\sum_{i=x}^{r'}a_i,x\in\{pos,pos+1,\dots,r'\}$，则： $\forall x_1,x_2\in\{pos,pos+1,\dots,r'\},x_1\lt x_2$，都有 $$\begin{aligned} g(x_1)-g(x_2)&=\displaystyle\sum_{i=x_1}^{r'}a_i-\displaystyle\sum_{i=x_2}^{r'}a_i\\ &=\displaystyle\sum_{i=x_1}^{x_2-1}a_i \end{aligned}$$ $x_1,x_2-1\in\{pos,pos+1,\dots,r'-1\}\implies\forall i\in\{x_1,x_1+1,\dots,x_2-1\},a_i\leqslant0 即 $g(x_1)\leqslant g(x_2)$，因此 $g(x)$ 是 **非严格单调递增** 函数。 根据上述推理，$g(l')\gt0\implies$ 数对 $(l',r')$ 符合题意。由上述 **单调性** 证明，我们可以通过二分，找到满足 $g(l')\gt0$ 的最小的 $l'=p$。此时我们已经满足了数对 $(l',r')$ 符合题意的充要条件。 此时我们还没有考虑到询问区间的 $l$ 和 $r$。$r'\leqslant r$ 的约束已经满足。此时我们找到的 $l'$ 若大于等于 $l$，则符合题意。否则，**根据单调性**，取询问区间的 $l$，即为满足所有约束的最小的 $l'$。 因此答案的增加量为 $\min(r'-p+1,r'-l+1)$，思路正确。 ### 具体实现 我们预处理出 $sum_{1,i}=\displaystyle\sum_{j=1}^i[a_i\leqslant0]$，$sum_{2,i}=\displaystyle\sum_{j=1}^ia_i$。这一部分使用 **前缀和** 预处理。 对于每个询问，首先枚举 $r'\in[l,r]$，若 $a_{r'}\leqslant0$，则跳过该右端点。否则二分出位置 $p$： 设置初始位置左右端点 $L=1,R=r'$，当前位置中点 $mid=\lfloor\dfrac{L+R}{2}\rfloor$。判断此时的 $mid$ 是否满足：$\displaystyle\sum_{i=mid}^{r'-1}[a_i\leqslant0]=r'-mid\land\displaystyle\sum_{i=mid}^{r'}a_i\gt0$，即是否满足 $sum_{1,r'-1}-sum_{1,mid-1}=r'-mid\land sum_{2,r'}-sum_{2,mid-1}\gt0$。若 **满足**，则向 **更靠左** 的位置二分；否则，向 **更靠右** 的位置二分。 最终得到一个位置 $p$，则将答案增加 $\min(r'-p+1,r'-l+1)$。 枚举完所有的 $r'$，输出答案。 ### 时间复杂度分析 预处理前缀和，复杂度 $O(n)$。对于每个询问，枚举 $r'$，复杂度为 $O(n)$；二分出一个位置，复杂度为 $O(\log n)$。 总时间复杂度 $O(qn\log n)$，可以通过 **子任务 0**、**子任务 1** 和 **子任务 2**。 ### 参考核心代码 ```cpp for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; for(i=1;i<=n;i++) sum1[i]=sum1[i-1]+(a[i]<=0);//预处理两个前缀和 ... int ans=0; for(i=l;i<=r;i++){ if(a[i]<=0) continue;//若a[i]<=0一定不合题意 int lt=0,rt=i+1; while(lt+1!=rt){//二分出最小的l' int mid=(lt+rt)>>1; if(sum[i]-sum[mid-1]>0&&sum1[i-1]-sum1[mid-1]==i-mid)//判断条件，区间和大于0且[mid,i-1]中只能有非正数 rt=mid;//向左二分 else lt=mid; } ans+=min(i-rt+1,i-l+1);//注意要取min } printf("%d\n",ans); ``` ### 期望得分 $35$ 分。 ## 子任务 3 ### 做法 将所有询问 **离线**，并按照左端点 $l$ **降序排序**。将端点从 $n$ 向左扫，记开始扫之前答案为 $0$。设当前扫到了位置 $i$，若 $a_i>0$，则 **答案加 $1$**；否则，记位置 $p$ 为满足 $p>i$，且 $a_p>0$ 的第一个位置，若存在位置 $p$ 且有 $\displaystyle\sum_{j=i}^pa_j>0$，则 **答案加 $1$**；否则，**答案不变**。执行上述操作后，所有左端点 $l=i$ 的询问的答案即为当前答案。 扫完整个序列后，即可求出所有询问的答案。 ### 正确性证明 由于所有询问的 **右端点固定**，都为 $n$，因此我们可以只考虑左端点移动对答案的 **贡献**。由于我们可以按照左端点排序，因此我们可以只考虑左端点 **向左移动** 对答案的贡献。 记 $ans(x)$ 为区间 $[x,n]$ 的答案。当 $x$ 变为 $x-1$ 时，增加的区间有 $[x-1,x-1],[x-1,x],[x-1,x+1],\dots,[x-1,n-1],[x-1,n]$。 若 $a_{x-1}\gt0$，则有 $\forall i\in\{x,x+1,x+2,\dots,n\}$，都必然 $\exists j\in\{x-1,x,\dots,i\},a_j\gt0$，因此区间 $[x-1,x],[x-1,x+1],\dots,[x-1,n-1],[x-1,n]$ 都不符合题意（一个区间 $[l',r']$ 对应的数对 $(l',r')$ 符合题意的条件见 **子任务 2** 的证明）。由于 $a_{x-1}\gt0$，且该区间只有一个元素，故符合题意。 因此，$a_{x-1}\gt0\implies ans(x-1)=ans(x)+1$ 。 若 $a_{x-1}\leqslant0$，则 $\forall i\in\{x-1,x,\dots,p-1\}$，都有 $a_i\leqslant0$（$p$ 的含义同上文），因此区间 $[x-1,x-1],[x-1,x],\dots,[x-1,p-1]$ 都 **不符合题意**（原因见 **子任务 2** 的证明）。同时，由于 $a_p\gt0$，因此区间 $[x-1,p+1],[x-1,p+2],\dots,[x-1,n]$ 都不符合题意（原因见上文）。 若还有 $\displaystyle\sum_{i=x-1}^pa_i\gt0$，则满足所有符合题意的充要条件，则区间 $[x-1,p]$ 符合题意，则此时 $ans(x-1)=ans(x)+1$。 否则，区间 $[x-1,p]$ 不合题意，则此时 $ans(x-1)=ans(x)$。 这样我们讨论完了左端点向左移动一个位置时的所有情况，因此所有左端点为当前左端点的询问的答案即为当前答案，故 **思路正确**。 ### 具体实现 记录所有询问的左端点及询问编号，使用 **计数排序** 的方式将所有左端点相同的询问编号挂在同一个左端点上。**这里使用 `vector` 实现**。 设置端点为 $n$，将该端点从 $n$ 向 $1$ 位置扫。设当前扫到了位置 $i$。首先判断 $a_i\gt0$ 是否成立，若成立，答案加 $1$。否则，我们 **找到** 在位置 $i$ 之后的第一个位置 $p$ 满足 $a_p\gt0$，并使用前缀和判断区间 $[i,p]$ 的元素和是否大于 $0$。若是，答案加 $1$；否则，答案不变。 我们 **动态更新** 当前在位置 $i$ 之后第一个 $a_p\gt0$ 的位置 $p$。初始 $p=n+1$，若当前位置 $i$ 的 $a_i\gt0$，则令 $p\leftarrow i$。 回答左端点为 $i$ 的所有询问，并存在对应询问编号的答案中。扫完整个序列，按编号顺次输出每个询问的答案。 ### 时间复杂度分析 将询问离线并降序排序，按上述实现，复杂度为 $O(q)$。从右往左扫一遍复杂度 $O(n)$。每个位置，可以 $O(1)$ 找到位置 $p$，故计算一个询问的答案，复杂度为 $O(1)$。 总时间复杂度 $O(n+q)$，可以通过 **子任务 3**。 ### 参考核心代码 ```cpp vector<int>ask[N]; ... for(i=1;i<=q;i++){ int l=R(),r=R(); ask[l].push_back(i);//将询问编号i放入询问左端点为l的vector中，相当于计数排序 } int ans=0,now=n+1;//now记录当前位置右边第一个a[p]>=0的位置p for(i=n;i>=1;i--){ if(a[i]>0){ ans++; now=i;//若a[i]>0答案加1，并更新now } else if(now!=n+1)//now位置存在 if(sum[now]-sum[i-1]>0)//判断符合题意 ans++; for(auto qid:ask[i]) anss[qid]=ans;//回答询问 } for(i=1;i<=q;i++) printf("%d\n",anss[i]); ``` ### 期望得分 $15$ 分。结合 **子任务 0** 的解法可以获得 $15$ 分，结合 **子任务 1** 的解法可以获得 $30$ 分，结合 **子任务 2** 的解法可以获得 $50$ 分。 ## 子任务 4 ### 做法 将所有询问离线，并按照右端点 $r$ **升序排序**。将端点从 $1$ 向右扫，设开始扫之前答案为 $0$。设当前扫到的位置为 $i$，若 $a_i\leqslant0$，则答案不变。否则，二分出位置 $p$，满足 $\displaystyle\sum_{i=p}^{r'}a_i\gt0\land\forall x\in \{p,p+1,p+2,\dots,r'-1\},a_x\leqslant 0$，且 $\displaystyle\sum_{i=p-1}^{r'}a_i\leqslant0\lor\exists x\in\{p-1,p,p+1,\dots,r'-1\},a_x\gt0$，将 $i-p+1$ 加入答案。执行完上述操作后，当前答案即为所有 $r=i$ 的询问的答案。 ### 正确性证明 由于 **左端点固定**，均为 $1$，且我们可以按照右端点将询问排序，因此我们只需要考虑右端点 **右移一个位置** 对答案的贡献。 可以发现，右端点右移一个位置时，增加的所有区间的右端点 **相同**。这就转化为：**固定右端点 $r'$，求所有符合题意的数对 $(l',r')$ 个数**。该问题与 **子任务 2** 中的问题相同，因此解法也与那一问题相同，具体见 **子任务 2**。注意到此时必有 $l=1$，因此二分得到的位置 $p$ 一定是符合区间左端点约束的，即必有 $p\geqslant1$。因此将 $i-p+1$ 加入答案即可。 我们正确解决了右端点右移一个位置对答案的贡献问题，因此该思路是正确的。 ### 具体实现 使用 `vector` 实现对询问的按右端点排序。设置端点为 $1$，从 $1$ 扫到 $n$。设当前扫到的位置为 $i$。首先判断 $a_i\gt0$ 是否成立，若不成立，答案不变。否则，二分出上述位置 $p$，具体方法见 **子任务 2**。答案增加 $i-p+1$。回答右端点为 $i$ 的所有询问，将答案存入对应的询问编号。 最后按照询问编号顺次输出答案。 ### 时间复杂度分析 按照上述实现，对询问排序是 $O(n)$ 的。从左往右扫，每次可能需要二分，单次复杂度 $O(\log n)$，回答询问总复杂度为 $O(q)$。 总时间复杂度 $O(n\log n)$，可以通过 **子任务 4**。 ### 参考核心代码 ```cpp for(i=1;i<=q;i++){ int l=R(),r=R(); ask[r].push_back(i);//将询问按右端点升序排序 } int ans=0; for(i=1;i<=n;i++){ if(a[i]>0){//只有a[i]>0才可能更新答案 int lt=0,rt=i+1; while(lt+1!=rt){ int mid=(lt+rt)>>1; if(sum[i]-sum[mid-1]>0&&sum1[i-1]-sum1[mid-1]==i-mid) rt=mid; else lt=mid; } ans+=i-rt+1;//二分出位置p } for(auto qid:ask[i]) anss[qid]=ans;//回答询问 } for(i=1;i<=q;i++) printf("%d\n",anss[i]); ``` ### 期望得分 $15$ 分。结合 **子任务 0** 的解法可以获得 $15$ 分，结合 **子任务 1** 的解法可以获得 $30$ 分，结合 **子任务 3** 的解法可以获得 $30$ 分，结合 **子任务 0** 和 **子任务 3** 的解法可以获得 $30$ 分，结合 **子任务 1** 和 **子任务 3** 的解法可以获得 $45$ 分，结合 **子任务 2** 的解法可以获得 $50$ 分，结合 **子任务 2** 和 **子任务 3** 的解法可以获得 $65$ 分。 ## 子任务 5 ### 做法 对于每个位置 $i$，使用二分法，**预处理** 出以 $i$ 为右端点 $i=r'$ 的所有符合题意的数对 $(l',r')$ 个数 $num_i$（具体方法见 **子任务 2**）。对于一个询问 $(l,r)$，设区间 $[l,r]$ 中最小的位置 $p$，满足 $a_p\gt0$，求出 $\min(num_p,p-l+1)+\displaystyle\sum_{i=p+1}^rnum_i$，即为该询问的答案。 ### 正确性证明 由于原序列 $a$ **不发生改变**，因此我们可以预处理出上述的 $num_i$（正确性证明见 **子任务 2**）。 设一个位置 $i$ 满足 $a_i\gt0$，位置 $las$ 也满足 $a_{las}\gt0$，且有 $\forall j\in\{las+1,las+2,\dots,i-1\}$。都有 $a_j\leqslant0$，设对于位置 $i$，二分出的位置为 $pos$。根据 **子任务 2** 中的推断，假设 $pos\leqslant las$，则 $\exists j\in\{pos,pos+1,\dots,i-1\}$，满足 $a_j\gt0$，则区间 $[pos,i]$ 不合法，这与 **$pos$ 为满足区间 $[l',i]$ 合法的最小的 $l'$** 这一结论相矛盾。因此假设不成立，故 $pos\gt las$。 对于一个询问 $(l,r)$，设其中所有满足 $a_i\gt0$ 的所有 $i$ 从小到大分别为 $i_1,i_2,\dots,i_k$，其中 $k=\displaystyle\sum_{i=l}^r[a_i\gt0]$。该询问的答案 $ans=\displaystyle\sum_{i=l}^r\min(i-l+1,num_i)$。对于 $a_i\leqslant0$ 的位置 $i$，$num_i=0$，因此 $\min(i-l+1,num_i)=num_i$。对于 $j\in\{2,3,\dots,k\}$，根据上述推理，**必有对应的 $p\gt i_{j-1}\geqslant l$**，因此 $num_{i_j}\lt i_j-l+1\implies \min(i_j-l+1,num_{i_j})=num_{i_j}$。**只有 $i_1$ 位置的 $i_1-l+1$ 与 $num_{i_1}$ 大小关系不确定，需要单独计算**。 **即证**：$ans=\min(p-l+1,num_p)+\displaystyle\sum_{i=p+1}^rnum_i$，其中 $p$ 的含义与本子任务“做法”中 $p$ 含义相同。 因此该思路正确。 ### 具体实现 首先预处理出 $num_i$ 数组，具体方法见 **子任务 2**。根据上述证明，我们也可以动态记录每个数左边第一个元素值大于 $0$ 的位置，将二分左端点设置为上一个满足 $a_i\gt0$ 的位置 $i$，实现一个小优化。 预处理出 $num_i$ 数组的 **前缀和** 数组 $sumn_i$，预处理出每个数 **右边** 第一个元素值大于 $0$ 的位置。对于一个询问，直接计算 $sumn_r-sumn_{l-1}$，并找到 $l-1$ 右边第一个元素值大于 $0$ 的位置 $x$，减去 $num_x$，并加上 $\min(num_x,x-l+1)$，即为该询问的答案，输出即可。 ### 时间复杂度分析 预处理 $num_i$ 数组，单次处理复杂度 $O(\log n)$，总复杂度 $O(n\log n)$；预处理 $sumn_i$ 数组与每个数右边第一个元素值大于 $0$ 的位置，复杂度都是 $O(n)$。单次处理询问，计算、查找位置，复杂度都为 $O(1)$，总复杂度 $O(q)$。 总时间复杂度 $O(n\log n)$，可以通过 **本题**。 ### 参考核心代码 ```cpp int now=0; for(i=1;i<=n;i++){ lef[i]=now;//前面第一个正数位置 if(a[i]>0) now=i; } now=n+1; for(i=n;i>=1;i--){ rig[i]=now;//后面第一个正数位置 if(a[i]>0) now=i; } ...（预处理num数组及前缀和） int l=R(),r=R(),pos=rig[l-1];//找到l-1右边第一个正数的位置 if(pos>r){//注意这里要特判，否则会使得找到的pos越界导致错误 puts("0"); continue; } printf("%d\n",sumn[r]-sumn[l-1]-num[pos]+min(num[pos],pos-l+1));//根据上述式子计算答案 ``` ### 期望得分 $100$ 分。