【分块】[LUOGU 教主的魔法] 分块模板

2023-11-11 22:18

本文主要是介绍【分块】[LUOGU 教主的魔法] 分块模板,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

题目链接:[LUOGU 教主的魔法]
题解:
(才发现我的分块再洛谷上交的题比较少都是在别的OJ上写的比较多,所以就打算补补。。。)
这个题就是个分块的模板题,,,,

这里还是也要补充一下数组和vector的比较:
vector:不定长的数组,但是是动态的,相对于数组来说会比较慢(毕竟是STL),但是比较好排序,以及比较由于是不定长的所以就不用管它的长度。
数组:比较固定是静态的,由于是c++自带的所以就比较简洁而且比较快,但是需要范围的固定。

代码:

#include<bits/stdc++.h>
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e6+7;
int n,m,block,num,a[sea],b[sea],belong[sea],l[sea],r[sea],lazy[sea];
void reset(int x){for(int i=l[x];i<=min(n,r[x]);i++) b[i]=a[i];sort(b+l[x],b+r[x]+1);}//这一点=我之前是用vector写的,但是竟然反复TLE所以就改成了数组,,
int find(int x,int z)
{int L=(x-1)*block+1,R=min(x*block,n);int last=R;while(L<=R){int mid=(L+R)>>1;if(b[mid]<z)L=mid+1; else R=mid-1;}return last-L+1;
}
void build()
{block=sqrt(n); num=n/block;if(n%block) num++; for(int i=1;i<=n;i++) a[i]=read(),belong[i]=(i-1)/block+1,b[i]=a[i];for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block; r[num]=n;for(int i=1;i<num;i++) reset(i);
}
void alter(int x,int y,int z)
{for(int i=x;i<=min(r[belong[x]],y);i++) a[i]+=z;if(belong[x]!=belong[y]){for(int i=l[belong[y]];i<=y;i++) a[i]+=z; for(int i=belong[x]+1;i<belong[y];i++) lazy[i]+=z;	} reset(belong[x]);reset(belong[y]);
}
int ask(int x,int y,int z)
{int ans=0;for(int i=x;i<=min(r[belong[x]],y);i++) if(a[i]+lazy[belong[x]]>=z) ans++;if(belong[x]!=belong[y]){for(int i=l[belong[y]];i<=y;i++) if(a[i]+lazy[belong[y]]>=z) ans++;for(int i=belong[x]+1;i<belong[y];i++) ans+=find(i,z-lazy[i]); //这点原来尝试着用lower_bound(),但是好像不是很对,,而且改完之后就WA掉了,比较不想搞了,就直接手写了,,,} return ans;
}
int main()
{n=read(); m=read(); build();for(int i=1;i<=m;i++){char ch[5];scanf("%s",ch); int x=read(),y=read(),z=read();if(ch[0]=='M') alter(x,y,z);else printf("%d\n",ask(x,y,z));}return 0;
}

Continue……

这篇关于【分块】[LUOGU 教主的魔法] 分块模板的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>

Python中Flask模板的使用与高级技巧详解

《Python中Flask模板的使用与高级技巧详解》在Web开发中,直接将HTML代码写在Python文件中会导致诸多问题,Flask内置了Jinja2模板引擎,完美解决了这些问题,下面我们就来看看F... 目录一、模板渲染基础1.1 为什么需要模板引擎1.2 第一个模板渲染示例1.3 模板渲染原理二、模板

利用Python打造一个Excel记账模板

《利用Python打造一个Excel记账模板》这篇文章主要为大家详细介绍了如何使用Python打造一个超实用的Excel记账模板,可以帮助大家高效管理财务,迈向财富自由之路,感兴趣的小伙伴快跟随小编一... 目录设置预算百分比超支标红预警记账模板功能介绍基础记账预算管理可视化分析摸鱼时间理财法碎片时间利用财

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Rust中的Drop特性之解读自动化资源清理的魔法

《Rust中的Drop特性之解读自动化资源清理的魔法》Rust通过Drop特性实现了自动清理机制,确保资源在对象超出作用域时自动释放,避免了手动管理资源时可能出现的内存泄漏或双重释放问题,智能指针如B... 目录自动清理机制:Rust 的析构函数提前释放资源:std::mem::drop android的妙

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�