P1253 扶苏的问题(洛谷)(线段树)

2023-11-27 08:40

本文主要是介绍P1253 扶苏的问题(洛谷)(线段树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

     tag值存两个,一个覆盖值,一个累加值,再开一个变量存是否有覆盖值。因为覆盖值可能为零,也可以置为一个极小的值作为覆盖值是否存在的判断条件(如-1e18),除了注释的部分要注意一下以外,其余纯模板。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define int long long
typedef pair<int, int> PII;
int n, m, k;
int T;
int a[N];
int tree[N * 4];
struct node
{int x, y, z;          //分别指的是覆盖值,累加值和是否有覆盖值。只需要维护覆盖值,不需要维护累加值
} tag[N * 4];
void push_up(int rt)
{tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}void build(int rt, int l, int r)
{if (l == r){tree[rt] = a[l];return;}int mid = l + r >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt);
}void push_down(int rt)
{if(tag[rt].z)       //如果有覆盖值{tag[rt<<1].x = tag[rt].x, tag[rt<<1|1].x = tag[rt].x;tag[rt<<1].y = tag[rt].y, tag[rt<<1|1].y = tag[rt].y; //特别注意这里的累加值要直接赋值过去,而不是+=tag[rt<<1].z = tag[rt<<1|1].z = 1;                   //因为若存在覆盖值,之前存在的累加值就已经没有意义tree[rt<<1] = tag[rt].x + tag[rt].y;tree[rt<<1|1] = tag[rt].x + tag[rt].y;}else{tag[rt<<1].y += tag[rt].y;tag[rt<<1|1].y += tag[rt].y;tree[rt<<1] += tag[rt].y;tree[rt<<1|1] += tag[rt].y;}tag[rt].x = tag[rt].y = tag[rt].z = 0;
}void updata(int rt, int l, int r, int start, int end, int data, int f)
{if(f==1){if(start <= l && end >= r){tag[rt].x = data;tag[rt].y = 0;        //累加值置为0,都被覆盖了,已经没有意义tree[rt] = data;tag[rt].z = 1;        //存在覆盖值(覆盖值可以是零,所以不能用tag[i].x==0作为判断条件)return;}}else{if(start <= l && end >= r){tree[rt] += data;tag[rt].y += data;return;}}push_down(rt);int mid = l + r >> 1;if(start <= mid) updata(rt<<1, l, mid, start, end, data, f);if(end >= mid + 1) updata(rt<<1|1, mid+1, r, start, end, data, f);push_up(rt); 
}int query(int rt, int l, int r, int start, int end)
{if(start <= l && end >= r)return tree[rt];push_down(rt);int res = -1e18;          //因为会爆int,一定要非常小,没注意到,写的0x3f3f3f3f卡好久int mid = l + r >> 1;if(start <= mid) res = max(res, query(rt<<1, l, mid, start, end));if(end >= mid+1) res = max(res, query(rt<<1|1, mid+1, r, start, end));return res;
}signed main()
{ios::sync_with_stdio(false), cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}build(1, 1, n);while (m--){int a, b, c, d;cin >> k;if (k == 1){cin >> a >> b >> c;updata(1, 1, n, a, b, c, 1);}else if (k == 2){cin >> a >> b >> c;updata(1, 1, n, a, b, c, 2);}else{cin >> a >> b;int t = query(1, 1, n, a, b);cout << t << "\n";}}return 0;
}

这篇关于P1253 扶苏的问题(洛谷)(线段树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/427372

相关文章

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

Pyserial设置缓冲区大小失败的问题解决

《Pyserial设置缓冲区大小失败的问题解决》本文主要介绍了Pyserial设置缓冲区大小失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录问题描述原因分析解决方案问题描述使用set_buffer_size()设置缓冲区大小后,buf

resultMap如何处理复杂映射问题

《resultMap如何处理复杂映射问题》:本文主要介绍resultMap如何处理复杂映射问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录resultMap复杂映射问题Ⅰ 多对一查询:学生——老师Ⅱ 一对多查询:老师——学生总结resultMap复杂映射问题

java实现延迟/超时/定时问题

《java实现延迟/超时/定时问题》:本文主要介绍java实现延迟/超时/定时问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java实现延迟/超时/定时java 每间隔5秒执行一次,一共执行5次然后结束scheduleAtFixedRate 和 schedu

如何解决mmcv无法安装或安装之后报错问题

《如何解决mmcv无法安装或安装之后报错问题》:本文主要介绍如何解决mmcv无法安装或安装之后报错问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mmcv无法安装或安装之后报错问题1.当我们运行YOwww.chinasem.cnLO时遇到2.找到下图所示这里3.

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

Vue3使用router,params传参为空问题

《Vue3使用router,params传参为空问题》:本文主要介绍Vue3使用router,params传参为空问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录vue3使用China编程router,params传参为空1.使用query方式传参2.使用 Histo

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La