acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」
问题 简单 建议 收藏 整数 标记 线段 懒惰
2023-06-13 09:13:02 时间
大家好,又见面了,我是你们的朋友全栈君。
原题链接 给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:
C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。 Q l r,表示询问数列中第 l∼r 个数的和。 对于每个询问,输出一个整数表示答案。
输入格式 第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。
输出格式 对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围 1≤N,M≤105, |d|≤10000, |A[i]|≤109 输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例:
4
55
9
15
题解 线段树模板
#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
struct Node{
int l,r;
ll v;
ll add; //懒惰标记,保存当前节点以及子节点应该加上的值
}tr[N * 4];
int a[N];
void push_up(int u){
tr[u].v = tr[left(u)].v + (tr[left(u)].r - tr[left(u)].l + 1) * tr[left(u)].add
+ tr[right(u)].v + (tr[right(u)].r - tr[right(u)].l + 1) * tr[right(u)].add;
}
void push_down(int u){
if(tr[u].add){
tr[u].v += (tr[u].r - tr[u].l + 1) * tr[u].add;
tr[left(u)].add += tr[u].add;
tr[right(u)].add += tr[u].add;
tr[u].add = 0;
}
}
void build(int l,int r,int u){
if(l == r){
tr[u] = {
l,r,a[l],0};
return;
}
else{
tr[u] = {
l,r,0,0};
int mid = (l + r) >> 1;
build(l, mid, left(u));
build(mid + 1, r, right(u));
push_up(u);
}
}
ll query(int l,int r,int u){
push_down(u);
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].v;
}
int mid = (tr[u].l + tr[u].r) >> 1;
ll sum = 0;
if(l <= mid)sum += query(l,r,left(u));
if(r > mid)sum += query(l,r,right(u));
return sum;
}
void modify(int l,int r,int x,int u){
if(tr[u].l >= l && tr[u].r <= r)tr[u].add += x;
else{
push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid)modify(l,r,x,left(u));
if(r > mid)modify(l,r,x,right(u));
push_up(u); //修改了值就要push_up
}
}
void update(int x,int y,int u){
if(tr[u].l == x && tr[u].r == x)tr[u].v = y;
else{
push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid)update(x,y,left(u));
else update(x,y,right(u));
push_up(u);
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i ++){
cin>>a[i];
}
build(1,n,1);
char c;
int l,r,a;
for(int i = 0;i < m;i ++){
cin>>c>>l>>r;
if(c == 'Q'){
cout<<query(l,r,1)<<endl;
}else if(c == 'C'){
cin>>a;
modify(l,r,a,1);
}
}
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/168777.html原文链接:https://javaforall.cn
相关文章
- Ubuntu下VLC播放器的字幕乱码问题
- 八数码问题简单解决办法
- 删除重复项很简单?来看看这个实际工作问题? | Power Query实战
- python猴子摘桃问题_python解决简单实际问题
- 【面试高频题】难度 1/5,简单二叉树寻值问题
- Centos7用户名密码正确,在登录界面循环问题
- 最新!最简单!解决注册ChatGPT手机号无法接收验证码问题亲测有效!【图文并茂的教程】
- Windows 远程时提示CredSSP 加密数据库修正 问题的简单处理.
- Linux简介及最常用命令(简单易学,但能解决95%以上的问题)
- 聊聊使用RedisTemplat实现简单的分布式锁的问题
- 解决JDBC的class.forName()问题
- 破解Linux显示问题:从未更简单(linux显示不全)
- 解决Linux菜单栏消失问题,快速找回桌面常用功能(linux菜单栏消失了)
- 解决Mysql乱码问题:做好保存准备(保存到mysql乱码)
- 解决Linux下Web乱码问题的有效方法(linuxweb乱码)
- Oracle01002解决你的数据库问题(oracle-01002)
- 解决MySQLpn文件丢失问题的简单方法(mysql_pn文件丢失)
- 解决方法MySQL无法读取INI文件的问题(mysql不加载ini)
- 解决MySQL安装问题一些简单方法(mysql不能安装怎么办)
- 踩坑记使用Redis遇到的问题(使用redis遇到的问题)
- 攻克oracle上云难题追求卓越之路(oracle 上云问题)
- mysql4.1以上版本连接时出现Clientdoesnotsupportauthenticationprotocol问题解决办法
- 关于js中alert弹出窗口文本换行问题简单详细说明
- C#Js时间格式化问题简单实例
- 快速解决jquery之get缓存问题的最简单方法介绍
- ajax获取数据中文乱码问题最简单的完美解决方案