#6280. 数列分块入门 4

news/2024/2/28 18:54:30

#6280. 数列分块入门 4

内存限制:256 MiB时间限制:500 ms标准输入输出

题目描述

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,区间求和。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字,第 i 个数字为 ai,以空格隔开。

接下来输入 n 行询问,每行输入四个数字 opt、l、r、c,以空格隔开。

若 opt=0,表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1,表示询问 [l,r] 中,的所有数字的和mod(c+1)。

输出格式

对于每次询问,输出一行一个数字表示答案。

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输出

1
4

思路:区间的和,用一个sum数组来维护每个块的和,对于每次区间更新,如果是在完整的块里更新的时候直接给该块打上一个add加法标记,并更新每块的sum数组的值,用add数组来维护加法标记,如果是不完整的块,直接暴力修改每个块的值,且同时更新区间和的值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+7;
typedef long long ll;
inline int read()
{char ch = getchar(); int x = 0, f = 1;while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}return x * f;
}
int a[maxn],l[maxn],r[maxn],belong[maxn];
ll sum[maxn],add[maxn];
int n,num,block;void build()
{block = sqrt(n);num = n / block; if(n % block) num++;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 <= n; i++){belong[i] = (i - 1) / block + 1;sum[belong[i]] += a[i];}
}void update(int x,int y,int c)
{int t1 = belong[x], t2 = belong[y];for(int i = x; i <= min(r[t1], y); i++){a[i] += c;sum[t1] += c;}if(t1 != t2) for(int i = l[t2]; i <= y; i++){a[i] += c;sum[t2] += c;}for(int i = t1 + 1; i < t2; i++)sum[i] += block * c, add[i] += c;
}ll query(int x,int y,int c)
{ll ans = 0;int t1 = belong[x], t2 = belong[y];for(int i = x; i <= min(r[t1], y); i++)ans += a[i] + add[t1];if(t1 != t2) for(int i = l[t2]; i <= y; i++)ans += a[i] + add[t2];for(int i = t1 + 1; i < t2; i++)ans += sum[i];return ans % (c + 1);
}int main()
{while(~scanf("%d",&n)){for(int i = 1; i <= n; i++) a[i] = read();build();for(int i = 1; i <= n; i++){int op = read(), l = read(), r = read(), c = read();if(op == 1) printf("%lld\n", query(l,r,c));else update(l,r,c);}}return 0;
}

 


http://www.ppmy.cn/news/277581.html

相关文章

【LibreOJ】#6280. 数列分块入门 4 分块

题目描述 给出一个长为 的数列&#xff0c;以及 个操作&#xff0c;操作涉及区间加法&#xff0c;区间求和。 输入格式 第一行输入一个数字 。 第二行输入 个数字&#xff0c;第 个数字为 &#xff0c;以空格隔开。 接下来输入 行询问&#xff0c;每行输入四个数字 、、、&a…

快速搭建,降低成本!了解低代码平台适用的五大场景

对于希望简化应用程序开发流程的公司来说&#xff0c;低代码平台已经成为一种有效的解决方案。这些平台使创建和部署应用程序成为可能&#xff0c;而不需要广泛的编码技能或知识&#xff0c;从而使过程更快、更高效、更具成本效益。但是&#xff0c;低代码平台适用于哪些场景呢…

LibreOJ #6280. 数列分块入门 4 分块

https://loj.ac/problem/6280 思路&#xff1a;分块 l a z y lazy lazy标记。和线段树的思路差不多。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<set> #include<map>…

LibreOJ #6280. 数列分块入门 4

题目链接&#xff1a; https://loj.ac/problem/6280 题意&#xff1a; 给你一个n个整数的序列&#xff0c;让你进行两种操作&#xff1b; 给 [ l , r ] [l,r] [l,r]的之间的数字加上一个值 x x x询问 [ l , r ] [l,r] [l,r]的之间的数字的和 m o d mod mod ( x 1 ) (x1) …

LOJ6280 数列分块入门4

LOJ6280 数列分块入门 4 标签 分块入门 前言 我的csdn和博客园是同步的&#xff0c;欢迎来访danzh-博客园~ 简明题意 维护序列&#xff0c;支持两种操作&#xff1a; 区间加区间查询 思路 多维护一个tag[]和一个sum[]就可以了~ 注意事项 无 总结 无 AC代码 #include<…

LOJ6280 数列分块入门 4

LOJ6280 数列分块入门 4 标签 分块入门 前言 我的csdn和博客园是同步的&#xff0c;欢迎来访danzh-博客园~ 简明题意 维护序列&#xff0c;支持两种操作&#xff1a; 区间加区间查询 思路 多维护一个tag[]和一个sum[]就可以了~ 注意事项 无 总结 无 AC代码 #include<cstdio&…

一块带给无数人年少欢乐的CPU,别说你没用过它

Part1一块带给无数人年少欢乐的CPU&#xff0c;别说你没用过它 图上的这些你有用过吗&#xff1f; 1975 年推出时&#xff0c;它是市场上最便宜的微处理器&#xff08;售价25美元&#xff09;&#xff0c;其优势相当可观。它最初的售价不到大公司&#xff08;如 6800 或英特尔 …

【力扣周赛#326】6279.数组乘积中的不同质因数数目+6196.将字符串分割成值不超过K的子字符串+6280.范围内最接近的两个质数

目录 6278.统计能整除数字的位数 - 简单ac 6279.数组乘积中的不同质因数数目 - 质因数 6196.将字符串分割成值不超过K的子字符串 - 贪心 6280.范围内最接近的两个质数 - 质数筛 贪心 6278.统计能整除数字的位数 - 简单ac 6278. 统计能整除数字的位数 class Solution {pu…

webpack打包处理字体图标、map4、map3、avi资源

一、字体图标资源的下载&#xff08;阿里巴巴图标库&#xff09; iconfont官网&#xff1a;https://www.iconfont.cn/ 这里你可以搜索你想要的字体图标&#xff0c;或者选择官方的图标库中查找&#xff0c;我这里就以官方的图标库为例&#xff1a; 选择几个加入购物车 点…

MC30P6280 上海晟矽微8位1K内存MTP单片机

MC30P6280可以理解为是晟矽微的6250升级型号&#xff0c;性价比更高&#xff01; MC30P6280 8 位 CPU 内核 & 精简指令集&#xff0c;5 级深度硬件堆栈 & CPU 为单时钟&#xff0c;仅在系统主时钟下运行 & 系统主时钟下 FCPU 固定为 FOSC 的 2 分频 MC30P6280 程…

linux环境下QT使用QProcess 关闭程序

Windows关闭程序的方法&#xff1a; 在qt代码里有时需要qprocess调用第三方程序&#xff0c;调用完后需要终止。手动叉掉不合适。此时可以调用window下的taskkill程序关闭该程序 QProcess process; process.execute("taskkill /im xx.exe /f"); linux关闭程序的方…

C++学习之旅 -类和对象(重点)

文章目录 封装封装的意义案例1案例2 访问权限C中class和struct的区别成员属性私有化构造函数和析构函数构造函数析构函数构造函数的分类以及调用构造&调用 拷贝构造函数调用时机深拷贝&浅拷贝初始化列表类对象作为类成员静态成员C对象模型&this指针成员变量和成员函…

Lenovo Y750 7-15IMH05 LA-J561P Rev 1.0笔记本原理图

品牌 联想Lenovo 型号 Legion Y750 7-15IMH05 版号 LA-J561P 版本号 Rev 1.0 图纸类型 笔记本图纸 图纸内容 笔记本电路原理图纸 图纸格式 PDF 共100页

RS485以及MODBUS知识积累

1、金沙滩开发板的知识以及代码 RS485的知识注意点 需要注意的是&#xff0c;RS485是要设置收发模式的&#xff0c;因此&#xff0c;必须进行收发模式的设置。 第二个要注意的是&#xff0c;RS485的通信的RTU模式的CRC校验&#xff0c;是低位在前&#xff0c;高位在后。必须要…

RS485 / RS422

RS422可以变为RS485&#xff1a;A和Y短路&#xff08;然后接T/R&#xff09;&#xff0c;B和Z短路&#xff08;然后接T/R-&#xff09; RS485是半双工&#xff0c;只有两根线通信线&#xff0c;要么接收状态&#xff0c;要么发送状态 RE为低电平&#xff0c;作为接收器 DE为高电…

详解RS232、RS485、RS422串口协议

RS232、RS485、RS422基础知识 &#xff08;1&#xff09;RS232基础知识 计算机与计算机或计算机与终端之间的数据传送可以采用串行通讯和并行通讯两种方式。由于串行通讯方式具有使用线路少、成本低&#xff0c;特别是在远程传输时&#xff0c;避免了多条线路特性的不一致而被…

C++/MFC串口应用总结(232/485)

参考&#xff1a;https://blog.csdn.net/woxinfei/article/details/2394101 串口基础 在C/MFC中&#xff0c;如果不使用串口控件&#xff0c;则无法直接操作串口“硬件”&#xff0c;因此需要把串口当做文件看待。 串口的一些函数 原型&#xff1a;HANDLE CreateFile(LPCTS…

Android基于串口通讯笔记(USB,485协议,232协议)

串口通信&#xff08;Serial Communications&#xff09;的概念非常简单&#xff0c;串口按位&#xff08;bit&#xff09;发送和接收字节。尽管比按字节&#xff08;byte&#xff09;的并行通信慢&#xff0c;但是串口可以在使用一根线发送数据的同时用另一根线接收数据。它很…

STC15W408AS的485串口实现自发自收

STC15W408AS的485串口实现自发自收 485串口 STC的坑 STC单片机发送数据给485串口的时候&#xff0c;发数据一般都没有问题&#xff0c;但是收数据的时候&#xff0c;一般收不到。我改动了两版电路板&#xff0c;才得到正确的方式。STC新版的单片机和以前的不一样了。部分不具…
最新文章