|
1 | 1 | packageg3201_3300.s3245_alternating_groups_iii; |
2 | 2 |
|
3 | | -// #Hard #Array #Binary_Indexed_Tree #2025_02_12_Time_135_ms_(86.36%)_Space_84.24_MB_(40.91%) |
| 3 | +// #Hard #Array #Binary_Indexed_Tree #2025_03_14_Time_38_ms_(91.84%)_Space_77.53_MB_(87.76%) |
4 | 4 |
|
5 | 5 | importjava.util.ArrayList; |
| 6 | +importjava.util.BitSet; |
6 | 7 | importjava.util.List; |
7 | | -importjava.util.Map; |
8 | | -importjava.util.TreeMap; |
9 | 8 |
|
10 | 9 | publicclassSolution { |
11 | | -privatestaticfinalintSZ =63333; |
12 | | -privatestaticfinalintOFFSET =SZ -10; |
13 | | -privatestaticfinalBIT[]BITS = {newBIT(),newBIT()}; |
14 | | - |
15 | | -// Binary Indexed Tree (BIT) class. |
16 | | -privatestaticclassBIT { |
17 | | -int[]bs =newint[SZ]; |
18 | | - |
19 | | -// Update BIT: add value y to index x. |
20 | | -voidupdate(intx,inty) { |
21 | | -x =OFFSET -x; |
22 | | -for (;x <SZ;x +=x & -x) { |
23 | | -bs[x] +=y; |
24 | | - } |
25 | | - } |
26 | | - |
27 | | -// Query BIT: get the prefix sum up to index x. |
28 | | -intquery(intx) { |
29 | | -x =OFFSET -x; |
30 | | -intans =0; |
31 | | -for (;x >0;x -=x & -x) { |
32 | | -ans +=bs[x]; |
| 10 | +publicList<Integer>numberOfAlternatingGroups(int[]colors,int[][]queries) { |
| 11 | +intn =colors.length; |
| 12 | +BitSetset =newBitSet(); |
| 13 | +BITbit =newBIT(n); |
| 14 | +for (inti =0;i <n;i++) { |
| 15 | +if (colors[i] ==colors[getIndex(i +1,n)]) { |
| 16 | +add(set,bit,n,i); |
33 | 17 | } |
34 | | -returnans; |
35 | 18 | } |
36 | | - |
37 | | -// Clear BIT values starting from index x. |
38 | | -voidclear(intx) { |
39 | | -x =OFFSET -x; |
40 | | -for (;x <SZ;x +=x & -x) { |
41 | | -bs[x] =0; |
| 19 | +List<Integer>ans =newArrayList<>(); |
| 20 | +for (int[]q :queries) { |
| 21 | +if (q[0] ==1) { |
| 22 | +if (set.isEmpty()) { |
| 23 | +ans.add(n); |
| 24 | + }else { |
| 25 | +intsize =q[1]; |
| 26 | +int[]res =bit.query(size); |
| 27 | +ans.add(res[1] -res[0] * (size -1)); |
| 28 | + } |
| 29 | + }else { |
| 30 | +inti =q[1]; |
| 31 | +intcolor =colors[i]; |
| 32 | +if (q[2] ==color) { |
| 33 | +continue; |
| 34 | + } |
| 35 | +intpre =getIndex(i -1,n); |
| 36 | +if (colors[pre] ==color) { |
| 37 | +remove(set,bit,n,pre); |
| 38 | + } |
| 39 | +intnext =getIndex(i +1,n); |
| 40 | +if (colors[next] ==color) { |
| 41 | +remove(set,bit,n,i); |
| 42 | + } |
| 43 | +colors[i] ^=1; |
| 44 | +color =colors[i]; |
| 45 | +if (colors[pre] ==color) { |
| 46 | +add(set,bit,n,pre); |
| 47 | + } |
| 48 | +if (colors[next] ==color) { |
| 49 | +add(set,bit,n,i); |
| 50 | + } |
42 | 51 | } |
43 | 52 | } |
| 53 | +returnans; |
44 | 54 | } |
45 | 55 |
|
46 | | -// --- BIT wrapper methods --- |
47 | | -// Updates both BITs for a given group length. |
48 | | -privatevoidedt(intx,inty) { |
49 | | -// Second BIT is updated with x * y. |
50 | | -BITS[1].update(x,x *y); |
51 | | -// First BIT is updated with y. |
52 | | -BITS[0].update(x,y); |
53 | | - } |
54 | | - |
55 | | -// Combines BIT queries to get the result for a given x. |
56 | | -privateintqry(intx) { |
57 | | -returnBITS[1].query(x) + (1 -x) *BITS[0].query(x); |
58 | | - } |
59 | | - |
60 | | -// Returns the length of a group from index x to y. |
61 | | -privateintlen(intx,inty) { |
62 | | -returny -x +1; |
63 | | - } |
64 | | - |
65 | | -// --- Group operations --- |
66 | | -// Removes a group (block) by updating BIT with a negative value. |
67 | | -privatevoidremoveGroup(intstart,intend) { |
68 | | -edt(len(start,end), -1); |
69 | | - } |
70 | | - |
71 | | -// Adds a group (block) by updating BIT with a positive value. |
72 | | -privatevoidaddGroup(intstart,intend) { |
73 | | -edt(len(start,end),1); |
74 | | - } |
75 | | - |
76 | | -// Initializes the alternating groups using the colors array. |
77 | | -privatevoidinitializeGroups(int[]colors,TreeMap<Integer,Integer>groups) { |
78 | | -intn =colors.length; |
79 | | -inti =0; |
80 | | -while (i <n) { |
81 | | -intr =i; |
82 | | -// Determine the end of the current alternating group. |
83 | | -while (r <n && (colors[r] +colors[i] +r +i) %2 ==0) { |
84 | | - ++r; |
85 | | - } |
86 | | -// The group spans from index i to r-1. |
87 | | -groups.put(i,r -1); |
88 | | -// Update BITs with the length of this group. |
89 | | -edt(r -i,1); |
90 | | -// Skip to the end of the current group. |
91 | | -i =r -1; |
92 | | - ++i; |
| 56 | +privatevoidadd(BitSetset,BITbit,intn,inti) { |
| 57 | +if (set.isEmpty()) { |
| 58 | +bit.update(n,1); |
| 59 | + }else { |
| 60 | +update(set,bit,n,i,1); |
93 | 61 | } |
| 62 | +set.set(i); |
94 | 63 | } |
95 | 64 |
|
96 | | -// Processes a type 1 query: returns the number of alternating groups |
97 | | -// of at least the given size. |
98 | | -privateintprocessQueryType1(int[]colors,TreeMap<Integer,Integer>groups,intgroupSize) { |
99 | | -intans =qry(groupSize); |
100 | | -Map.Entry<Integer,Integer>firstGroup =groups.firstEntry(); |
101 | | -Map.Entry<Integer,Integer>lastGroup =groups.lastEntry(); |
102 | | -// If there is more than one group and the first and last colors differ, |
103 | | -// adjust the answer by "merging" the groups at the boundaries. |
104 | | -if (firstGroup !=lastGroup &&colors[0] !=colors[colors.length -1]) { |
105 | | -intleftLen =len(firstGroup.getKey(),firstGroup.getValue()); |
106 | | -intrightLen =len(lastGroup.getKey(),lastGroup.getValue()); |
107 | | -ans -=Math.max(leftLen -groupSize +1,0); |
108 | | -ans -=Math.max(rightLen -groupSize +1,0); |
109 | | -ans +=Math.max(leftLen +rightLen -groupSize +1,0); |
| 65 | +privatevoidremove(BitSetset,BITbit,intn,inti) { |
| 66 | +set.clear(i); |
| 67 | +if (set.isEmpty()) { |
| 68 | +bit.update(n, -1); |
| 69 | + }else { |
| 70 | +update(set,bit,n,i, -1); |
110 | 71 | } |
111 | | -returnans; |
112 | 72 | } |
113 | 73 |
|
114 | | -// Processes a type 2 query: updates the color at index x and adjusts groups. |
115 | | -privatevoidprocessQueryType2( |
116 | | -int[]colors,TreeMap<Integer,Integer>groups,intx,intnewColor) { |
117 | | -if (colors[x] ==newColor) { |
118 | | -return; |
119 | | - } |
120 | | -// Update the color at index x. |
121 | | -colors[x] =newColor; |
122 | | -// Find the group (block) that contains index x. |
123 | | -Map.Entry<Integer,Integer>it =groups.floorEntry(x); |
124 | | -intl =it.getKey(); |
125 | | -intr =it.getValue(); |
126 | | -// Remove the old group from BIT and map. |
127 | | -removeGroup(l,r); |
128 | | -groups.remove(l); |
129 | | -intml =x; |
130 | | -intmr =x; |
131 | | -// Process the left side of index x. |
132 | | -if (l !=x) { |
133 | | -groups.put(l,x -1); |
134 | | -addGroup(l,x -1); |
135 | | - }else { |
136 | | -if (x >0 &&colors[x] !=colors[x -1]) { |
137 | | -it =groups.floorEntry(x -1); |
138 | | -if (it !=null) { |
139 | | -ml =it.getKey(); |
140 | | -removeGroup(it.getKey(),it.getValue()); |
141 | | -groups.remove(it.getKey()); |
142 | | - } |
143 | | - } |
| 74 | +privatevoidupdate(BitSetset,BITbit,intn,inti,intv) { |
| 75 | +intpre =set.previousSetBit(i); |
| 76 | +if (pre == -1) { |
| 77 | +pre =set.previousSetBit(n); |
144 | 78 | } |
145 | | -// Process the right side of index x. |
146 | | -if (r !=x) { |
147 | | -groups.put(x +1,r); |
148 | | -addGroup(x +1,r); |
149 | | - }else { |
150 | | -if (x +1 <colors.length &&colors[x +1] !=colors[x]) { |
151 | | -it =groups.ceilingEntry(x +1); |
152 | | -if (it !=null) { |
153 | | -mr =it.getValue(); |
154 | | -removeGroup(it.getKey(),it.getValue()); |
155 | | -groups.remove(it.getKey()); |
156 | | - } |
157 | | - } |
| 79 | +intnext =set.nextSetBit(i); |
| 80 | +if (next == -1) { |
| 81 | +next =set.nextSetBit(0); |
158 | 82 | } |
| 83 | +bit.update(getIndex(next -pre +n -1,n) +1, -v); |
| 84 | +bit.update(getIndex(i -pre,n),v); |
| 85 | +bit.update(getIndex(next -i,n),v); |
| 86 | + } |
159 | 87 |
|
160 | | -// Merge the affected groups into one new group. |
161 | | -groups.put(ml,mr); |
162 | | -addGroup(ml,mr); |
| 88 | +privateintgetIndex(intindex,intmod) { |
| 89 | +intresult =index >=mod ?index -mod :index; |
| 90 | +returnindex <0 ?index +mod :result; |
163 | 91 | } |
164 | 92 |
|
165 | | -// Clears both BITs. This is done after processing all queries. |
166 | | -privatevoidclearAllBITs(intn) { |
167 | | -for (inti =0;i <=n +2; ++i) { |
168 | | -BITS[0].clear(i); |
169 | | -BITS[1].clear(i); |
| 93 | +privatestaticclassBIT { |
| 94 | +intn; |
| 95 | +int[]tree1; |
| 96 | +int[]tree2; |
| 97 | + |
| 98 | +BIT(intn) { |
| 99 | +this.n =n +1; |
| 100 | +tree1 =newint[n +1]; |
| 101 | +tree2 =newint[n +1]; |
170 | 102 | } |
171 | | - } |
172 | 103 |
|
173 | | -// Main function to handle queries on alternating groups. |
174 | | -publicList<Integer>numberOfAlternatingGroups(int[]colors,int[][]queries) { |
175 | | -TreeMap<Integer,Integer>groups =newTreeMap<>(); |
176 | | -intn =colors.length; |
177 | | -List<Integer>results =newArrayList<>(); |
178 | | -// Initialize alternating groups. |
179 | | -initializeGroups(colors,groups); |
180 | | -// Process each query. |
181 | | -for (int[]query :queries) { |
182 | | -if (query[0] ==1) { |
183 | | -// Type 1 query: count alternating groups of at least a given size. |
184 | | -intgroupSize =query[1]; |
185 | | -intans =processQueryType1(colors,groups,groupSize); |
186 | | -results.add(ans); |
187 | | - }else { |
188 | | -// Type 2 query: update the color at a given index. |
189 | | -intindex =query[1]; |
190 | | -intnewColor =query[2]; |
191 | | -processQueryType2(colors,groups,index,newColor); |
| 104 | +voidupdate(intsize,intv) { |
| 105 | +for (inti =size;i >0;i -=i & -i) { |
| 106 | +tree1[i] +=v; |
| 107 | +tree2[i] +=v *size; |
| 108 | + } |
| 109 | + } |
| 110 | + |
| 111 | +int[]query(intsize) { |
| 112 | +intcount =0; |
| 113 | +intsum =0; |
| 114 | +for (inti =size;i <n;i +=i & -i) { |
| 115 | +count +=tree1[i]; |
| 116 | +sum +=tree2[i]; |
192 | 117 | } |
| 118 | +returnnewint[] {count,sum}; |
193 | 119 | } |
194 | | -// Clear BITs after processing all queries. |
195 | | -clearAllBITs(n); |
196 | | -returnresults; |
197 | 120 | } |
198 | 121 | } |