题解：P13977 数列分块入门 2

IGpig · 2025-09-06 15:46:27 · 题解

P13977

主要讲一下代码细节，对于数据结构的原理请去看模板。

Solution

首先有两种操作，区间查询和区间加法，先说说加法。

首先判断 l,r 是不是在一个块里，如果是就直接处理。\ 否则先把两端多出来的部分处理掉，让 l,r 刚好到达块的端点，然后把中间的整块的懒标记加上 c 就好了。

接下来是区间查询有多少个小于等于 c^2 的个数，显然因为每次的查询不一样，是没有办法一直在线维护的。\ 所以这个数据给的很极限，我们可以在修改之后还排序，这样查询就很方便了。\ 所以还是一样先处理两边，因为加法之后会影响顺序，所以需要重新排序，然后查询的时候直接二分一下位置就可以了。

具体实现细节请看代码，个人认为应该容易看懂。

Code

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
LL n,a[500005],lazy[500005],len,L[500005];
vector<LL> v[50005];
inline LL get(LL x){
    return x/len+1;
}
void resort(LL x){
    int i=L[x];v[x].clear();
    while(get(i)==x&&i<=n) v[x].push_back(a[i++]);
    sort(v[x].begin(),v[x].end());
}
void update(LL l,LL r,LL c){
    if(get(l)==get(r)){
        for(int i=l;i<=r;i++) a[i]+=c;
        resort(get(l));
    }else {
        int i=l,j=r;
        while (get(i) == get(l)) a[i++] += c;
        while (get(j) == get(r)) a[j--] += c;
        resort(get(l));resort(get(r));
        for (int k = get(i);k <= get(j);k++) lazy[k] += c;
    }
}
LL query(LL l,LL r,LL c){
    LL res=0;
    if(get(l)==get(r)){
        for(int i=l;i<=r;i++){
            if(a[i]+lazy[get(i)]<c) res++;
        }
    }
    else{
        int i=l,j=r;
        while(get(i)==get(l)) if(a[i++]+lazy[get(l)]<c) res++;
        while(get(j)==get(r)) if(a[j--]+lazy[get(r)]<c) res++;
        for (int k = get(i);k <= get(j);k++) {
            res += lower_bound(v[k].begin(), v[k].end(), c - lazy[k]) - v[k].begin();
        }
    }
    return res;
}
int main(){
    cin>>n;
    len=int(sqrt(n));
    memset(L,0x3f,sizeof(L));
    for(LL i=1;i<=n;i++){
        cin>>a[i];
        LL x=get(i);
        L[x]=min(L[x],i);
        v[x].push_back(a[i]); 
    }
    for(int i=1;i<=n/len;i++) sort(v[i].begin(),v[i].end());
    for(int i=1;i<=n;i++){
        LL l,r,c,op;
        cin>>op>>l>>r>>c;
        if(op) cout<<query(l,r,c*c)<<endl;
        else{
            update(l,r,c);
        }
    }
    return 0;
}