首页 > 其他分享 >[DS记录] 线段树 Beats

[DS记录] 线段树 Beats

时间：2023-03-20 22:55:58浏览次数：37  
标签：标记 int 线段 add 最大值 Beats 区间 DS define

0. 前言

所谓线段树 Beats，就是吉老师打出来的线段树。

1. 基本操作

P6242 线段树 3

  1. 区间加
  2. 区间取 min
  3. 区间最大值
  4. 区间和
  5. 区间历史最大值

首先考虑 1 3 4 咋做。就是直接做对吧。

然后 5 咋做，我们发现难处在于历史最大值的维护。（废话）

比如我现在 \(+= k\)，再 \(-= v\)。（都是正数）如果这两个操作执行完下传， 我们发现第一个操作执行完的历史最大值。因为标记把他们合并成了 \(k - v\)。

我们见招拆招，维护一个历史最大标记怎么样。就是 pushdown，我们先修改这个标记，再处理普通标记。

记这两个标记为 \(add_1, add_3\)。（为了适应后面的定义）

那么 \(add_1\) 为普通区间加标记。\(add_3\) 为下放 \(add_1\) 之前，\(add_1\) 的出现过的最大值。（标记的历史最大）

那这样我们是不是赢了。

然后 2. 取 min 其实很简单。相信大家都知道这个东西需要均摊分析。先说明处理过程。

维护最大值 \(maxa\)，严格次大值 \(se\)，最大值出现次数 \(cnt\)。递归时，假设取 min 的是 \(val\)。

  • 如果 \(val > maxa\)，那么结束。
  • 如果 \(maxa > val > se\)，那么可以通过 \(cnt\) 计算贡献。
  • 否则暴力递归。

复杂度为什么是对的？设一个节点的容（我的理解：一个抽象的东西，描述节点的信息量多少？）为区间中数的种类数。由于暴力递归必然使得 最大值 和 严格次大值 合并。容 -= 1。而所有节点的种类数之和是 \(O(n\log n)\)（n 个数两两不同，每个数对 \(log\) 个节点贡献 1）

那这样我们就赢麻了。

怎么结合这两个玩意呢？我们考虑维护两套标记。

\(add_1, add_3\) 和 \(add_2, add_4\) 前者针对最大值，后者针对非最大值。

然后 pushdown 也需要修改。如果左边最大值 = 区间最大值，那么左边最大值继承区间最大值的标记，否则继承非最大值的标记。而左边非最大值继承区间非最大值标记。右边同理。

那这样我们就啥都会了。

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fout freopen("out.out","w",stdout);
#define fin freopen("in.in","r",stdin);
#define DE {cerr << "QAQ" << endl;}
#define dd(x) cerr << #x" = " << x << endl;
inline int read() {
	int x=0, v=1,ch=getchar();
	while('0'>ch||ch>'9') {
		if(ch=='-') v=0;
		ch=getchar();
	}while('0'<=ch&&ch<='9') {
		x=(x*10)+(ch^'0');
		ch=getchar();
	}return v?x:-x;
}
const int MAX = 5e5 + 5;
const int INF = -2e9;
struct node {
	ll sum;
	int maxa, se, maxb, cnt, len;
	int add1, add2, add3, add4;
	void upd(int k1, int k2, int k3, int k4) {
		sum += 1ll * cnt * k1 + 1ll * (len - cnt) * k2;
		maxb = max(maxb, maxa + k3); // ÕâÀï k3 ÊÇ ×î´óÖµ + ÀúÊ·×î´ó±ê¼Ç¡£ 
		maxa += k1; 
		if(se != INF) se += k2;
		add3 = max(add3, add1 + k3);
		add4 = max(add4, add2 + k4);  
		add1 += k1, add2 += k2;
	}
	void upd2(int v) {
		sum += len * v;
		maxb = max(maxb, maxa + v);
		maxa += v;
		if(se != INF) se += v;
		add3 = max(add3, add1 + v);
		add4 = max(add4, add2 + v);
		add1 += v;
		add2 += v;
	}
} tr[MAX << 2];

#define ls x << 1, l, mid
#define rs x << 1 | 1, mid + 1, r
#define rt 1, 1, n

void ps(int x) {
	node &m = tr[x];
	node l = tr[x << 1], r = tr[x << 1 | 1];
	m.sum = l.sum + r.sum;
	m.maxa = max(l.maxa, r.maxa);
	m.maxb = max(l.maxb, r.maxb);
	if(l.maxa == r.maxa) {
		m.se = max(l.se, r.se);
		m.cnt = l.cnt + r.cnt;
	}else if(m.maxa == l.maxa) {
		m.se = max(l.se, r.maxa);
		m.cnt = l.cnt;
	}else if(m.maxa == r.maxa){
		m.se = max(r.se, l.maxa);
		m.cnt = r.cnt;
	}
}
void pd(int x) {
	int v = max(tr[x << 1].maxa, tr[x << 1 | 1].maxa);
	
	if(v == tr[x << 1].maxa) 
		 tr[x << 1].upd(tr[x].add1, tr[x].add2, tr[x].add3, tr[x].add4);
	else tr[x << 1].upd(tr[x].add2, tr[x].add2, tr[x].add4, tr[x].add4);
	
	if(v == tr[x << 1 | 1].maxa) 
		 tr[x << 1 | 1].upd(tr[x].add1, tr[x].add2, tr[x].add3, tr[x].add4);
	else tr[x << 1 | 1].upd(tr[x].add2, tr[x].add2, tr[x].add4, tr[x].add4);
	
	tr[x].add1 = tr[x].add2 = tr[x].add3 = tr[x].add4 = 0;
} 
void build(int x, int l, int r) {
	tr[x].len = r - l + 1;
	if(l == r) {
		int v = read();
		tr[x].sum = tr[x].maxa = tr[x].maxb = v; 
		tr[x].se = INF;
		tr[x].cnt = 1;
		return ;
	} 
	int mid = l + r >> 1;
	build(ls), build(rs), ps(x);
}
void mdf_min(int x, int l, int r, int s, int t, int v){
	if(v > tr[x].maxa) return ;
	if(s <= l && r <= t && v > tr[x].se) {
		int d = tr[x].maxa - v;
		tr[x].sum -= 1ll * d * tr[x].cnt;
		tr[x].add1 -= d;
		tr[x].maxa = v;
		return ;
	}
	int mid = l + r >> 1; pd(x);
	if(s <= mid) mdf_min(ls, s, t, v);
	if(mid < t) mdf_min(rs, s, t, v);
	ps(x);
}
void mdf_add(int x, int l, int r, int s, int t, int v) {
	if(s <= l && r <= t) {
		tr[x].upd2(v);
		return ;
	}
	int mid = l + r >> 1; pd(x);
	if(s <= mid) mdf_add(ls, s, t, v);
	if(mid < t) mdf_add(rs, s, t, v);
	ps(x);
}
ll ask_sum(int x, int l, int r, int s, int t) {
	if(s <= l && r <= t) return tr[x].sum;
	ll ret = 0; int mid = l + r >> 1; pd(x);
	if(s <= mid) ret += ask_sum(ls, s, t);
	if(mid < t) ret += ask_sum(rs, s, t);
	return ret;
}
int ask_maxa(int x, int l, int r, int s, int t) {
	if(s <= l && r <= t) return tr[x].maxa;
	int mid = l + r >> 1; int ret = INF; pd(x);
	if(s <= mid) ret = max(ret, ask_maxa(ls, s, t));
	if(mid < t) ret = max(ret, ask_maxa(rs, s, t));
	return ret; 
}
int ask_maxb(int x, int l, int r, int s, int t) {
	if(s <= l && r <= t) return tr[x].maxb;
	int mid = l + r >> 1; int ret = INF; pd(x);
	if(s <= mid) ret = max(ret, ask_maxb(ls, s, t));
	if(mid < t) ret = max(ret, ask_maxb(rs, s, t));
	return ret;
}

int n, m;
signed main() {
//	fin;
	n = read(), m = read();
	build(1, 1, n);
	for(int i = 1; i <= m; ++ i) {
		int op = read(), l = read(), r = read();
		if(op == 1) {
			int k = read();
			mdf_add(rt, l, r, k);
		}else if(op == 2) {
			int k = read();
			mdf_min(rt, l, r, k);
		}
		else if(op == 3) printf("%lld\n", ask_sum(rt, l, r));
		else if(op == 4) printf("%d\n", ask_maxa(rt, l, r));
		else printf("%d\n", ask_maxb(rt, l, r));
	}
	return 0;
}

CPU 监控

区间加，区间赋值，区间最大值，区间历史最大值。

多了个区间赋值。意味着我们需要理清楚两个标记之间的关系！（就像线段树 2）

实际上我们只有一个标记，\((add, cov)\)，表示先区间加 \(add\)，再区间赋值成 \(cov\)。

因为如果我们进行了一次区间赋值，我们的区间加操作都可以变成区间赋值操作。

我们维护标记 \(add, hadd, cov, hcov, flag\) 表示：

区间加标记，区间加标记的历史最大，区间赋值标记，区间赋值标记的历史最大。

点击查看代码 
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fout freopen("out.out","w",stdout);
#define fin freopen("in.in","r",stdin);
#define DE {cerr << "QAQ" << endl;}
#define dd(x) cerr << #x" = " << x << endl;
inline int read() {
	int x=0, v=1,ch=getchar();
	while('0'>ch||ch>'9') {
		if(ch=='-') v=0;
		ch=getchar();
	}while('0'<=ch&&ch<='9') {
		x=(x*10)+(ch^'0');
		ch=getchar();
	}return v?x:-x;
}
inline char readc() {
	char ch = 0;
	while(ch < 'A' || ch > 'Z') ch = getchar();
	return ch; 
} 
int n;
const int MAX = 1e5 + 5;
struct node {
	int maxa, maxb;
	int add, hadd; // ¼Ó·¨±ê¼Ç£¬¼Ó·¨±ê¼ÇµÄÀúÊ·×î´ó 
	int cov, hcov; // ¸³Öµ±ê¼Ç£¬¸³Öµ±ê¼ÇµÄÀúÊ·×î´ó 
	int fl; 	   // ÊÇ·ñ½øÐÐÁ˸³Öµ±ê¼Ç 
	void upd_add(int k1, int k2) {
		// ËùνµÄ¸³Öµ ºÍ ¼Ó·¨»¥Ïàת»¯¡£ 
		// ¸Ð¾õÉÏ£º½øÐÐ cover Ç°£¬¹±Ï׶¼ÔÚ¸³Öµ²Ù×÷ͳ¼Æ¡£ 
		maxb = max(maxb, maxa + k2);
		maxa += k1;
		if(fl) {
			hcov = max(hcov, cov + k2);
			cov += k1;
		}else {
			hadd = max(hadd, add + k2);
			add += k1; 
		}
	} 
	void upd_cov(int k1, int k2) {
		fl = 1;
		maxb = max(maxb, k2);
		maxa = cov = k1;
		hcov = max(hcov, k2);
	}
} tr[MAX << 2];
#define ls x << 1, l, mid
#define rs x << 1 | 1, mid + 1, r 
#define rt 1, 1, n
void ps(int x) {
	tr[x].maxa = max(tr[x << 1].maxa, tr[x << 1 | 1].maxa);
	tr[x].maxb = max(tr[x << 1].maxb, tr[x << 1 | 1].maxb);
}
void pd(int x) {
	if(tr[x].add || tr[x].hadd) {
		tr[x << 1].upd_add(tr[x].add, tr[x].hadd);
		tr[x << 1 | 1].upd_add(tr[x].add, tr[x].hadd);
		tr[x].add = tr[x].hadd = 0;
	}
	if(tr[x].fl) {
		tr[x << 1].upd_cov(tr[x].cov, tr[x].hcov);
		tr[x << 1 | 1].upd_cov(tr[x].cov, tr[x].hcov);
		tr[x].fl = 0;
	}
}
void add(int x, int l, int r, int s, int t, int v) {
	if(s <= l && r <= t) { tr[x].upd_add(v, max(v, 0)); return ; }
	int mid = l + r >> 1; pd(x);
	if(s <= mid) add(ls, s, t, v);
	if(mid < t) add(rs, s, t, v);
	ps(x);
}
void mdf(int x, int l, int r, int s, int t, int v) {
	if(s <= l && r <= t) { tr[x].upd_cov(v, v); return ; }
	int mid = l + r >> 1; pd(x);
	if(s <= mid) mdf(ls, s, t, v);
	if(mid < t) mdf(rs, s, t, v);
	ps(x);
}

int hans, ans;
void qry(int x, int l, int r, int s, int t) {
	if(s <= l && r <= t) {
		ans = max(ans, tr[x].maxa);
		hans = max(hans, tr[x].maxb);
		return ;
	} int mid = l + r >> 1; pd(x);
	if(s <= mid) qry(ls, s, t);
	if(mid < t) qry(rs, s, t);
	ps(x); 
} 

void build(int x, int l, int r) {
	if(l == r) {
		int v = read();
		tr[x].maxa = tr[x].maxb = v;
		return ;
	} 
	int mid = l + r >> 1;
	build(ls), build(rs), ps(x);
}

signed main() {
//	fin;
	n = read();
	build(rt);
	int T = read();
	while(T--) {
		char op = readc();
		int l = read(), r = read();
		if(op == 'Q') {
			ans = - 1 << 31;
			qry(rt, l, r);
			printf("%d\n", ans);
		}else if(op == 'A'){
			hans = - 1 << 31;
			qry(rt, l, r);
			printf("%d\n", hans);
		}else if(op == 'P') {
			int c = read();
			add(rt, l, r, c);
		}else {
			int c = read();
			mdf(rt, l, r, c);
		}
	}
	return 0;
}

标签：标记,int,线段,add,最大值,Beats,区间,DS,define
From： https://www.cnblogs.com/Lates/p/17238227.html

相关文章

  • [浅谈] 线段树优化建边
    \(\color{purple}\text{P6348[PA2011]Journeys}\)\(\color{green}\text{2023.1.1010:58}\)线段树优化建边。题意：给定一个图，每次对区间\([a,b]\)至区间\([c,d]\)建......
  • fieldset的样式和使用
    fieldset{border:1pxsolid#61B5CF;margin-top:16px;padding:8px;}legend{font:bold12pxArial,Helvetica,sans-serif;color:#00008B;background-col......
  • 收集IBM DS8800 PE Package
    1.1注意本文适用于微码64.xx或以上版本1.2收集方法1.选择StorageFacilityManagement，选择相应的StorageFacility，在SFImage#1菜单界面下选择“DataCollectionTas......
  • [CVPR2020] RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clou
    大佬的TensorFlow代码：here另一个大佬的Pytorch代码：等我看完代码再贴链接，之前那个不太行keywords高分辨率点云——约\(10^5\)点云语义分割多层次特征在正式开始......
  • #yyds干货盘点# LeetCode面试题：螺旋矩阵
    1.简述：给你一个m行n列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例1：输入：matrix=[[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]示例2：输......
  • #yyds干货盘点 【React工作记录二十七】moment处理日期格式
     目录​​前言​​​​导语​​​​解决思路​​​​总结​​前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五......
  • #yyds干货盘点 【React工作记录二十八】重置ant design得样式
     目录​​前言​​​​导语​​​​代码部分​​​​总结​​前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五......
  • FastDDS-5.发现机制
    5、发现机制FastDDS作为一种数据分发服务（DDS）实现，提供了发现机制，允许在域参与者之间自动查找和匹配DataWriter和DataReader，以便他们可以开始共享数据。对于所有机制，此发......
  • 密码学SAT入门文献1——Algebraic and Logic Solving Methods for Cryptanalysis
    密码学SAT入门文献2——CDCL(Crypto)SATSolversforCryptanalysis  Abstract Algebraicsolvingofpolynomialsystemsandsatisfiabilityofproposi......
  • Goods
    selected=sort_links.loc[sort_links['Types']=='果蔬']#挑选商品类别为“果蔬”并排序child_nums=selected['id'].sum()#对所有的“果蔬”求和selected['c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99