devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——线段树学习笔记_线段树学习笔记 例题

作者：weixin_40725706 | 2024-02-25 12:06:41

赞

踩

线段树学习笔记 例题

如果对线段树还没有了解，建议先阅读这一篇文章

线段树进阶练习

P1253 [yLOI2018] 扶苏的问题

P1253 [yLOI2018] 扶苏的问题
比普通的线段树多了一个覆盖操作，针对这个问题，我们可以设定三个懒惰标记，分别表示当前位置需要加多少，需不需要被覆盖（也可以不要，如果将不用覆盖的区间的需要被覆盖成的数字设为一个不可能出现的也可以）和需要被覆盖成的数字。
由于出现了覆盖和加法两种情况， p u s h _ d o w n push\_down push_down 函数需要进行一些改动：

void push_down(long long i)
{
	if(tre[i].chan){//覆盖操作
		tre[i*2].sum=(tre[i*2].r-tre[i*2].l+1)*tre[i].change;
		tre[i*2].Max=tre[i].change;
		tre[i*2].chan=true;
		tre[i*2].change=tre[i].change;
		tre[i*2].laz=0;//由于左子树被覆盖，原来不管加了多少，都会被覆盖为同一个数，不能再加了
		tre[i*2+1].sum=(tre[i*2+1].r-tre[i*2+1].l+1)*tre[i].change;
		tre[i*2+1].Max=tre[i].change;
		tre[i*2+1].chan=true;
		tre[i*2+1].change=tre[i].change;
		tre[i*2+1].laz=0;//由于右子树被覆盖，原来不管加了多少，都会被覆盖为同一个数，不能再加了
		tre[i].chan=false;
		tre[i].change=0;
	}
	if(tre[i].laz!=0){//常规加法懒惰标记下推操作
		tre[i*2].laz+=tre[i].laz;
		tre[i*2].sum=tre[i*2].sum+tre[i].laz*(tre[i*2].r-tre[i*2].l+1);
		tre[i*2].Max+=tre[i].laz;
		tre[i*2+1].laz+=tre[i].laz;
		tre[i*2+1].sum=tre[i*2+1].sum+tre[i].laz*(tre[i*2+1].r-tre[i*2+1].l+1);
		tre[i*2+1].Max+=tre[i].laz;
		tre[i].laz=0;
	}
	return;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

区间覆盖操作：

void cover(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){//当前子树已经完全包括在了所要改变的区间里
		//覆盖并标记
		tre[i].laz=0;
		tre[i].sum=num*(tre[i].r-tre[i].l+1);
		tre[i].Max=num;
		tre[i].chan=true;
		tre[i].change=num;
		return;
	}
	push_down(i);
	if(tre[i*2].r>=l)
		cover(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		cover(i*2+1,l,r,num);
	//更新
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	return;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
完整代码
#include<bits/stdc++.h>
using namespace std;
struct node{
	bool chan;
	long long l,r,sum,laz,change,Max;
} tre[5000000];
long long n,t,a[1000010],a_1,coun;
void setup(long long i,long long l,long long r)
{
	tre[i].l=l;
	tre[i].r=r;
	tre[i].chan=false;
	if(l==r){
		tre[i].sum=a[l];
		tre[i].Max=a[l];
		return;
	}
	long long mid=((l+r)>>1);
	setup(i*2,l,mid);
	setup(i*2+1,mid+1,r);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	return;
}
void push_down(long long i)
{
	if(tre[i].chan){
		tre[i*2].sum=(tre[i*2].r-tre[i*2].l+1)*tre[i].change;
		tre[i*2].Max=tre[i].change;
		tre[i*2].chan=true;
		tre[i*2].change=tre[i].change;
		tre[i*2].laz=0;
		tre[i*2+1].sum=(tre[i*2+1].r-tre[i*2+1].l+1)*tre[i].change;
		tre[i*2+1].Max=tre[i].change;
		tre[i*2+1].chan=true;
		tre[i*2+1].change=tre[i].change;
		tre[i*2+1].laz=0;
		tre[i].chan=false;
		tre[i].change=0;
	}
	if(tre[i].laz!=0){
		tre[i*2].laz+=tre[i].laz;
		tre[i*2].sum=tre[i*2].sum+tre[i].laz*(tre[i*2].r-tre[i*2].l+1);
		tre[i*2].Max+=tre[i].laz;
		tre[i*2+1].laz+=tre[i].laz;
		tre[i*2+1].sum=tre[i*2+1].sum+tre[i].laz*(tre[i*2+1].r-tre[i*2+1].l+1);
		tre[i*2+1].Max+=tre[i].laz;
		tre[i].laz=0;
	}
	return;
}
void add(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){
		tre[i].sum=tre[i].sum+num*(tre[i].r-tre[i].l+1);
		tre[i].laz+=num;
		tre[i].Max+=num;
		return;
	}
	push_down(i);
	if(tre[i*2].r>=l)
		add(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		add(i*2+1,l,r,num);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	return;
}
void cover(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){
		tre[i].laz=0;
		tre[i].sum=num*(tre[i].r-tre[i].l+1);
		tre[i].Max=num;
		tre[i].chan=true;
		tre[i].change=num;
		return;
	}
	push_down(i);
	if(tre[i*2].r>=l)
		cover(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		cover(i*2+1,l,r,num);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	return;
}
long long ask_max(long long i,long long l,long long r)
{
	if(tre[i].l>=l&&tre[i].r<=r)
		return tre[i].Max;
	push_down(i);
	long long ans=-1e15;
	if(tre[i*2].r>=l)
		ans=max(ans,ask_max(i*2,l,r));
	if(tre[i*2+1].l<=r)
		ans=max(ans,ask_max(i*2+1,l,r));
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	setup(1,1,n);
	for(int i=1;i<=t;i++){
		long long q,l,r,x;
		cin>>q;
		if(q==1){
			cin>>l>>r>>x;
			cover(1,l,r,x);
		}
		else if(q==2){
			cin>>l>>r>>x;
			add(1,l,r,x);
		}
		else{
			cin>>l>>r;
			cout<<ask_max(1,l,r)<<endl;
		}
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125

可能大家都会有一个疑问：为什么 p u s h _ d o w n push\_down push_down 函数一定是先将 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记 下推，再推 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记，先后顺序不会有问题吗？，接下来，我们就来分析一下：
对于每个位置，只有当两种懒惰标记都有，才可能出现先后顺序的问题。那么如果又一个节点同时出现了两种懒惰标记，只有如下两种情况：

  1. 原来有 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记，又被放上了 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记（使这种情况出现的两种可能：1.一个节点原有 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记，在 p u s h _ d o w n push\_down push_down 后又被放上了一个 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记；2.一个节点原有 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记 ，在 a d d add add 函数递归到底后又被放上了一个 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记；），这种情况下，就是应该先进行 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记 的下推，再进行 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记 的下推，嗯，没问题。
  2. 原来有 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记，又被放上了 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记。使这种情况出现的两种可能：1.一个节点原有 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记，在 p u s h _ d o w n push\_down push_down 后又被放上了一个 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记，但这种情况实际上 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记已经没有用处了，所以这种节点的 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记 在 p u s h _ d o w n push\_down push_down 后已经被清零了；2.一个节点原有 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记，在 c o v e r cover cover 函数递归到底后又被放上了一个 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记，但这种情况实际上 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记 已经没有用处了，所以这种节点的 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记 在 c o v e r cover cover 后已经被清零；

综上，如果一个节点的两种懒惰标记都不为零，则一定是先下推 覆 盖 懒 惰 标 记 覆盖懒惰标记 覆盖懒惰标记 再下推 加 法 懒 惰 标 记 加法懒惰标记 加法懒惰标记。

P8024 [ONTAK2015] Stumilowy sad

P8024 [ONTAK2015] Stumilowy sad

先来分析一下操作

  • 1 l r c：将第 l l l 片区域到第 r r r 片区域内的所有树的高度拔高 c c c 个单位。
  • 2 l r h：将一把刀固定在高度为 h h h 的空中，对第 l l l 片区域到第 r r r 片区域内的所有树进行砍伐。
  • 3 l r h：往第 l l l 片区域到第 r r r 片区域内的每个区域种上一棵高度为 h h h 的树。
  • 4 l r：查询第 l l l 片区域到第 r r r 片区域内最高的树的高度。

我们发现，由于查询只对区间内区域内最大值的最大值进行查询，并且不管什么操作，都不可能让原来区域内不是最大值的数值变得比最大值更大，所以对于每个区域，只维护最大值即可，所以，操作就变为了（假设初始第 i i i 片区域所种的树的高度为 A i A_i Ai​）：

  • 1 l r c：将第 l l l 片区域到第 r r r 片区域内的所有数加上 c c c 区间加
  • 2 l r h：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，将 A i A_i Ai​ 变成 min ⁡ ( A i , h ) \min(A_i,h) min(Ai​,h) 区间取 min ⁡ \min min
  • 3 l r h：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，将 A i A_i Ai​ 变成 min ⁡ ( A i , h ) \min(A_i,h) min(Ai​,h) 区间取 max ⁡ \max max
  • 4 l r：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，求 A i A_i Ai​ 的最大值 区间求最大值

大家可以参考上一题的方法尝试完成，实在做不出来，可以参考下面代码：

完整代码
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r,laz,cover,Max,Min;
	bool change;
} tre[2000010];
long long n,t,input[500010];
void setup(long long i,long long l,long long r)
{
	tre[i].l=l;
	tre[i].r=r;
	if(l==r){
		tre[i].Max=input[l];
		tre[i].Min=input[l];
		return;
	}
	long long mid=((l+r)>>1);
	setup(i*2,l,mid);
	setup(i*2+1,mid+1,r);
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	tre[i].Min=min(tre[i*2].Min,tre[i*2+1].Min);
	return;
}
void push_d(long long i)
{
	if(tre[i].change){
		tre[i*2].Max=tre[i].cover;
		tre[i*2+1].Max=tre[i].cover;
		tre[i*2].Min=tre[i].cover;
		tre[i*2+1].Min=tre[i].cover;
		tre[i*2].cover=tre[i].cover;
		tre[i*2+1].cover=tre[i].cover;
		tre[i*2].change=true;
		tre[i*2+1].change=true;
		tre[i*2].laz=0;
		tre[i*2+1].laz=0;
		tre[i].cover=0;
		tre[i].change=false;
	}
	if(tre[i].laz){
		tre[i*2].Max+=tre[i].laz;
		tre[i*2].Min+=tre[i].laz;
		tre[i*2+1].Min+=tre[i].laz;
		tre[i*2+1].Max+=tre[i].laz;
		tre[i*2].laz+=tre[i].laz;
		tre[i*2+1].laz+=tre[i].laz;
		tre[i].laz=0;
	}
	return;
}
void add(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){
		tre[i].Max+=num;
		tre[i].Min+=num;
		tre[i].laz+=num;
		return;
	}
	push_d(i);
	if(tre[i*2].r>=l)
		add(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		add(i*2+1,l,r,num);
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	tre[i].Min=min(tre[i*2].Min,tre[i*2+1].Min);
	return;
}
void cut_tree(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){
		if(tre[i].Min>=num){
			tre[i].Max=num;
			tre[i].Min=num;
			tre[i].cover=num;
			tre[i].change=true;
			tre[i].laz=0;
			return;
		}
		if(tre[i].Max<=num)
			return;
	}
	push_d(i);
	if(tre[i*2].r>=l)
		cut_tree(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		cut_tree(i*2+1,l,r,num);
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	tre[i].Min=min(tre[i*2].Min,tre[i*2+1].Min);
	return;
}
void grow_tree(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){
		if(tre[i].Max<=num){
			tre[i].Min=num;
			tre[i].Max=num;
			tre[i].cover=num;
			tre[i].change=true;
			tre[i].laz=0;
			return; 
		}
		if(tre[i].Min>=num)
			return; 
	}
	push_d(i);
	if(tre[i*2].r>=l)
		grow_tree(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		grow_tree(i*2+1,l,r,num);
	tre[i].Max=max(tre[i*2].Max,tre[i*2+1].Max);
	tre[i].Min=min(tre[i*2].Min,tre[i*2+1].Min);
	return;
}
long long ask(long long i,long long l,long long r)
{
	if(tre[i].l>=l&&tre[i].r<=r)
		return tre[i].Max;
	long long value=-1e15;
	push_d(i);
	if(tre[i*2].r>=l)
		value=max(value,ask(i*2,l,r));
	if(tre[i*2+1].l<=r)
		value=max(value,ask(i*2+1,l,r));
	return value;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>input[i];
	setup(1,1,n);
	for(int i=1;i<=t;i++){
		long long q,l,r,num;
		cin>>q;
		if(q==1){
			cin>>l>>r>>num;
			add(1,l,r,num);
		}
		else if(q==2){
			cin>>l>>r>>num;
			cut_tree(1,l,r,num);
		}
		else if(q==3){
			cin>>l>>r>>num;
			grow_tree(1,l,r,num);
		}
		else{
			cin>>l>>r;
			cout<<ask(1,l,r)<<endl;
		}
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155

P1438 无聊的数列

P1438 无聊的数列
首先分析一下操作：

  • 1 l r K D：给出一个长度等于 r − l + 1 r-l+1 r−l+1 的等差数列，首项为 K K K，公差为 D D D，并将它对应加到 [ l , r ] [l,r] [l,r] 范围中的每一个数上。即：令 a l = a l + K , a l + 1 = a l + 1 + K + D … a r = a r + K + ( r − l ) × D a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D al​=al​+K,al+1​=al+1​+K+D…ar​=ar​+K+(r−l)×D。
  • 2 p：询问序列的第 p p p 个数的值 a p a_p ap​。

题目对我们还挺仁慈的，看一下操作一，你看到了什么？首项为K，公差为D，你又想到了什么？差分？没毛病，就是差分！
原数列的差分数组为 0 , 0 , 0 , . . . 0,0,0,... 0,0,0,...，如果使用操作一1 1 4 1 1，则这个差分就会变成： 1 , 1 , 1 , 1 , 0 , . . . 1,1,1,1,0,... 1,1,1,1,0,...(首项变的差分数组加上 K K K，后边一直到区间末尾，差分数组全部加上 D D D)
如果询问第 p p p 个数，按照差分的性质，只要将前 p p p 个位置的数字加起来即可

完整代码
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r,sum,laz;
} tre[400010];
long long s[100010],a[100010],n,t;
void setup(long long i,long long l,long long r)
{
	tre[i].l=l;
	tre[i].r=r;
	tre[i].laz=0;
	if(l==r){
		tre[i].sum=a[l];
		return;
	}
	long long mid=((l+r)>>1);
	setup(i*2,l,mid);
	setup(i*2+1,mid+1,r);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	return;
}
void push_d(long long i)
{
	if(tre[i].laz){
		tre[i*2].laz+=tre[i].laz;
		tre[i*2+1].laz+=tre[i].laz;
		tre[i*2].sum=tre[i*2].sum+tre[i].laz*(tre[i*2].r-tre[i*2].l+1);
		tre[i*2+1].sum=tre[i*2+1].sum+tre[i].laz*(tre[i*2+1].r-tre[i*2+1].l+1);
		tre[i].laz=0;
	}
	return;
}
void add(long long i,long long l,long long r,long long num)
{
	if(l<=tre[i].l&&tre[i].r<=r){
		tre[i].sum=tre[i].sum+(tre[i].r-tre[i].l+1)*num;
		tre[i].laz+=num;
		return;
	}
	push_d(i);
	if(tre[i*2].r>=l)
		add(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		add(i*2+1,l,r,num);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	return;
}
long long ask(long long i,long long l,long long r)
{
	if(l<=tre[i].l&&tre[i].r<=r)
		return tre[i].sum;
	push_d(i);
	long long ans=0;
	if(tre[i*2].r>=l)
		ans+=ask(i*2,l,r);
	if(tre[i*2+1].l<=r)
		ans+=ask(i*2+1,l,r);
	return ans;
}
int main()
{
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n-1;i>0;i--)
		a[i+1]=a[i+1]-a[i];
	setup(1,1,n);
	for(int i=1;i<=t;i++){
		long long q,l,r,num1,num2;
		cin>>q;
		if(q==1){
			cin>>l>>r>>num1>>num2;
			add(1,l,l,num1);
			if(l+1<=r)
				add(1,l+1,r,num2);
			if(r<n)
				add(1,r+1,r+1,-(num1+num2*(r-l)));
		}
		else{
			cin>>l;
			cout<<ask(1,1,l)<<endl;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

P6373 「StOI-1」IOI计数

P6373 「StOI-1」IOI计数
我们可以发现，操作2所做的询问，实际上就是在询问字符串 S S S 中有多少字串为 I O I IOI IOI。那就先来考虑给定一个字符串，如何统计有多少个为 I O I IOI IOI 的子串。如果将两个字符串合并起来，怎么得到 I O I IOI IOI 子串的个数？考虑使用加法和乘法原理。首先，至少，两边出现过的 I O I IOI IOI 子串，合并之后依然会有，所以， 目 前 字 符 串 I O I 子 串 个 数 + = ( 左 区 间 I O I 子 串 个 数 + 右 区 间 I O I 子 串 个 数 ) 目前字符串IOI子串个数+=(左区间IOI子串个数+右区间IOI子串个数) 目前字符串IOI子串个数+=(左区间IOI子串个数+右区间IOI子串个数)，接下来，考虑将两区间拼接起来后又得到的 I O I IOI IOI 子串个数加上。分类讨论一下，有以下几种情况：

  • 左区间存在 I O IO IO 子串，并且右区间存在 I I I 子串，这种情况所得到的子串个数为 左 区 间 I O 子 串 个 数 × 右 区 间 I 子 串 个 数 左区间IO子串个数\times右区间I子串个数 左区间IO子串个数×右区间I子串个数
  • 左区间存在 I I I 子串，并且右区间存在 O I OI OI 子串，这种情况所得到的子串个数为 左 区 间 I 子 串 个 数 × 右 区 间 O I 子 串 个 数 左区间I子串个数\times右区间OI子串个数 左区间I子串个数×右区间OI子串个数

∴ 目 前 字 符 串 I O I 子 串 个 数 + = ( 左 区 间 I O 子 串 个 数 × 右 区 间 I 子 串 个 数 + 左 区 间 I 子 串 个 数 × 右 区 间 O I 子 串 个 数 ) \therefore目前字符串IOI子串个数+=(左区间IO子串个数\times右区间I子串个数+左区间I子串个数\times右区间OI子串个数) ∴目前字符串IOI子串个数+=(左区间IO子串个数×右区间I子串个数+左区间I子串个数×右区间OI子串个数)
∴ 目 前 字 符 串 I O I 子 串 个 数 = 左 区 间 I O I 子 串 个 数 + 右 区 间 I O I 子 串 个 数 + 左 区 间 个 数 I O 子 串 × 右 区 间 I 子 串 个 数 + 左 区 间 I 子 串 个 数 × 右 区 间 O I 子 串 个 数 \therefore目前字符串IOI子串个数=左区间IOI子串个数+右区间IOI子串个数+左区间个数IO子串\times右区间I子串个数+左区间I子串个数\times右区间OI子串个数 ∴目前字符串IOI子串个数=左区间IOI子串个数+右区间IOI子串个数+左区间个数IO子串×右区间I子串个数+左区间I子串个数×右区间OI子串个数
这样就能写线段树了！但是在计算过程中，也使用过左右子串的 I , I O , O I , O I,IO,OI,O I,IO,OI,O 子串个数，所以，也需要对每个子串的这些子串的个数进行维护：

  • 目 前 字 符 串 I 子 串 个 数 = 左 区 间 I 子 串 个 数 + 右 区 间 I 子 串 个 数 目前字符串I子串个数=左区间I子串个数+右区间I子串个数 目前字符串I子串个数=左区间I子串个数+右区间I子串个数
  • 目 前 字 符 串 O 子 串 个 数 = 左 区 间 O 子 串 个 数 + 右 区 间 O 子 串 个 数 目前字符串O子串个数=左区间O子串个数+右区间O子串个数 目前字符串O子串个数=左区间O子串个数+右区间O子串个数
  • 目 前 字 符 串 I O 子 串 个 数 = 左 区 间 I 子 串 个 数 × 右 区 间 O 子 串 个 数 目前字符串IO子串个数=左区间I子串个数\times右区间O子串个数 目前字符串IO子串个数=左区间I子串个数×右区间O子串个数
  • 目 前 字 符 串 O I 子 串 个 数 = 左 区 间 O 子 串 个 数 × 右 区 间 I 子 串 个 数 目前字符串OI子串个数=左区间O子串个数\times右区间I子串个数 目前字符串OI子串个数=左区间O子串个数×右区间I子串个数

这样，就可以用线段树做了。而操作一就算一个简单的单点修改，有了上面的更新方法，也可以轻松解决了。

完整代码
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r,sum_i,sum_o,sum_io,sum_oi,sum_ioi;
} tre[2000100];
long long n,t,a[500010];
char c;
void push_up(long long i)
{
	tre[i].sum_i=tre[i*2].sum_i+tre[i*2+1].sum_i;
	tre[i].sum_o=tre[i*2].sum_o+tre[i*2+1].sum_o;
	tre[i].sum_oi=tre[i*2].sum_oi+tre[i*2+1].sum_oi+tre[i*2].sum_o*tre[i*2+1].sum_i;
	tre[i].sum_io=tre[i*2].sum_io+tre[i*2+1].sum_io+tre[i*2].sum_i*tre[i*2+1].sum_o;
	tre[i].sum_ioi=tre[i*2].sum_ioi+tre[i*2+1].sum_ioi+tre[i*2].sum_i*tre[i*2+1].sum_oi+tre[i*2].sum_io*tre[i*2+1].sum_i;
	return;
}
void setup(long long i,long long l,long long r)
{
	tre[i].l=l;
	tre[i].r=r;
	if(l==r){
		if(a[l]==1)
			tre[i].sum_i++;
		else if(a[l]==2)
			tre[i].sum_o++;
		return;
	}
	long long mid=((l+r)>>1);
	setup(i*2,l,mid);
	setup(i*2+1,mid+1,r);
	push_up(i);
}
void change(long long i,long long p,long long change_to)
{
	if(tre[i].l==tre[i].r){
		if(change_to==1){
			if(tre[i].sum_i==0)
				tre[i].sum_i++;
			if(tre[i].sum_o!=0)
				tre[i].sum_o--;
		}
		else{
			if(tre[i].sum_o==0)
				tre[i].sum_o++;
			if(tre[i].sum_i!=0)
				tre[i].sum_i--;
		}
		return;
	}
	if(tre[i*2].r>=p)
		change(i*2,p,change_to);
	if(tre[i*2+1].l<=p)
		change(i*2+1,p,change_to);
	push_up(i);
}
node ask(long long i,long long l,long long r)
{
	if(l<=tre[i].l&&tre[i].r<=r)
		return tre[i];
	node ans,ans1;
	if(tre[i*2].r>=l){
		ans1=ask(i*2,l,r);
		if(tre[i*2+1].l<=r){
			node ans2=ask(i*2+1,l,r);
			ans.sum_i=ans1.sum_i+ans2.sum_i;
			ans.sum_o=ans1.sum_o+ans2.sum_o;
			ans.sum_io=ans1.sum_io+ans2.sum_io+ans1.sum_i*ans2.sum_o;
			ans.sum_oi=ans1.sum_oi+ans2.sum_oi+ans1.sum_o*ans2.sum_i;
			ans.sum_ioi=ans1.sum_ioi+ans2.sum_ioi+ans1.sum_i*ans2.sum_oi+ans1.sum_io*ans2.sum_i; 
		}
		else
			ans=ans1;
	}
	else if(tre[i*2+1].l<=r)
		ans=ask(i*2+1,l,r);
	return ans;
}
int main()
{
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>c;
		if(c=='I')
			a[i]=1;
		else
			a[i]=2;
	}
	setup(1,1,n);
	for(int i=1;i<=t;i++){
		long long q,l,r,num;
		cin>>q;
		if(q==1){
			cin>>l>>c;
			if(c=='I')
				change(1,l,1);
			else
				change(1,l,2);
		}
		else{
			cin>>l>>r;
			cout<<ask(1,l,r).sum_ioi<<endl;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104

P4588 [TJOI2018]数学计算

P4588 [TJOI2018]数学计算
我们可以考虑以时间为下标，维护一个数组，支持单点修改（初始状态， A A A 中全部为 1 1 1），第 i i i 次操作就将 A i A_i Ai​ 的值修改为所乘的值，遇到还原操作，要求还原第 p o s pos pos 个操作，那么我们就将 A p o s A_{pos} Apos​ 的值还原为 1 1 1。由于未执行到的操作都未 1 1 1，对答案不会出现影响，只有已近操作过的位置，才对答案有影响，并且所有要求还原的位置也都为 1 1 1，所以答案就是将数组内所有点的数值全部相乘的值（相当于所有操作过，并且未被还原的位置相乘）模上 M M M，熟悉的区间乘，线段树维护即可。

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r,ans;
} tre[400010];
long long Mod,n,m,t,tot,p_t_p[100010],cb[100010];
void setup(long long i,long long l,long long r)
{
	tre[i].l=l;
	tre[i].r=r;
	if(l==r){
		tre[i].ans=1;
		return;
	}
	long long mid=((l+r)>>1);
	setup(i*2,l,mid);
	setup(i*2+1,mid+1,r);
	tre[i].ans=tre[i*2].ans*tre[i*2+1].ans;
	return;
}
void change(long long i,long long p,long long num)
{
	if(tre[i].l==tre[i].r){
		tre[i].ans=num;
		return;
	}
	if(tre[i*2].r>=p)
		change(i*2,p,num);
	else
		change(i*2+1,p,num);
	tre[i].ans=tre[i*2].ans*tre[i*2+1].ans%Mod;
	return;
}
void change_back(long long i,long long p)
{
	if(tre[i].l==tre[i].r){
		tre[i].ans=1;
		return;
	}
	if(tre[i*2].r>=p)
		change_back(i*2,p);
	else
		change_back(i*2+1,p);
	tre[i].ans=tre[i*2].ans*tre[i*2+1].ans%Mod;
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	for(int i=1;i<=t;i++){
		memset(tre,0,sizeof(tre));
		cin>>n>>Mod;
		setup(1,1,n);
		for(int j=1;j<=n;j++){
			long long q,p;
			cin>>q>>p;
			if(q==1){
				change(1,j,p);
				cout<<tre[1].ans<<endl;
			}
			else{
				change_back(1,p);
				cout<<tre[1].ans<<endl;
			}
		}
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

吉老师线段树

此算法来自于区间最值操作与历史最值问题——吉如一（第六篇）
我们可以借助下面这道例题进行学习

例题：P6242 【模板】线段树 3

P6242 【模板】线段树 3
简单来讲，就是让我们进行如下操作：

  • 1 l r k：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，将 A i A_i Ai​ 加上 k k k（ k k k 可以为负数） 区间加
  • 2 l r v：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，将 A i A_i Ai​ 变成 min ⁡ ( A i , v ) \min(A_i,v) min(Ai​,v) 区间取 min ⁡ \min min
  • 3 l r：求 ∑ i = l r A i \sum\limits_{i=l}^{r}A_i i=l∑r​Ai​ 求区间和
  • 4 l r：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，求 A i A_i Ai​ 的最大值 区间求最大值
  • 5 l r：对于所有的 i ∈ [ l , r ] i\in[l,r] i∈[l,r]，求 B i B_i Bi​ 的最大值 求区间历史最大值

其中操作 1 , 3 , 4 1,3,4 1,3,4 对于我们已经是老朋友了，普普通通的线段树就可以搞定了，那怎么做到操作二和五？
先来看操作二：
嗯，也挺熟悉的，仿佛有点像这道题，当时，是给每个区间维护最大值和最小值，然后一直遍历，如果遇到最大值小于等于所要取最小值的数，这个区间便不用改变（直接return），而如果最小值大于等于所要取最小值，就是直接将整个区间进行覆盖。我试着做了一下，太麻烦了主要是都调不对，然后仔细思考并参考了亿下题解，发现可以简单很多，因为这一题不用维护最小值，只有最大值。
所以当一个区间内取 m i n min min 的时候，只要我们将区间分得足够小，就只有两种情况：1.全部不变（区间内最大值小于等于 v v v）；2.只有最大值改变（区间内最大值大于等于 v v v 并且严格次大值小于 v v v）。第一种情况是不用管的，而对于第二种情况，如果我们将每个区间内的数字分为两组，一组为最大值（可能重复），其他的数字就分为另一组（每组对应自己的懒惰标记），就不再需要覆盖操作，只需改变最大值的懒惰标记，将他们都减成需要改变为的数就好了（如将 5 , 5 , 2 5,5,2 5,5,2 覆盖为 3 , 3 , 2 3,3,2 3,3,2 就相当于是将整个区间内所有的最大值都加上一个 − 2 -2 −2）
所以我们只需维护两个懒惰标记，维护一个最大值，并维护最大值个数，再维护一个严格次大值，就可以实现操作二。

再来看操作五：
按照题目本意，就是让我们再另外建一棵树。那如果这样该怎么办？我们可以参考上面的建树方法。但是，再更新的过程中，就需要一些改变。那么假设（注：1. 原 原 原 表示还未改动的;2.下面括号内的东西不一定需要理解，下面有解释）：

  • h i s t o r y _ m a x _ l a z history\_max\_laz history_max_laz 为当前区间内最大值的历史懒惰标记（ 原 n o w _ m a x + 父 节 点 h i s t o r y _ m a x _ l a z = 本 次 更 新 后 的 h i s t o r y _ m a x 原now\_max+父节点history\_max\_laz=本次更新后的history\_max 原now_max+父节点history_max_laz=本次更新后的history_max，且 原 n o w _ m a x _ l a z + 父 节 点 h i s t o r y _ m a x _ l a z = 本 次 更 新 后 的 h i s t o r t _ m a x _ l a z 原now\_max\_laz+父节点history\_max\_laz=本次更新后的histort\_max\_laz 原now_max_laz+父节点history_max_laz=本次更新后的histort_max_laz），
  • h i s t o r y _ u n m a x _ l a z history\_unmax\_laz history_unmax_laz 当前区间内非最大值的历史懒惰标记（ 原 n o w _ u n m a x _ l a z + 父 节 点 h i s t o r y _ u n m a x _ l a z = 本 次 更 新 后 的 h i s t o r y _ u n m a x _ l a z 原now\_unmax\_laz+父节点history\_unmax\_laz=本次更新后的history\_unmax\_laz 原now_unmax_laz+父节点history_unmax_laz=本次更新后的history_unmax_laz ，若父节点的最大值不在该子树内，则 原 n o w _ m a x + 父 节 点 h i s t o r y _ u n m a x _ l a z = 本 次 更 新 后 的 h i s t o r y _ m a x 原now\_max+父节点history\_unmax\_laz=本次更新后的history\_max 原now_max+父节点history_unmax_laz=本次更新后的history_max 且 原 n o w _ m a x _ l a z + 父 节 点 h i s t o r y _ u n m a x _ l a z = 本 次 更 新 后 的 h i s t o r y _ m a x _ l a z 原now\_max\_laz+父节点history\_unmax\_laz=本次更新后的history\_max\_laz 原now_max_laz+父节点history_unmax_laz=本次更新后的history_max_laz），
  • h i s t o r y _ m a x history\_max history_max 为区间内历史出现过的最大值，
  • n o w _ m a x _ l a z now\_max\_laz now_max_laz 为当前区间最大值的懒惰标记，
  • n o w _ u n m a x _ l a z now\_unmax\_laz now_unmax_laz 为当前区间非最大值的懒惰标记，
  • n o w _ m a x now\_max now_max 为当前区间内的最大值，
  • n u m _ o f _ n o w _ m a x num\_of\_now\_max num_of_now_max 为当前区间内最大值的数量，
  • n o w _ m a x _ a d d now\_max\_add now_max_add 为当前区间最大值需要加的数字，
  • n o w _ u n m a x _ a d d now\_unmax\_add now_unmax_add 为当前区间非最大值需要加的数字，
  • h i s t o r y _ m a x _ a d d history\_max\_add history_max_add 为区间内历史最大值所需要加的数字，

更新操作如下：

void update(long long i,long long now_max_add,long long history_max_add,long long now
_unmax_add,long long history_unmax_add)//更新函数
{
	tre[i].sum=(long long)tre[i].sum+now_max_add*tre[i].num_of_now_max+now_unmax_add*(tre[i].r-tre[i].l+1-tre[i].num_of_now_max);//更新和，原来的+最大值的变化+非最大值的变化
	tre[i].history_max=max(tre[i].history_max,tre[i].now_max+history_max_add);//更新区间内历史最大值，注意：此处的now_max未修改
	tre[i].history_max_laz=max(tre[i].history_max_laz,tre[i].now_max_laz+history_max_add);//更新区间内历史最大值的懒惰标记，与当前区间懒惰标记的更新不同，是因为此处所取的是历史最大值，只要是所有出现过的数值中最大的，所以如果当前更新会让数字更小，就可以选择不去进行更新（典型的贪心）
	tre[i].history_unmax_laz=max(tre[i].history_unmax_laz,tre[i].now_unmax_laz+history_unmax_add);//理由同上，至于为什么不需要一起进行更新，是因为一个区间内的历史最大值，不一定要一起进行改动。比如可能是在这一次出现了当前区间内最大值的历史最大值，但又是在下一次出现了当前区间内非最大值的历史最大值，若让两者同时更新，就不能满足所有位置都是历史出现过的至中最大的值了
	tre[i].now_max+=now_max_add;//懒惰标记常规更新
	tre[i].now_max_laz+=now_max_add;//懒惰标记常规更新
	if(tre[i].second_now_max!=(long long)-1000000000)//-1000000000是在建树过程中为防止一个区间内所有数字都重复（无严格次大值），所设置的极限小值
		tre[i].second_now_max+=now_unmax_add;//若有严格次大值，就进行更新
	tre[i].now_unmax_laz+=now_unmax_add;//懒惰标记常规更新
	return;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

实际上，这样相当于是维护了两棵树，一棵保存当前状态（以 n o w _ now\_ now_ 为开头的），另一棵保存历史状态（以 h i s t o r y _ history\_ history_ 为开头的），但两棵树又有联系：

  1. h i s t o r y history history 树中的所有懒惰标记都是以 n o w now now 树为准的（主要联系），如：
    原 n o w _ m a x + 父 节 点 h i s t o r y _ m a x _ l a z = 本 次 更 新 后 的 h i s t o r y _ m a x 原now\_max+父节点history\_max\_laz=本次更新后的history\_max 原now_max+父节点history_max_laz=本次更新后的history_max
    原 n o w _ m a x _ l a z + 父 节 点 h i s t o r y _ m a x _ l a z = 本 次 更 新 后 的 h i s t o r y _ m a x _ l a z 原now\_max\_laz+父节点history\_max\_laz=本次更新后的history\_max\_laz 原now_max_laz+父节点history_max_laz=本次更新后的history_max_laz
    （以上的“父节点”是因为正在下推）
  2. 两树公用左右起始和终止点（ l , r l,r l,r）

接下来来看 p u s h _ d o w n push\_down push_down 函数：

void push_d(long long i)
{
	long long now_max=max(tre[i*2].now_max,tre[i*2+1].now_max);//注意，不可取 tre[i].now_max，因为当前节点的数据已经更新过，而左右子树还未更新
	if(tre[i*2].now_max==now_max)//分类讨论，如果左子树内有最大值
		update(i*2,tre[i].now_max_laz,tre[i].history_max_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);//如果左子树内有该区间最大值,则左子树的最大值就是该区间的最大值
	else//如果左子树内没有最大值
		update(i*2,tre[i].now_unmax_laz,tre[i].history_unmax_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);//如果左子树内没有该区间最大值,则左子树的最大值就是该区间的非最大值
	if(tre[i*2+1].now_max==now_max)//分类讨论，如果右子树内有最大值
		update(i*2+1,tre[i].now_max_laz,tre[i].history_max_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);//如果右子树内有该区间最大值,则右子树的最大值就是该区间的最大值
	else
		update(i*2+1,tre[i].now_unmax_laz,tre[i].history_unmax_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);//如果右子树内没有该区间最大值,则右子树的最大值就是该区间的非最大值
	//清零懒惰标记
	tre[i].history_max_laz=0;
	tre[i].history_unmax_laz=0;
	tre[i].now_max_laz=0;
	tre[i].now_unmax_laz=0;
	return;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

最后看一下区间合并的操作：

void merge(long long i)
{
	//区间合并常规操作
	tre[i].history_max=max(tre[i*2].history_max,tre[i*2+1].history_max);
	tre[i].now_max=max(tre[i*2].now_max,tre[i*2+1].now_max);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	//更新最大值以及其个数
	if(tre[i*2].now_max==tre[i*2+1].now_max){//分类讨论，若左右子树都有该区间的最大值
		tre[i].second_now_max=max(tre[i*2].second_now_max,tre[i*2+1].second_now_max);//严格次大值就是两子树内严格次大值的最大值
		tre[i].num_of_now_max=tre[i*2].num_of_now_max+tre[i*2+1].num_of_now_max;//左右最大值个数之和
	}
	else if(tre[i*2].now_max>tre[i*2+1].now_max){//分类讨论，若最大值在左子树
		tre[i].second_now_max=max(tre[i*2].second_now_max,tre[i*2+1].now_max);//严格次大值就是左子树严格次大值和右子树最大值中的最大值（因为右子树中的最大值一定小于该区间最大值，并且一定是右子树中所有小于该区间最大值的值中的最大值）
		tre[i].num_of_now_max=tre[i*2].num_of_now_max;//全在左子树
	}
	else{
		tre[i].second_now_max=max(tre[i*2].now_max,tre[i*2+1].second_now_max);//严格次大值就是右子树严格次大值和左子树最大值中的最大值（因为左子树中的最大值一定小于该区间最大值，并且一定是左子树中所有小于该区间最大值的值中的最大值）
		tre[i].num_of_now_max=tre[i*2+1].num_of_now_max;//全在右子树
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

剩下的操作就都是普通线段树中的常规操作了。

完整代码

真的难调

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r,sum,history_max,now_max,second_now_max,num_of_now_max,history_max_laz,history_unmax_laz,now_max_laz,now_unmax_laz;
} tre[2000010];
long long n,m,a[500010];
void merge(long long i)
{
	tre[i].history_max=max(tre[i*2].history_max,tre[i*2+1].history_max);
	tre[i].now_max=max(tre[i*2].now_max,tre[i*2+1].now_max);
	tre[i].sum=tre[i*2].sum+tre[i*2+1].sum;
	if(tre[i*2].now_max==tre[i*2+1].now_max){
		tre[i].second_now_max=max(tre[i*2].second_now_max,tre[i*2+1].second_now_max);
		tre[i].num_of_now_max=tre[i*2].num_of_now_max+tre[i*2+1].num_of_now_max;
	}
	else if(tre[i*2].now_max>tre[i*2+1].now_max){
		tre[i].second_now_max=max(tre[i*2].second_now_max,tre[i*2+1].now_max);
		tre[i].num_of_now_max=tre[i*2].num_of_now_max;
	}
	else{
		tre[i].second_now_max=max(tre[i*2].now_max,tre[i*2+1].second_now_max);
		tre[i].num_of_now_max=tre[i*2+1].num_of_now_max;
	}
}
void update(long long i,long long now_max_add,long long history_max_add,long long now_unmax_add,long long history_unmax_add)
{
	tre[i].sum=(long long)tre[i].sum+now_max_add*tre[i].num_of_now_max+now_unmax_add*(tre[i].r-tre[i].l+1-tre[i].num_of_now_max);
	tre[i].history_max=max(tre[i].history_max,tre[i].now_max+history_max_add);
	tre[i].history_max_laz=max(tre[i].history_max_laz,tre[i].now_max_laz+history_max_add);
	tre[i].history_unmax_laz=max(tre[i].history_unmax_laz,tre[i].now_unmax_laz+history_unmax_add);
	tre[i].now_max+=now_max_add;
	tre[i].now_max_laz+=now_max_add;
	if(tre[i].second_now_max!=(long long)-1000000000)
		tre[i].second_now_max+=now_unmax_add;
	tre[i].now_unmax_laz+=now_unmax_add;
	return;
}
void push_d(long long i)
{
	long long now_max=max(tre[i*2].now_max,tre[i*2+1].now_max);
	if(tre[i*2].now_max==now_max)
		update(i*2,tre[i].now_max_laz,tre[i].history_max_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);
	else
		update(i*2,tre[i].now_unmax_laz,tre[i].history_unmax_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);
	if(tre[i*2+1].now_max==now_max)
		update(i*2+1,tre[i].now_max_laz,tre[i].history_max_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);
	else
		update(i*2+1,tre[i].now_unmax_laz,tre[i].history_unmax_laz,tre[i].now_unmax_laz,tre[i].history_unmax_laz);
	tre[i].history_max_laz=0;
	tre[i].history_unmax_laz=0;
	tre[i].now_max_laz=0;
	tre[i].now_unmax_laz=0;
	return;
}
void setup(long long i,long long l,long long r)
{
	tre[i].l=l;
	tre[i].r=r;
	if(l==r){
		tre[i].sum=a[l];
		tre[i].now_max=a[l];
		tre[i].history_max=a[l];
		tre[i].num_of_now_max=1;
		tre[i].second_now_max=(long long)-1000000000;
		return;
	}
	long long mid=((l+r)>>1);
	setup(i*2,l,mid);
	setup(i*2+1,mid+1,r);
	merge(i);
	return;
}
void change_add(long long i,long long l,long long r,long long num)
{
	if(tre[i].l>=l&&tre[i].r<=r){
		update(i,num,num,num,num);
		return;
	}
	push_d(i);
	if(tre[i*2].r>=l)
		change_add(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		change_add(i*2+1,l,r,num);
	merge(i);
	return;
}
void change_min(long long i,long long l,long long r,long long num)
{
	if(tre[i].now_max<=num)
		return;
	if(tre[i].l>=l&&tre[i].r<=r&&tre[i].second_now_max<num){
		update(i,num-tre[i].now_max,num-tre[i].now_max,0,0);
		return;
	}
	push_d(i);
	if(tre[i*2].r>=l)
		change_min(i*2,l,r,num);
	if(tre[i*2+1].l<=r)
		change_min(i*2+1,l,r,num);
	merge(i);
	return;
}
long long ask_sum(long long i,long long l,long long r)
{
	if(tre[i].l>=l&&tre[i].r<=r)
		return tre[i].sum;
	push_d(i);
	long long value=0;
	if(tre[i*2].r>=l)
		value+=ask_sum(i*2,l,r);
	if(tre[i*2+1].l<=r)
		value+=ask_sum(i*2+1,l,r);
	return value;
}
long long ask_now_max(long long i,long long l,long long r)
{
	if(tre[i].l>=l&&tre[i].r<=r)
		return tre[i].now_max;
	push_d(i);
	long long value=(long long)-1000000000;
	if(tre[i*2].r>=l)
		value=max(value,ask_now_max(i*2,l,r));
	if(tre[i*2+1].l<=r)
		value=max(value,ask_now_max(i*2+1,l,r));
	return value;
}
long long ask_history_max(long long i,long long l,long long r)
{
	if(tre[i].l>=l&&tre[i].r<=r)
		return tre[i].history_max;
	push_d(i);
	long long value=(long long)-1000000000;
	if(tre[i*2].r>=l)
		value=max(value,ask_history_max(i*2,l,r));
	if(tre[i*2+1].l<=r)
		value=max(value,ask_history_max(i*2+1,l,r));
	return value;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	setup(1,1,n);
	for(int i=1;i<=m;i++){
		long long q,l,r,num;
		cin>>q>>l>>r;
		if(q==1){
			cin>>num;
			change_add(1,l,r,num);
		}
		else if(q==2){
			cin>>num;
			change_min(1,l,r,num);
		}
		else if(q==3)
			cout<<ask_sum(1,l,r)<<"\n";
		else if(q==4)
			cout<<ask_now_max(1,l,r)<<"\n";
		else
			cout<<ask_history_max(1,l,r)<<"\n";
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166

可持久化线段树（主席树）

还没学会，正在学

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/140739
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号