最近大概是泛做了线段树相关题目，但是这些线段树大概都需要比较强的思维和比较长的代码……(2333)
$ m{Task1} $子段和
其实这个算是比较简单的了，毕竟(qyf)曾经给我们讲过，当时我就觉得十分的……麻烦233.
那么例题其实就是(
m{SPOJ})的(GSS)系列——的前三道题(后几道题都不会做)
(GSS1)区间求最大子段和(不带修)
(2333)应该算是比较简单的了，我们对于每个区间维护一个区间和，维护一个从最左端开始且必须包含最左端元素的最大子段和，再维护一个从最右端开始且必须包含最右端元素的最大子段和，最后维护一个区间最大子段和。
那么转移((push\_up))时就显得十分方便。我们的父区间的(Lmax)只取决于左子区间的(Lmax)和当左区间的(Sum)等于(Max)时（即左区间全部都要纳入到其最大子段和中时），左区间的(Sum)与右区间的(Lmax)的和。那么对于区间的(Rsum)，也是一个道理。最终对于该区间的最大子段和，我们不考虑从已经转移来的(Lmax/Rmax)，而是考虑从左右区间的(Max)以及左右区间的和来转移。大体代码：
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)这种感觉。
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 ;
}
然后总代码：
#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
", query(1, 1, N).Sum) ; return 0 ;
}
(GSS3)区间求最大子段和(带修)
……其实吧，这个带修不带修……好像影响并不大？
#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
", query(1, 1, N).Sum) ;
}
}
(GSS4)区间开根问题
这个和子段和一点儿关系都没有，顺便整一下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))的样子，无非就是多几个常数。
#include <cmath>
#include <cstdio>
#include <iostream>
#define MAXN 500010
#define ll long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std ;
ll N, M, K, i, L, R ;
ll base[MAXN], T[MAXN], tot ;
inline ll qr(){
ll k = 0 ; char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) k = k * 10 + c - 48, c = getchar() ;
return k ;
}
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:
", 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
", _query(1, 1, N, L, R)) ;
continue ;
}
_Sqrt(1, 1, N, L, R) ;
}
printf("
") ;
}
return 0 ;
}
( m{Task2}) 最长连续问题
这个东西其实应该跟最大子段和差不多——要求的都是连续的东西。对于所有包括连续字样的东西，基本的思路大概都是维护一个从左端开始的，维护一个从右端开始的，然后从下向上不断(push_up)即可。
(emmm)在这边整理几道思路不错的题吧：
( m{USACO}) 酒店((hotel))
初始的一个全零的序列，我们对它准确来说有以下三个操作：
- 区间置(0)
- 区间置(1)
- 询问是否有一段长度为(k)的连续的零区间，如果有的话，选取最靠左的，输出其左端点并执行操作②
这个题在我看来，应该算是一个思维题。对于最后一个操作，我十分地懵逼——因为我压根不知道该怎么维护。
但事实上……这就是学数据结构学傻了的后果……毕竟数据结构只会是一个辅助而已。仔细想来，好像除了权值线段树能够维护( m{DP})之外，没做过什么数据结构的好题，都是一些数据结构的裸题……大概这就是学傻了吧，只会专一的一门学科，或者说只会专精一种东西——还是十分蠢笨迟钝地“专精”。
唉，大概检验一个人学没学过数据结构，不是通过他会不会做类似于(NOI2005)维护数列那样的毒瘤裸题，而是看他到底可不可以和其他的东西结合在一起。学习大抵也是同样的道理，不可以把学的东西迁移到其他地方，照样是白学吧。
诶，好像扯了什么奇怪的东西……
回到正题，我们不考虑直接维护这个东西，而是通过维护区间内的最长连续(0)的个数，达到辅助查找区间的目的。那么我们查找区间的时候，就直接**择最左边的区间优先，并(check)其是否有足够的(0)。
对于查询，我们先查询左区间，再查询中间（左区间的右边与右区间的并集），最后查询右区间。
#include <cstdio>
#include <iostream>
#define MAXN 200100
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define mid ((l + r) >> 1)
using namespace std ;
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
", t = query(1, 1, N)), update(1, 1, N, t, t + A - 1, 0) ;
else
putchar('0'), putchar('
') ;
}
} return 0 ;
}
(emmm)这个题码量其实不大，思维含量也不高，但是成功地把做数据结构题做傻了的我拉回了正途。
( m{SCOI}) 序列操作
对于一个(01)序列，大体是这几种操作：
- 区间清零
- 区间置为(1)
- 区间全部取非
- 区间查询(1)的个数
- 区间查询最长连续的(1)的长度
好的，这道题被我秒了，爽啊……不过秒是秒了，对拍调试法调了好久(233)。
其实对于(1,2,4,5)都好说，只是第(3)个操作，需要再另维护区间最长连续的(0)的长度，如果存在取非标记生效，就交换一下就行。
#include <cstdio>
#include <iostream>
#define MAX 200010
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define mid ((l + r) >> 1)
using namespace std ;
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
", Sum(1, 1, N)) ;
else printf("%d", query(1, 1, N).Sum), putchar('
') ;
// cout << " qwerweafasdfsdf " << endl ;
}
}
(push\_up)真长啊(233)
艹完这个题是真的爽啊~
(Task3~) 总结一下
其实这东西和(DP)是一样的吧？你只需要确定你想要维护什么(等价于确定状态)，然后明确父子区间如何向上维护(等价于状态之间如何转移)。
嗯，万物相同。
野马也，尘埃也，生物之以息向吹也。天之苍苍，其正色耶？其远而无所至极耶？
不知为什么，突然想到了这句话。