LuoguP1253 扶苏的问题

夏佑 | XiaU

线段树。

Sol.

实际上相当于维护一颗线段树,支持区间覆盖、区间加和区间查询最大值。

维护最大值很好办,区间覆盖和区间加我们怎么维护呢?

首先,区间覆盖和区间加一定都分别需要记一个懒标记。我们把区间覆盖的懒标记记为 \(ctag\),区间加的懒标记记为 \(atag\),那么我们如何把标记 \(\text{pushdown}\) 呢?

首先,初始化要选择一个尽量不影响之后操作的值。\(atag\) 显然选择 \(0\) 即可。由于要更改的数字有正有负,\(ctag\) 可以选取 \(-\infty\),在程序中我选用了 \(1e18+7\) 作为 \(\text{INF}\)

考虑到如果我们当前节点有一个 \(atag\) 标记,之后又打上了一个 \(ctag\) 标记,那么要覆盖的值会直接把要加的值覆盖,也就是说 \(ctag\) 会直接清除 \(atag\)。而如果先打上 \(ctag\),再打上 \(atag\),则需要先把 \(ctag\) 下放,再下放 \(atag\)。那么我们的 \(\text{pushdown}\) 可以这么写:

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
void af(int k, int v) //把下放的操作封装一下可以使代码更简洁
{
t[k].maxx += v;
t[k].atag += v;
}

void cf(int k, int v)
{
t[k].maxx = v;
t[k].ctag = v;
}

void cpushdown(int k) //ctag 的下放
{
if(t[k].ctag == -INF) return; //如果没有标记,返回
t[ls].atag = t[rs].atag = 0; //抹除 atag
cf(ls, t[k].ctag), cf(rs, t[k].ctag); //ctag 下放
t[k].ctag = -INF; //当前节点 ctag 清零
}

void apushdown(int k) //atag 的下放
{
if(t[k].atag == 0) return; //如果没有标记,返回
cpushdown(k); //先把 ctag 下放
af(ls, t[k].atag), af(rs, t[k].atag); //atag 下放
t[k].atag = 0; //当前节点 atag 清零
}

void pushdown(int k)
{
cpushdown(k);
apushdown(k);
}
//一次 pushdown 操作包括 ctag 的下放和 atag 的下放,都要进行

那么操作呢?区间加操作和之前一样即可,区间覆盖操作需要清除当前节点的 \(atag\)

其他部分即为普通线段树模板。

Code

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
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 1e6 + 7;
const int INF = 1e18 + 7;

#define ls (k << 1)
#define rs (k << 1 | 1)

inline int read()
{
int s = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * f;
}

struct Tree
{
int maxx;
int l, r;
int atag, ctag;
}t[MAXN << 2];

int a[MAXN];

int n, q;

void pushup(int k)
{
t[k].maxx = max(t[ls].maxx, t[rs].maxx);
}

void af(int k, int v)
{
t[k].maxx += v;
t[k].atag += v;
}

void cf(int k, int v)
{
t[k].maxx = v;
t[k].ctag = v;
}

void cpushdown(int k)
{
if(t[k].ctag == -INF) return;
t[ls].atag = t[rs].atag = 0;
cf(ls, t[k].ctag), cf(rs, t[k].ctag);
t[k].ctag = -INF;
}

void apushdown(int k)
{
if(t[k].atag == 0) return;
cpushdown(k);
af(ls, t[k].atag), af(rs, t[k].atag);
t[k].atag = 0;
}

void pushdown(int k)
{
cpushdown(k);
apushdown(k);
}

void build(int k, int l, int r)
{
t[k].l = l;
t[k].r = r;
t[k].atag = 0;
t[k].ctag = -INF;
if(l == r)
{
t[k].maxx = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(k);
}

void update(int k, int l, int r, int v)
{
if(l <= t[k].l && t[k].r <= r)
{
af(k, v);
return;
}
pushdown(k);
int mid = (t[k].l + t[k].r) >> 1;
if(l <= mid) update(ls, l, r, v);
if(r > mid) update(rs, l, r, v);
pushup(k);
}

void cover(int k, int l, int r, int v)
{
if(l <= t[k].l && t[k].r <= r)
{
t[k].atag = 0;
cf(k, v);
return;
}
pushdown(k);
int mid = (t[k].l + t[k].r) >> 1;
if(l <= mid) cover(ls, l, r, v);
if(r > mid) cover(rs, l, r, v);
pushup(k);
}

int query(int k, int l, int r)
{
int res = -INF;
if(l <= t[k].l && t[k].r <= r) return t[k].maxx;
pushdown(k);
int mid = (t[k].l + t[k].r) >> 1;
if(l <= mid) res = max(res, query(ls, l, r));
if(r > mid) res = max(res, query(rs, l, r));
return res;
}

signed main()
{
n = read(), q = read();
for(int i = 1; i <= n; i++) a[i] = read();
build(1, 1, n);
while(q--)
{
int opt = read();
if(opt == 1)
{
int l = read(), r = read(), x = read();
cover(1, l, r, x);
}
if(opt == 2)
{
int l = read(), r = read(), x = read();
update(1, l, r, x);
}
if(opt == 3)
{
int l = read(), r = read();
printf("%lld\n", query(1, l, r));
}
}
return 0;
}
  • 标题: LuoguP1253 扶苏的问题
  • 作者: 夏佑 | XiaU
  • 创建于 : 2022-09-01 00:00:00
  • 更新于 : 2023-09-15 09:13:32
  • 链接: https://summace.cc/LGP1253/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
此页目录
LuoguP1253 扶苏的问题