自动搬运

查看原文

来自洛谷，原作者为

	HFanGDoDM 热夏你归来听蝉，再游于北方知寒。沿途不枉为少年，终有个结局圆满。

搬运于2025-08-24 22:50:42，当前版本为作者最后更新于2023-10-07 00:11:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置知识

二分法

题意简述

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

• $l\leqslant l'\leqslant r'\leqslant r$。

• $\displaystyle\sum_{i=l'}^{r'}a_i\gt 0$。

• $\forall x,y,l'\leqslant x\leqslant y\lt r',\displaystyle\sum_{i=x}^ya_i\leqslant 0$。

数据范围

子任务 0

$n\in\{4,7\}$，$q\in\{3,6\}$，$1\leqslant l\leqslant 5$，$r\in\{2,3,4,5,7\}$，$1\leqslant l\leqslant r\leqslant n$，$a_i\in\{-4,-1,2,3\}$。

子任务 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。

参考核心代码

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。

参考核心代码

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$

$\implies g(x_1)-g(x_2)\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。

参考核心代码

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。

参考核心代码

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。

参考核心代码

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)$，可以通过 本题。

参考核心代码

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$ 分。