题目链接:https://syzoj.com/problem/247

解题心得:

  • 可持久化线段树其实就是一个线段树功能的加强版,加强在哪里呢?那就是如果一颗普通的线段树多次修改之后还能知道最开始的线段树长什么样子吗?肯定不能,如果就要问你这棵线段树在某一时刻是什么样子那能咋办。最直接的思维就是创建n棵线段树,将每一个时刻都记录下来。但是想一下时间复杂度和空间复杂度都是很大的。
  • 可持久化线段树就是解决这个问题的。仔细想一想如果只修改线段树上一个叶子结点,那么对于线段树来说有改变的节点有多少个,log n 个,也就是线段树上面的一条枝。这样就可以建立一个新的根结点将需要改变的这个枝创建出来连接到新的结点上。那没有改变的节点咋办,那就值将这个新创建的节点指向上一个时刻树上没有改变的节点就行了。
//
// ┏┛ ┻━━━━━┛ ┻┓
// ┃       ┃
// ┃   ━   ┃
// ┃ ┳┛  ┗┳ ┃
// ┃       ┃
// ┃   ┻   ┃
// ┃       ┃
// ┗━┓   ┏━━━┛
// ┃   ┃ 神兽保佑
// ┃   ┃ 代码无BUG!
// ┃   ┗━━━━━━━━━┓
// ┃        ┣┓
// ┃     ┏┛
// ┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
// ┃ ┫ ┫ ┃ ┫ ┫
// ┗━┻━┛ ┗━┻━┛
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+; int lson[maxn], rson[maxn], T[maxn];
int n,m,cnt = , sz = , node[maxn]; void updata(int root) {
node[root] = max(node[lson[root]], node[rson[root]]);
} void build_tree(int &root, int l, int r){//注意要取地质,因为是创立的新的结点
root = ++sz;
if(l == r) {
scanf("%d", &node[root]);
return ;
}
int mid = (l + r) >> ;
build_tree(lson[root], l, mid);
build_tree(rson[root], mid+, r);
updata(root);
} void init() {
scanf("%d%d",&n,&m);
build_tree(T[++cnt], , n);
} void change(int& root, int pre, int pos, int l, int r, int va){
root = ++sz;//需要改变的结点
node[root] = node[pre];
if(l == r) {
node[root] = va;
return ;
}
lson[root] = lson[pre];//新的结点的儿子直接指向前一刻树的结点
rson[root] = rson[pre];
int mid = (l + r) >> ;
if(mid >= pos)
change(lson[root], lson[pre], pos, l, mid, va);
else
change(rson[root], rson[pre], pos, mid+, r, va);
updata(root);
} int query(int root, int ql, int qr, int l, int r) {
if(l == ql && r == qr) {
return node[root];
}
int mid = (l + r) >> ;
if(mid >= qr)
return query(lson[root], ql, qr, l, mid);
else if(mid < ql)
return query(rson[root], ql, qr, mid+, r);
else
return max(query(lson[root], ql, mid, l, mid) , query(rson[root], mid+, qr, mid+, r));
} int main() {
init();
int a,b,c,d;
while(m--) {
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a == ) {
change(T[++cnt], T[b], c, , n, d);//T记录第cnt课树是从哪里开始的
} else {
int ans = query(T[b], c, d, , n);
printf("%d\n",ans);
}
}
return ;
}

最新文章

  1. .NET 类型(Types)的那些事
  2. [数据库]redis与redis操作
  3. android toast几种使用方法
  4. Unity5网络模块UNet介绍
  5. js千分位的函数
  6. SQL NULL Values
  7. css中关于transform、transition、animate的区别
  8. Oracle EBS-SQL (WIP-13):检查任务组件未选MRP净值.sql
  9. java中static关键字的继承问题
  10. python clock装饰器 计算函数执行时间,执行结果及传入的参数
  11. iOS----------Runtime 获取属性列表 方法列表
  12. hdu2844 Coins -----多重背包+二进制优化
  13. Automatically migrating data to new machines kafka集群扩充迁移topic
  14. 斯坦福大学公开课机器学习:advice for applying machine learning - deciding what to try next(设计机器学习系统时,怎样确定最适合、最正确的方法)
  15. BZOJ1926[Sdoi2010]粟粟的书架——二分答案+主席树
  16. 【Important】数据库索引原理
  17. php新加扩展模块
  18. ubuntu14.04下搜狗输入法不能输入中文问题解决
  19. 每日英语:Got 5 Minutes? &#39;Flash Fiction&#39; Catches On
  20. spring 注解列表

热门文章

  1. vue-cli3 项目从搭建优化到docker部署
  2. SAP成都研究院廖婧:SAP C4C社交媒体集成概述
  3. 删除所有正在运行和退出的docker实例
  4. Visual Stuio 2010 常用快捷及操作
  5. datatable 动态显示/隐藏列
  6. Android(java)学习笔记27:TextView属性大全
  7. 【BZOJ2510】弱题
  8. C++函数委托
  9. data-ng-click 指令
  10. c语言描述的简单选择排序