线段树 区间赋值 + 区间加减 + 求区间最值

线段树好题:P1253 扶苏的问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间赋值 + 区间加减 + 求区间最大。

对于区间赋值和区间加减来说,需要两个懒标记,一个表示赋值cover,一个表示加减add

区间赋值的优先级大于区间加减。

对于区间赋值来说,需要将区间加减的标记重置,因为赋值完后,之前的区间加减队现在的值没有影响。

void coverdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.cover != -INF) {left.add = right.add = 0;left.ma = right.ma = root.cover;left.cover = right.cover = root.cover;root.cover = -INF;}
}

对于区间加减来说,需要先用区间赋值得到最新的值,之后再进行加减操作。

void sumdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.add) {coverdown(u);left.ma += root.add; right.ma += root.add;left.add += root.add; right.add += root.add;root.add = 0;}    
}

线段树中一般的pushdown的顺序不变,但是在pushdown函数中,需要先执行coverdown再执行sumdown。

void pushdown(int u) {coverdown(u); sumdown(u);
}

区间加减时,只需要先进行区间赋值就行。

void modify_add(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {coverdown(u);tr[u].ma += d;tr[u].add += d;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_add(ls(u), l ,r, d);if(r > mid) modify_add(rs(u), l, r, d);pushup(u);}
}

区间赋值时,需要先将区间加减懒标记重置,其他一样。

void modify_cover(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {tr[u].add = 0;tr[u].ma = d;tr[u].cover = d;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_cover(ls(u), l, r, d);if(r > mid) modify_cover(rs(u), l, r, d);pushup(u);}
}

AC代码:

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;// #define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pair<int,int> PII;const int INF = 1e18;
const int N = 1e6 + 21;// 当输入数据大于 1e6 时用快读
inline int fread() // 快读
{int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * f;
}int w[N],n,m; // 注意 w[N] 开LL ( https://www.luogu.com.cn/problem/P2357
struct adt {int l,r;int ma,add,cover;
}tr[N << 2];
// 左子树
inline int ls(int p) {return p<<1; }
// 右子树
inline int rs(int p) {return p<<1|1; }
// 向上更新
void pushup(int u) {tr[u].ma = max(tr[ls(u)].ma, tr[rs(u)].ma);
}void coverdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.cover != -INF) {left.add = right.add = 0;left.ma = right.ma = root.cover;left.cover = right.cover = root.cover;root.cover = -INF;}
}
void sumdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.add) {coverdown(u);left.ma += root.add; right.ma += root.add;left.add += root.add; right.add += root.add;root.add = 0;}    
}
void pushdown(int u) {coverdown(u); sumdown(u);
}
// 建树
void build(int u, int l, int r) {if(l == r) tr[u] = {l, r, w[r], 0, -INF};else {tr[u] = {l,r, 0, 0, -INF}; // 容易忘int mid = l + r >> 1;build(ls(u), l, mid), build(rs(u), mid + 1, r);pushup(u);}
}
// 修改
void modify_add(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {coverdown(u);tr[u].ma += d;tr[u].add += d;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_add(ls(u), l ,r, d);if(r > mid) modify_add(rs(u), l, r, d);pushup(u);}
}
void modify_cover(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {tr[u].add = 0;tr[u].ma = d;tr[u].cover = d;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_cover(ls(u), l, r, d);if(r > mid) modify_cover(rs(u), l, r, d);pushup(u);}
}
// 查询
LL query(int u, int l, int r) {if(tr[u].l >= l && tr[u].r <= r) {return tr[u].ma;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = -INF;if(l <= mid) res = query(ls(u), l, r);if(r > mid ) res =max(res, query(rs(u), l, r));return res;
}void inpfile();
void solve() {int n,q; cin>>n>>q;for(int i = 1; i <= n; ++i) w[i] = fread();build(1,1,n);while(q--) {// int opt,l,r,x; cin>>opt>>l>>r;int opt = fread(), l = fread(), r = fread();if(opt == 1) {// cin>>x;int x = fread();modify_cover(1,l,r,x);} else if(opt == 2) {// cin>>x;int x = fread();modify_add(1,l,r,x);} else {cout<<query(1,l,r)<<'\n';}}
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cin>>T;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen("ANSWER.txt", "w",stdout);#endif
}

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在这里插入图片描述

P1253 扶苏的问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【AI视野·今日Sound 声学论文速览 第三十二期】Tue, 24 Oct 2023

AI视野今日CS.Sound 声学论文速览 Tue, 24 Oct 2023 Totally 20 papers &#x1f449;上期速览✈更多精彩请移步主页 Interesting: &#x1f4da;nvas3d, 基于任意录音和室内3D信息合成重建不同听角&#xff08;位置&#xff09;处的新的声音。(from apple cmu) website: htt…

在职一年多,一个29岁软件测试工程师的心声

简单的先说一下&#xff0c;坐标西安&#xff0c;16届本科毕业&#xff0c;目前在跳槽&#xff0c;算上国庆节前的面试&#xff0c;一共有面试了5家公司&#xff08;因为不想请假&#xff0c;因此只是每个晚上去其他公司面试&#xff0c;所以面试的公司比较少&#xff09;其中成…

【394.字符串解码】

目录 一、题目描述二、算法原理三、代码实现 一、题目描述 二、算法原理 三、代码实现 class Solution { public:string decodeString(string s) {stack<string> s1;s1.push("");stack<int> s2;int i 0, n s.size();while (i < n){//1.如果是数字入…

css:transform实现平移、旋转、缩放、倾斜元素

目录 文档语法示例旋转元素 transform-rotate旋转过渡旋转动画 参考文章 文档 https://developer.mozilla.org/zh-CN/docs/Web/CSS/transform 语法 /* Keyword values */ transform: none;/* Function values */ transform: matrix(1, 2, 3, 4, 5, 6); transform: translate…

京东数据分析:2023年9月京东洗地机行业品牌销售排行榜

鲸参谋监测的京东平台9月份洗地机市场销售数据已出炉&#xff01; 9月份&#xff0c;洗地机市场的销售额增长。根据鲸参谋电商数据分析平台的相关数据显示&#xff0c;9月京东平台上洗地机的销量为9.2万&#xff0c;销售额将近2.2亿&#xff0c;同比增长约9%。从价格上看&#…

Android NDK开发详解之Android.mk探秘

Android NDK开发详解之Android.mk探秘 概览基础知识变量和宏NDK 定义的 include 变量CLEAR_VARSBUILD_EXECUTABLEBUILD_SHARED_LIBRARYBUILD_STATIC_LIBRARYPREBUILT_SHARED_LIBRARYPREBUILT_STATIC_LIBRARY 目标信息变量TARGET_ARCHTARGET_PLATFORMTARGET_ABI 模块描述变量LOC…

【组件】身份证卡片

效果展示 组件代码 <div class"cardOneRoot"><img :src"itemInfo.psnPicUrl ? itemInfo.psnPicUrl : " alt""/><div class"infoDiv" v-if"itemInfo.noInfo 1"><div v-for"(item2, index2) in …

信号、进程、线程、I/O介绍

文章目录 信号进程进程通信线程可/不可重入函数线程同步互斥锁条件变量自旋锁读写锁 I/O操作阻塞/非阻塞I/OI/O多路复用存储映射I/O 信号 信号是事件发生时对进程的通知机制&#xff0c;可以看做软件中断。信号与硬件中断的相似之处在于其能够打断程序当前执行的正常流程。大多…

保护生产中 Node.js 应用程序安全的 15 项最佳实践

在后端开发方面&#xff0c;Node.js 是开发人员最喜欢的技术之一。它的受欢迎程度不断上升&#xff0c;现已成为在线攻击的主要目标之一。这就是为什么保护 Node.js 免受漏洞和威胁至关重要。 在本指南中&#xff0c;您将看到为生产设计安全 Node.js 应用程序架构的 15 种最佳…

阿里云CTO周靖人:打造一朵AI时代最开放的云

10月31日&#xff0c;在2023云栖大会上&#xff0c;阿里云CTO周靖人表示&#xff0c;面向智能时代&#xff0c;阿里云将通过从底层算力到AI平台再到模型服务的全栈技术创新&#xff0c;升级云计算体系&#xff0c;打造一朵AI时代最开放的云。在现场&#xff0c;周靖人公布了云计…

如何使用内网穿透远程访问Linux SVN服务?

文章目录 前言1. Ubuntu安装SVN服务2. 修改配置文件2.1 修改svnserve.conf文件2.2 修改passwd文件2.3 修改authz文件 3. 启动svn服务4. 内网穿透4.1 安装cpolar内网穿透4.2 创建隧道映射本地端口 5. 测试公网访问6. 配置固定公网TCP端口地址6.1 保留一个固定的公网TCP端口地址6…

2023年【道路运输企业主要负责人】考试技巧及道路运输企业主要负责人复审模拟考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年【道路运输企业主要负责人】考试技巧及道路运输企业主要负责人复审模拟考试&#xff0c;包含道路运输企业主要负责人考试技巧答案和解析及道路运输企业主要负责人复审模拟考试练习。安全生产模拟考试一点通结合…

【ES专题】ElasticSearch快速入门

目录 前言从一个【搜索】说起 阅读对象阅读导航笔记正文一、全文检索1.1 什么是【全文检索】1.2 【全文检索】原理1.3 什么是倒排索引 二、ElasticSearch简介2.1 ElasticSearch介绍2.2 ElasticSearch应用场景2.3 数据库横向对比 三、ElasticSearch环境搭建3.1 Windows下安装3.2…

蓝桥杯(C++ 扫雷)

题目&#xff1a; 思想&#xff1a; 1、遍历每个点是否有地雷&#xff0c;有地雷则直接返回为9&#xff0c;无地雷则遍历该点的周围八个点&#xff0c;计数一共有多少个地雷&#xff0c;则返回该数。 代码&#xff1a; #include<iostream> using namespace std; int g[…

SpringCloud Gateway实现请求解密和响应加密

文章目录 前言正文一、项目简介二、核心代码2.1 自定义过滤器2.2 网关配置2.3 自定义配置类2.4 加密组件接口2.5 加密组件实现&#xff0c;AES算法2.6 启动类&#xff0c;校验支持的算法配置 三、请求报文示例四、测试结果4.1 网关项目启动时4.2 发生请求时 前言 本文环境使用比…

Python基础入门例程27-NP27 朋友们的喜好(列表)

最近的博文&#xff1a; Python基础入门例程26-NP26 牛牛的反转列表&#xff08;列表&#xff09;-CSDN博客 Python基础入门例程25-NP25 有序的列表&#xff08;列表&#xff09;-CSDN博客 Python基础入门例程24-NP24 淘汰排名最后的学生&#xff08;列表&#xff09;-CSDN博客…

2017年第三届 美亚杯电子取证 个人赛题解

记录做题个人赛题目 取证大师直接取证 1 Gary的笔记本电脑已成功取证并制作成镜像 (Forensic Image)&#xff0c;下列哪个是其MD5哈希值。 A.0CFB3A0BB016165F1BDEB87EE9F710C9 B.5F1BDEB87EE9F710C90CFB3A0BB01616 C.A0BB016160CFB3A0BB0161661670CFB3 D.16160CFB3A0BB0161…

如何在MacOS使用homebrew安装Nginx

文章目录 Homebrew安装nginxbrew启动Nginxbrew关闭Nginx 参考文章地址 Homebrew安装nginx 在确保MacOS 安装Homebrew成功以后&#xff0c;执行如下命令 brew install nginx注意&#xff1a;Nginx安装成功后会提示目录位置&#xff1b;每个人的系统可能因为Homebrew的安装位置…

【Java数据结构重点知识】第三节:认识包装类和泛型

目录 一&#xff1a;包装类 1.什么是包装类 2.装箱和拆箱 3.一个经典面试题 二&#xff1a;泛型 1.什么是泛型 2.语法 3.使用 4.泛型是如何编译的 5.泛型的上界 一&#xff1a;包装类 1.什么是包装类 &#xff08;1&#xff09;概念&#xff1a;在Java中&#xff0…

在Win10系统进行MySQL的安装、连接、卸载

在Win10系统进行MySQL的安装、连接、卸载 MySQL的安装 本教程在Win10系统下安装部署MySQL-8.0.32版。 MySQL安装参考地址 MySQL安装包地址 提取码: rnbc。 选择下载mysql-installer-community-8.0.32.0安装包。 连接数据库 方式一&#xff1a; 安装后&#xff0c;可以在开始…