首页 > 其他分享 >线段树进阶

线段树进阶

时间:2023-09-07 09:03:42浏览次数:48  
标签:le 进阶 标记 int 线段 pushdown 乘法

普通线段树

核心在于上传标记(pushup)和下传标记(pushdown)以及懒标记的设计。

P3373 【模板】线段树 2

维护一个加法标记和乘法标记。

下传标记时,将乘法标记更新加法标记。

标记下传实现
void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    tr[u<<1].val=(tr[u<<1].val*tr[u].mul+tr[u].add*(mid-l+1))%P;
    tr[u<<1|1].val=(tr[u<<1|1].val*tr[u].mul+tr[u].add*(r-mid))%P;
    tr[u<<1].mul=(tr[u<<1].mul*tr[u].mul)%P;
    tr[u<<1|1].mul=(tr[u<<1|1].mul*tr[u].mul)%P;
    tr[u<<1].add=(tr[u<<1].add*tr[u].mul+tr[u].add)%P;
    tr[u<<1|1].add=(tr[u<<1|1].add*tr[u].mul+tr[u].add)%P;
    tr[u].add=0;tr[u].mul=1;
}

Q4.4.5.1. 区间背包问题

维护懒标记 \(f(i)\) 和 \(g(i)\) 表示该区间的背包,在容量不超过 \(i\) 时,最大的价值、物品个数。

乘法操作时,我们直接将 \(f(i)\)(\(0\le i\le m\)) 全变成 \(f(i/w)\),\(g(i)\) 全变成 \(g(i/w)\)。区间覆盖操作,我们就将 \(f(i)\) 变成 \(g(i)\times v\)。

下传懒标记的操作与这些相似。

注意乘法标记要每次更新后与 \(m+1\) 取较小值,因为 \(m+1\) 等价于比 \(m\) 大的所有数。

标记下传与上传实现
void pushup(int u){
	for(int i=0;i<=m;i++){
		tr[u].f[i]=0;tr[u].g[i]=0;
		for(int j=0;j<=i;j++){
			tr[u].f[i]=max(tr[u].f[i],tr[u<<1].f[j]+tr[u<<1|1].f[i-j]);
			tr[u].g[i]=max(tr[u].g[i],tr[u<<1].g[j]+tr[u<<1|1].g[i-j]);
		}
	}
}
void pushdown(int u){
	if(tr[u].lazy1>1){
		for(int i=m;i>=0;i--)
			tr[u<<1].f[i]=tr[u<<1].f[i/tr[u].lazy1],tr[u<<1|1].f[i]=tr[u<<1|1].f[i/tr[u].lazy1],
			tr[u<<1].g[i]=tr[u<<1].g[i/tr[u].lazy1],tr[u<<1|1].g[i]=tr[u<<1|1].g[i/tr[u].lazy1];
		tr[u<<1].lazy1=min(tr[u<<1].lazy1*tr[u].lazy1,(ll)m+1);
		tr[u<<1|1].lazy1=min(tr[u<<1|1].lazy1*tr[u].lazy1,(ll)m+1);
	}
	if(tr[u].lazy2){
		for(int i=0;i<=m;i++)
			tr[u<<1].f[i]=(ll)tr[u<<1].g[i]*tr[u].lazy2,tr[u<<1|1].f[i]=(ll)tr[u<<1|1].g[i]*tr[u].lazy2;
		tr[u<<1].lazy2=tr[u<<1|1].lazy2=tr[u].lazy2;
	}
	tr[u].lazy1=1;tr[u].lazy2=0;
}

标签:le,进阶,标记,int,线段,pushdown,乘法
From: https://www.cnblogs.com/includec/p/17683887.html

相关文章

  • MySQL系列之主从复制进阶——延时从库、半同步、过滤复制、GTID复制
    目录1.延时从库1.1介绍1.2为什么要有延时从1.3配置延时从库1.4延时从库应用1.4.1故障恢复思路1.4.2故障模拟及恢复2.半同步***2.1半同步复制工作原理的变化2.2配置半同步复制3.过滤复制3.1说明4.GTID复制4.1GTID引入4.2GTID介绍4.3GTID核心参数4.4......
  • Rust-高级进阶
    Rust高级进阶生命周期进阶生命周期约束通过形如'a:'b的语法,可以说明两个生命周期的长短关系。'a:'b这种情况说明生命周期'a>='b。structDoubleRef<'a,'b:'a,T>{r:&'aT,s:&'bT}T:'a类型T必须比'a活得要久:st......
  • 【C语言进阶】指针数组 —— 数组指针
    (文章目录)......
  • Codeforces Round 406 (Div. 2) D. Legacy 线段树优化建图
    传送门题目大意:给定n个点,m个操作,和起点s。其中n和q大于等于1小于等于1e5,s大于等于1小于等于n其中m个操作有三种情况:  1.输入1uvval表示从u号点向v号点连一个权值为val的有向边,其中1<=u<=n,1<=v<=n,1<=val<=1e9  2.输入2ulrval表示从u号点......
  • Linux C 进阶 —— 可变参数
    1#include<stdio.h>2#include<stdarg.h>3/*方式1C99宏方式GNUC扩展宏方式*/4#defineMC_C99_PRINT(fmt,...)printf(fmt,##__VA_ARGS__)//##作用:当变参列表为空时,消除fmt后的逗号5#defineMC_GNC_PRINT(fmt,args...)printf(fmt,##args)6/*......
  • C进阶(数据存储)
    空类型void表示空类型(无类型)通常应用于函数的返回类型、函数的参数、指针类型大小端存储模式(使用代码段判断大小端)大端存储 数据的低位保存在内存的高地址中,而数据高位,保存在内存低地址中小端存储数据的低位保存在内存的低地址中,而数据高位,保存在内存高地址中补码反码原码三种表......
  • C进阶(指针)
    一维数组传参的几种形式(5种)voidtest(intarr[])//{}voidtest(intarr[10])//{}voidtest(int*arr)//{}voidtest2(int*arr[20])//{}voidtest2(int**arr)//{}intmain(){intarr[10]={0};int*arr2[20]={0};test(arr);test2(arr2);}二维数组传参的几......
  • 吉司机线段树
    一、区间历史最值以区间历史最大值为例。首先,相应地,设\(maxb\)表示一个节点的区间历史最大值。为了更新一个区间的子区间,再设一个\(tag2\),表示\(tag1\)从上次\(push\_down\)以后到现在达到过的最大值。\(code:\)voidpush_up(intu){p[u].w=p[u<<1].w+p[u<<1|1].w......
  • 李超线段树学习笔记
    李超线段树学习笔记P4097【模板】李超线段树/[HEOI2013]Segment题意要求在平面直角坐标系下维护两个操作:在平面上加入一条线段。记第\(i\)条被插入的线段的标号为\(i\)。给定一个数\(k\),询问与直线\(x=k\)相交的线段中,交点纵坐标最大的线段的编号。做法首先,......
  • 线段树
    建树:inta[100005],d[100005];voidbuild(ints,inte,intp){//建树 //对区间[s,t]建立线段树,当前根编号为p if(s==e){ d[p]=a[s]; return; } intm=s+((e-s)>>1); build(s,m,p*2); build(m+1,e,p*2+1);//分割出两个子区间 d[p]=d[p*2]+d[(p*2)+1];}//d[i]为......