【探究向】一类线段树的转移

奇奇怪怪的线段树散发着奇奇怪怪的香气(

最近大概是泛做了线段树相关题目,但是这些线段树大概都需要比较强的思维和比较长的代码……$2333$

子段和

其实这个算是比较简单的了,毕竟 $qyf$ 曾经给我们讲过,当时我就觉得十分的……麻烦233.

那么例题其实就是 $\rm{SPOJ}$ 的 $GSS$ 系列——的前三道题(后几道题都不会做)

GSS1​ 区间求最大子段和(不带修)

应该算是比较简单的了。我们对于每个区间维护一个区间和,维护一个从最左端开始且必须包含最左端元素的最大子段和,再维护一个从最右端开始且必须包含最右端元素的最大子段和,最后维护一个区间最大子段和

那么转移(push_up)时就显得十分方便。我们的父区间的 Lmax 只取决于左子区间的 Lmax当左区间的 Sum 等于 Max 时(即左区间全部都要纳入到其最大子段和中时),左区间的 Sum 与右区间的 Lmax 的和。那么对于区间的 Rsum,也是一个道理。最终对于该区间的最大子段和,我们不考虑从已经转移来的 Lmax/Rmax,而是考虑从左右区间的 Max 以及左右区间的和来转移。大体代码:

1
2
3
4
5
6
inline void P_u(int rt){
S(rt) = S(ls(rt)) + S(rs(rt)) ;
Lsum(rt) = max(Lsum(ls(rt)), S(ls(rt)) + Lsum(rs(rt))) ;
Rsum(rt) = max(Rsum(rs(rt)), S(rs(rt)) + Rsum(ls(rt))) ;
Sum(rt) = max(max(Sum(ls(rt)), Sum(rs(rt))), Lsum(rs(rt)) + Rsum(ls(rt))) ;
}

还有值得注意的一点:在询问的时候,它比较膈应…就是由于是连续的,所以你不能直接像普通的线段树一样询问然后加起来…所以所就要类似于边询问,边 push_up​ 这种感觉。

1
2
3
4
5
6
7
8
9
10
11

Tree query(int rt, int l, int r){
if (L <= l && r <= R) return T[rt] ;
Tree res, A, B ;
if (mid >= R) return query(ls(rt), l, mid) ;
if (mid < L) return query(rs(rt), mid + 1, r) ;
A = query(ls(rt), l, mid), B = query(rs(rt), mid + 1, r) ;
res.Lsum = max(A.Lsum, A.S + B.Lsum) ; res.Rsum = max(B.Rsum, B.S + A.Rsum) ;
res.Sum = max(max(A.Sum, B.Sum), A.Rsum + B.Lsum) ; res.S = A.S + B.S ;
return res ;
}

然后总代码:

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
inline LL my_Fuckmax(LL A, LL B){
return A & ((B - A) >> 63) | B & ((~(B - A)) >> 63) ;
}
inline void P_u(int rt){
S(rt) = S(ls(rt)) + S(rs(rt)) ;
Lsum(rt) = max(Lsum(ls(rt)), S(ls(rt)) + Lsum(rs(rt))) ;
Rsum(rt) = max(Rsum(rs(rt)), S(rs(rt)) + Rsum(ls(rt))) ;
Sum(rt) = max(max(Sum(ls(rt)), Sum(rs(rt))), Lsum(rs(rt)) + Rsum(ls(rt))) ;
}
inline void build(int rt, int l, int r){
if (l == r){
T[rt].Lsum = T[rt].Rsum =
T[rt].S = T[rt].Sum = base[l] ; return ;
} build(ls(rt), l, mid), build(rs(rt), mid + 1, r), P_u(rt) ;
}
Tree query(int rt, int l, int r){
if (L <= l && r <= R)
return T[rt] ;
Tree res, A, B ;
if (mid >= R) return query(ls(rt), l, mid) ;
if (mid < L) return query(rs(rt), mid + 1, r) ;
A = query(ls(rt), l, mid), B = query(rs(rt), mid + 1, r) ;
res.Lsum = max(A.Lsum, A.S + B.Lsum) ; res.Rsum = max(B.Rsum, B.S + A.Rsum) ;
res.Sum = max(max(A.Sum, B.Sum), A.Rsum + B.Lsum) ; res.S = A.S + B.S ; return res ;
}
int main(){
cin >> N ; register int i ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ; build(1, 1, N) ; cin >> M ;
while (M --) scanf("%d%d", &L, &R), printf("%lld\n", query(1, 1, N).Sum) ; return 0 ;
}

GSS3 区间求最大子段和(带修)

$\color{violet}{Link}$

…其实吧,这个带修不带修……好像影响并不大?

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
inline LL my_Fuckmax(LL A, LL B){
return A & ((B - A) >> 63) | B & ((~(B - A)) >> 63) ;
}
inline void P_u(int rt){
S(rt) = S(ls(rt)) + S(rs(rt)) ;
Lsum(rt) = max(Lsum(ls(rt)), S(ls(rt)) + Lsum(rs(rt))) ;
Rsum(rt) = max(Rsum(rs(rt)), S(rs(rt)) + Rsum(ls(rt))) ;
Sum(rt) = max(max(Sum(ls(rt)), Sum(rs(rt))), Lsum(rs(rt)) + Rsum(ls(rt))) ;
}
inline void build(int rt, int l, int r){
if (l == r){
T[rt].Lsum = T[rt].Rsum =
T[rt].S = T[rt].Sum = base[l] ; return ;
} build(ls(rt), l, mid), build(rs(rt), mid + 1, r), P_u(rt) ;
}
Tree query(int rt, int l, int r){
if (L <= l && r <= R)
return T[rt] ;
Tree res, A, B ;
if (mid >= R) return query(ls(rt), l, mid) ;
if (mid < L) return query(rs(rt), mid + 1, r) ;
A = query(ls(rt), l, mid), B = query(rs(rt), mid + 1, r) ;
res.Lsum = max(A.Lsum, A.S + B.Lsum) ; res.Rsum = max(B.Rsum, B.S + A.Rsum) ;
res.Sum = max(max(A.Sum, B.Sum), A.Rsum + B.Lsum) ; res.S = A.S + B.S ; return res ;
}
inline void change(int rt, int l, int r, int k){
if (L == l && L == r){
T[rt].Sum = T[rt].Lsum = T[rt].Rsum = T[rt].S = k ; return ;
}
if (L <= mid) change(ls(rt), l, mid, k) ;
else change(rs(rt), mid + 1, r, k ) ; P_u(rt) ;
}
int main(){
cin >> N ; register int i ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ; build(1, 1, N) ; cin >> M ;
while (M --) {
scanf("%d%d%d", &MArk, &L, &R) ;
if (!MArk) change(1, 1, N, R) ;
else printf("%lld\n", query(1, 1, N).Sum) ;
}
}

GSS4 区间开根问题

$\color{violet}{Link}$

这个和子段和一点儿关系都没有,顺便整一下233.

就是让你区间开根(向下取整)+查询……这个东西大概就是对于一个 $2^{63}$ 内的数值$N$,我们假设其开根 $k$ 次可以得到 $N < 2$ —— 只要 $N < 2$ ,之后的计算就会集中在一个紧确的范围 $(1,2)$ 内,向下取整之后永远都会是$1$,所以我们不需要再去考虑。

那么现在问题就在于 $k$ 的大小。首先,$\sqrt n$ 在 $[0,+\infty]$ 是单调递增的,同理三次方根也是,四次方根也是…所以我们不妨取最大值,考虑 $N=2^{63}$ 时,$k$ 值的大小。而很显然,此时的 $k$ 应该为 $\log _263+1 ≈ 6.978$ 。

总之,我们得出,似乎运算次数的上界就是 $k≈7$,所以说我们直接暴力除就好了,聚合分析一下,复杂度的上界似乎是 $O(n)$ 的样子,无非就是多几个常数。

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
ll N, M, K, i, L, R ; 
ll base[MAXN], T[MAXN], tot ;

inline void p_u(ll rt){ ;}
void _Build(ll rt, ll l, ll r){
if (l == r){T[rt] = base[l] ; return ;}
_Build(ls(rt), l, mid) ;
_Build(rs(rt), mid + 1, r) ;
T[rt] = T[ls(rt)] + T[rs(rt)] ;
}
inline ll _query(ll rt, ll l, ll r, ll sl, ll sr){
if (l >= sl && r <= sr) return T[rt] ;
ll ret = 0 ;
if (mid >= sl) ret += _query(ls(rt), l, mid, sl, sr) ;
if (mid < sr) ret += _query(rs(rt), mid + 1, r, sl, sr) ;
return ret ;
}
inline void _Sqrt(ll rt, ll l, ll r, ll sl, ll sr){
if (l >= sl && r <= sr){
if (T[rt] <= (r - l + 1)) return ;
else {
if (l == r){
T[rt] = (int)(pow((double)T[rt], 0.5)) ;
return ;
}
}
}
if (mid >= sl) _Sqrt(ls(rt), l, mid, sl, sr),
T[rt] = T[ls(rt)] + T[rs(rt)] ;
if (mid < sr) _Sqrt(rs(rt), mid + 1, r, sl, sr),
T[rt] = T[ls(rt)] + T[rs(rt)] ;
}
int main(){
while(cin >> N){
++ tot, printf("Case #%d:\n", tot) ;
for (i = 1; i <= N ; ++ i) base[i] = qr() ;
_Build(1, 1, N) ; cin >> M ;
for (i = 1; i <= M ; ++ i){
K = qr(), L = qr(), R = qr() ;
if (L > R) swap(L, R) ;
if (K){
printf("%lld\n", _query(1, 1, N, L, R)) ;
continue ;
}
_Sqrt(1, 1, N, L, R) ;
}
printf("\n") ;
}
return 0 ;
}

最长连续问题

这个东西其实应该跟最大子段和差不多——要求的都是连续的东西。对于所有包括连续字样的东西,基本的思路大概都是维护一个从左端开始的,维护一个从右端开始的,然后从下向上不断 push_up 即可。

emmm​ 在这边整理几道思路不错的题吧:

$\rm{USACO}$ 酒店($hotel$)

$\color{violet}{Link}$

初始的一个全零的序列,我们对它准确来说有以下三个操作:

  • 1、区间置 $0$ 。
  • 2、区间置 $1$ 。
  • 3、询问是否有一段长度为 $k$ 的连续的零区间,如果有的话,选取最靠左的,输出其左端点并执行操作②

这个题在我看来,应该算是一个思维题。对于最后一个操作,我十分地懵逼——因为我压根不知道该怎么维护。

但事实上…这就是学数据结构学傻了的后果…毕竟数据结构只会是一个辅助而已。仔细想来,好像除了权值线段树能够维 护$\rm{DP}$之外,没做过什么数据结构的好题,都是一些数据结构的裸题……大概这就是学傻了吧,只会专一的一门学科,或者说只会专精一种东西——还是十分蠢笨迟钝地“专精”。

唉,大概检验一个人学没学过数据结构,不是通过他会不会做类似于 $NOI2005$ 维护数列那样的毒瘤裸题,而是看他到底可不可以和其他的东西结合在一起。学习大抵也是同样的道理,不可以把学的东西迁移到其他地方,照样是白学吧。

诶,好像扯了什么奇怪的东西……

回到正题,我们不考虑直接维护这个东西,而是通过维护区间内的最长连续 $0$ 的个数,达到辅助查找区间的目的。那么我们查找区间的时候,就直接选择最左边的区间优先,并 $check$ 其是否有足够的 $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

struct Tree{
int Sum, Len, Lsum, Rsum, tag ;
}T[MAXN << 1] ; int A, B, N, M, MArk, i, t ;

inline void push_down(int rt){
if (T[rt].tag == -1) return ;
else if (T[rt].tag == 0){
T[ls(rt)].tag = T[rs(rt)].tag = 0 ;
T[ls(rt)].Lsum = T[ls(rt)].Sum = T[ls(rt)].Rsum = 0 ;
T[rs(rt)].Lsum = T[rs(rt)].Sum = T[rs(rt)].Rsum = 0 ;
}
else{
T[ls(rt)].tag = T[rs(rt)].tag = 1 ;
T[ls(rt)].Lsum = T[ls(rt)].Sum = T[ls(rt)].Rsum = T[ls(rt)].Len ;
T[rs(rt)].Lsum = T[rs(rt)].Sum = T[rs(rt)].Rsum = T[rs(rt)].Len ;
}
T[rt].tag = -1 ;
}
inline void push_up(int rt){
if (T[ls(rt)].Sum == T[ls(rt)].Len)
T[rt].Lsum = T[ls(rt)].Len + T[rs(rt)].Lsum ;
else T[rt].Lsum = T[ls(rt)].Lsum ;
if (T[rs(rt)].Sum == T[rs(rt)].Len)
T[rt].Rsum = T[rs(rt)].Len + T[ls(rt)].Rsum ;
else T[rt].Rsum = T[rs(rt)].Rsum ;
T[rt].Sum = max(T[ls(rt)].Sum, T[rs(rt)].Sum),
T[rt].Sum = max(T[rt].Sum, T[ls(rt)].Rsum + T[rs(rt)].Lsum) ;
}
void build(int rt, int l, int r){
T[rt].tag = -1,
T[rt].Len = T[rt].Lsum =
T[rt].Rsum = T[rt].Sum = r - l + 1 ;
if (l == r){ return ; }
build(ls(rt), l, mid), build(rs(rt), mid + 1, r) ;
}
void update(int rt, int l, int r, int ul, int ur, int k){
if (ul <= l && ur >= r){
T[rt].tag = k ;
if (k == 0) T[rt].Lsum = T[rt].Rsum = T[rt].Sum = 0 ;
else T[rt].Lsum = T[rt].Rsum = T[rt].Sum = T[rt].Len ;
return ;
}
push_down(rt) ;
if (ul <= mid) update(ls(rt), l, mid, ul, ur, k) ;
if (ur > mid) update(rs(rt), mid + 1, r, ul, ur, k) ;
push_up(rt) ;
}
int query(int rt, int l, int r){
push_down(rt) ;
if (l == r) return l ;
if (T[ls(rt)].Sum >= A) return query(ls(rt), l, mid) ;
else if (T[ls(rt)].Rsum + T[rs(rt)].Lsum >= A) return mid - T[ls(rt)].Rsum + 1 ;
return query(rs(rt), mid + 1, r) ;
}
int main(){
cin >> N >> M ;
build(1, 1, N) ;
while(M --){
scanf("%d", &MArk) ;
if (MArk == 2) scanf("%d%d", &A, &B), update(1, 1, N, A, A + B - 1, 1) ;
else {
scanf("%d", &A) ;
if (T[1].Sum >= A)
printf("%d\n", t = query(1, 1, N)), update(1, 1, N, t, t + A - 1, 0) ;
else
putchar('0'), putchar('\n') ;
}
} return 0 ;
}

$emmm$这个题码量其实不大,思维含量也不高,但是成功地把做数据结构题做傻了的我拉回了正途。

$\rm{SCOI}$ 序列操作

$\color{violet}{Link}$

对于一个$01$序列,大体是这几种操作:

  • 1、区间清零 。
  • 2、区间置为$1$ 。
  • 3、区间全部取反。
  • 4、区间查询$1$的个数。
  • 5、区间查询最长连续的$1$的长度。

好的,这道题被我秒了,爽啊…不过秒是秒了,对拍调,调了好久$233$。

其实对于 $1,2,4,5$ 都好说,只是第$3$个操作,需要再另维护区间最长连续的 $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
struct Tree{
int OS, OL, OR ;
int Sum, Lsum, Len, Rsum, S, tag, t ;
//tag = 1 -> 1,tag = 0 -> 0, tag = 2 -> xor
}T[MAX << 1] ; int N, M, MArk, L, R, base[MAX], i ;

inline void up(int rt){//
T[rt].S = T[ls(rt)].S + T[rs(rt)].S ;
//1
if (T[ls(rt)].S == T[ls(rt)].Len)
T[rt].Lsum = max(T[ls(rt)].Lsum, T[ls(rt)].Len + T[rs(rt)].Lsum) ;
else T[rt].Lsum = T[ls(rt)].Lsum ;
if (T[rs(rt)].S == T[rs(rt)].Len)
T[rt].Rsum = max(T[rs(rt)].Rsum, T[rs(rt)].Len + T[ls(rt)].Rsum) ;
else T[rt].Rsum = T[rs(rt)].Rsum ;
T[rt].Sum = max(T[ls(rt)].Rsum + T[rs(rt)].Lsum, max(T[ls(rt)].Sum, T[rs(rt)].Sum)) ;
//0
if (!T[ls(rt)].S)
T[rt].OL = max(T[ls(rt)].OL, T[ls(rt)].Len + T[rs(rt)].OL) ;
else T[rt].OL = T[ls(rt)].OL ;
if (!T[rs(rt)].S)
T[rt].OR = max(T[rs(rt)].OR, T[rs(rt)].Len + T[ls(rt)].OR) ;
else T[rt].OR = T[rs(rt)].OR ;
T[rt].OS = max(T[ls(rt)].OR + T[rs(rt)].OL, max(T[ls(rt)].OS, T[rs(rt)].OS)) ;
}
inline void down(int rt){//
if (T[rt].tag == -1) return ;
if (T[rt].t == 1){
T[ls(rt)].tag ^= 1, T[rs(rt)].tag ^= 1 ;
T[ls(rt)].S = T[ls(rt)].Len - T[ls(rt)].S ;
T[rs(rt)].S = T[rs(rt)].Len - T[rs(rt)].S ;
//l
T[ls(rt)].Sum ^= T[ls(rt)].OS ^= T[ls(rt)].Sum ^= T[ls(rt)].OS ;
T[ls(rt)].Lsum ^= T[ls(rt)].OL ^= T[ls(rt)].Lsum ^= T[ls(rt)].OL ;
T[ls(rt)].Rsum ^= T[ls(rt)].OR ^= T[ls(rt)].Rsum ^= T[ls(rt)].OR ;
//r
T[rs(rt)].Sum ^= T[rs(rt)].OS ^= T[rs(rt)].Sum ^= T[rs(rt)].OS ;
T[rs(rt)].Lsum ^= T[rs(rt)].OL ^= T[rs(rt)].Lsum ^= T[rs(rt)].OL ;
T[rs(rt)].Rsum ^= T[rs(rt)].OR ^= T[rs(rt)].Rsum ^= T[rs(rt)].OR ;
}
if (T[rt].tag == 0){
T[ls(rt)].tag = T[rs(rt)].tag = 0 ;
T[ls(rt)].OL = T[ls(rt)].OR = T[ls(rt)].OS = T[ls(rt)].Len ;
T[rs(rt)].OL = T[rs(rt)].OR = T[rs(rt)].OS = T[rs(rt)].Len ;
T[ls(rt)].Lsum = T[ls(rt)].Rsum = T[ls(rt)].Sum = T[ls(rt)].S = 0 ;
T[rs(rt)].Lsum = T[rs(rt)].Rsum = T[rs(rt)].Sum = T[rs(rt)].S = 0 ;
}
if (T[rt].tag == 1){
T[ls(rt)].tag = T[rs(rt)].tag = 1 ;
T[ls(rt)].OL = T[ls(rt)].OR = T[ls(rt)].OS = 0 ;
T[rs(rt)].OL = T[rs(rt)].OR = T[rs(rt)].OS = 0 ;
T[ls(rt)].Lsum = T[ls(rt)].Rsum = T[ls(rt)].Sum = T[ls(rt)].S = T[ls(rt)].Len ;
T[rs(rt)].Lsum = T[rs(rt)].Rsum = T[rs(rt)].Sum = T[rs(rt)].S = T[rs(rt)].Len ;
}
T[rt].tag = -1, T[rt].t = 0 ;
}
void _change(int rt, int l, int r, int k){//
if (L <= l && r <= R){
T[rt].tag = k ;
if (!k)
T[rt].OL = T[rt].OR = T[rt].OS = T[rt].Len,
T[rt].Lsum = T[rt].Rsum = T[rt].Sum = T[rt].S = 0 ;
else T[rt].OL = T[rt].OR = T[rt].OS = 0,
T[rt].Lsum = T[rt].Rsum = T[rt].Sum = T[rt].S = T[rt].Len ;
return ;
}
down(rt) ;
if (L <= mid) _change(ls(rt), l, mid, k) ;
if (R > mid) _change(rs(rt), mid + 1, r, k) ;
up(rt) ;
}
void _reverse(int rt, int l, int r){//
if (L <= l && r <= R){
T[rt].t = 1 ;
T[rt].Sum ^= T[rt].OS ^= T[rt].Sum ^= T[rt].OS ;
T[rt].Lsum ^= T[rt].OL ^= T[rt].Lsum ^= T[rt].OL ;
T[rt].Rsum ^= T[rt].OR ^= T[rt].Rsum ^= T[rt].OR ;
return ;
}
down(rt) ;
if (L <= mid) _reverse(ls(rt), l, mid) ;
if (R > mid) _reverse(rs(rt), mid + 1, r) ;
up(rt) ;
}
inline int Sum(int rt, int l, int r){//
if (L <= l && R >= r) return T[rt].S ;
down(rt) ; int res = 0 ;
if (L <= mid) res += Sum(ls(rt), l, mid) ;
if (R > mid) res += Sum(rs(rt), mid + 1, r) ;
return res ;
}
inline void build(int rt, int l, int r){//
T[rt].tag = -1 ;
T[rt].Len = r - l + 1 ;
if (l == r){
if (!base[l]) T[rt].OL = T[rt].OR = T[rt].OS = 1 ;
else T[rt].Sum = T[rt].Lsum = T[rt].Rsum = T[rt].S = 1 ;
return ;
}
build(ls(rt), l, mid), build(rs(rt), mid + 1, r), up(rt) ;
}
inline Tree query(int rt, int l, int r){
if (L <= l && R >= r) return T[rt] ;
Tree res, A, B ;
if (mid >= R) return query(ls(rt), l, mid) ;
if (mid < L) return query(rs(rt), mid + 1, r) ;
A = query(ls(rt), l, mid), B = query(rs(rt), mid + 1, r) ;
res.Lsum = max(A.Lsum, A.S + B.Lsum) ; res.Rsum = max(B.Rsum, B.S + A.Rsum) ;
res.Sum = max(max(A.Sum, B.Sum), A.Rsum + B.Lsum) ; res.S = A.S + B.S ;
return res ;
}
int main(){
cin >> N >> M ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
build(1, 1, N) ;
while (M --){
// cout << M << " " << "qwerweafasdfsdf" << endl ;
scanf("%d%d%d", &MArk, &L, &R),
++ L, ++ R ;
if (MArk == 0) _change(1, 1, N, 0) ;
else if (MArk == 1) _change(1, 1, N, 1) ;
else if (MArk == 2) _reverse(1, 1, N) ;
else if (MArk == 3) printf("%d\n", Sum(1, 1, N)) ;
else printf("%d", query(1, 1, N).Sum), putchar('\n') ;
// cout << " qwerweafasdfsdf " << endl ;
}
}

push_up 真长啊 $233$ 。

艹完这个题是真的爽啊~

总结一下

其实这东西和 $DP$ 某种程度上有共通之处。你只需要确定你想要维护什么(等价于确定状态),然后明确父子区间如何向上维护(等价于状态之间如何转移)。

嗯,万物相同。

野马也,尘埃也,生物之以息向吹也。天之苍苍,其正色耶?其远而无所至极耶?

不知为什么,突然想到了这句话。

$\mathscr{The~End}$