首页 > 其他分享 >Daimayuan Online Judge 线段树2

Daimayuan Online Judge 线段树2

时间:2023-08-29 21:12:09浏览次数:40  
标签:Info std int Daimayuan mid seg Online Judge id

给 \(n\) 个数 \(a_1, a_2, \cdots, a_n\) 。
支持 \(q\) 个操作:

  1. 1 x d ,修改 \(a_x = d\) 。
  2. 2 l r ,查询 \([l, r]\) 中的最大子段和。

一:确定需要维护的信息。根据分治中线讨论,哪些信息可以合并出所需信息。递归讨论新信息如何合并。直至完全拆解。

  1. 不越过分治中线:\([l, r]\) 的最大子段和,要么是 \([l, mid]\) 的最大子段和,要么是 \([mid + 1, r]\) 的最大子段和。
  2. 越过分治中线:\([l, mid]\) 的最大后缀和 + \([mid + 1, r]\) 的最大前缀和。
  3. 递归讨论 \([l, r]\) 的最大后缀和最大前缀如何维护:
    1. 不越过分治中线:\([l, r]\) 的最大后缀和为 \([mid + 1, r]\) 的最大后缀和;\([l, r]\) 的最大前缀和为 \([l, mid]\) 的最大前缀和。
    2. 越过分治中线:\([l, r]\) 的最大后缀和为 \([l, mid]\) 的最大后缀和 + \([mid + 1, r]\) 的和;\([l, r]\) 的最大前缀和为 \([mid + 1, r]\) 的最大前缀和 + \([l, mid]\) 的和。
    3. 递归讨论 \([l, r]\) 的和如何维护:
      1. \([l, r]\) 的和显然越过分治中线,为 \([l, mid + 1]\) 的和 + \([mid + 1, r]\) 的和。不再产生新信息。
  4. 补充: \(update\) 时 \([l, r]\) 信息与 \([l, mid]\) 和 \([mid + 1, r]\) 的信息独立,不需要考虑 \([l, r]\) 信息更新的顺序。
struct Info {
	long long mss, mpre, msuf, s; // 最大子段和,最大前缀和,最大后缀和,区间和 
};

struct Node {
	Info f;
} seg[N * 4];

Info operator + (const Info &l, const Info &r) {
	Info ret;
	ret.mss = std::max({l.mss, r.mss, l.sufs + r.pres});
	ret.pres = std::max(l.mpre, l.s + r.mpre);
	ret.sufs = std::max(r.msuf, l.msuf + r.s);
	ret.s = l.s + r.s;
	return ret;
}

void update(int id) {
	seg[id].f = seg[ id * 2 ].f + seg[ id * 2 + 1 ].f;
}

二:完成主程序框架

int main() {
	int n, q;
	std::cin >> n >> q;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= q; i++) {
		int typ; std::cin >> typ;
		if ( typ == 1 ) {
			int x, d; std::cin >> x >> d;
			change(1, 1, n, x, d);
		}
		else {
			int l, r; std::cin >> l >> r;
			auto ans = query(1, 1, n, l, r);
			std::cout << ans.mss << '\n';
		}
	}
	return 0;
}

三:完成建树、查询、单点修改(实际上只有建树递归到点上初始化信息、单点修改递归到点上修改信息的代码有变化)

void build(int id, int l, int r) {
	if (l == r) {
		seg[id].f = {a[l], a[l], a[l], a[l]};
	}
	else {
		int mid = ( l + r ) >> 1;
		build( id * 2, l, mid );
		build (id * 2 + 1, mid + 1, r );
		update(id);
	}
}

Info query(int id, int l, int r, int ql, int qr) {
	if ( l == ql && r == qr ) {
		return seg[id].f;
	}
	else {
		int mid = ( l + r ) >> 1;
		if (qr <= mid) return query( id * 2, l, mid, ql, qr );
		else if (ql > mid) return query( id * 2 + 1, mid + 1, r, ql, qr );
		else return query( id * 2, l, mid, ql, mid ) + query( id * 2 + 1, mid + 1, r, mid + 1, qr );
	}
}

void change(int id, int l, int r, int pos, int d) {
	if ( l == r ) {
		seg[id].f = {d, d, d, d};
	}
	else {
		int mid = ( l + r ) >> 1;
		if ( pos <= mid ) change( id * 2, l, mid, pos, d );
		else change( id * 2 + 1, mid + 1, r, pos, d );
		update(id);
	}
}

完整代码

view
#include <bits/stdc++.h>

const int N = 200005;

int a[N]; 

struct Info {
	long long mss, mpre, msuf, s; // 最大子段和,最大前缀和,最大后缀和,区间和 
};

struct Node {
	Info f;
} seg[N * 4];

Info operator + (const Info &l, const Info &r) {
	Info ret;
	ret.mss = std::max({l.mss, r.mss, l.msuf + r.mpre});
	ret.mpre = std::max(l.mpre, l.s + r.mpre);
	ret.msuf = std::max(r.msuf, l.msuf + r.s);
	ret.s = l.s + r.s;
	return ret;
}

void update(int id) {
	seg[id].f = seg[ id * 2 ].f + seg[ id * 2 + 1 ].f;
}

void build(int id, int l, int r) {
	if (l == r) {
		seg[id].f = {a[l], a[l], a[l], a[l]};
	}
	else {
		int mid = ( l + r ) >> 1;
		build( id * 2, l, mid );
		build (id * 2 + 1, mid + 1, r );
		update(id);
	}
}

Info query(int id, int l, int r, int ql, int qr) {
	if ( l == ql && r == qr ) {
		return seg[id].f;
	}
	else {
		int mid = ( l + r ) >> 1;
		if (qr <= mid) return query( id * 2, l, mid, ql, qr );
		else if (ql > mid) return query( id * 2 + 1, mid + 1, r, ql, qr );
		else return query( id * 2, l, mid, ql, mid ) + query( id * 2 + 1, mid + 1, r, mid + 1, qr );
	}
}

void change(int id, int l, int r, int pos, int d) {
	if ( l == r ) {
		seg[id].f = {d, d, d, d};
	}
	else {
		int mid = ( l + r ) >> 1;
		if ( pos <= mid ) change( id * 2, l, mid, pos, d );
		else change( id * 2 + 1, mid + 1, r, pos, d );
		update(id);
	}
}

int main() {
	int n, q;
	std::cin >> n >> q;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= q; i++) {
		int typ; std::cin >> typ;
		if ( typ == 1 ) {
			int x, d; std::cin >> x >> d;
			change(1, 1, n, x, d);
		}
		else {
			int l, r; std::cin >> l >> r;
			auto ans = query(1, 1, n, l, r);
			std::cout << ans.mss << '\n';
		}
	}
	return 0;
}

标签:Info,std,int,Daimayuan,mid,seg,Online,Judge,id
From: https://www.cnblogs.com/zsxuan/p/17665391.html

相关文章

  • Daimayuan Online Judge 线段树1
    给\(n\)个数\(a_1,a_2,\cdots,a_n\)。支持\(q\)个操作:1.1xd,修改\(a_x=d\)。2.2lr,查询\(min_{i=l}^{r}a_i\),并输出\(\sum_{i=l}^{r}[a_i=min_{i=l}^{r}a_i]\)。一:确定出需要维护的信息\(Info\)。建立线段树节点structInfo{ intminv......
  • virtual judge [Submit with your own account]
     https://vjudge.net/article/2790然后要启用开发者模式,然后就可以打开开发者工具。(Safari–Preferences呼出首选项面板(或用快捷键command+,直接呼出)。在Advanced菜单面板下,勾选ShowDevelopMenuinmenuBar。可知: Option+command+C 即可打开开发者工具)......
  • MySQL online DDl原理
    onlineDDL从5.6开始,不阻塞DML但是会阻塞所有的DDL,online有三种模式:INSTANT(8.0.12),INPLACE(rebuild),INPLACE(no-rebuild),具体操作如下:1、只修改表的元数据信息删除二级索引修改索引名(5.7)修改字段名设置(删除)字段的默认值增加varchar长度,如果表示字符串长度的字节数变化则会使用c......
  • 无涯教程-PHP Online Test函数
    该PHP在线测试模拟了真正的在线认证考试。您将看到基于PHP概念的多项选择题(MCQ),将为您提供四个options。您将为该问题选择最合适的答案,然后继续进行下一个问题,而不会浪费时间。完成完整的考试后,您将获得在线考试分数。总问题数-20最长时间-20分钟StartTest参......
  • 无涯教程-PHP Online Quiz函数
    以下测验提供与PHP相关的多项选择题(MCQ)。您将必须阅读所有给定的答案,然后单击正确的答案。如果您不确定答案,则可以使用显示答案按钮检查答案。您可以使用下一个测验按钮检查测验中的新问题集。Q1-关于PHP,以下哪项是正确的?A-PHP可以访问cookie变量并设置cookie。......
  • daimayuan252 | 摸鱼(状压, 枚举, 小技巧)
    题目很straightforward的,看到n范围很小考虑状压,暴力枚举所有的可能pattern.第一种做法,暴力枚举是\(O(2^n)\)的,然后check函数判断是\(O(n^2)\)的,一共是\(O(n^22^n)\)的,可以通过.第二种做法,我们考虑把判断pattern是否合法的限制条件也压成二进制串,那么我们比对条......
  • The 2022 ICPC Asia Regionals Online Contest (II) EJFB
    The2022ICPCAsiaRegionalsOnlineContest(II)EAnInterestingSequence232323232323323232323232#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;voidsolve(){ lln,k; cin>>n>>k; llres=k; llt=0; for(......
  • The 2022 ICPC Asia Regionals Online Contest (I) C L A
    The2022ICPCAsiaRegionalsOnlineContest(I)C统计度的大小,算贡献,特判\(n=1\)#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;typedeflonglongll;intn,d[N];vector<int>e[N];llres=0;voiddfs(intu,intfrom){ ......
  • Intention-Aware Online POMDP Planning for Autonomous Driving in a Crowd
    一、论文信息发表日期:2015年发表机构:新加坡国立大学,计算机科学系二、论文内容1.解决问题:无人车在人员密集处的速度规划算法2.方法:前向仿真+强化学习概念   ①.路径规划和速度规划进行解耦,进行速度规划之前路径已确定。 ②.速度规划采取部分可观测马尔可夫决策过程,......
  • 无涯教程-jQuery Online Test函数
    jQuery在线测试模拟了真正的在线认证考试。您将看到基于jQuery框架概念的多项选择题(MCQ),将为您提供四个options。您将为该问题选择最合适的答案,然后继续进行下一个问题,而不会浪费时间。完成完整的考试后,您将获得在线考试分数。总问题数-20最长时间-20分钟StartTe......