P9681题解

LYBT · 2023-12-24 21:31:08 · 题解

First —— 分析题意

核心要素就是去推理幽默数列的性质。
首先性质一显而易见，这个序列总和大于 0。
再看性质二，这个序列的区间 [l,r-1] 任何子序列总和小于等于 0，其中注意 x\le y，说明这个子序列可以是一个数，便可得出结论：除了最后一项以外，这个序列的任何数都是非正数。

Then —— 设计算法

既然得出结论后，便可以想到，要想找到这种的数列，必须需要保证最后一项为正数。于是，我们可以找出原序列的所有正数，这样我们就把原序列分割成了由非正数构成的“块”。如样例二：

可以处理成三个块：

把每一个正数当做每一种方案的结尾，我们就可以把每一个块从后往前算，凡是后缀和大于 0 的便可以归为一种方案。注意，作为正数本身也是一种合法方案。以此在处理出方案的后缀和，这样就可以实现 O(1) 的查询。
当我们开始查询时，求 [l,r] 的方案数又该怎么利用已经处理好的方案后缀和呢？有的同学可能会直接算出 sum_l-sum_{r+1} 的值，但这只适用于结尾是正数的序列。如果说这个序列结尾是后面一个块遗留下来的负数，那么方案数会增加多余的部分。这时我们就应该考虑把后面的“负数尾巴”删去，可以维护一个每个位置前最近的正数，这样便可以忽略后面的“负数尾巴”。

Finally —— 参考 AC 代码

听思路比较笼统，接着通过看代码注释可能效果会更好。
My code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    char c=getchar();
    int sum=0,flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c^48);c=getchar();}
    return sum*flag;
}//快读
void write(int x){
    if(x<0) x=(~x)+1,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10|48);
}//快写
const int N=2e5+5;
int n=read(),q=read(),a[N],num[N],tot,sum[N],z[N];
// a数组是原序列，num是每一个正数的位置，tot为正数个数。sum为方案后缀和
// z数组用来统计离i最近的正数
signed main(){
    for(int i=1;i<=n;i++){
        a[i]=read();
        z[i]=z[i-1];
        if(a[i]>0) num[++tot]=i,z[i]++;
    }
    for(int i=tot;i>0;i--){//从后往前不影响后缀和
        int cnt=0;//当前块的后缀和
        for(int j=num[i];j>0&&(a[j]<=0||j==num[i]);j--){//遍历当前块
            cnt+=a[j];
            if(cnt>0) sum[j]=sum[j+1]+1;//如果大于0，可以将方案数加一
            else sum[j]=sum[j+1];//否则保持上应该状态
        }
    }
    for(int i=1;i<=q;i++){
        int l=read(),r=read();
        if(l==1||r==n) while(1);//防作弊QWQ，不要在意
        if(z[r]==0) write(0);//如果r前没有正数，说明无方案
        else if(num[z[r]]<l) write(0);//如果r前的正数位置不在序列，说明
        // 这个序列在一个块的中央位置，只有负数，方案数为0
        else write(sum[l]-sum[num[z[r]]+1]);//否则就用前缀和的方式，
        // 求出l到最后一个正数区间的方案数，忽略“负数尾巴”。
        putchar('\n');
    }
    return 0;
}