题解：P13977 数列分块入门 2

NTT__int128 · 2025-11-26 16:11:04 · 题解

题解：P13977 数列分块入门 2

翻了一圈发现没有 \Theta(n\sqrt{n\log n}) 的做法，来发交一发题解。

首先，我们考虑分块，维护每个块的 tag 表示这个块每个数都要加上的数。

其次，每个块维护一个 vector 存下这个块内的数从小到大排序后的结果以方便查询。

发现修改散块暴力重构 \Theta(B\log B) 的，整块是 \Theta(\frac nB) 的。

查询散块枚举可以做到 \Theta(B)，整块用 lower_bound 二分可以做到 \Theta(\frac nB\log B)。

此时，取 B=\sqrt n 可以做到 \Theta(n\sqrt n\log{\sqrt n})。

但我们发现，其实修改散块时可以做到 \Theta(B)。具体的，修改一个散块时，把散块分为两部分，一部分为不修改的，一部分为修改的。发现这两部分提取出来后的相对顺序不会变，然后把这两部分归并即可。

于是可以做到 \Theta(n(B+\frac nB\log B))，取 B=\sqrt{n\log n} 可以做到 \Theta(n\sqrt{n\log n})。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,a[N];
int b;
vector<pair<int,int>>r[N];
int g[N];
void re(int x,int ql,int qr){
    vector<pair<int,int>>o,d;
    for(int i=0,sz=r[x].size();i<sz;i++){
        int p=r[x][i].second;
        if(p>qr||p<ql)o.push_back({a[p],p});
        else d.push_back({a[p],p});
    }
    merge(o.begin(),o.end(),d.begin(),d.end(),r[x].begin());
}
void up(int ql,int qr,int v){
    if(ql/b==qr/b){
        for(int i=ql;i<=qr;i++)a[i]+=v;
        re(ql/b,ql,qr);
    }
    else{
        for(int i=ql;i<ql/b*b+b;i++)a[i]+=v;
        re(ql/b,ql,ql/b*b+b-1);
        for(int i=qr/b*b;i<=qr;i++)a[i]+=v;
        re(qr/b,qr/b*b,qr);
        for(int i=ql/b+1;i<qr/b;i++)g[i]+=v;
    }
}
int qy(int ql,int qr,int v){
    int ans=0;
    if(ql/b==qr/b){
        for(int i=ql;i<=qr;i++)ans+=(a[i]+g[ql/b]<v);
    }
    else{
        for(int i=ql;i<ql/b*b+b;i++)ans+=(a[i]+g[ql/b]<v);
        for(int i=qr/b*b;i<=qr;i++)ans+=(a[i]+g[qr/b]<v);
        for(int i=ql/b+1;i<qr/b;i++)ans+=lower_bound(r[i].begin(),r[i].end(),make_pair(v-g[i],-1))-r[i].begin();
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;b=sqrt(n*log(n));
    for(int i=0;i<n;i++)cin>>a[i],r[i/b].push_back({a[i],i});
    for(int i=0;i<=(n-1)/b;i++)sort(r[i].begin(),r[i].end());
    for(int i=1;i<=n;i++){
        int op,l,r,c;cin>>op>>l>>r>>c;
        --l,--r;
        if(op==0)up(l,r,c);
        else cout<<qy(l,r,c*c)<<'\n';
    }
    return 0;
}