首页 > > 程序设计 > C/C++ >

数列分块入门 1

2018-06-17 20:43:19来源：未知阅读 ()

给出一个长为

第一行输入一个数字

第二行输入 $aia_ia?i??，以空格隔开。$

接下来输入 $opt\mathrm{opt}opt、lll、rrr、ccc，以空格隔开。$

若 $opt=0\mathrm{opt} = 0opt=0，表示将位于 [l,r][l, r][l,r] 的之间的数字都加 ccc。$

若 $opt=1\mathrm{opt} = 1opt=1，表示询问 ara_ra?r?? 的值（lll 和 ccc 忽略）。$

对于每次询问，输出一行一个数字表示答案。

思路：

最简单的数列分块

先明确一波分块的概念：

将一个长为n数列拆成k块儿（一般k=sqrt（n））；

然后对区间的修改变为对完整块的修改和对区间两端不完整块的暴力

那如何描述对区间的修改和查询呢？

lazy大法好！！

建一个标记数组，存储对整个区间的修改

最后输出标记数组与原值的和即可

代码：

#include<iostream>  
#include<cstdio>  
#include<cmath>  
using namespace std;  
int x[50005],sy[50005],fk[50005],n,opt,l,r,c,a,b,d,dx,cnt,bnt;  
int main()  
{  
    // freopen("a1.in","r",stdin);  
    // freopen("1.out","w",stdout);  
    cin>>n;  
    dx=sqrt(n);  
    bnt=1;  
    for(a=1;a<=n;a++)  
    {  
        scanf("%d",&x[a]);  
        sy[a]=(a-1)/dx+1;  
    }  
    for(a=1;a<=n;a++)  
    {  
        scanf("%d%d%d%d",&opt,&l,&r,&c);  
        if(opt==1)  
        {  
            printf("%d\n",x[r]+fk[sy[r]]);  
        }  
        else  
        {  
            if(sy[l]==sy[r])  
            {  
                for(b=l;b<=r;b++)  
                {  
                    x[b]+=c;  
                }  
                continue;  
            }   
            int lf,ri;  
            lf=sy[l];  
            ri=sy[r];  
            for(b=l;b<=lf*dx;b++)  
            {  
                x[b]+=c;  
            }  
            for(b=(ri-1)*dx+1;b<=r;b++)  
            {  
                x[b]+=c;  
            }  
            for(b=lf+1;b<=ri-1;b++)  
            {  
                fk[b]+=c;  
            }  
        }  
    }  
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有