IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 公园遛狗 / 小白逛公园【ybt高效进阶4-4-3】【luogu P4513】【题解未完成】 -> 正文阅读

[数据结构与算法]公园遛狗 / 小白逛公园【ybt高效进阶4-4-3】【luogu P4513】【题解未完成】

公园遛狗 / 小白逛公园【ybt高效进阶4-4-3】【luogu P4513】【题解未完成】

题目大意:题目大意

给你一个序列,要维护两个操作。
单点修改和在一个区间中找它的最大子段和。

暂时先贴代码

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define r register
#define rep(i,x,y) for(r ll i=x;i<=y;++i)
#define per(i,x,y) for(r ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=5*1e5+10;
ll a[V],n,m,k,x,y;
struct node
{
	ll ls,rs,val,len;
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define val(x) tree[x].val
	#define len(x) tree[x].len
}tree[V<<3];
void update(ll x)
{
	val(x)=val(x<<1)+val(x<<1|1);
	ls(x)=max(ls(x<<1),val(x<<1)+ls(x<<1|1));
	rs(x)=max(rs(x<<1|1),val(x<<1|1)+rs(x<<1));
	len(x)=max(max(len(x<<1),len(x<<1|1)),ls(x<<1|1)+rs(x<<1));
}
void build(ll now,ll le,ll ri)
{
	if(le==ri)
	{
		ls(now)=rs(now)=val(now)=len(now)=a[le];
		return ;
	}
	ll mid=le+ri>>1;
	build(now<<1,le,mid);
	build(now<<1|1,mid+1,ri);
	update(now);
}
void add(ll now,ll le,ll ri,ll p,ll v)
{
	if(le==ri)
	{
		ls(now)=rs(now)=val(now)=len(now)=v;
		return ;
	}
	ll mid=le+ri>>1;
	if(p<=mid) add(now<<1,le,mid,p,v);
	else add(now<<1|1,mid+1,ri,p,v);
	update(now);
}
node ask(ll now,ll le,ll ri,ll x,ll y)
{
	if(le>=x&&ri<=y) return tree[now];
	ll mid=le+ri>>1;
	node res;
	if(mid>=y) return ask(now<<1,le,mid,x,y);
	else if(mid+1<=x) return ask(now<<1|1,mid+1,ri,x,y);
	node r1=ask(now<<1,le,mid,x,y);
	node r2=ask(now<<1|1,mid+1,ri,x,y);
	res.val=r1.val+r2.val;
	res.ls=max(r1.ls,r2.ls+r1.val);
	res.rs=max(r2.rs,r1.rs+r2.val);
	res.len=max(max(r1.len,r2.len),r1.rs+r2.ls);
	return res;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	rep(i,1,n)
	 scanf("%lld",&a[i]);
	build(1,1,n);
	rep(i,1,m)
	{
		scanf("%lld%lld%lld",&k,&x,&y);
		if(k==2) add(1,1,n,x,y);
		else
		{
			if(x>y) swap(x,y);
			node ans=ask(1,1,n,x,y);
			printf("%lld\n",ans.len);
		} 
	}
	return 0;
}
  数据结构与算法 最新文章
LeetCode 383 赎金信[数组] HERODING的Leet
matlab中fill函数的使用方法
动态规划总结篇一
LeetCode530 二叉搜索树的最小绝对差
单链表的增删改查
拓扑排序 golang实现
用栈实现队列的功能Java(leetcode)
两数相加
动态规划思路
希尔排序——C++实现
上一篇文章      下一篇文章      查看所有文章
加:2021-07-14 23:11:55  更:2021-07-14 23:12:47 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年12日历 -2021/12/4 21:20:31-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码