首页 > 其他分享 >分块

分块

时间:2023-08-10 23:00:42浏览次数:32  
标签:分块 int add 数组 部分 block

题目链接

如果用暴力来把\([l,r]\)区间内的数字都加上\(c\),肯定会超时。
这时候,我们就可以用分块。


分块基本思想

分块,顾名思义,就是把一个数组分成很多区域,对于一整块区域,可以直接用一个数组来标记这个区间一共加上了几。对于不完整的块,可以直接在\(a\)数组上进行操作。

我们需要的数组:

$\ \ \ \ \ \ \ \ \ \ $ \(block[i]\)表示\(i\)所在的块的序号。
$\ \ \ \ \ \ \ \ \ \ $ \(add[i]\)表示序号为\(i\)的区间一共加上了几
$\ \ \ \ \ \ \ \ \ \ $ \(a[i]\)表示数组\(a\)


分块代码理解

代码部分1:分区域

输入了\(a\)数组后,我们需要把这个数组进行分区域,把分到区域的序号放在\(block\)数组里。每个块的长度为\(\sqrt n\),所以,\(a[i]\)所在的区域序号为(i-1)/sqrt(n)+1,我们把这个数放到\(block[i]\)里面就完成了第一部分的操作。

代码部分2:一个元素的大小

使用分块,我们知道,下标为\(i\)的大小由两个部分组成。一个是本身的\(a[i]\),还有一个就是存在\(add\)数组里的整块区间加上的数字。所以,它的总大小就是a[r]+add[block[r]]

代码部分3:区间加法

我们知道,区间加分为两个部分,一个是整体区域,一个不完整的部分。我们先来看不完整的部分。首先,我们进行区间加法的开始,肯定是\(l\),但是我们不知道,到底是\(r\)大,还是\(l\)所在的区域更大,所以,我们要用带\(min\)函数,来看\(l\)到\(r\)中是否有完整的部分。

for (int i = l; i <= min(r, block[l]*v); i++) { //对于不在整块区域的区间加
    //block[l]*tmp l到l所在的区域结束这一小块区间
    a[i] += c;
}

接着,如果\(l\)和\(r\)所处的是同一个区域,就说明,已经完成了区间加法,可以返回了。

if (block[r] == block[l]) { //l和r所处的区间是同一块
    return ;
}

刚才处理的是左边部分的不完整部分,那么现在,就处理右边的不完整部分。

for (int i = (block[r] - 1) * v + 1; i <= r; i++) {
    a[i] += c;
}

最后,我们进行整块的加法。因为在\(l\)之前的部分已经算过了,\(r\)所在的部分也做过了,所以,我们只需要从两个区域的中间开始完整的加法。

for (int i = block[l] + 1; i <= block[r] - 1; i++) { //l到r中间的空间
    add[i] += c;
}

这题就解决了,下面是完整代码。

#include<cmath>
#include<vector>
#include<iostream>
#define endl "\n"
#define int long long
using namespace std;

const int N=50010;
int block[N],a[N],add[N];
int n,v;
//block 记录每个数字所处的块
//a 数组
//add 存每个块加上的数字

void Add(int l,int r,int c){//l~r +c
    for(int i=l; i<=min(r,block[l]*v); i++){//对于不在整块区域的区间加
        //block[l]*tmp l到l所在的区域结束这一小块区间
        a[i]+=c;
    }
    if(block[r]==block[l]){//l和r所处的区间是同一块
        return ;
    }
    for(int i=(block[r]-1)*v+1; i<=r; i++){
        a[i]+=c;
    }
    for(int i=block[l]+1; i<=block[r]-1; i++){//l到r中间的空间
        add[i]+=c;
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.tie(0);
    cin>>n;
    v=sqrt(n);
    for(int i=1; i<=n; i++){
        cin>>a[i];
        block[i]=(i-1)/v+1;//给每个数字分块
    }
    for(int i=1; i<=n; i++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0){
            Add(l,r,c);
            /*
            cout<<"IS"<<" ";
            for(int i=1; i<=n; i++){
                cout<<a[i]<<" ";
            }
            */
        }
        if(opt==1){
            //add[block[r]] 储存着下标为r的数字所需要加上的数字
            cout<<a[r]+add[block[r]]<<endl;
        }
    }
    return 0;
}

标签:分块,int,add,数组,部分,block
From: https://www.cnblogs.com/wrl2010/p/17621836.html

相关文章

  • 数论分块
    数论分块学习用途快速计算含有\(\lfloor{\frac{n}{i}}\rfloor\)的和式(\(i\)为变量)引理引理1\[\foralla,b,c\in\mathbb{N_+},\quad\Big\lfloor\frac{a}{bc}\Big\rfloor=\bigg\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\bigg\rfloor\]证明1\[\text{let}\qua......
  • [Ynoi2016] 这是我自己的发明(根号分治+分块/莫队)
    题目传送门soltion简单题换根显然可以拆成\(O(1)\)个区间,这里先不管。直接做法是莫队,把双子树拆成\(dfs\)序上的双前缀,可以直接莫队,但是常数比较大。另一种做法是根分,对颜色出现次数分治,大于的求出\(dfs\)序的前缀和即可,小于的因为一共只有\(O(n\sqrtn)\)个点对,所以......
  • 分块,优雅的暴力
    来看一下一个例题:现在给出一个长度为\(N\)序列A,定义两个操作如下:1lrv,表示从\(A_l\simA_r\)每个数都加上\(v\)。2lr,对\(A_l\simA_r\)求和。传统的线段树可以很优秀地实现这两个操作,但是需要打\(lazytag\)。同时因为线段树(非动态开点)的空间复杂度为......
  • Nginx实现浏览器端大文件分块上传
    ​PHP用超级全局变量数组$_FILES来记录文件上传相关信息的。1.file_uploads=on/off 是否允许通过http方式上传文件2.max_execution_time=30 允许脚本最大执行时间,超过这个时间就会报错3.memory_limit=50M 设置脚本可以分配的最大内存量,防止失控脚本占用过多内存,此指......
  • javascript实现浏览器端大文件分块上传
    ​ 以ASP.NETCoreWebAPI 作后端 API ,用 Vue 构建前端页面,用 Axios 从前端访问后端 API,包括文件的上传和下载。 准备文件上传的API #region 文件上传  可以带参数        [HttpPost("upload")]        publicJsonResultuploadProject(I......
  • js实现浏览器端大文件分块上传
    ​ 第一点:Java代码实现文件上传FormFilefile=manform.getFile();StringnewfileName= null;Stringnewpathname= null;StringfileAddre= "/numUp";try{    InputStreamstream=file.getInputStream();// 把文件读入    StringfilePath=request.......
  • vue实现浏览器端大文件分块上传
    ​ 这里只写后端的代码,基本的思想就是,前端将文件分片,然后每次访问上传接口的时候,向后端传入参数:当前为第几块文件,和分片总数下面直接贴代码吧,一些难懂的我大部分都加上注释了:上传文件实体类:看得出来,实体类中已经有很多我们需要的功能了,还有实用的属性。如MD5秒传的信息。pub......
  • http实现浏览器端大文件分块上传
    ​ 前言文件上传是一个老生常谈的话题了,在文件相对比较小的情况下,可以直接把文件转化为字节流上传到服务器,但在文件比较大的情况下,用普通的方式进行上传,这可不是一个好的办法,毕竟很少有人会忍受,当文件上传到一半中断后,继续上传却只能重头开始上传,这种让人不爽的体验。那有没有......
  • 分块-优雅的暴力
    前言某人:线段树好难,学不会,树状数组感觉用途少好多,怎么办啊Ben:入我分块神教!ps:作者不认为分块是数据结构,而是一种思想。本文代码来自作者不同时期,马蜂习惯存在差别前置芝士:循环,数组,没了一序列分块对于给定序列要求增删改查类问题,一般最常用线段树和BIT,毕竟是高贵的log但......
  • Web实现浏览器端大文件分块上传
    ​ASP.NET上传文件用FileUpLoad就可以,但是对文件夹的操作却不能用FileUpLoad来实现。下面这个示例便是使用ASP.NET来实现上传文件夹并对文件夹进行压缩以及解压。ASP.NET页面设计:TextBox和Button按钮。 ​编辑TextBox中需要自己受到输入文件夹的路径(包含文件夹),通过Button......