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

· · 题解

Solution

不是很会卡空间……

显然，线段只有可能的 O(n) 个，且右端点互不相同。

设 f(u) 为左端点大于 u 的所有线段中，右端点的最小值。

显然对 l 和 r 处理询问时，令 x = l-1，不断 x \leftarrow f(x) 直到 f(x) > r。

显然 (x,f(x)) 形成了一棵树。如果不卡空间，可以倍增。还有一种做法是从左往右扫描，维护目前所有联通块（使用并查集）

后者时空都是 O(n) 的（但是找线段部分实际上是 O(n \log n) 的），精细实现即可通过。

一些可能的卡空间方法：

  1. 重复利用数组。
  2. 尽量别开 long long，不用 STL。

在公开代码的人中，斩获了时间空间最优解（2024.12.20 之前）

#include<bits/stdc++.h>
#define llx long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=4e5+10;
int tot,n,q,fa[MAXN],anc[MAXN],ans[MAXN],hd[MAXN],nxt[MAXN],l[MAXN],r[MAXN],c[MAXN];
int find(int k) {return (anc[k]==k)?k:(anc[k]=find(anc[k]));}
void add(int u,int id) {return nxt[id]=hd[u],hd[u]=id,void();}
llx lsh[MAXN];
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) cin>>c[i];
    llx pre=0;
    memset(fa,0x3f,sizeof(fa)),memset(ans,-1,sizeof(ans));
    ffor(i,0,n) pre+=c[i],lsh[++tot]=pre;
    sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1,pre=0;
    ffor(i,0,n) {
        pre+=c[i];
        int id=lower_bound(lsh+1,lsh+tot+1,pre)-lsh;
        if(ans[id]!=-1) fa[ans[id]]=i;
        ans[id]=i;
    }
    tot=0;
    fa[n]=n+1;
    roff(i,n,0) fa[i]=min(fa[i],fa[i+1]);
    ffor(i,0,n+1) l[i]=n+2,r[i]=-1;
    ffor(i,0,n) l[fa[i]]=min(l[fa[i]],i),r[fa[i]]=max(r[fa[i]],i);
    fa[n+1]=0;
    roff(i,n,0) fa[i]=fa[fa[i]]+1;
    ffor(i,0,n) anc[i]=i;
    cin>>q;
    ffor(i,1,q) {
        int l,r;
        cin>>l>>r;
        c[i]=l-1,add(r,i),ans[i]=fa[l-1];
    }
    ffor(i,0,n) {
        ffor(j,l[i],r[i]) anc[j]=i;
        for(int id=hd[i];id;id=nxt[id]) ans[id]-=fa[find(c[id])];
    }
    ffor(i,1,q) cout<<ans[i]<<'\n';
    return 0;
}