LOJ #6277 数列分块入门1

妖狐艹你老母 2022-05-19 06:49 143阅读 0赞

[传送门][Link 1]

题意：给你长为n的数列，n次操作，操作涉及区间加法，单点查值。 1≤n≤50000

思路：区间加法，单点查值，我们很容易想到用线段树或者树状数组做，但这里我们考虑用分块莽一波，我们用一个sum数组来维护每个完整的块里面需要加的值，每次更新到完整的块的时候就给该块的sum数组打上标记，我们假设每个块大小设为m，则有n/m个块，对于不在完整块里面的区间，就直接暴力更新，因为每个块的大小不超过m，所以复杂度是2m，所以每次更新的复杂度是O（n/m + m）由均值不等式可知，当m等于√n时，复杂度最小。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+7;
    int n,num,block,belong[maxn],l[maxn],r[maxn];
    int a[maxn],sum[maxn];
     
    long long read()
    {
    	char ch=getchar();long long ret=0,f=1;
    	while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    	return f*ret;
    }
     
    void build()
    {
        block=sqrt(n);
        num=n/block;if(n%block) num++;/**如果右边凸出了一点,块数加1*/
        for(int i=1;i<=num;i++)
            l[i]=(i-1)*block+1,r[i]=i*block; /**每个块的左边界和右边界*/
        r[num]=n;
        for(int i=1;i<=n;i++)
            belong[i]=(i-1)/block+1;/**每个块的编号*/
    }
     
    void update(int x,int y,int c)
    {
       if(belong[x]==belong[y])/**如果该区间是同一个块,直接暴力更新*/
       {
            for(int i=x;i<=y;i++)
                a[i]+=c;
            return;
       }
       for(int i=x;i<=r[belong[x]];i++)/**左边凸出来的部分直接暴力更新*/
            a[i]+=c;
       for(int i=belong[x]+1;i<belong[y];i++)/**维护每个整块的信息*/
            sum[i]+=c;
       for(int i=l[belong[y]];i<=y;i++)/**右边凸出来的部分直接暴力更新*/
            a[i]+=c;
    }
     
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        build();
        for(int i=0;i<n;i++)
        {
            int op=read(),l=read(),r=read(),c=read();
            if(op==1) printf("%d\n",a[r]+sum[belong[r]]);
            else update(l,r,c);
        }
        return 0;
    }

[Link 1]: https://loj.ac/problem/6277