数列分块入门

本期是数列分块入门。其中的大部分题目来自hzwer在LOJ上提供的数列分块入门系列。

Blog:here  (其实是对之前分块的 blog 的整理补充)     sto   hzwer   orz     %%%            [转载]

------------------------------------------------------------------------------------------------------------------------

分块

我举个例子来说分块。

在一个学校里,有很多班级,而每一个班级就是一个块。

假设某天校长想知道一个班考试的总分,直接查询即可。那如果要查询 1 班的 30 号到 10 班的 20 号呢?对于完整的班级,直接查询;不完整的暴力。

那什么时候这个算法时间复杂度最低呢?答:当块的长度为\sqrt n时。

而这就是分块。

例题

LOJ-P6277:

我们每m个元素个元素分为一块,共有\frac{n}{m}块,以及区间两侧的两个不完整的块。这两个不完整的块中至多2m个元素。我们给每个块设置一个tag(就是记录这个块中元素一起加了多少),每次操作对每个整块直接\Theta (1)标记,而不完整的块元素较少,暴力修改元素的值。

这样,每次询问时返回元素的值加上其所在块的加法标记即可。

时间复杂度\Theta (\frac{n}{m})+\Theta (m)。根据均值不等式,当m\sqrt{n}时总复杂度最低。

#include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
int a[maxn],idx[maxn],tag[maxn],tot;
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++)a[i]+=c;if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)a[i]+=c;}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
int main(){int n;cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)idx[i]=(i-1)/tot+1;for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==1)cout<<a[r]+tag[idx[r]]<<endl;}return O;
}

LOJ-P6278:

我们先来思考只有询问操作的情况,不完整的块枚举统计即可;而要在每个整块内寻找小于一个值的元素数,于是我们不得不要求块内元素是有序的,这样就能使用二分法对块内查询,需要预处理时每块做一遍排序,复杂度\Theta (n\: log\: n),每次查询在\sqrt{n}个块内二分,以及暴力2 \sqrt{n}个元素,总复杂度\Theta (n\: log\: n+n\sqrt{n}\:\: log\: \sqrt{n})

那么区间加怎么办呢?套用第一题的方法,维护一个加法标记,略有区别的地方在于,不完整的块修改后可能会使得该块内数字乱序,所以头尾两个不完整块需要重新排序。在加法标记下的询问操作,块外还是暴力,查询小于(x-tag)的元素个数,块内用(x-tag)作为二分的值即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
int a[maxn],idx[maxn],tag[maxn],tot,n;
vector<int> block[505];
void reset(int x){block[x].clear();for(int i=(x-1)*tot+1;i<=min(x*tot,n);i++)block[x].push_back(a[i]);sort(block[x].begin(),block[x].end());
}
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++)a[i]+=c;reset(idx[l]);if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)a[i]+=c;reset(idx[r]);}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
int query(int l,int r,int c){int ans=0;for(int i=l;i<=min(idx[l]*tot,r);i++){if(a[i]+tag[idx[l]]<c)ans++;}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){if(a[i]+tag[idx[r]]<c)ans++;}}for(int i=idx[l]+1;i<=idx[r]-1;i++)ans+=lower_bound(block[i].begin(),block[i].end(),c-tag[i])-block[i].begin();return ans;
}
int main(){cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;block[idx[i]].push_back(a[i]);}for(int i=1;i<=idx[n];i++)sort(block[i].begin(),block[i].end());for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==1)cout<<query(l,r,c*c)<<endl;}return O;
}

LOJ-P6279:

接着第二题的解法,其实只要把块内查询的二分稍作修改即可。

不过这题其实想表达:可以在块内维护其它结构使其更具有拓展性,比如放一个set,这样如果还有插入、删除元素的操作,会更加的方便。

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000S;
int a[maxn],idx[maxn],tag[maxn],tot=1000;
set<int> st[10S];
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++){st[idx[l]].erase(a[i]);a[i]+=c;st[idx[l]].insert(a[i]);}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){st[idx[r]].erase(a[i]);a[i]+=c;st[idx[r]].insert(a[i]);}}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
int query(int l,int r,int c){int ans=-1;for(int i=l;i<=min(idx[l]*tot,r);i++){int val=a[i]+tag[idx[l]];if(val<c)ans=max(val,ans);}if(idx[l]!=idx[r]){     for(int i=(idx[r]-1)*tot+1;i<=r;i++){int val=a[i]+tag[idx[r]];if(val<c)ans=max(val,ans);}}for(int i=idx[l]+1;i<=idx[r]-1;i++){int x=c-tag[i];set<int>::iterator itr=st[i].lower_bound(x);if(itr==st[i].begin())continue;--itr;ans=max(ans,*itr+tag[i]);}return ans;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;st[idx[i]].insert(a[i]);}for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==1)cout<<query(l,r,c)<<endl;}return 0;
}

LOJ-P6280:

这题的询问变成了区间上的询问,不完整的块还是暴力;而要想快速统计完整块的答案,需要维护每个块的元素和,先要预处理一下。

考虑区间修改操作,不完整的块直接改,顺便更新块的元素和;完整的块类似之前标记的做法,直接根据块的元素和所加的值计算元素和的增量。

#include <bits/stdc++.h>
using namespace std;
int idx[50005],tot;
long long a[50005],tag[50005],sum[50005];
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++){a[i]+=c;sum[idx[l]]+=c;}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){a[i]+=c;sum[idx[r]]+=c;}}for(int i=idx[l]+1;i<=idx[r]-1;i++)tag[i]+=c;
}
long long query(int l,int r){long long ans=0;for(int i=l;i<=min(idx[l]*tot,r);i++)ans+=a[i]+tag[idx[l]];if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)ans+=a[i]+tag[idx[r]];}for(int i=idx[l]+1;i<=idx[r]-1;i++)ans+=sum[i]+tot*tag[i];return ans;
}
int main(){int n;cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;sum[idx[i]]+=a[i];}for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c; if(opt==O)change(l,r,c);if(opt==1)cout<<query(l,r)%(c+1)<<endl;}return 0;
}

LOJ-P6281:

稍作思考可以发现,开方操作比较棘手,主要是对于整块开方时,必须要知道每一个元素,才能知道他们开方后的和,也就是说,难以快速对一个块信息进行更新。

看来我们要另辟蹊径。不难发现,这题的修改就只有下取整开方,而一个数经过几次开方之后,它的值就会变成0或者1

如果每次区间开方只不涉及完整的块,意味着不超过2\sqrt{n}个元素,直接暴力即可。

如果涉及了一些完整的块,这些块经过几次操作以后就会都变成01,于是我们采取一种分块优化的暴力做法,只要每个整块暴力开方后,记录一下元素是否都变成了01,区间修改时跳过那些全为01的块即可。

这样每个元素至多被开方不超过4次,显然复杂度没有问题。

#include <bits/stdc++.h> 
using namespace std;
int a[50005],sum[50005],idx[50005],tot;
bool flag[50005];
void solve(int x){if(flag[x])return;flag[x]=1;sum[x]=0;for(int i=(x-1)*tot+1;i<=x*tot;i++){a[i]=sqrt(a[i]);sum[x]+=a[i];if(a[i]>1)flag[x]=0;}
}
void change(int l,int r,int c){for(int i=l;i<=min(idx[l]*tot,r);i++){sum[idx[l]]-=a[i];a[i]=sqrt(a[i]);sum[idx[l]]+=a[i];}if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++){sum[idx[r]]-=a[i];a[i]=sqrt(a[i]);sum[idx[r]]+=a[i];}}for(int i=idx[l]+1;i<=idx[r]-1;i++)solve(i);
}
int query(int l,int r){int ans=0;for(int i=l;i<=min(idx[l]*tot,r);i++)ans+=a[i];if(idx[l]!=idx[r]){for(int i=(idx[r]-1)*tot+1;i<=r;i++)ans+=a[i];}for(int i=idx[l]+1;i<=idx[r]-1;i++)ans+=sum[i];return ans;
}
int main(){int n;cin>>n;tot=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){idx[i]=(i-1)/tot+1;sum[idx[i]]+=a[i];}for(int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if(opt==0)change(l,r,c);if(opt==l)cout<<query(l,r)<<endl;}return 0;
}

LOJ-P6284:

区间修改没有什么难度,这题难在区间查询比较奇怪,因为权值种类比较多,似乎没有什么好的维护方法。

模拟一些数据可以发现,询问后一整段都会被修改,几次询问后数列可能只剩下几段不同的区间了。

我们思考这样一个暴力,还是分块,维护每个分块是否只有一种权值,区间操作的时候,对于同权值的一个块就\Theta(1)统计答案,否则暴力统计答案,并修改标记,不完整的块也暴力。

这样看似最差情况每次都会耗费\Theta(n)的时间,但其实可以这样分析:

假设初始序列都是同一个值,那么查询是\Theta(\sqrt n),如果这时进行一个区间操作,它最多破坏首尾2个块的标记,所以只能使后面的询问至多多2个块的暴力时间,所以均摊每次操作复杂度还是\Theta(\sqrt{n})。换句话说,要想让一个操作耗费\Theta(n)的时间,要先花费\sqrt{n}个操作对数列进行修改。初始序列不同值,经过类似分析后,就可以放心的暴力啦。

#include <bits/stdc++.h>
using namespace std;
int a[maxn],block[maxn],tag[maxn],n,s;
void reset(int x){if(tag[x]==-1)return;for(int i=(x-1)*s+1;i<=s*x;i++)a[i]=tag[x];tag[x]=-1;
}
int query(int l,int r,int c){    int ans=0;reset(block[l]);for(int i=l;i<=min(block[l]*s,r);i++){if(a[i]!=c)a[i]=c;elseans++;}if(block[l]!=block[r]){reset(block[r]);for(int i=(block[r]-1)*s+1;i<=r;i++){if(a[i]!=c)a[i]=c;elseans++;}}for(int i=block[l]+1;i<=block[r]-1;i++){if(tag[i]!=-1){if(tag[i]!=c)tag[i]=c;elseans+=s;}else{for(int j=(i-1)*s+1;j<=i*s;j++){if(a[j]!=c)a[j]=c;elseans++;}tag[i]=c;}}return ans;
}
int main(){memset(tag,-1,sizeof(tag));int n;cin>>n;s=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)block[i]=(i-1)/s+1;for(int i=1;i<=n;i++){int l,r,c;cin>>l>>r>>c;cout<<query(l,r,c)<<endl;}return 0;
}

HDU 5057:

分块板题。

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int v[maxn][15],tag[320][15][15],a[maxn];
void update(int x,int y,int z){for(int d=1;d<=10;d++){v[x][d]=y%10;tag[x/S][d][y%10]+=z;y/=10;}
}
int query(int l,int r,int d,int p){int L=l/S,R=r/S,res=0;if(L==R){for(int i=l;i<=r;i++)res+=(v[i][d]==p);}else{for(int i=l;i<(L+1)*S;i++)res+=(v[i][d]==p);for(int i=R*S;i<=r;i++)res+=(v[i][d]==p);for(int i=L+1;i<R;i++)res+=tag[i][d][p];}return res;
}
int main(){int t;cin>>t;while(t--){memset(tag,0,sizeof(tag));memset(v,0,sizeof(v));int n,m;cin>>n>>m;S=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];update(i,a[i],1);}while(m--){char op;cin>>op;if(op=='S'){int x,y;cin>>x>>y;update(x,a[x],-1);update(x,y,1);a[x]=y;}else{int l,r,d,p;cin>>l>>r>>d>>p;cout<<query(l,r,d,p)<<endl;}}}return 0;
}

友情提醒:不要Ctrl C+Ctrl V

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/3473.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

模型自动绑骨,在线生成动画,神奇的网站《Mixamo》

英文名mixamo 网站地址&#xff1a;Mixamohttps://www.mixamo.com/#/首先进入需要注册&#xff0c;国内的手机号就可以&#xff0c;但是会有一些慢&#xff0c;多试几次 1、进入界面如下 2、载入自己的模型 2、绑定骨骼 拖动这几个有颜色的圈圈分别对应右图位置&#xff0c;点…

2024 CSS保姆级教程四

CSS中的动画 CSS动画&#xff08;CSS Animations&#xff09;是为层叠样式表建议的允许可扩展标记语言&#xff08;XML&#xff09;元素使用CSS的动画的模块​ 即指元素从一种样式逐渐过渡为另一种样式的过程​ 常见的动画效果有很多&#xff0c;如平移、旋转、缩放等等&#…

Docker安装anythingllm

拉镜像 docker pull mintplexlabs/anythingllm 启动 anythingllm docker run -d --name anythingllm --add-hosthost.docker.internal:host-gateway --env STORAGE_DIR/app/server/storage --health-cmd "/bin/bash/usr/local/bin/docker-healthcheck.sh || exit 1"…

格行:从新晋网红到国货之光,它究竟做对了什么?

作为一家迅速崛起的新消费品牌&#xff0c;近两年来&#xff0c;格行饱受质疑。 无论是商家还是消费者&#xff0c;都有人对其爱之恨之&#xff0c;喜欢它的人&#xff0c;认为它是正义的化身&#xff0c;价格的屠夫&#xff0c;国货的骄傲&#xff0c;原本需要花几百才能买到…

小菜家教平台(二):基于SpringBoot+Vue打造一站式学习管理系统

目录 前言 今日进度 详细过程 一、数据库重构 二、编写登录接口 相关知识点 前言 昨天我们重启了小菜家教平台的开发&#xff0c;创建了新项目并初步进行了配置&#xff0c;今天我们继续。大家要是有需要源码的话可以在评论区跟我说&#xff0c;博客中就不添加源码了~ 今…

数学期望和联合概率密度

数学期望的定义 数学期望是描述随机变量平均趋势的一个重要统计量。根据随机变量的类型&#xff08;离散或连续&#xff09;&#xff0c;数学期望的定义有所不同。 离散型随机变量的数学期望&#xff1a; 若离散型随机变量 X X X取值为 x 1 , x 2 , … , x n , … x_1,x_2,\do…

MRCTF2020:你传你ma呢

文件上传题先判断黑白名单过滤&#xff0c;先传个最简单的木马 这里上传不了php文件&#xff0c;猜测可能是对php文件进行了过滤&#xff0c;将文件改为任意后缀这里改为.abc 还是上传不成功&#xff0c;猜测可能对MIME也做了过滤&#xff0c;将Content-Type更改为image/jpeg再…

Harmony项目基础

项目基础 开发环境 DevEco Stuio下载和安装 DevEco Studio下载 下载链接:https://developer.huawei.com/consumer/cn/deveco-studio/ 安装IDE 直接运行安装文件即可 配置SDK及工具链 DevEco Studio 提供 SDK Manager 统一管理 SDK 及工具组件&#xff0c;包括如下组件包&…

《使用Gin框架构建分布式应用》阅读笔记:p307-p392

《用Gin框架构建分布式应用》学习第16天&#xff0c;p307-p392总结&#xff0c;总86页。 一、技术总结 1.AWS chapter 08讲使用AWS进行部署&#xff0c;可以根据需要选择是否阅读。因为使用到的概率很小&#xff0c;且还要绑卡&#xff0c;本人选择跳过。 2.CI/CD (1)什么…

新一代跟踪器StrongSORT: Make DeepSORT Great Again论文解析—让 DeepSORT 再次伟大

新一代跟踪器StrongSORT: Make DeepSORT Great Again论文解析—让 DeepSORT 再次伟大 时间&#xff1a;2023年 机构:北京邮电大学 发表在&#xff1a;IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 25, 2023 代码源码地址&#xff1a; pytorch版本&#xff1a;https://github.com/dyh…

windows下安装jdk并配置环境

【1】安装jdk 这里建议傻瓜式安装&#xff0c;不要自定义路径&#xff0c;直接下一步下一步。 在Windows系统中安装JDK并设置环境变量&#xff08;包括JAVA_HOME和CLASSPATH&#xff09;是一个常见的任务。 1. 下载并安装JDK 访问Oracle官方网站或其他可信来源下载JDK安装包…

云安全真知实践 国内头部能源企业全面灵活云安全方案大公开

能源与安全&#xff0c;是两个紧密相连的齿轮&#xff0c;驱动着当今社会的运转与发展。能源是动力源泉&#xff0c;而安全则是守护这一动力的坚实支撑&#xff0c;保障着能源系统的运作与敏感数据的安全。 亚信安全一直以来为国内能源行业提供着安全保障&#xff0c;从石油、…

Photoshop 2025重磅来袭 :全新功能炫耀安装!Adobe全家桶

2024年10月&#xff0c;备受期待的Adobe Photoshop 2025正式版如约而至。每年的十月份&#xff0c;Adobe都会带来其软件的重要更新&#xff0c;而今年的Photoshop 2025则在改进和新功能方面做出了重磅升级&#xff0c;让创意工作者和设计师们倍感振奋。 新界面与核心功能 Ph…

【Java面试——计算机基础——网络——一篇就够了!!!】

1. 网络分层模型 1.1 OSI七层模型 OSI 七层模型 是国际标准化组织提出的一个网络分层模型&#xff0c;其大体结构以及每一层提供的功能如下图所示&#xff1a; 每一层都专注做一件事情&#xff0c;并且每一层都需要使用下一层提供的功能比如传输层需要使用网络层提供的路由和…

C#/.NET/.NET Core技术前沿周刊 | 第 11 期(2024年10.21-10.31)

前言 C#/.NET/.NET Core技术前沿周刊&#xff0c;你的每周技术指南针&#xff01;记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿&#xff0c;助力技术成长与视野拓宽。 欢迎投稿、推荐…

(C#面向初学者的 .NET 的生成 AI) 第 3 部分-ChatGPT 简介

在本部分中&#xff0c;将简要介绍ChatGPT。我们将了解ChatGPT是什么&#xff0c;稍微探讨一下ChatGPT中的角色分工&#xff0c;聊天和消息历史记录的作用。最后我们将查看一个使用OpenAI .NET SDK的ChatGPT代码示例。 1、ChatGPT是什么呢&#xff1f; ChatGPT中的GPT部分来…

Java中的日期与时间的间隔:Period类、Duration类

1、Period 类 在 Java 中&#xff0c;Period 类和 Duration 类都是用于表示时间间隔的类&#xff0c;但它们有不同的使用场景和特性。Period 类位于 java.time 包中&#xff0c;主要用于表示基于日期的时间间隔&#xff0c;即年、月、日的差异。它常用于处理日期之间的计算&am…

算法: 链表题目练习

文章目录 链表题目练习两数相加两两交换链表中的节点重排链表合并 K 个升序链表K 个一组翻转链表 总结 链表题目练习 两数相加 坑: 两个链表都遍历完后,可能需要进位. class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 l1;ListNode…

交替传译收费标准

交替传译是一种高端口服务&#xff0c;常用于国际会议、商务洽谈、学术交流等多语言会议场合&#xff0c;演讲者的发言一般不超过15分钟&#xff0c;交替传译员和演讲者采取接力式交替发言&#xff0c;在这种模式下&#xff0c;口译员需要具备优秀的记忆能力和翻译功底。其价格…

灵动AI视频:重塑视频创作,智启无限灵感!

&#x1f680; 在这个视觉为王的时代&#xff0c;视频创作已成为展现创意与才华的重要舞台。然而&#xff0c;繁琐的剪辑流程、有限的创意资源往往成为制约创作者发挥的瓶颈。灵动AI视频&#xff0c;一款集智能、高效、创意于一体的视频编辑神器&#xff0c;正为视频创作领域带…