|
1 | 1 | packageg3101_3200.s3165_maximum_sum_of_subsequence_with_non_adjacent_elements; |
2 | 2 |
|
3 | 3 | // #Hard #Array #Dynamic_Programming #Divide_and_Conquer #Segment_Tree |
4 | | -// #2024_06_02_Time_1927_ms_(87.75%)_Space_82.1_MB_(5.31%) |
5 | | - |
6 | | -importjava.util.stream.Stream; |
| 4 | +// #2024_11_09_Time_64_ms_(100.00%)_Space_64.1_MB_(97.01%) |
7 | 5 |
|
8 | 6 | publicclassSolution { |
| 7 | +privatestaticfinalintYY =0; |
| 8 | +privatestaticfinalintYN =1; |
| 9 | +privatestaticfinalintNY =2; |
| 10 | +privatestaticfinalintNN =3; |
9 | 11 | privatestaticfinalintMOD =1_000_000_007; |
10 | 12 |
|
11 | 13 | publicintmaximumSumSubsequence(int[]nums,int[][]queries) { |
12 | | -intans =0; |
13 | | -SegTreesegTree =newSegTree(nums); |
14 | | -for (int[]q :queries) { |
15 | | -intidx =q[0]; |
16 | | -intval =q[1]; |
17 | | -segTree.update(idx,val); |
18 | | -ans = (ans +segTree.getMax()) %MOD; |
| 14 | +long[][]tree =build(nums); |
| 15 | +longresult =0; |
| 16 | +for (inti =0;i <queries.length; ++i) { |
| 17 | +result +=set(tree,queries[i][0],queries[i][1]); |
| 18 | +result %=MOD; |
19 | 19 | } |
20 | | -returnans; |
| 20 | +return(int)result; |
21 | 21 | } |
22 | 22 |
|
23 | | -staticclassSegTree { |
24 | | -privatestaticclassRecord { |
25 | | -inttakeFirstTakeLast; |
26 | | -inttakeFirstSkipLast; |
27 | | -intskipFirstSkipLast; |
28 | | -intskipFirstTakeLast; |
29 | | - |
30 | | -publicIntegergetMax() { |
31 | | -returnStream.of( |
32 | | -this.takeFirstSkipLast, |
33 | | -this.takeFirstTakeLast, |
34 | | -this.skipFirstSkipLast, |
35 | | -this.skipFirstTakeLast) |
36 | | - .max(Integer::compare) |
37 | | - .orElse(null); |
38 | | - } |
39 | | - |
40 | | -publicIntegerskipLast() { |
41 | | -returnStream.of(this.takeFirstSkipLast,this.skipFirstSkipLast) |
42 | | - .max(Integer::compare) |
43 | | - .orElse(null); |
44 | | - } |
45 | | - |
46 | | -publicIntegertakeLast() { |
47 | | -returnStream.of(this.skipFirstTakeLast,this.takeFirstTakeLast) |
48 | | - .max(Integer::compare) |
49 | | - .orElse(null); |
50 | | - } |
| 23 | +privatestaticlong[][]build(int[]nums) { |
| 24 | +finalintlen =nums.length; |
| 25 | +intsize =1; |
| 26 | +while (size <len) { |
| 27 | +size <<=1; |
51 | 28 | } |
52 | | - |
53 | | -privatefinalRecord[]seg; |
54 | | -privatefinalint[]nums; |
55 | | - |
56 | | -publicSegTree(int[]nums) { |
57 | | -this.nums =nums; |
58 | | -seg =newRecord[4 *nums.length]; |
59 | | -for (inti =0;i <4 *nums.length; ++i) { |
60 | | -seg[i] =newRecord(); |
61 | | - } |
62 | | -build(0,nums.length -1,0); |
| 29 | +long[][]tree =newlong[size *2][4]; |
| 30 | +for (inti =0;i <len; ++i) { |
| 31 | +tree[size +i][YY] =nums[i]; |
63 | 32 | } |
64 | | - |
65 | | -privatevoidbuild(inti,intj,intk) { |
66 | | -if (i ==j) { |
67 | | -seg[k].takeFirstTakeLast =nums[i]; |
68 | | -return; |
69 | | - } |
70 | | -intmid = (i +j) >>1; |
71 | | -build(i,mid,2 *k +1); |
72 | | -build(mid +1,j,2 *k +2); |
73 | | -merge(k); |
74 | | - } |
75 | | - |
76 | | -// merge [2*k+1, 2*k+2] into k |
77 | | -privatevoidmerge(intk) { |
78 | | -seg[k].takeFirstSkipLast = |
| 33 | +for (inti =size -1;i >0; --i) { |
| 34 | +tree[i][YY] = |
79 | 35 | Math.max( |
80 | | -seg[2 *k +1].takeFirstSkipLast +seg[2 *k +2].skipLast(), |
81 | | -seg[2 *k +1].takeFirstTakeLast +seg[2 *k +2].skipFirstSkipLast); |
82 | | - |
83 | | -seg[k].takeFirstTakeLast = |
| 36 | +tree[2 *i][YY] +tree[2 *i +1][NY], |
| 37 | +tree[2 *i][YN] +Math.max(tree[2 *i +1][YY],tree[2 *i +1][NY])); |
| 38 | +tree[i][YN] = |
84 | 39 | Math.max( |
85 | | -seg[2 *k +1].takeFirstSkipLast +seg[2 *k +2].takeLast(), |
86 | | -seg[2 *k +1].takeFirstTakeLast +seg[2 *k +2].skipFirstTakeLast); |
87 | | - |
88 | | -seg[k].skipFirstTakeLast = |
| 40 | +tree[2 *i][YY] +tree[2 *i +1][NN], |
| 41 | +tree[2 *i][YN] +Math.max(tree[2 *i +1][YN],tree[2 *i +1][NN])); |
| 42 | +tree[i][NY] = |
89 | 43 | Math.max( |
90 | | -seg[2 *k +1].skipFirstSkipLast +seg[2 *k +2].takeLast(), |
91 | | -seg[2 *k +1].skipFirstTakeLast +seg[2 *k +2].skipFirstTakeLast); |
92 | | - |
93 | | -seg[k].skipFirstSkipLast = |
| 44 | +tree[2 *i][NY] +tree[2 *i +1][NY], |
| 45 | +tree[2 *i][NN] +Math.max(tree[2 *i +1][YY],tree[2 *i +1][NY])); |
| 46 | +tree[i][NN] = |
94 | 47 | Math.max( |
95 | | -seg[2 *k +1].skipFirstSkipLast +seg[2 *k +2].skipLast(), |
96 | | -seg[2 *k +1].skipFirstTakeLast +seg[2 *k +2].skipFirstSkipLast); |
97 | | - } |
98 | | - |
99 | | -// child -> parent |
100 | | -publicvoidupdate(intidx,intval) { |
101 | | -inti =0; |
102 | | -intj =nums.length -1; |
103 | | -intk =0; |
104 | | -update(idx,val,k,i,j); |
105 | | - } |
106 | | - |
107 | | -privatevoidupdate(intidx,intval,intk,inti,intj) { |
108 | | -if (i ==j) { |
109 | | -seg[k].takeFirstTakeLast =val; |
110 | | -return; |
111 | | - } |
112 | | -intmid = (i +j) >>1; |
113 | | -if (idx <=mid) { |
114 | | -update(idx,val,2 *k +1,i,mid); |
115 | | - }else { |
116 | | -update(idx,val,2 *k +2,mid +1,j); |
117 | | - } |
118 | | -merge(k); |
| 48 | +tree[2 *i][NY] +tree[2 *i +1][NN], |
| 49 | +tree[2 *i][NN] +Math.max(tree[2 *i +1][YN],tree[2 *i +1][NN])); |
119 | 50 | } |
| 51 | +returntree; |
| 52 | + } |
120 | 53 |
|
121 | | -publicintgetMax() { |
122 | | -returnseg[0].getMax(); |
| 54 | +privatestaticlongset(long[][]tree,intidx,intval) { |
| 55 | +intsize =tree.length /2; |
| 56 | +tree[size +idx][YY] =val; |
| 57 | +for (inti = (size +idx) /2;i >0;i /=2) { |
| 58 | +tree[i][YY] = |
| 59 | +Math.max( |
| 60 | +tree[2 *i][YY] +tree[2 *i +1][NY], |
| 61 | +tree[2 *i][YN] +Math.max(tree[2 *i +1][YY],tree[2 *i +1][NY])); |
| 62 | +tree[i][YN] = |
| 63 | +Math.max( |
| 64 | +tree[2 *i][YY] +tree[2 *i +1][NN], |
| 65 | +tree[2 *i][YN] +Math.max(tree[2 *i +1][YN],tree[2 *i +1][NN])); |
| 66 | +tree[i][NY] = |
| 67 | +Math.max( |
| 68 | +tree[2 *i][NY] +tree[2 *i +1][NY], |
| 69 | +tree[2 *i][NN] +Math.max(tree[2 *i +1][YY],tree[2 *i +1][NY])); |
| 70 | +tree[i][NN] = |
| 71 | +Math.max( |
| 72 | +tree[2 *i][NY] +tree[2 *i +1][NN], |
| 73 | +tree[2 *i][NN] +Math.max(tree[2 *i +1][YN],tree[2 *i +1][NN])); |
123 | 74 | } |
| 75 | +returnMath.max(tree[1][YY],Math.max(tree[1][YN],Math.max(tree[1][NY],tree[1][NN]))); |
124 | 76 | } |
125 | 77 | } |