luo3372线段树模板的分块做法_Qiubo123456789的博客-程序员宅基地

题目大意

请你维护一个有n个元素的整数序列,要求支持区间查询&区间修改

对于100%的数据,\(1<=n<=10^5\)

分析

正常做法是线段树维护区间修改、区间查询,今天我要讲的是一种暴力做法:分块

分块的思想并不复杂,分块把一个长度为n的区间分成num段,操作时如果是整段用标记修改,不是整段的部分暴力修改

分析时间复杂度:在这题中,每段的标记修改是\(O(1)\)的,最多有num段,整段标记修改所用时间是\(O(num)\)的;不是整段的部分最多有\(O(n/num)\)个,暴力修改所用的时间是\(O(n/num)\)的;所以总时间是\(O(num+n/num)\)

根据基本不等式,num取\(\sqrt n\)时该式有最小值;所以num取\(\sqrt n\)

实现

分块的思想并不复杂,时间复杂度也不玄学,但是实现起来并不方便(可能是我弱)

分块的修改/查询都分为2部分:

  1. 整块的修改
  2. “零头”的修改

整块的修改是否简便:add[i] += val;
“零头”的修改直接修改,同时不要忘了维护所在块的信息:

a[i] += val;
sum[id[i]] += val;

修改就愉快地解决了,查询和修改差不多。

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 100007;
int n, m, num, id[maxn];
long long sum[1000], add[1000], a[maxn];

int main(){
    scanf("%d%d", &n, &m);
    num = sqrt(n);
    for (int i = 1; i <= n; ++i){
        scanf("%lld", &a[i]);
        id[i] = (i-1) / num;
        sum[id[i]] += a[i];
    }

    while (m--){
        int d; scanf("%d", &d);
        if (d==1){
            int x, y, C; scanf("%d%d%d", &x, &y, &C);
            int Leftid = (x-1) / num + 1;
            int Rightid = (y-1) / num - 1;

            long long res = 0;
            for (int i = Leftid; i <= Rightid; ++i)
                 add[i] += C;

            for (int i = x; i <= Leftid * num; ++i)
                a[i] += C, sum[id[i]] += C;

            for (int i = (Rightid+1)*num+1; i <= y; ++i)
                a[i] += C, sum[id[i]] += C;
        }else{
            int x, y; scanf("%d%d", &x, &y);
            int Leftid = (x-1) / num + 1;
            int Rightid = (y-1) / num - 1;

            if (id[x] == id[y]){
                long long res = 0;
                for (int i = x; i <= y; ++i)
                    res += a[i] + add[id[i]];
                printf("%lld\n", res);
                continue;
            }

            long long res = 0;
            for (int i = Leftid; i <= Rightid; ++i)
                res += sum[i] + add[i] * num;

            for (int i = x; i <= Leftid * num; ++i)
                res += a[i] + add[Leftid-1];

            for (int i = (Rightid+1)*num+1; i <= y; ++i)
                res += a[i] + add[Rightid+1];

            printf("%lld\n", res);

        }
    }
    return 0;
}

转载于:https://www.cnblogs.com/YJZoier/p/9721774.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Qiubo123456789/article/details/101159086

智能推荐

【237期推荐】医院自主开发LIS系统,费力不讨好的活!_weixin_34195546的博客-程序员宅基地

本周热点:LIS系统由自己的医院的人员开发是最好不过!这样既可以节省资金,又一次可以满足自己医院的需求,不用再进行客户化修改或二次开发.节省很多资源.  不过并不是所有的医院的员工都有能力来开发LIS的,所以对于没有能力开发的医院来讲,可以选择一家LIS系统开发的比较完善、全面的公司来做。有条件的医院也可以与LIS公司合作。还有一种办法,就是购买源码,...

支付宝自动续费申请PHP,APP是如何实现自动续费的?_周不宅的博客-程序员宅基地

APP会员自动续费功能流程:1.1、会员自动续费授权会员自动续费本质是委托扣款模式。只有用户完成签约,商户才可以对用户账户进行自动扣款,从而完成会员订单的支付操作。用户在应用内通过微信或支付宝的SDK完成代扣签约,微信或支付宝在用户签约成功后将签约信息通过异步通知的方式通知给商户后台。商户后台需要维护用户的签约信息,签约ID为核心信息,在订单的代扣请求中用于验证授权。1.2、会员到期后自动发起续费...

[题解][LG-P3791]普通数学题_juruohjr的博客-程序员宅基地

可以想到将ddd函数的前缀和转化一下:Sd(i)=∑i=1nd(i)=∑i=1n⌊ni⌋S_d(i)=\sum_{i=1}^n d(i)=\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloorSd​(i)=i=1∑n​d(i)=i=1∑n​⌊in​⌋那么就可以求出O(n)O(\sqrt{n})O(n​)求出每一个前缀和了(整除分块),加上一个unordered_map去除不必要的计算。将问题修改一下:i≤n,j≤m⟶i&lt;n+1,j&lt;m+1i

宏观角度认识分布式架构_木兮君的博客-程序员宅基地

分布式系统前言分布式架构概念架构演进架构演进图分布式架构的缺点常见分布式架构总结前言小编最近陆续开启了两个新的篇章,第一个是分布式系统之dubbo,会从他的基本使用(快速上手,dubbo基本理论,企业开发),然后高级应用(负载均衡配置,性能优化,服务降级等等),到核心源码的阅读(注册调用,协议传输等等);第二个是myBatis源码阅读。对之前的设计模式以及spring应用,会陆续更新,spring这边小编还缺乏aop,beanPostProcesser扩展,还有监听器理论以及对应源码框架的讲解。大家共同

java自定义测试报告,测试报告 之 testNG + Velocity 编写自定义html测试报告_996黄金一代的博客-程序员宅基地

之前用testNG自带的test-outputemailable-report.html,做出的UI自动化测试报告,页面不太好看。 在网上找到一个新的报告编写,自己尝试了一下,埋了一些坑,修改了输出时间格式,最终出的结果比以前稍好。 简单介绍下Velocity1.不用像jsp那样编译成servlet(.Class)文件,直接装载后就可以运行了,装载的过程在web.xml里面配置。【后缀名为.vht...

python语法错误修改病句_高考语文病句类型及改错方法 病句改错(请先说出是什么语法错误) 天安..._weixin_39870092的博客-程序员宅基地

所谓“病句”是指不符合现代汉语语法规则、不合逻辑事理的句子。简单说就是在语法或逻辑上有毛病的句子。它是历年来高考考查的一个重点。《考试大纲》对病句的测试要求是“辨析并修改病句”能力层级为D级。主要考查以下六种病句类型:表意不明、语序不当、不合逻辑、搭配不当、成分残缺或赘余、结构混乱。1、语序不对(1)我国棉花的生产,现在已经自给有余。(定语和中心语的位置颠倒,应改为“生产的棉花”)(2)在休息室里...

随便推点

ubuntu14.04 sublime 出错_a178796665的博客-程序员宅基地

1.问题:在ubuntu14.04安装 sublime 3 ,通过官网下载.deb格式安装包安装;由于很久没有使用,再次使用时,发现需要更新,于是在官网又下载.deb格式安装包,双击安装;但是,没有成功,提示出错;以后只要通过sudo apt-get install 方式安装其他软件都会报错,如图:如图,在安装mysql时,出现错误,都是关于sublime的,导致ph...

oracle四个表,Oracle 数据库基础学习 (三) Oracle 四个表结构_张简宁的博客-程序员宅基地

DOS&amp;colon;将某文件夹下面的所有某一类型文件名输出C:\Users\lv&gt;cd /d C:\Siemens\Teamcenter11\lib C:\Siemens\Teamcenter11\lib&gt;dir /B *.lib &gt;lis ...&amp;lbrack;Android&amp;rsqb;在Adapter的getView方法中绑定OnClickListen...

关于浏览器和网络的20项须知-HTML、JAVASCRIPT、CSS..._猫踹猫莱克雷的博客-程序员宅基地

AJAX不再是从前的样子了。        网页都是用HTML语言编写的,这是一种网络编程语言,可以指示浏览器如何在网页上构建和展现内容。换句话说,HTML为网页提供了构建基础。很长一段时间以来,这些构建基础都很简单,而且是静态的,只包含文本行,链接和图片。        如今,我们的要求更高了,例如会想要在线下棋或者无缝滚动浏览周边地图,但不想每下一步棋或每滚动一下地图都要等待整个网页重

5天玩转C#并行和多线程编程 —— 第二天 并行集合和PLinq 转载_weixin_30628801的博客-程序员宅基地

5天玩转C#并行和多线程编程系列文章目录5天玩转C#并行和多线程编程 —— 第一天 认识Parallel5天玩转C#并行和多线程编程 —— 第二天 并行集合和PLinq5天玩转C#并行和多线程编程 —— 第三天 认识和使用Task5天玩转C#并行和多线程编程 —— 第四天 Task进阶5天玩转C#并行和多线程编程 —— 第五天 多线程编程大总结  在上一篇博客...

[Protues]初识并构建51的最小系统_素履求知的博客-程序员宅基地

文章目录1 认识Proteus1.1 面板说明1.1.1 菜单栏1.1.2 工具栏1.1.3 选择栏1.1.4 旋转和镜像工具栏1.1.5 仿真工具栏1.1.6 状态栏2 构建51最小系统2.1 选择元器件模式2.2 选择需要的元器件1 认识Proteus1.1 面板说明1.1.1 菜单栏对照中英文1.1.2 工具栏1.1.3 选择栏1.1.4 旋转和镜像工具栏旋转和镜像工具栏,第一个为顺时针旋转,第二个为逆时针旋转旋转度数为90°旋转度数在下方文本框也可以自由选择最下面的两个按