线段树练习
P1198 [JSOI2008] 最大数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// Problem: P1198 [JSOI2008] 最大数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1198
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 2e5 + 10;
#define int long long
struct
{int l,r;int v;
}tr[maxn * 4];
void push_down(int u)
{tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}void built(int u,int l,int r)
{tr[u] = {l, r};if(l == r)return;//int mid = (l + r) >> 1;built(u << 1, l , mid);built(u << 1 | 1, mid + 1,r);
}void modify(int u,int x,int v)
{if(tr[u].l == x && tr[u].r == x)tr[u].v = v;else{int mid = (tr[u].l + tr[u].r) >> 1;if(x > mid)modify(u << 1 | 1,x , v);else modify(u << 1,x , v);push_down(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].v; //int v = 0;int mid = tr[u].l + tr[u].r >> 1; //if(l <= mid)v = query(u << 1, l, r);if(r > mid)v = max(v, query(u << 1 | 1,l , r));return v;
}signed main()
{cin.tie(0) -> sync_with_stdio(false);int M, D;int n = 0;//队列数int last = 0;//最后一个数 cin >> M >> D;built(1, 1, M);//query modifywhile(M--){char key;int x;cin >> key >> x;if('A' == key){modify(1, ++n,(last + x) % D);}else{last = query(1,n - x + 1,n);cout << last << endl; }}return 0;
}
245. 你能回答这些问题吗 - AcWing题库
P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// Problem: P3374 【模板】树状数组 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3374
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//只有单点修改
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
#include<memory>//for unique_ptr shared_ptr
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA(x) cout << x << endl;
#define lowbit(x) x & -x
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, k, d, T = 1, A, B;template<typename T>void read(T &x) {T f = 1;x = 0;char s = getchar();while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}x *= f;
}template<typename T>void print(T x) {if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');putchar('\n');
}
constexpr int Init(int x)
{return x * 2;
}
int a[maxn];
struct node
{int l, r, sum;
}tr[maxn * 4];void pushdown(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void built(int u,int l,int r)
{tr[u] = {l, r};if(l == r)return;else{int mid = (l + r) >> 1;built(u << 1, l, mid);built(u << 1 | 1, mid + 1, r);}
}void modify(int u, int x, int d)
{if(tr[u].l == x && tr[u].r == x)tr[u].sum += d;else{int mid = (tr[u].l + tr[u].r) >> 1;if(x <= mid)modify(u << 1, x, d);else modify(u << 1 | 1, x , d);pushdown(u);}
}int query(int u,int l,int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum;else{int mid = (tr[u].r + tr[u].l) >> 1;int res = 0;if(l <= mid)res += query(u << 1, l, r);if(r > mid)res += query(u << 1 | 1,l , r);return res;}
}void solve()
{auto x = make_unique<int>();cin >> n >> m;built(1, 1, n);for(int i = 1;i <= n;i++)cin >> a[i];for(int i = 1;i <= n;i++)modify(1, i, a[i]);for(int i = 1;i <= m;i++){cin >> k >> A >> B;if(1 == k)modify(1, A, B);elsecout << query(1, A, B) << endl;}}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//read(T);while (T--) solve();return 0;
}
P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// Problem: P3372 【模板】线段树 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
#include<memory>//for unique_ptr shared_ptr
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA(x) cout << x << endl;
#define lowbit(x) x & -x
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, k, d, T = 1, A, B;template<typename T>void read(T &x) {T f = 1;x = 0;char s = getchar();while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}x *= f;
}template<typename T>void print(T x) {if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');putchar('\n');
}
constexpr int Init(int x)
{return x * 2;
}
int a[maxn];
struct node
{int l, r, sum, add;
}tr[maxn * 4];void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u)
{auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];if(root.add){left.add += root.add; left.sum += (left.r - left.l + 1) * root.add;right.add += root.add; right.sum += (right.r - right.l + 1) * root.add;root.add = 0;}
}void built(int u, int l, int r)
{if(l == r){tr[u] = {l, r, a[l], 0};return;}tr[u] = {l, r};int mid = (l + r) >> 1;built(u << 1, l, mid);built(u << 1 | 1, mid + 1, r);pushup(u);
}void modify(int u, int l, int r, int d)
{if(tr[u].l >= l && tr[u].r <= r){tr[u].sum += (tr[u].r - tr[u].l + 1) * d;tr[u].add += d;}else{pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;if(l <= mid)modify(u << 1, l, r, d);if(r > mid)modify(u << 1 | 1, l, r, d);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum;pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;int res = 0;if(l <= mid)res += query(u << 1, l, r);if(r > mid)res += query(u << 1 | 1, l, r);return res;
}
void solve()
{auto x = make_unique<int>();cin >> n >> m;for(int i = 1;i <= n;i++)cin >> a[i];built(1, 1, n);while(m--){cin >> k >> A >> B;if(1 == k){int d;cin >> d;modify(1, A, B, d);}elsecout << query(1, A, B) << endl;}
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//read(T);while (T--) solve();return 0;
}
247. 亚特兰蒂斯 - AcWing题库
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;#define p1 (p<<1)
#define p2 (p<<1|1)const int N=10005;struct T {int l,r,mini,add;double len; //区间长度double minlen; //区间最小值的区间长度
} t[N*8];
struct A {double x,y1,y2;int add;
} a[N*2];
int n,len;
double lsh[N*2];bool cmp(A u,A v) {return u.x<v.x;}
int val(double x) {return lower_bound(lsh+1,lsh+1+len,x)-lsh;}
double raw(int x) {return lsh[x];}void pushUp(int p) {t[p].mini=min(t[p1].mini,t[p2].mini);double minlen=0;if(t[p].mini==t[p1].mini) minlen+=t[p1].minlen;if(t[p].mini==t[p2].mini) minlen+=t[p2].minlen;t[p].minlen=minlen;
}void build(int p,int l,int r) {double len=raw(r+1)-raw(l);t[p]={l,r,0,0,len,len};if(l==r) return;int mid=l+r>>1;build(p1,l,mid),build(p2,mid+1,r);
}void pushDown(int p) {t[p1].add+=t[p].add,t[p2].add+=t[p].add;t[p1].mini+=t[p].add,t[p2].mini+=t[p].add;t[p].add=0;
}void upd(int p,int l,int r,int add) {if(t[p].l>=l && t[p].r<=r) {t[p].mini+=add,t[p].add+=add; return;}if(t[p].add!=0) pushDown(p);int mid=t[p].l+t[p].r>>1;if(l<=mid) upd(p1,l,r,add);if(r>mid) upd(p2,l,r,add);pushUp(p);
}int main()
{for(int tim=1;;tim++) {scanf("%d",&n);if(!n) break;printf("Test case #%d\n",tim);for(int i=1;i<=n;i++) {double x1,y1,x2,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);a[i]={x1,y1,y2,1},a[i+n]={x2,y1,y2,-1};lsh[i]=y1,lsh[i+n]=y2;}n*=2;sort(a+1,a+1+n,cmp),sort(lsh+1,lsh+1+n);len=unique(lsh+1,lsh+1+n)-lsh-1;build(1,1,len-1);double ans=0;upd(1,val(a[1].y1),val(a[1].y2)-1,a[1].add);for(int i=2;i<=n;i++) {double len=t[1].len;if(!t[1].mini) len-=t[1].minlen;ans+=len*(a[i].x-a[i-1].x);upd(1,val(a[i].y1),val(a[i].y2)-1,a[i].add);}printf("Total explored area: %.2lf\n\n",ans);}return 0;
}
线段树扫描线应用
P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// Problem: P3373 【模板】线段树 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3373
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
#include<cstring>
#include<cmath>
#include<bitset>
#include<sstream>//切割strtream头文件
#include<climits>//INT_MAX文件
#include <utility>
#include<memory>//for unique_ptr shared_ptr
using i64 = int64_t;
using namespace std;
#define int i64
#define endl '\n'
#define AC return 0;
#define WA(x) cout << x << endl;
#define lowbit(x) x & -x
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n, m, k, d, T = 1, A, B, p;template<typename T>void read(T &x) {T f = 1;x = 0;char s = getchar();while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}x *= f;
}template<typename T>void print(T x) {if(x < 0) putchar('-'),x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');putchar('\n');
}
constexpr int Init(int x)
{return x * 2;
}
int a[maxn];struct node
{int l, r, sum, add, mul;
}tr[maxn];void eval(node &root,int add, int mul)
{root.sum = (root.sum * mul + ((root.r - root.l + 1) * add)) % p;root.mul = root.mul * mul % p;root.add = (root.add * mul + add) % p;
}void pushup(int u)
{tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}void pushdown(int u)
{eval(tr[u << 1],tr[u].add, tr[u].mul);eval(tr[u << 1 | 1],tr[u].add, tr[u].mul);tr[u].add = 0;tr[u].mul = 1;
}void built(int u, int l, int r)
{if(l == r)tr[u] = {l, r, a[l], 0, 1};else{tr[u] = {l, r, 0, 0 , 1};int mid = (l + r) >> 1;built(u << 1, l, mid);built(u << 1 | 1,mid + 1, r);pushup(u);}
}void modify(int u, int l, int r, int add, int mul)
{if(tr[u].l >= l && tr[u].r <= r)eval(tr[u], add, mul);else{pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;if(l <= mid)modify(u << 1, l, r, add, mul);if(r > mid)modify(u << 1 | 1, l, r, add, mul);pushup(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum % p;pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;int res = 0;if(l <= mid)res += query(u << 1, l, r) % p;if(r > mid)res += query(u << 1 | 1, l, r) % p;return res % p;
}void solve()
{auto x = make_unique<int>();cin >> n >> m >> p;for(int i = 1;i <= n;i++)cin >> a[i];built(1, 1, n);while(m--){cin >> k >> A >> B;if(3 == k)cout << query(1, A, B) << endl;else{int d; cin >> d;k == 1 ? modify(1, A, B, 0, d) : modify(1, A, B, d, 1);}}
}signed main() {cin.tie(0) -> sync_with_stdio(false);int T = 1;//read(T);while (T--) solve();return 0;
}
相关文章:
线段树练习
P1198 [JSOI2008] 最大数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) // Problem: P1198 [JSOI2008] 最大数 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P1198 // Memory Limit: 128 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://c…...
Mybatis映射.动态sql.分页
介绍: 动态SQL是MyBatis提供的一种动态生成SQL语句的方式,可以根据不同的条件生成不同的SQL语句,从而实现更加灵活的查询和操作。 在MyBatis的映射文件中,可以通过使用if、choose、when、otherwise、foreach等标签来实现动态SQL…...
springboot向resources下写文件的两种方式
文章目录 方式一:方式二: 方式一: import java.io.File; import java.io.FileWriter; import java.io.IOException;public class WriterFileUtils {private static final String prefix "classpath:";public static void writeFi…...

Sloare flare网卡信息
详细的安装信息 https://github.com/Xilinx-CNS/onload/tree/master/scripts 进行下载 Solarflare网卡开发:openonload 安装与调试_openonload安装_Erice_s的博客-CSDN博客 cns-sfnettest测试 cns-sfnettest 下载 https://github.com/Xilinx-CNS/cns-sfnettes…...
Redis知识点整理
第一部分:Redis基础知识点 1、数据类型 5种常用基础类型:string,hash,list,set,zset – 字符串,Hash表,List顺序集合,Set无序集合,ZSet有序集合3中特殊类型:bitmap-字节地图, hyperloglog-统计…...

React笔记(一)初识React
一、React概述 1、什么是react react的官网:React 用于构建用户界面的 JavaScript 库,它也是一个渐进式的用于构建用户界面的javascript框架 2、主要特征 声明式:使用原生JS编写的页面存在着开发效率低下、性能较差的情况,使用react大家就…...

C语言——指针进阶(一)
目录 编辑 一.字符指针 1.1 基本概念 1.2 面试题 二.指针数组 三.数组指针 3.1 数组指针的定义 3.2 &数组名VS数组名 3.3 数组指针的使用 四.数组参数、指针参数 4.1 一维数组传参 编辑 4.2 二维数组传参 4.3 一级指针传参 4.4 二级指针传参 编辑 五.…...

【ArcGIS Pro二次开发】(62):复制字段
应网友需求,做了这么一个复制字段的小工具。 假定这样一个场景,手头有一个要素1,要素里有10个字段,另一个要素2,除了shape_area等图形字段外,没有其它字段。 现在的需求是,想把要素1中的8个字…...

【Tkinter系列02/5】界面初步和布局
本文是系列文章第二部分。前文见:【Tkinter系列01/5】界面初步和布局_无水先生的博客-CSDN博客 说明 一般来说,界面开发中,如果不是大型的软件,就不必用QT之类的实现,用Tkinter已经足够,然而即便是Tkinter规…...

2023年03月 C/C++(四级)真题解析#中国电子学会#全国青少年软件编程等级考试
第1题:最佳路径 如下所示的由正整数数字构成的三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的…...
介绍一些编程语言— CSS 语言
介绍一些编程语言— CSS 语言 CSS 语言 简介 CSS,层叠样式表,是一种用来表现 HTML 或 XML 等文件样式的计算机语言。CSS 不仅可以静态地修饰网页,还可以配合各种脚本语言动态地对网页各元素进行格式化。 CSS 能够对网页中元素位置的排版进…...
一文讲清楚c/c++中的宏
一文讲清楚c/c中的宏 文章目录 一文讲清楚c/c中的宏一、如何理解这个“宏”字面的意思呢?二、c/c中的宏详解三、宏的使用场景 一、如何理解这个“宏”字面的意思呢? 在刚开始学习C语言的时候,始终有点分不清楚"宏"这个字面上的意思…...
typescript进阶语法
typescript进阶语法 interface 接口定义 interface userType {name:string,age:number,sex?:string }type接口定义 type userType {name:string,age:number,sex?:string } type userType username # 固定值写法 let user:userType age # 报错 只能等于usernamepick摘取…...
宝塔终端 查看 7003端口 占用 并且杀死
要查看端口是否被占用并杀死相关进程,你可以按照以下步骤执行: 打开宝塔面板,进入服务器管理页面。在左侧导航栏中选择「工具」,然后选择「终端」进入宝塔终端界面。输入以下命令查看端口占用情况:netstat -tuln | gr…...

可解释性的相关介绍
一、可解释性的元定义(Meta-definitions of Interpretability) The extent to which an individual can comprehend the cause of a model’s outcome. [1]The degree to which a human can consistently predict a model’s outcome. [2] 可解释性&am…...

AUTOSAR规范与ECU软件开发(实践篇)6.7 服务软件组件与应用层软件组件端口连接
在生成了BSW模块的代码后, 切换到ISOLAR-A系统级设计界面,会发现产生一些基础软件模块的服务软件组件: BswM、 ComM、 Det和EcuM等, 如图6.60所示。 图6.60 生成了BSW后的服务软件组件 此时, 如果涉及服务软件组件与应用层软件组件的交互, 就需要为应用层软件组…...
菜鸟教程《Python 3 教程》笔记(6):列表
菜鸟教程《Python 3 教程》笔记(6) 6 列表6.1 删除列表元素6.2 列表函数和方法6.2.1 max()、min()6.2.2 reverse()6.2.3 sort() 6 列表 出处: 菜鸟教程 - Python3 列表 6.1 删除列表元素 >>> list [Google, Runoob, 1997, 2000]…...

LeetCode-56-合并区间
题目描述: 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 可以使用 LinkedList,…...
Git gui教程---番外篇 gitignore 的文件使用
想说的 .gitignore 的文件一般大型的编译器带git的都会生成,他可以将你不想提交的文件在git下忽略掉,你应该不想将一大堆编译生成的过程文件,还有一些贼大的文件提交上git的。 凡是都有例外,一些冥顽不灵的编辑器,只能…...
javaee spring 用注解的方式实现ioc
spring 用注解的方式实现ioc spring核心依赖 <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...

什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...