题解：P11406 [RMI 2020] 零和 / Sum Zero

_JoeyJ_ · 2025-11-19 09:26:05 · 题解

首先前面的部分和其他题解是相同的，即找到最小的 j>i 使得 [i,j] 中存在一个零段。

这显然是可以倍增解决的，但是我们只能开 9 个 int 数组了。

所以 4 进制倍增就好了，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
using ll=long long;
const int N=4e5+9;
const int lgN=9e0;

int a[N],f[N][lgN],n,q;

signed main(){
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    vector<ll> b(a,a+n+1);
    partial_sum(b.begin(),b.end(),b.begin());
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    ll tmp=0;
    for(int i=0;i<=n;tmp+=a[++i]) a[i]=lower_bound(b.begin(),b.end(),tmp)-b.begin()+1;
    b.clear();
    b.shrink_to_fit();
    b.resize(n+1,n+1);
    for(int i=n;i>=0;i--) f[i][0]=b[a[i]],b[a[i]]=i;

    for(int k=0;k<lgN;k++) f[n+1][k]=n+1;
    for(int i=n;i>=0;i--) f[i][0]=min(f[i+1][0],f[i][0]);
    for(int k=1;k<lgN;k++){
        for(int i=0;i<=n;i++) f[i][k]=f[f[f[f[i][k-1]][k-1]][k-1]][k-1];
    }

    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;

        l--;
        int ans=0;
        for(int k=lgN-1;~k;k--){
            while(f[l][k]<=r) l=f[l][k],ans+=1<<(k<<1);
        }

        cout<<ans<<endl;
    }

    return 0;
}