奇奇怪怪的线段树1(子段和+最长连续)

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

$\rm{Task1} $子段和

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

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

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

$\color{violet}{Link}$

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

那么转移($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
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <iostream>
#define MAXN 200010
#define LL long long
#define max my_Fuckmax
#define ls(rt) rt << 1
#define rs(rt) rt << 1 | 1
#define mid ((l + r) >> 1)

using namespace std ;
struct Tree{
LL S, Sum, Lsum, Rsum ;
}T[MAXN << 1] ; int N, M, L, R, base[MAXN] ;

#define S(x) T[x].S
#define Sum(x) T[x].Sum
#define Lsum(x) T[x].Lsum
#define Rsum(x) T[x].Rsum


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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <iostream>
#define MAXN 200010
#define LL long long
#define max my_Fuckmax
#define ls(rt) rt << 1
#define rs(rt) rt << 1 | 1
#define mid ((l + r) >> 1)

using namespace std ;
bool MArk ;
struct Tree{
LL S, Sum, Lsum, Rsum ;
}T[MAXN << 1] ; int N, M, L, R, base[MAXN] ;

#define S(x) T[x].S
#define Sum(x) T[x].Sum
#define Lsum(x) T[x].Lsum
#define Rsum(x) T[x].Rsum


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$,所以说我们直接暴力除就好了,聚合分析一下,复杂度的上界似乎是$\Omega(7n)$的样子,无非就是多几个常数。

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 ;
}

$\rm{Task2}$ 最长连续问题

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

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

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

$\color{violet}{Link}$

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

  • 区间置$0$
  • 区间置$1$
  • 询问是否有一段长度为$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
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$
  • 区间全部取非
  • 区间查询$1$的个数
  • 区间查询最长连续的$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$

艹完这个题是真的爽啊~

$Task3~$ 总结一下

其实这东西和$DP$是一样的吧?你只需要确定你想要维护什么(等价于确定状态),然后明确父子区间如何向上维护(等价于状态之间如何转移)。

嗯,万物相同。

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

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

$\mathscr{The~End}$