HDU 5454 Excited Database 线段树的维护

http://acm.hdu.edu.cn/showproblem.php?pid=5454

Excited Database

Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 298    Accepted Submission(s): 83

Problem Description
She says that any Pavarotti among the nightingales will serenade his mate while she sits on her eggs.
She says that any excited database can answer the queries efficiently.

You are given the two dimensional database as a matrix A with n rows and n columns. In the beginning, A[i][j]=0 for all 1i,jn.
Then q operations or queries will be given in turn.

You should maintain the database for two type of operations:
1 L R: for each element A[i][j] which satisfy Li+jR, increase the value to A[i][j]+1, where 2LR2n.
2 L R: for each element A[i][j] which satisfy LijR, increase the value to A[i][j]+1, where 1nLRn1.
Meanwhile, you should answer the queries:
3 x1 x2 y1 y2: count the value of elements A[i][j] which satisfy x1ix2 and y1jy2, where 1x1<x2n and 1y1<y2n.

 

Input
The input contains several test cases. The first line of the input is a single integer t which is the number of test cases. Then t test cases follow.

Each test case contains several lines. The first line contains the integer n and q.
The i-th line of the next q lines contains an operation 1 L R" or 2 L R", or a query 3 x1 x2 y1 y2".

The sum of n for all test cases would not be larger than 200000 and the sum of q would not be larger than 50000.

 

Output
For each test case, you should output answers to queries printed one per line.

 

Sample Input
2 6 6 2 0 1 3 1 4 3 5 3 2 5 2 3 1 5 7 3 1 4 3 5 3 2 5 2 3 6 26 2 -4 -1 3 1 4 2 5 3 3 6 4 6 1 4 7 3 2 5 2 3 3 1 4 2 5 2 -3 -1 3 1 4 3 5 1 3 5 1 2 3 3 2 5 2 3 3 1 4 2 5 3 3 6 4 6 2 0 4 3 1 4 3 5 3 1 4 2 5 1 9 11 2 1 2 3 2 5 2 3 3 3 6 4 6 2 -2 2 1 7 12 3 1 4 3 5 3 2 5 2 3 3 1 4 2 5 3 3 6 4 6

 

Sample Output
Case #1: 3 4 11 10 Case #2: 10 6 8 22 26 12 38 13 32 44 23 30 49 33 67 53

 

Source

 

Recommend
wange2014
题意:在一个n*n的矩阵中,(n<=20w),有两种操作:操作1:将A[i]j](L<= i + j <=R)  +1,操作2:将A[i][j](L<=i - j < =R )   +1. 询问x1,y1到x2,y2区域内的和。
思路:按照主对角线和副对角线分别建立线段树,操作就是区间累加操作,维护需要维护区间的sum和A[i]*i的和,查询是将矩形分解为2个等腰直角三角形和一个平行四边形。分别进行询问。
代码:

 

Codeforces 575B Bribes树链剖分+离线+区间端点打标记

http://codeforces.com/contest/575/problem/B

B. Bribes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ruritania is a country with a very badly maintained road network, which is not exactly good news for lorry drivers that constantly have to do deliveries. In fact, when roads are maintained, they become one-way. It turns out that it is sometimes impossible to get from one town to another in a legal way – however, we know that all towns are reachable, though illegally!

Fortunately for us, the police tend to be very corrupt and they will allow a lorry driver to break the rules and drive in the wrong direction provided they receive ‘a small gift’. There is one patrol car for every road and they will request 1000 Ruritanian dinars when a driver drives in the wrong direction. However, being greedy, every time a patrol car notices the same driver breaking the rule, they will charge double the amount of money they requested the previous time on that particular road.

Borna is a lorry driver that managed to figure out this bribing pattern. As part of his job, he has to make K stops in some towns all over Ruritania and he has to make these stops in a certain order. There are N towns (enumerated from 1 to N) in Ruritania and Borna’s initial location is the capital city i.e. town 1. He happens to know which ones out of the N - 1 roads in Ruritania are currently unidirectional, but he is unable to compute the least amount of money he needs to prepare for bribing the police. Help Borna by providing him with an answer and you will be richly rewarded.

Input

The first line contains N, the number of towns in Ruritania. The following N - 1 lines contain information regarding individual roads between towns. A road is represented by a tuple of integers (a,b,x), which are separated with a single whitespace character. The numbers a and b represent the cities connected by this particular road, and x is either 0 or 1: 0 means that the road is bidirectional, 1 means that only the a → b direction is legal. The next line contains K, the number of stops Borna has to make. The final line of input contains K positive integers s1, …, sK: the towns Borna has to visit.

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ 106
  • 1 ≤ a, b ≤ N for all roads
  • for all roads
  • 1 ≤ si ≤ N for all 1 ≤ i ≤ K
Output

The output should contain a single number: the least amount of thousands of Ruritanian dinars Borna should allocate for bribes, modulo 109 + 7.

Sample test(s)
Input

Output

Note

Borna first takes the route 1 → 5 and has to pay 1000 dinars. After that, he takes the route 5 → 1 → 2 → 3 → 4 and pays nothing this time. However, when he has to return via 4 → 3 → 2 → 1 → 5, he needs to prepare 3000 (1000+2000) dinars. Afterwards, getting to 2 via 5 → 1 → 2 will cost him nothing. Finally, he doesn't even have to leave town 2 to get to 2, so there is no need to prepare any additional bribe money. Hence he has to prepare 4000 dinars in total.

题意:在一棵树上,有一些边是单向边,有一些是双向边。如果逆向行驶单向边,第一次逆行这条边,罚款1,……第i次罚款2^i.

然后给出k个点,分别为ki,到达ki后再去ki+1,初始的时候在1点。问按照上面的安排,最少被罚多少。%10^9+7

思路:将询问离线后,求出每条单向边被反向走了多少次。将单向边分为往上走为逆向和往下走为逆行的两类。对于每一次询问,可采取将这个树进行剖分后,在重链上走动,重链上的点的dfs序是连续的。先从起点往上走到lca。区间内的第一类反向边都被走了一次。这些区间的首尾打上标记。再从lca走到终点,区间内的第二类反向边被走了一次。打上标记。最后从1-n扫一次,算出每条单向边反行了多少次,就能算出答案了。。注意,,边权下方到儿子节点。

 

HDU5390 tree dfs序+线段树分层离线+字典树求异或最大值

http://acm.hdu.edu.cn/showproblem.php?pid=5390

tree

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 313    Accepted Submission(s): 70

Problem Description
Given a rooted tree(node 1 is the root) with n nodes. The ithnode has a positive value vi at beginning.
We define the universal set S includes all nodes.
There are two types of Memphis's operation.
First, Memphis may change the value of one node. It's the first type operation:

0  u  v   (uS,0v109)

What's more, Memphis wants to know what's the maxinum of vuvt(tpath(u,root),  means  xor) . It's the second type operation:

1  u   (uS)

 

Input
This problem has multi test cases(no more than 3).
The first line contains a single integer T, which denotes the number of test cases.
For each test case,the first line contains two non-negative integer n,m(1n,m100000) - the number of nodes and operations.
The second line contains n1 non-negative integer f2fn(fi<i) - the father of ithnode.
The third line contains n non-negative integer v1vn(0vi109) - the value of nodes at beginning.
Follow m lines describe each operation.

 

Output
For each test cases,for each second operation print a non-negative integer.

 

Sample Input
1 10 10 1 1 2 2 3 1 2 3 5 23512 460943 835901 491571 399045 97756 413210 800843 283274 106134 0 7 369164 0 7 296167 0 6 488033 0 7 187367 0 9 734984 1 6 0 5 329287 1 5 0 7 798656 1 10

 

Sample Output
766812 351647 431641

 

Author
SXYZ

 

Source

 

Recommend
wange2014
题意:给定一个数,根节点为1,每个点有一个点权。有两个操作,0操作是询问某点的点权与这个点到根的路径上的点的点权的异或的最大值。1操作是修改某个点的点权。

思路:求在集合中查找异或的最大值,想到的是使用字典树。用线段树按照dfs序建树,某个点的权值将对其区间内(子树)的点的询问造成影响,所以点权修改就是对其覆盖的区间上的字典树进行修改。询问就是从这个点的dfs序在线段树内的节点往上走,在经过的每个线段树节点的字典树内查询,让后取最大值。

上面做法的在时间上是可行的,但是会MLE。我们采取按线段树分层的办法。从线段树最下层开始,对于每一个操作,得到这个操作在这一层对应的区间,然后进行操作或者询问,没有就不操作。最后询问的结果依然是这个点在每层询问中的最大值。

代码:

 

HDU 4718 The LCIS on the Tree 树上路径倍增

http://acm.hdu.edu.cn/showproblem.php?pid=4718

The LCIS on the Tree

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 775    Accepted Submission(s): 236

Problem Description
For a sequence S1, S2, ... , SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 < ... < Sj-1 < Sj , then the sequence Si, Si+1, ... , Sj is a CIS(Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).
Now we consider a tree rooted at node 1. Nodes have values. We have Q queries, each with two nodes u and v. You have to find the shortest path from u to v. And write down each nodes' value on the path, from u to v, inclusive. Then you will get a sequence, and please show us the length of its LCIS.

 

Input
The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 ... , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N - 1 numbers p2, p3, p4 ... , pN, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.
Then comes a number Q, it is the number of queries. (Q <= 105)
For next Q lines, each with two numbers u and v. As described above.

 

Output
For test case X, output "Case #X:" at the first line.
Then output Q lines, each with an answer to the query.
There should be a blank line *BETWEEN* each test case.

 

Sample Input
1 5 1 2 3 4 5 1 1 3 3 3 1 5 4 5 2 5

 

Sample Output
Case #1: 3 2 3

 

Source

 

Recommend
zhuyuanchen520
题意:给定一个节点数小于10w的树,每个节点有一个点权。再给出Q次询问(小于10w),每次给定一个起点和终点u,v。求在u点到v点的最短路上,节点点权的最长上连续升子段的长度。
思路:
    除了数链剖分,动态树等方法之外,此题还可采用树上路径倍增的方法来解决。分别维护以某个节点,往上走2^i步之后的区间内的一些信息。这里,假设这个区间是有方向的,就是以上述的“某个”节点为起点,以上述的”往上走2^i步之后“到达的点为终点。用LL[0],LL[1]分别表示这个区间从起点(定义为左端点)开始最长连续的上升、下降子段长度,RR[0]、RR[1]表示终点为区间右端点的最长的连续上升、下降的子段长度。用ans[0]、ans[1]分别维护这个区间内连续上升、下降的长度。特别注意,这里说的上升下降,是在规定了区间起点和终点的情况下说的!
    对于每一次询问,先求出u,v的lca。lca也用树上路径倍增的方法来维护和求得。维护的到u-lca段上的右连续上升和这个区间内的最长连续上升段的长度,维护得到v-lca的右连续下降长度和这个区间内的最长下降段的长度。对于lca-v这区间,颠倒起点终点之后,维护的值都代表上升的长度啦!最后答案就是u-lca的答案,v-lca的答案,两个右连续的和,这三个值取最大值。

这个方法,效率挺高的。

HDU5336 XYZ and Drops 暴力模拟

http://acm.hdu.edu.cn/showproblem.php?pid=5336

XYZ and Drops

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1641    Accepted Submission(s): 548

Problem Description
XYZ is playing an interesting game called "drops". It is played on a rc grid. Each grid cell is either empty, or occupied by a waterdrop. Each waterdrop has a property "size". The waterdrop cracks when its size is larger than 4, and produces 4 small drops moving towards 4 different directions (up, down, left and right).

In every second, every small drop moves to the next cell of its direction. It is possible that multiple small drops can be at same cell, and they won't collide. Then for each cell occupied by a waterdrop, the waterdrop's size increases by the number of the small drops in this cell, and these small drops disappears.

You are given a game and a position (x, y), before the first second there is a waterdrop cracking at position (x, y). XYZ wants to know each waterdrop's status afterT seconds, can you help him?

1r100, 1c100, 1n100, 1T10000

 

Input
The first line contains four integers r, c, n and T. n stands for the numbers of waterdrops at the beginning.
Each line of the following n lines contains three integers xi, yi, sizei, meaning that the i-th waterdrop is at position (xi, yi) and its size is sizei. (1sizei4)
The next line contains two integers x, y.

It is guaranteed that all the positions in the input are distinct.

Multiple test cases (about 100 cases), please read until EOF (End Of File).

 

Output
n lines. Each line contains two integers Ai, Bi:
If the i-th waterdrop cracks in T seconds, Ai=0, Bi= the time when it cracked.
If the i-th waterdrop doesn't crack in T seconds, Ai=1, Bi= its size after T seconds.

 

Sample Input
4 4 5 10 2 1 4 2 3 3 2 4 4 3 1 2 4 3 4 4 4

 

Sample Output
0 5 0 3 0 2 1 3 0 1

 

Author
XJZX

 

Source
题意:在一个r*c的棋盘上,有n个水坑,1<=r,c,n<=100。当一个水坑的size大于4只会,就会分裂成四个水滴,分别向四个不同的方向移动,并且水坑消失。当一个水滴进入到水坑时,水坑的size+1,水滴消失。初始的时候,在x,y点一个水坑分裂。问在T秒时各个水坑的状况。
思路:暴力模拟每秒每个水坑和水滴。
对于每一秒,移动每一个存在的水滴,当在棋盘外或者进入水坑时,该水滴消失,水坑size或者+1。再暴力枚举每个存在的水坑,检查其size,如果size>4,消失,产生四个不同方向水滴。
代码:

 

HDU 5324 Boring Class 树状数组套平衡树

http://acm.hdu.edu.cn/showproblem.php?pid=5324

Boring Class

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1070    Accepted Submission(s): 305

Problem Description
Mr. Zstu and Mr. Hdu are taking a boring class , Mr. Zstu comes up with a problem to kill time, Mr. Hdu thinks it’s too easy, he solved it very quickly, what about you guys?
Here is the problem:
Give you two sequences L1,L2,...,Ln and R1,R2,...,Rn.
Your task is to find a longest subsequence v1,v2,...vm satisfies
v11,vmn,vi<vi+1 .(for i from 1 to m - 1)
LviLvi+1,RviRvi+1(for i from 1 to m - 1)
If there are many longest subsequence satisfy the condition, output the sequence which has the smallest lexicographic order.

 

Input
There are several test cases, each test case begins with an integer n.
1n50000
Both of the following two lines contain n integers describe the two sequences.
1Li,Ri109

 

Output
For each test case ,output the an integer m indicates the length of the longest subsequence as described.
Output m integers in the next line.

 

Sample Input
5 5 4 3 2 1 6 7 8 9 10 2 1 2 3 4

 

Sample Output
5 1 2 3 4 5 1 1

 

Author
ZSTU

 

Source

 

Recommend
wange2014
题意:给出两个长度为n(n< 5w)的数组A,B,数组元素小于10^9 。求一个序列Vi。要求1<=Vi<=n,Vi<Vi+1,且长度最长的条件下字典序最小,使得Avi>=Avi+1且Bvi<=Bvi+1。
思路:要求字典序最小,只能倒着来,用DP[i]表示从最后一位到第i的能构成序列的最长长度,用Pre[i]来表示在上述条件下的前驱的位置。如果暴力DP,是会TLE,需要进行优化。将两个数组进行离散化。建立一个树状数组,数组数组的每个节点建立一个平衡树。树状数组按A数组的值建树。平衡树按照B值建树(关键值),维护DP的最大值,DP最大值条件下的下标的最小值。当更新第i个位置的dp值的时候,选取数组数组中小于等于x的区间(废话),在这些平衡树中找关键值大于等于B[i]的DP的最大值及其ID最小值。得到后直接更新dp和pre即可。更新完成后在将i位置的信息插入树套树中。
代码:

附上CDQ分治代码:

 

HDU 5335 Walk Out 状压DP乱搞

http://acm.hdu.edu.cn/showproblem.php?pid=5335

Walk Out

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3787    Accepted Submission(s): 776

Problem Description
In an nm maze, the right-bottom corner is the exit (position (n,m) is the exit). In every position of this maze, there is either a 0 or a 1 written on it.

An explorer gets lost in this grid. His position now is (1,1), and he wants to go to the exit. Since to arrive at the exit is easy for him, he wants to do something more difficult. At first, he'll write down the number on position (1,1). Every time, he could make a move to one adjacent position (two positions are adjacent if and only if they share an edge). While walking, he will write down the number on the position he's on to the end of his number. When finished, he will get a binary number. Please determine the minimum value of this number in binary system.

 

Input
The first line of the input is a single integer T (T=10), indicating the number of testcases.

For each testcase, the first line contains two integers n and m (1n,m1000). The i-th line of the next n lines contains one 01 string of length m, which represents i-th row of the maze.

 

Output
For each testcase, print the answer in binary system. Please eliminate all the preceding 0 unless the answer itself is 0 (in this case, print 0 instead).

 

Sample Input
2 2 2 11 11 3 3 001 111 101

 

Sample Output
111 101

 

Author
XJZX

 

Source

 

Recommend
wange2014
题意:在一个n*m的01矩阵中,起点在左上角,出口在右下角。求一条路径,是路径表示的二进制数的值最小,输出这个数的二进制。
思路:从起点出发,在‘0’上进行bfs,找到一个或多个里出口曼哈顿距离最近的点,从这种点走字典序最小的最短路到出口,这条路径就是所求的路径。
前面的bfs都没什么问题,关键是后面的路径怎么找,由于要求字典序最小,可以由出口进行状压dp得到。但是,位数太多了,只能自己建立一个状压类型,见代码的struct Bit。但是,存下所有点的状态,内存是不够的,动态分配内存又太慢,所有采用数组分配内存的方式,再用模拟栈来回收内存。就这样乱搞的方法完美解决了这题。

 

HDU5323 Solve this interesting problem 暴力DFS

Solve this interesting problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2622    Accepted Submission(s): 815

Problem Description
Have you learned something about segment tree? If not, don’t worry, I will explain it for you.
Segment Tree is a kind of binary tree, it can be defined as this:
- For each node u in Segment Tree, u has two values: Lu and Ru.
- If Lu=Ru, u is a leaf node.
- If LuRu, u has two children x and y,with Lx=Lu,Rx=Lu+Ru2,Ly=Lu+Ru2+1,Ry=Ru.
Here is an example of segment tree to do range query of sum.

Given two integers L and R, Your task is to find the minimum non-negative n satisfy that: A Segment Tree with root node's value Lroot=0 and Rroot=n contains a node u with Lu=L and Ru=R.

 

Input
The input consists of several test cases.
Each test case contains two integers L and R, as described above.
0LR109
LRL+12015

 

Output
For each test, output one line contains one integer. If there is no such n, just output -1.

 

Sample Input
6 7 10 13 10 11

 

Sample Output
7 -1 12

 

Author
ZSTU

 

Source

 

Recommend
wange2014
题意:给定一对L,R。问是否存在一个线段树【0,n】他的一个区间为【L,R】。
思路:每次dfs,往这个区间的左边或者右边加一个区间,根据线段树的性质,左区间的长度=右区间长度,或者+1.可以将这个设置为dfs的剪枝条件。当L==0时,R就是搜到的答案之一,取最小值即可。

 

HDU5317 RGCDQ 质因子分解

http://acm.hdu.edu.cn/showproblem.php?pid=5317

RGCDQ

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2409    Accepted Submission(s): 969

Problem Description
Mr. Hdu is interested in Greatest Common Divisor (GCD). He wants to find more and more interesting things about GCD. Today He comes up with Range Greatest Common Divisor Query (RGCDQ). What’s RGCDQ? Please let me explain it to you gradually. For a positive integer x, F(x) indicates the number of kind of prime factor of x. For example F(2)=1. F(10)=2, because 10=2*5. F(12)=2, because 12=2*2*3, there are two kinds of prime factor. For each query, we will get an interval [L, R], Hdu wants to know maxGCD(F(i),F(j)) (Li<jR)

 

Input
There are multiple queries. In the first line of the input file there is an integer T indicates the number of queries.
In the next T lines, each line contains L, R which is mentioned above.All input items are integers.
1<= T <= 1000000
2<=L < R<=1000000

 

Output
For each query,output the answer in a single line.
See the sample for more details.

 

Sample Input
2 2 3 3 5

 

Sample Output
1 1

 

Author
ZSTU

 

Source

 

Recommend
wange2014
题意:定义F(i)为i的质因子的个数(去重),给定一个L,R。求gcd(f(i),f(j))的最大值,要求2<=L<=i<j<=R<=100w.测试组数小于100w
思路:测试组数太多了,必须要O(1)得出每一组测试。先预处理出1到100w的每个数的f(i)。由于i最大只有100w,所以f(i)的最大值只有7。用sum[i][j]记录从0~j,f[j]==i的数的个数。查询的时候,直接枚举f(i)和f(j)的值即可。
代码:

 

HDU5316 Magician 线段树区间合并

http://acm.hdu.edu.cn/showproblem.php?pid=5316

Magician

Time Limit: 18000/9000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Fantasy magicians usually gain their ability through one of three usual methods: possessing it as an innate talent, gaining it through study and practice, or receiving it from another being, often a god, spirit, or demon of some sort. Some wizards are depicted as having a special gift which sets them apart from the vast majority of characters in fantasy worlds who are unable to learn magic.

Magicians, sorcerers, wizards, magi, and practitioners of magic by other titles have appeared in myths, folktales, and literature throughout recorded history, with fantasy works drawing from this background.

In medieval chivalric romance, the wizard often appears as a wise old man and acts as a mentor, with Merlin from the King Arthur stories representing a prime example. Other magicians can appear as villains, hostile to the hero.

Mr. Zstu is a magician, he has many elves like dobby, each of which has a magic power (maybe negative). One day, Mr. Zstu want to test his ability of doing some magic. He made the elves stand in a straight line, from position 1 to position n, and he used two kinds of magic, Change magic and Query Magic, the first is to change an elf’s power, the second is get the maximum sum of beautiful subsequence of a given interval. A beautiful subsequence is a subsequence that all the adjacent pairs of elves in the sequence have a different parity of position. Can you do the same thing as Mr. Zstu ?

Input
The first line is an integer T represent the number of test cases.
Each of the test case begins with two integers n, m represent the number of elves and the number of time that Mr. Zstu used his magic.
(n,m <= 100000)
The next line has n integers represent elves’ magic power, magic power is between -1000000000 and 1000000000.
Followed m lines, each line has three integers like
type a b describe a magic.
If type equals 0, you should output the maximum sum of beautiful subsequence of interval [a,b].(1 <= a <= b <= n)
If type equals 1, you should change the magic power of the elf at position a to b.(1 <= a <= n, 1 <= b <= 1e9)
Output
For each 0 type query, output the corresponding answer.
Sample Input
1 1 1 1 0 1 1
Sample Output
1

题意:给定一个数组,长度小于10w,数组元素的大小的绝对值小于10^9。有一个操作:单点修改。有一个询问:在给定的[L,R]区间内,选出一个子序列,要求子序列的相邻的两个数的下标奇偶性不同,求子序列的最大和。

思路:用线段树维护每个区间,以奇数下标开头、奇数下标结尾的子序列的最大和jj;奇数下标开头、偶数下标结尾的子序列的最大和jo;偶数数下标开头、奇数下标结尾的子序列的最大和oj;偶数下标开头、偶数下标结尾的子序列的最大和oo;

当然,在叶子节点的时候,只有jj或者oo才有效,其他3个值全部赋值为-INF,合并的时候注意溢出。区间合并时,以oj为例,oj值可能来自于左区间或者右区间的oj,还可能来自左区间的oj+右区间的oj,左区间的oo+右区间的jj。