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

Daimayuan Online Judge 线段树1

时间:2023-08-29 21:11:59浏览次数:44  
标签:Info int Daimayuan mid seg Online Judge id minv

给 \(n\) 个数 \(a_1, a_2, \cdots, a_n\) 。
支持 \(q\) 个操作:
1. 1 x d ,修改 \(a_x = d\) 。
2. 2 l r ,查询 \(min_{i = l}^{r} a_i\) ,并输出 \(\sum_{i = l}^{r} [a_i = min_{i = l}^{r} a_i]\) 。

一:确定出需要维护的信息 \(Info\) 。建立线段树节点

struct Info {
	int minv, mincnt;
};

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

二:确定信息加法以即如何更新。封装 \(update\) ,通常情况下只需要把左右区间的信息合并。

Info operator + (const Info &l, const Info &r) {
	Info ret;
	if ( l.minv < r.minv ) ret = l;
	else if ( r.minv < l.minv ) ret = r;
	else ret = {l.minv, l.mincnt + r.mincnt};
	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.minv << ' ' << ans.mincnt << '\n';
		}
	}
	return 0;
}

四:完成建树、查询、单点修改

void build(int id, int l, int r) {
	if (l == r) {
		seg[id].f = {a[l], 1};
	}
	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.minv = 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 {
	int minv, mincnt;
};

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

Info operator + (const Info &l, const Info &r) {
	Info ret;
	if ( l.minv < r.minv ) ret = l;
	else if ( r.minv < l.minv ) ret = r;
	else ret = {l.minv, l.mincnt + r.mincnt};
	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], 1};
	}
	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.minv = 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.minv << ' ' << ans.mincnt << '\n';
		}
	}
	return 0;
}

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

相关文章

  • 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......
  • 无涯教程-jQuery Online Quiz函数
    以下测验提供与jQueryFramework相关的多项选择题(MCQ)。您将必须阅读所有给定的答案,然后单击正确的答案。如果您不确定答案,则可以使用显示答案按钮检查答案。您可以使用下一个测验按钮检查测验中的新问题集。Q1-如何获得传递给函数的参数总数?A-使用args.length属性......