数列分块入门 1 (单点查值,区间加法)

简介: 数列分块入门 1 (单点查值,区间加法)

描述:


给出一个长为n 的数列,以及 n 个操作,操作涉及区间加法,单点查值。


输入:


第一行输入一个数字n。

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

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

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

若opt=1,表示询问ar 的值(l和c忽略)。


输出:


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

int len=sqrt(n);//块长
int add[N];//每个块要加的元素
block[i] //第 i 个元素所在的块的编号
len*block[i]//第 i 个块的右边界
(block[i]-1)*len+1//第 i 个块的左边界
block[i]=(i-1)/len+1;//元素与块编号对应关系
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e5+100;
const int p = 1e4;
const double eps = 1e-8;
int n;
int a[N],block[N];
int len;//块长 
int add[N];
void Add(int l,int r,int c)
{   
  for(int i=l;i<=min(r,len*block[l]);i++)
    a[i]+=c;//处理左边非整块
  if(block[l]!=block[r])
    for(int i=(block[r]-1)*len+1;i<=r;i++)
      a[i]+=c;//处理右边非整块
  for(int i=block[l]+1;i<=block[r]-1;i++)
    add[i]+=c;//处理中间的整块 
}
void query(int x)
{
  printf("%d\n",a[x]+add[block[x]]);
}//查询
int opt,l,r,c;
int main()
{
  cin>>n;
  len=sqrt(n);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
    block[i]=(i-1)/len+1;
  }
  for(int i=1;i<=n;i++)
  {
    cin>>opt>>l>>r>>c;
    if(opt==0) Add(l,r,c);
    else query(r);
  } 
}

目录
相关文章
|
7月前
|
安全 网络安全
单域名SSL证书跟通配符SSL证书对比
单域名SSL证书仅保护一个特定域名,如`www.example.com`,适合小型网站,价格较低且配置简单。通配符SSL证书可保护主域名及其所有子域名,如`*.example.com`,适合中大型企业,灵活性高但价格较高。选择时需根据实际需求权衡域名数量、预算和管理复杂度。
416 5
|
10月前
|
JavaScript 前端开发 API
Vue.js响应式原理深度解析:从Vue 2到Vue 3的演进
Vue.js响应式原理深度解析:从Vue 2到Vue 3的演进
271 17
|
11月前
|
前端开发 JavaScript 安全
探索JAMstack架构:现代Web开发的新范式
【10月更文挑战第7天】JAMstack是一种现代Web开发架构,代表JavaScript、APIs和Markup。本文介绍了JAMstack的核心概念、优势及实施步骤,包括内容设计、选择静态站点生成器、API集成、前端开发和部署托管。JAMstack提高了网站的性能、安全性和可扩展性,适用于营销网站、博客、电子商务和Web应用等多种场景。
|
Ubuntu C语言
Ubuntu升级Cmake、gcc、g++
以上就是在Ubuntu中升级Cmake、gcc、g++的步骤。
716 2
Go1.22 新特性:for 循环不再共享循环变量,且支持整数范围
Go1.22 新特性:for 循环不再共享循环变量,且支持整数范围
|
编解码 算法
掌握PWM:STM32F103实现PWM控制直流电机小风扇
PWM,即脉冲宽度调制(Pulse Width Modulation),是一种广泛应用于电子和电机控制领域的信号编码方法。PWM的核心思想是通过改变数字信号的脉冲宽度来模拟模拟信号的幅度变化,从而达到控制输出功率的目的。
1806 0
|
存储 数据库 数据安全/隐私保护
Windows系统部署AnyTXT Searcher并实现远程搜索本地内网设备中文件
Windows系统部署AnyTXT Searcher并实现远程搜索本地内网设备中文件
|
资源调度 JavaScript 前端开发
vue使用echarts图表
vue使用echarts图表
250 0
|
Linux BI
设置Linux服务器时间为北京时间
设置Linux服务器时间为北京时间
873 1
|
前端开发 JavaScript
浅谈React split_分割字符串
浅谈React split_分割字符串
230 0