分块战神之询问分块解线段树

MoCaRabbit · 2024-10-22 13:53:42 · 题解

询问分块解线段树问题。

这边先提供一种 O(m^2) 的神经做法。

对于每个询问，统计它之前所有修改对它的贡献。

直接求线段相交长度可做出。

两个区间相交的长度。

inline int J(int x,int y){//区间交集 
    if(l[x]>l[y]) swap(x,y);
    if(l[y]>r[x]) return 0;
    if(r[y]<r[x]) return r[y]-l[y]+1;
    return r[x]-l[y]+1;
}

挺简单的是吧。

再来一种 O(n^2) 的方法。

每次修改用差分统计，贡献加到前缀和数组上。

这种方法更笨。

如果结合一下呢？

尝试询问分块，在每个块内用第一种思路，有 B 个块，时间复杂度 O(\dfrac{m^2B}{B^2})=O(\dfrac{m^2}{B})。

接着，答完所有块的答案后，直接用差分统计这个块中的所有修改记录到 a 数组里，然后再统计前缀和，时间复杂度 O(nB)。

根据某些玩意儿，当 nB=\dfrac{m^2}{B} 时最优。

所以取 B=\dfrac{m}{\sqrt{n}} 最优，看来比 B=\sqrt{n} 快一点。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[100010],d[100010],s[100010];
int opt[1010],l[1010],r[1010],v[1010];
inline int J(int x,int y){//区间交集 
    if(l[x]>l[y]) swap(x,y);
    if(l[y]>r[x]) return 0;
    if(r[y]<r[x]) return r[y]-l[y]+1;
    return r[x]-l[y]+1;
}
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    int len=sqrt(n);//块长度为 m/B 为 sqrt(n) 
    for(int i=1;i<=m;i++){
        if(i%len==0 || i==m){//是块尾，统计答案
            cin>>opt[len];
            if(opt[len]==1) cin>>l[len]>>r[len]>>v[len];
            else cin>>l[len]>>r[len];
            for(int i=1;i<=len;i++)
                if(opt[i]==2){//统计贡献 
                    int ans=0; 
                    for(int j=1;j<i;j++) if(opt[j]==1) ans+=J(i,j)*v[j];//统计修改对答案的贡献  
                    cout<<ans+s[r[i]]-s[l[i]-1]<<"\n";
                }
                else d[l[i]]+=v[i],d[r[i]+1]-=v[i];//统计对后面的贡献 
            for(int i=1;i<=n;i++) d[i]+=d[i-1],a[i]+=d[i];//将差分贡献统计 
            for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//前缀和 
            memset(d,0,sizeof d);
            memset(opt,0,sizeof opt);//先清空 
        }
        else{//如果不是块尾，直接输入 
            int t=i%len;
            cin>>opt[t];
            if(opt[t]==1) cin>>l[t]>>r[t]>>v[t];
            else cin>>l[t]>>r[t];
        }
    }
    return 0;
}

这种方法常熟小，好想，好写，应用广。

设 n,m 同级，是 O(n\sqrt{n}) 的。