P13977 数列分块入门 2 题解

· · 题解

P13977 数列分块入门 2

设块号为 i 的块表示范围为 [(i-1)\times\sqrt{n}+1,i\times\sqrt{n}]

首先预处理出每个位置处于的块，记作 id[i] 。预处理时记录每一块的元素数量，同时记录每一块的每个元素的值与在原数组中的位置，用于块内排序。同时记录两个数组，add[i] 表示第 i 块的增量标记，d[i] 表示原数组中第 i 项对应块内编号为 d[i]。

修改操作

对于 l\le i\le p\times\sqrt{n}，是前面不完整的一段，朴素更新，更新之后依据每块位置 d[i] 的信息更新块内信息。然后重新块内排序，更新 d 数组。

对于 (q-1)\times\sqrt{n}+1\le i\le r，是后面不完整的一段，朴素更新，更新之后依据每块位置 d[i] 的信息更新块内信息。然后重新块内排序，更新 d 数组。

对于 p+1\le j\le q-1，是整块完整更新的块，更新标记 add[j] 增加 k。由于块内元素同增同减，顺序不变，不需要块内重排或更新 d 数组

询问操作

对于 l\le i\le p\times\sqrt{n}，是前面不完整的一段，朴素查询，比较每个元素加上其对应的组的 add 值与 c^2 的大小，如果小于，ans 自增。

对于 (q-1)\times\sqrt{n}+1\le i\le r，是后面不完整的一段，朴素查询，比较每个元素加上其对应的组的 add 值与 c^2 的大小，如果小于，ans 自增。

对于 p+1\le j\le q-1，是整块完整更新的块，由于块内元素有序，可以在每一块内部二分查找最大的小于 c^2 减去对应 add 值的元素，得到编号后就可以计算出小于 c^2 的元素个数。

总时间复杂度 O(n\sqrt{n}\log\sqrt{n})。

#include <bits/stdc++.h>
using namespace std;
struct node
{
    long long val,p;
}nei[500][500];
long long n,k,op,l,r,c,a[200010],id[200010],add[200010],num[200010],d[200010];
bool cmp(struct node a,struct node b)
{
    return a.val<b.val;
}

void adde()
{
    long long p=id[l],q=id[r];
    if(p==q)
       {
        for(long long i=l;i<=r;i++)
            {
            a[i]+=c;
            nei[p][d[i]].val+=c;
            }
        sort(nei[p]+1,nei[p]+num[p]+1,cmp);
        for(int j=1;j<=num[p];j++)d[nei[p][j].p]=j;
       }
    else
       {
        for(long long i=p+1;i<=q-1;i++)
            add[i]+=c;
        for(long long i=l;i<=p*k;i++)
            {
            a[i]+=c;
            nei[p][d[i]].val+=c;
            }
        sort(nei[p]+1,nei[p]+num[p]+1,cmp);
        for(int j=1;j<=num[p];j++)d[nei[p][j].p]=j;
        for(long long i=(q-1)*k+1;i<=r;i++)
            {
            a[i]+=c;
            nei[q][d[i]].val+=c;
            }
        sort(nei[q]+1,nei[q]+num[q]+1,cmp);
        for(int j=1;j<=num[q];j++)d[nei[q][j].p]=j;
       }
}

long long search(long long z,long long key)
{
    long long l=0,r=num[z];
    while(l<r)
       {
        long long mid=(l+r+1)/2;
        if(nei[z][mid].val<key)l=mid;
        else r=mid-1;
       }
    return l;
}

long long ask()
{
    long long p=id[l],q=id[r],ans=0;
    if(p==q)
       {
        for(long long i=l;i<=r;i++)if(a[i]+add[p]<c*c)ans++;
        return ans;
       }
    else
       {
        for(long long i=p+1;i<=q-1;i++)ans+=search(i,c*c-add[i]);
        for(long long i=l;i<=p*k;i++)if(a[i]+add[p]<c*c)ans++;
        for(long long i=(q-1)*k+1;i<=r;i++)if(a[i]+add[q]<c*c)ans++;
        return ans;
       }
}

int main()
{
    scanf("%lld",&n);
    k=sqrt(n);
    for(long long i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            id[i]=(i-1)/k+1;num[id[i]]++;
            nei[id[i]][i-(id[i]-1)*k].val=a[i];
            nei[id[i]][i-(id[i]-1)*k].p=i;
        }
    for(long long i=1;i<=id[n];i++)
        {
        sort(nei[i]+1,nei[i]+num[i]+1,cmp);
        for(int j=1;j<=num[i];j++)d[nei[i][j].p]=j;
        }
    for(long long i=1;i<=n;i++)
        {
            scanf("%lld%lld%lld%lld",&op,&l,&r,&c);
            if(op==0)adde();
            else if(op==1)printf("%lld\n",ask());
        } 
    return 0;
}