洛谷 P2801 教主的魔法 题解

之前学过 莫队 算法,其运用了分块思想;但是我居然是第一次写纯种的分块题目。

题意

给你一个长度为 n n n 的序列 a a a(一开始 ∀ a i ∈ [ 1 , 1000 ] \forall a_i\in[1,1000] ai[1,1000])。要求执行 q q q 次操作,操作有两种,每次形如 o p , l , r , w / c op,l,r,w/c op,l,r,w/c

  • o p op op M \rm M M,将 a l , a l + 1 , ⋯ , a r a_l,a_{l+1},\cdots,a_r al,al+1,,ar 分别加上 w w w
  • o p op op A \rm A A,查询 a l , a l + 1 , ⋯ , a r a_l,a_{l+1},\cdots,a_r al,al+1,,ar 中,有多少个数大于 c c c

n ≤ 1 0 6 , q ≤ 3000 , w ≤ 1000 , c ≤ 1 0 9 n\le10^6,q\le3000,w\le1000,c\le10^9 n106,q3000,w1000,c109

思路

主席树?是我早就不会打的。

如果我们把它变成一道分块练习题呢?

考虑对序列 a a a 分块,对于每一块内,使用辅助数组 b b b 以保证块内数有序。不妨设 b l t , b r t bl_t,br_t blt,brt 表示块 t t t 的左右端点, b e l i bel_i beli 表示下标 i i i 所在的块的编号。

对于修改操作 l , r , w l,r,w l,r,w,如果 ∃ t , b l t ≤ l < r ≤ b r t \exist t,bl_t\le l<r\le br_t t,bltl<rbrt,即同一块, t = b e l l = b e l r t=bel_l=bel_r t=bell=belr,如果其不在左右端点上,那么块内的排序性质就会被破坏;反之如果它们不在同一块,说明它们中间跨过了若干块整块的区间,我们发现被跨过的区间仍然保持有序

那么我们得到一个初步的修改方法:

  • 设左右端点所在的块分别在 l b = b e l l , r b = b e l r lb=bel_l,rb=bel_r lb=bell,rb=belr,如果 l b = r b lb=rb lb=rb,就块内暴力加 w w w 并快排更新;
  • 否则即 l b < r b lb<rb lb<rb,我们发现块 l b + 1 ∼ r b − 1 lb+1\sim rb-1 lb+1rb1 内仍然有序,那么不妨想线段树引入懒惰标记一样,我们搞一个加法标记,把整一块 t t t 内所有元素同时加的数,用 t a g t tag_t tagt 记录下来,等到查询时再处理;只强制更新更新 l ∼ b r l b l\sim br_{lb} lbrlb b l r b ∼ r bl_{rb}\sim r blrbr 的数据和块 l b , r b lb,rb lb,rb

这样子大大减少了排序的次数,每次修改操作顶多 2 × log ⁡ 2 n 2\times \log_2n 2×log2n,瓶颈在于快排。

void modify(ll t)//更新t块内数据
{for(int i=bl[t];i<=br[t];i++)b[i]=a[i];sort(b+bl[t],b+br[t]+1);
}
void add(ll ql,ll qr,ll x)//l,r,w
{ll lb=bel[ql],rb=bel[qr];//左右端所在块if(lb==rb)//同一块{for(int i=ql;i<=qr;i++)a[i]+=x;modify(lb);return;}//不同块for(int i=ql;i<=br[lb];i++)a[i]+=x;for(int i=bl[rb];i<=qr;i++)a[i]+=x;modify(lb);modify(rb);for(int i=lb+1;i<rb;i++)//lb+1~rb-1块打标记tag[i]+=x;
}

接下来就是查询,其实就和修改所运用的思想差不多了。同样讨论 l , r l,r l,r 在或不在同一块的两种情况。如果同一块就直接 q l ∼ q r ql\sim qr qlqr 扫过去(倒着枚举体检 break 凹时间也行、甚至乎二分,反正块内就是有序的),不同块就搜左右两边 l ∼ b r r b l\sim br_{rb} lbrrb b l r b ∼ r bl_{rb}\sim r blrbr,至于中间的整块整块的,按块二分就好。

ll find(ll ql,ll qr,ll x)
{ll l=ql,r=qr;while(l<=r){ll mid=(l+r)>>1;if(b[mid]<x)l=mid+1;else r=mid-1;}return qr-l+1;
}
ll query(ll ql,ll qr,ll x)
{ll ret=0,lb=bel[ql],rb=bel[qr];if(lb==rb){ret+=find(ql,qr,x-tag[lb]);return ret;}for(int i=ql;i<=br[lb];i++)if(a[i]+tag[lb]>=x)ret++;for(int i=bl[rb];i<=qr;i++)if(a[i]+tag[rb]>=x)ret++;for(int i=lb+1;i<rb;i++)ret+=find(bl[i],br[i],x-tag[i]);return ret;
}

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+9;
ll n,q,a[N];
ll tag[N];//加法标记
ll bSize,cnt_b,bel[N],bl[N],br[N],b[N];
void init()
{bSize=sqrt(n);cnt_b=n/bSize;if(n%bSize)cnt_b++;for(int i=1;i<=n;i++){bel[i]=(i-1)/bSize+1;b[i]=a[i];}for(int i=1;i<=cnt_b;i++){bl[i]=(i-1)*bSize+1;br[i]=i*bSize;}br[cnt_b]=n;for(int i=1;i<=cnt_b;i++)sort(b+bl[i],b+br[i]+1);
}
void modify(ll t)//更新t块内数据
{for(int i=bl[t];i<=br[t];i++)b[i]=a[i];sort(b+bl[t],b+br[t]+1);
}
void add(ll ql,ll qr,ll x)
{ll lb=bel[ql],rb=bel[qr];//左右端所在块if(lb==rb)//同一块{for(int i=ql;i<=qr;i++)a[i]+=x;modify(lb);return;}//不同块for(int i=ql;i<=br[lb];i++)a[i]+=x;for(int i=bl[rb];i<=qr;i++)a[i]+=x;modify(lb);modify(rb);for(int i=lb+1;i<rb;i++)//lb+1~rb-1块打标记tag[i]+=x;
}
ll find(ll ql,ll qr,ll x)
{ll l=ql,r=qr;while(l<=r){ll mid=(l+r)>>1;if(b[mid]<x)l=mid+1;else r=mid-1;}return qr-l+1;
}
ll query(ll ql,ll qr,ll x)
{ll ret=0,lb=bel[ql],rb=bel[qr];if(lb==rb){ret+=find(ql,qr,x-tag[lb]);return ret;}for(int i=ql;i<=br[lb];i++)if(a[i]+tag[lb]>=x)ret++;for(int i=bl[rb];i<=qr;i++)if(a[i]+tag[rb]>=x)ret++;for(int i=lb+1;i<rb;i++)ret+=find(bl[i],br[i],x-tag[i]);return ret;
}
int main()
{scanf("%lld%lld",&n,&q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);init();while(q--){char op;ll l,r,x;cin>>op;scanf("%lld%lld%lld",&l,&r,&x);if(op=='M')add(l,r,x);else printf("%lld\n",query(l,r,x));}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

不像人做的题————十四届蓝桥杯省赛真题解析(上)A,B,C,D题解析

题目A&#xff1a;日期统计 思路分析&#xff1a; 本题的题目比较繁琐&#xff0c;我们采用暴力加DFS剪枝的方式去做&#xff0c;我们在DFS中按照8位日期的每一个位的要求进行初步剪枝找出所有的八位子串&#xff0c;但是还是会存在19月的情况&#xff0c;为此还需要在CHECK函数…

宇树人形机器人开源模型

1. 下载源码 https://github.com/unitreerobotics/unitree_ros.git2. 启动Gazebo roslaunch h1_description gazebo.launch3. 仿真效果 H1 GO2 B2 Laikago Z1 4. VMware: vmw_ioctl_command error Invalid argument 这个错误通常出现在虚拟机环境中运行需要OpenGL支持的应用…

【C/C++算法】从浅到深学习--- 前缀和算法(图文兼备 + 源码详解)

绪论&#xff1a;冲击蓝桥杯一起加油&#xff01;&#xff01; 每日激励&#xff1a;“不设限和自我肯定的心态&#xff1a;I can do all things。 — Stephen Curry” 绪论​&#xff1a; 本章将使用八道题由浅到深的带你了解并基本掌握前缀和思想&#xff0c;以及前缀和的基…

脑电:时域分析(任务态)

时域分析&#xff1a;时间序列&#xff08;时域信号&#xff09; EEG和ERP都是时间序列 ERP&#xff1a;事件诱发的电位是随着时间变化 组水平&#xff1a;需要这一组的个体不能差异性太大。 提值的指标&#xff0c;选取平均幅值确定成分的显著情况 mean(EEG.data,3): 在第…

【C语言】自定义类型:结构体,联合,枚举(下)

前言&#xff1b;上一期我们侧重讲了一个非常重要的自定义类型结构体&#xff0c;这一期我们来说说另外两种自定义类型&#xff1a;联合&#xff0c;和枚举。 传送门&#xff1a;自定义类型&#xff1a;结构体&#xff0c;联合&#xff0c;枚举(上) 文章目录 一&#xff0c;联…

数组的介绍

1.数组的概念 数组是一组相同类型元素的集合&#xff0c;从这个描述中我们知道&#xff1a; 数组中存放1个或多个数据&#xff0c;但是数组的元素个数不为0。数组中存放的多个数据&#xff0c;类型是相同的。 数组分为一维数组和多维数组&#xff0c;多维数组一般比较多见的…

蓝桥杯 17110抓娃娃

问题描述 小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上&#xff0c;第 i 条线段的左端点在 li&#xff0c;右端点在 ri​。小明用 m 个区间去框这些线段&#xff0c;第 i个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内&#xff0c;…

linux ptrace 图文详解(二) PTRACE_TRACEME 跟踪程序

目录 一、基础介绍 二、PTRACE_TRACE 实现原理 三、代码实现 四、总结 &#xff08;代码&#xff1a;linux 6.3.1&#xff0c;架构&#xff1a;arm64&#xff09; One look is worth a thousand words. —— Tess Flanders 一、基础介绍 GDB&#xff08;GNU Debugger&…

记录致远OA服务器硬盘升级过程

前言 日常使用中OA系统突然卡死&#xff0c;刷新访问进不去系统&#xff0c;ping服务器地址正常&#xff0c;立马登录服务器检查&#xff0c;一看磁盘爆了。 我大脑直接萎缩了&#xff0c;谁家OA系统配400G的空间啊&#xff0c;过我手的服务器没有50也是30台&#xff0c;还是…

电网电压暂态扰动机理与工业设备抗失压防护策略研究

什么是晃电&#xff1f; 国标GB/T 30137-2013 中定义:工频电压方均根值突然降至额定值的90%~10%&#xff0c;持续时间为10ms~1min后恢复正常的现象。Acrel8757V 晃电的原因 1.系统侧因素 短路故障&#xff1a;雷击、线路接地、设备误碰等导致电网短路&#xff0c;故障点电压…

Linux监控网络状态

一、基本介绍 1、基本语法 netstat [选项] 2、常用选项 选项 说明 -a 显示所有连接和监听的套接字&#xff08;包括TCP、UDP&#xff09;。 -t 显示 TCP 连接。 -u 显示 UDP 连接。 -l 显示正在监听的套接字&#xff08;server端&#xff09;。 -n 显示数字格式的…

UE5以插件的形式加载第三方库

之前在UE中加载第三方库的形式是以静态或者动态链接的形式加载但是不太容易复用。就想着能不能以插件的形式加载第三方库&#xff0c;这样直接把插件打包发行就可以复用了&#xff0c;之前也找过相应的教程但是很难找到比较简单易懂的教程&#xff0c;要么是比较复杂&#xff0…

Go执行当前package下的所有方法

需求&#xff1a;需要一个文件一个定时任务方法&#xff0c;当项目初始化完毕后&#xff0c;自动加载并执行这些定时任务方法 项目目录架构 main.go 初始化 package mainimport ("sql_demo/schedule" )func main() {/***** 其他初始化完毕后的操作**/// 定时任务sc…

AnyAnomaly: 基于大型视觉语言模型的零样本可定制视频异常检测

文章目录 速览摘要1. 引言2. 相关工作视频异常检测大型视觉语言模型&#xff08;LVLMs&#xff09; 3. 方法3.1. 总览3.2. 关键帧选择模块3.3. 上下文生成基于 WinCLIP 的注意力机制网格图像生成 3.4. 异常检测提示词设计异常评分 4. 实验4.1. 数据集4.2. 评估标准4.3. 结果4.4…

【AWS入门】2025 AWS亚马逊云科技账户注册指南

【AWS入门】2025 AWS亚马逊云科技账户注册指南 A Guide To Register a New account on AWS By JacksonML 0. AWS亚马逊云科技简介 Amazon Web Service(AWS) 即亚马逊云科技&#xff0c;其在全球Cloud Computing(云计算)市场占有最为重要的地位。 AWS连续13年被Gartner评为…

Spring 中 SmartInitializingSingleton 的作用和示例

一、 接口定义 SmartInitializingSingleton 是 Spring 框架提供的一个 单例 Bean 全局初始化回调接口&#xff0c;用于在 所有非延迟单例 Bean 初始化完成后 执行自定义逻辑。 核心方法&#xff1a; public interface SmartInitializingSingleton {void afterSingletonsInsta…

element tree树形结构默认展开全部

背景&#xff1a; el-tree树形结构&#xff0c;默认展开全部&#xff0c;使用属性default-expand-all【是否默认展开所有节点】&#xff1b;默认展开一级&#xff0c;设置default-expanded-keys【默认展开的节点的 key 的数组】属性值为数组。 因为我这里的数据第一级是四川【省…

大数据-spark3.5安装部署之local模式

spark&#xff0c;一个数据处理框架和计算引擎。 下载 local模式即本地模式&#xff0c;就是不需要任何其他节点资源就可以在本地执行spark代码的环境。用于练习演示。 上传解压 使用PortX将文件上传至/opt 进入/opt目录&#xff0c;创建目录module&#xff0c;解压文件至/o…

Discuz建站教程之论坛头部logo跳转链接怎么修改?

在修改头部logo跳转链接前&#xff0c;我们需要知道对应代码在哪个文件目录&#xff0c;进入宝塔或是服务器&#xff0c;找到文件&#xff1a;\template\default\common\header.htm&#xff0c;编辑器打开&#xff0c;搜索以下代码&#xff0c;大概在135行 <a href"{i…

【FreeRTOS】FreeRTOS操作系统在嵌入式单片机上裸机移植

目录 一 RTOS概述 二 FreeRTOS移植 三 FreeRTOS使用 四 附录 一 RTOS概述 先了解一些基础概念,以下内容摘自FreeRTOS官网(FreeRTOS™ - FreeRTOS™): 【1】RTOS基础知识 实时操作系统 (RTOS) 是一种体积小巧、确定性强的计算机操作系统。 RTOS 通常用于需要在严格时间限…