题解：P13977 数列分块入门 2

· · 题解

前置知识

思路

这题也是分块中的经典题型，在洛谷上还有双倍经验 P2801 教主的魔法。

先考虑一个简单的问题：有一个长度为 n 的数组 a，接下来 q 次询问，每次询问求小于 x 的数组元素个数。一个很显然的思路就是先排序再二分。

在本题中我们也可以沿用这样的思路。具体的，对于每个块，进行排序。对于每一次询问，覆盖到的散块暴力查找，整块二分查找。用这样的思路可以 AC SP18185 GIVEAWAY - Give Away。但是这题和那题不一样，这题要区间修改。这里就可以用到懒标记了。用 tag_i 表示第 i 块加上的和，二分要找的就是 c^2 减去对应的 tag_i。

代码实现

给出代码：

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=1005;
int n;
ll a[N];
int blen,bnum;
ll block[N],tag[M];
int belong[N],bl[M],br[M];
void build()
{
    blen=sqrt(n);
    bnum=(n+blen-1)/blen;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/blen+1;
    for(int i=1;i<=bnum;i++)
    {
        bl[i]=(i-1)*blen+1;
        br[i]=min(i*blen,n);
    }
    for(int i=1;i<=n;i++)
        block[i]=a[i];
    for(int i=1;i<=bnum;i++)
        sort(block+bl[i],block+br[i]+1);
}
void _add(int x,int y,ll k)
{
    for(int i=x;i<=y;i++)
        a[i]+=k;
    int l=bl[belong[x]],r=br[belong[x]];
    for(int i=l;i<=r;i++)
        block[i]=a[i];
    sort(block+l,block+r+1);
}
void add(int x,int y,ll k)
{
    if(belong[x]==belong[y])
        _add(x,y,k);
    else
    {
        _add(x,br[belong[x]],k);
        _add(bl[belong[y]],y,k);
        for(int i=belong[x]+1;i<=belong[y]-1;i++)
            tag[i]+=k;
    }
}
int _query(int x,int y,ll k)
{
    int ret=0;
    for(int i=x;i<=y;i++)
        if(a[i]+tag[belong[x]]<k)
            ret++;
    return ret;
}
int find(int x,int y,ll k)
{
    int l=x,r=y,mid,ret=x-1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(block[mid]<k)
        {
            ret=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return ret;
}
int query(int x,int y,ll k)
{
    int ret=0;
    if(belong[x]==belong[y])
        ret+=_query(x,y,k);
    else
    {
        ret+=_query(x,br[belong[x]],k);
        ret+=_query(bl[belong[y]],y,k);
        for(int i=belong[x]+1;i<=belong[y]-1;i++)
        {
            int pos=find(bl[i],br[i],k-tag[i]);
            ret+=pos-bl[i]+1;
        }
    }
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    while(n--)
    {
        int op,l,r;
        ll c;
        scanf("%d%d%d%lld",&op,&l,&r,&c);
        if(op==0)
            add(l,r,c);
        else
            printf("%d\n",query(l,r,c*c));
    }
    return 0;
}