首页 > 其他分享 >线段树-多个懒标记pushdown

线段树-多个懒标记pushdown

时间：2023-11-16 12:55:57浏览次数：33  
标签：add2 add1 rs int 线段 标记 ls pushdown sum

P3373 【模板】线段树 2

这里需要用到两个懒标记，一个懒标记为add，记录加，另一个懒标记为mul，记录乘。
我们需要规定一个优先级，然后考虑如何将懒标记下传。
这里无非有两种顺序，一种是先乘后加，另一种是先加后乘。
我们先看先加后乘。

\[(sum + add1) * mul1 \]

当我们的懒标记$ add2 、 mul2 $下传

\[(sum + add1) * mul1 + add2 \quad (1) \]

\[(sum + add1) * mul1 * mul2 \quad (2) \]

我们更新懒标记仍需要化成

\[(sum + add) * mul \]

对于（1）

\[(sum + add1 + \frac{add2} {mul1}) * mul1 \quad (1) \]

可以看出如果要下传add标记就需要add2必须满足mul1，这个显然不容易满足
对于（2）

\[(sum + add1) * mul1 * mul2 \quad (2) \]

我们之间将mul标记更新为$ mul1 * mul2 $ 即可
显然先加后乘，下传加号标记是不好处理的
我们再看先乘后加

\[sum * mul1 + add1 \]

当懒标记$ add2 或 mul2 $下传

\[sum * mul1 + add1 + add2 \quad (1) \]

\[(sum * mul1 + add1) * mul2 \quad (2) \]

对于（1）
我们只需要将add标记更新为$ add1 + add2$即可
对于（2）

\[sum * mul1 * mul2 + add1 * mul2 \quad (2) \]

我们需要将add标记跟新为$ add1 * mul2 , 将mul标记更新为 mul1 * mul2$
我们发现先乘后加的情况，懒标记的下传都很容易做到，所以我们选择先乘后加这种顺序。
下面是代码：


#include <bits/stdc++.h> 
#define LL long long 
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
#define PII pair<int, int>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
ll n, q, mod, a[N];
struct node
{
	ll l, r, sum, mul, add;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define mul(x) tree[x].mul
	#define add(x) tree[x].add
	#define sum(x) tree[x].sum
} tree[4 * N];

void pushup(int p)
{
	sum(p) = (sum(ls) + sum(rs)) % mod;
}

void build(int p, ll l, ll r)
{
	l(p) = l; r(p) = r; mul(p) = 1, add(p) = 0;
	if(l == r)	
	{
		sum(p) = a[l] % mod;
		return;
	}
	int mid = (l(p) + r(p)) >> 1;
	build(ls, l(p), mid), build(rs, mid + 1, r(p));
	pushup(p);	 
}

void pushdown(int p)
{
	sum(ls) =  (sum(ls) * mul(p) + (r(ls) - l(ls) + 1) * add(p)) % mod;
	sum(rs) =  (sum(rs) * mul(p) + (r(rs) - l(rs) + 1) * add(p)) % mod;
	
	mul(ls) =  (mul(ls) * mul(p)) % mod;
	mul(rs) =  (mul(rs) * mul(p)) % mod;
	
	add(ls) =  (add(ls) * mul(p) + add(p)) % mod;
	add(rs) =  (add(rs) * mul(p) + add(p)) % mod;
	
	add(p) = 0; mul(p) = 1;
}

void modify(int p, ll l, ll r, int op, ll x)
{
	if(l(p) >= l && r(p) <= r)
	{
		if(op == 1)
		{
			sum(p) = (sum(p) * x) % mod;
			mul(p) = (mul(p) * x) % mod;
			add(p) = (add(p) * x) % mod;
		}
		else if(op == 2) 
		{ 
			sum(p) = (sum(p) + (r(p) - l(p) + 1) * x) % mod;
			add(p) = (add(p) + x) % mod;
		}
		return;
	}
	pushdown(p);
	int mid = (l(p) + r(p)) >> 1;
	if(l <= mid)	modify(ls, l, r, op, x);
	if(r > mid)	modify(rs , l, r, op, x);
	pushup(p);
}

ll query(int p, ll l, ll r)
{
	if(l(p) >= l && r(p) <= r)	return sum(p);
	pushdown(p);
	int mid = (l(p) + r(p)) >> 1;
	ll val = 0;
	if(l <= mid)	val = (val + query(ls, l, r)) % mod;
	if(r > mid)		val = (val + query(rs, l, r)) % mod;
	return val;
}

void solve()
{
	cin >> n >> mod;
	for(int i = 1; i <= n; ++ i)	cin >> a[i];
	cin >> q;
	build(1, 1, n);
	for(int i = 1; i <= q; ++ i)
	{
		int op; cin >> op;
		if(op == 1)
		{
			ll l, r, x;	cin >> l >> r >> x;
			modify(1, l, r, op, x);
		}
		else if(op == 2)
		{
			ll l, r, x; cin >> l >> r >> x;
			modify(1, l, r, op, x);
		}
		else
		{
			int l, r; cin >> l >> r;
			cout << query(1, l, r) << endl; 	
		}
	} 
}		
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	freopen("1.in", "r", stdin);
	solve(); 
	return 0;
}

P1253 扶苏的问题

这道题目也需要两个懒标记，一个把一个区间的所有数变成x的懒标记记为add1，另一个懒标记记为add2

特殊性：操作一会覆盖，假设有操作1，新增懒标记为$ add1 时， 我们就将 add2清空$
当新增一个操作2时，我们就直接增加 $ add2 标记即可 $

#include <bits/stdc++.h> 
#define LL long long 
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int n, q, a[N];
struct node
{
	int l, r, st;
	ll mx, add1, add2;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define add1(x) tree[x].add1
	#define add2(x) tree[x].add2
	#define st(x) tree[x].st
	#define mx(x) tree[x].mx
} tree[4 * N];

void pushup(int p)
{
	mx(p) = max(mx(ls), mx(rs));
}

void build(int p, int l, int r)
{
	l(p) = l; r(p) = r; st(p) = 0;
	if(l == r)	
	{
		mx(p) = a[l];
		return;
	}
	int mid = (l(p) + r(p)) >> 1;
	build(ls, l(p), mid), build(rs, mid + 1, r(p));
	pushup(p);	 
}

void pushdown(int p)
{
	if(st(p))
	{
		st(ls) = st(rs) = 1;
		add1(ls) = add1(rs) = add1(p);
		add2(ls) = add2(rs) = 0;
		mx(ls) = mx(rs) = add1(p);
		st(p) = add1(p) = 0;
	}
	mx(ls) += add2(p);	mx(rs) += add2(p);
	add2(ls) += add2(p);	add2(rs) += add2(p);
	add2(p) = 0;
}

void modify(int p, int l, int r, int op, int x)
{
	if(l(p) >= l && r(p) <= r)
	{
		if(op == 1)
		{
			mx(p) = x;
			st(p) = 1;
			add1(p) = x;
			add2(p) = 0;
		}
		else 
		{
			mx(p) += x;
			add2(p) += x;
		}
		return;
	}
	pushdown(p);
	int mid = (l(p) + r(p)) >> 1;
	if(l <= mid)	modify(ls, l, r, op, x);
	if(r > mid)	modify(rs , l, r, op, x);
	pushup(p);
}

ll query(int p, int l, int r)
{
	if(l(p) >= l && r(p) <= r)	return mx(p);
	pushdown(p);
	int mid = (l(p) + r(p)) >> 1;
	ll val = -1e18;
	if(l <= mid)	val = max(val, query(ls, l, r));
	if(r > mid)		val = max(val, query(rs, l, r));
//	pushup(p); 
	return val;
}

void solve()
{
	cin >> n >> q;
	for(int i = 1; i <= n; ++ i)	cin >> a[i];
	build(1, 1, n); 
	for(int i = 1; i <= q; ++ i)
	{
		int op; cin >> op;
		if(op == 1)
		{
			int l, r, x;	cin >> l >> r >> x;
			modify(1, l, r, op, x);
		}
		else if(op == 2)
		{
			int l, r, x; cin >> l >> r >> x;
			modify(1, l, r, op, x);
		}
		else
		{
			int l, r; cin >> l >> r;
			cout << query(1, l, r) << endl; 	
		}
	} 
	
}		
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	freopen("1.in", "r", stdin);
	solve(); 
	return 0;
}

标签：add2,add1,rs,int,线段,标记,ls,pushdown,sum
From： https://www.cnblogs.com/cxy8/p/17835852.html

相关文章

  • abc327F - Apples（线段树）
    https://atcoder.jp/contests/abc327/tasks/abc327_f我们将时间看作x轴，位置看作y轴，那么我们随着时间增加，维护新加的点对区间的贡献，同时减去过时的点，线段树区间加法维护最大值即可。#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<map>#incl......
  • vue的虚拟dom渲染真实dom的过程中首先会对新老VNode的开始和结束位置进行标记：oldStart
    关于Vue中的diff算法说法错误的是（）A比较只会在同层级节点进行比较,不会跨层级比较B在diff比较的过程中，循环从两边向中间收拢。Cvue的虚拟dom渲染真实dom的过程中首先会对新老VNode的开始和结束位置进行标记：oldStartIdx、oldEndIdx、newStartIdx、newEndIdxD当老VNode节......
  • excel条件格式——表格改动标记颜色
    工作中有一部分excel的工作处理。有几个场景我比较常用，记录下来。场景一：有一个大表excel，需要发给负责人核实里面的条目是否新增、改动。对方改动之后，会回复邮件给我。那我收到对方发来的附件，如何辨别改了哪里呢？需求：我需要很快识别出对方改动了哪里。于是在发送给对方excel表格之前，......
  • go中标记一个模块内容为过时
    今天在使用标准库ioutil时发现已经过时，是通过在注释上添加实现的。例如：//WsHandlerFuncislikeHandleFuncinGin.////Deprecated:Notsupport.typeWsHandlerFuncfunc(*websocket.Conn)在goland中调用时就会提示已废弃。......
  • 线段树
    线段树引入遇到过好多次线段树的题目，要么就是用其他的方法去解决，要么就是不会写！！今天痛定思痛，决定好好归纳整理一下线段树线段树解决的是「区间和」的问题，且该「区间」会被修改什么意思呢？举个简单的例子，对于nums=[1,2,3,4,5]如果我们需要多次求某些区间的和，是不是首先想......
  • 理解线段树和主席树：解决区间操作的利器
    在计算机科学和算法领域，区间操作问题是一类常见且重要的问题，它们涉及到在一维数据结构中执行查询和更新操作。线段树和主席树是两种用于解决这类问题的强大数据结构。本文将介绍这两种树状数据结构，以及它们在不同应用领域中的使用。什么是线段树？线段树是一种用于处理区间操作问......
  • 线段树历史值
    P6242【模板】线段树3支持区间加，区间取\(\min\)，区间求和，区间\(\max\)，区间历史\(\max\)。先提一嘴吉司机。就是对线段树的每个节点记录最大值，严格次大值和最大值个数，只在\(se<v<mx\)的区间操作，否则向下递归。如果没有区间加，复杂度势能分析是\(O((n+m)\logn)\)的，否则为......
  • 原点到线段的垂足
    原理：1) 求出向量ao在ab上的投影距离2)a沿着ab方向移动投影距离就是垂足点的位置 //获得原点到直线ab的垂点publicstaticVector2GetPerpendicularToOrigin(Vector2a,Vector2b){varab=b-a;varao=Vector2.zero-a;floatproj=Vector2.D......
  • 相似重复类似相同相近图片照片相片素材屏保搜索查找识别标记清理
    图片清理重复照片相片除重去重重复图片管理软件工具APP相似图片查找清理模糊匹配图片相似场景匹配系统文件扫描清理去重比DuplicateCleanerPro，DuplicatePhotoCleaner更方便实用全盘扫描重复文件清楚删除图片整理照片整理C盘清理高效办公个人照片管理相册管理文档管理数......
  • 向量叉乘判断两点是否在线段同侧
    ap1×ab与ap2×ab的结果异号，则表示两点在线段两侧；同号则表示在线段同侧 有一个点在线段上或两个点都在线段上，当做在线段同侧处理 //两点是否在线段同侧publicstaticboolIsTwoPointSameSideOfSegment(Vector2a,Vector2b,Vector2p1,Vector2p2){vara_p1=......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99