2156.md (44361B)
1 Source: https://codeforces.com/blog/entry/147761 2 3 ### Thank you for participating ! 4 5 Special Thanks to [hxu10](/profile/hxu10 "Master hxu10") for giving me the chance to write the editorial and for [maomao90](/profile/maomao90 "International Grandmaster maomao90") for enhancing the editorial !. 6 7 Editorial of Problems E and F are written by hxu10, and the rest are written by me. I hope they're insightful and concise, please let me hear your opinion about it or any feedback in general 💙. 8 9 #### [2156A - Pizza Time](/contest/2156/problem/A "Codeforces Round 1061 (Div. 2)") 10 11 **Hints** 12 13 **Hint 1** 14 15 Since $m_1 \le m_2$, the total number of slices Alice ate is always at least as much as the total number of slices Bob ate. What's optimal construction ? 16 17 **Hint 2** 18 19 We want to try to minimize the difference between the total number of slices Alice ate and the total number of slices Bob ate. 20 21 **Hint 3** 22 23 The optimal construction is to let both $m_1$ and $m_2$ to be equals to one. The sequence of operations, denoted by $(m_1, m_2, m_3)$, is as follows: 24 25 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots $ 26 27 **Solution** 28 29 The general form of the sequence 30 31 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots $ 32 33 Note that we're considering the operations when $m_1 \le m_2 \le m_3$. 34 35 Consider the case where $n$ is even: 36 37 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots \rightarrow (1,1,2)$ 38 39 The number of operations is the length of the sequence ${2,4,6,\ldots, 2(\frac{n}{2}-1)}$ which is $\frac{n}{2}-1$. 40 41 Consider the case where $n$ is odd: 42 43 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots \rightarrow (1,1,1)$ 44 45 The number of operations is the length of the sequence ${1,3,5,7,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$ 46 47 By the representation of odd numbers we've ${2(0)+1,2(1)1+,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$ , which is equivalent to the length of ${0,1,2,\ldots, \frac{n-1}{2}-1}$ which gives the length of $\frac{n-1}{2}$. 48 49 Both cases are equivalent to the close form 50 51 $\left \lfloor \frac{n-1}{2} \right \rfloor$ 52 53 Complexity $\mathcal{O}(1)$. 54 55 **Implementation 1 (MathModel)** 56 57 ``` 58 from math import * 59 60 def solve(): 61 n=int(input()) 62 print((n-1)//2) 63 64 for _ in range(int(input())): 65 solve() 66 ``` 67 68 **Solution 2** 69 70 It's possible to use fair split that's we use $\lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor + n \bmod 3$ and keep simulating with $n=m_3$ on steps except the first step until you reach $m_2 \le 2$. 71 72 Complexity $\mathcal{O}(\log_3(n))$ 73 74 **Implementation 2 (MathModel)** 75 76 ``` 77 from math import * 78 79 def solve(): 80 n=int(input()) 81 a,b,c=n//3,n//3,n//3+(n%3) 82 ans=0 83 while(n>2): 84 ans+=n//3 85 n=n//3+(n%3) 86 print(ans) 87 88 for _ in range(int(input())): 89 solve() 90 ``` 91 92 **Rate The Problem !** 93 94 Great 95 96 Good 97 98 Neutral 99 100 Bad 101 102 Didn't Solve 103 104 #### [2156B - Strange Machine](/contest/2156/problem/B "Codeforces Round 1061 (Div. 2)") 105 106 **Hints** 107 108 **Hint 1** 109 110 What's the consuming part of processing the string of operations $s$ ? 111 112 **Hint 2** 113 114 If the string $s$ contained at least one $\mathtt{B}$ operation , What's the maximum count of iterations we're going to run so that $a=0$ ? 115 116 **Hint 3** 117 118 If the string $s$ contains $x$ copies of $\mathtt{B}$ then $a$ is guaranteed to be $a=0$ in at most $\mathcal{O}(\log_{2x} A)$ where $A=\max(a_1,a_2,\ldots ,a_n)$ , that's at most $\mathcal{O}(n \log_2 A) \sim \mathcal{O}(30n)$ operations are required . 119 120 **Hint 4** 121 122 How to manage too many appearances of $\mathtt{A}$ for efficiency ? 123 124 **Hint 5** 125 126 It's enough to handle the case where $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ that's the answer for query $a$ is $a$ because we're incrementing by 1 at each iteration ; otherwise the complexity becomes $\mathcal{O}(10^9q)$ for such cases which is slow. and the rest can be done in $\mathcal{O}(nq \log_2(10^9))$ which is safe according to the constraints. 127 128 **Solution 1 : O(nq log A)** 129 130 If you've one $\color{blue}{\mathtt{B}}$ in string $s$ , then you'll have to do operations in $\mathcal{O}(n\log_2(A))$ which is $\sim \mathcal{O}(20 \cdot 30)$ which is fine for $n \le 20$ and $\sum q \le 10^4$ , at worst case this is roughly $\mathcal{O}(6 \cdot 10^5)$ which is safe. 131 132 If we've a string $s$ that's all $\color{red}{\mathtt{A}}$ i.e. : 133 134 $s=\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ 135 136 then answer is simply for each $a_i$ is $a_i$ itself because we cannot do anything except just subtracting by $1$ many times ; otherwise the complexity becomes $\mathcal{O}(10^9q)$ for such cases which is slow. 137 138 Complexity $\mathcal{O}(nq \log_2(10^9))$. 139 140 **Implementation 1 (MathModel)** 141 142 ``` 143 def solve(): 144 n,q=map(int,input().split()) 145 s=input().strip() 146 a=list(map(int,input().split())) 147 A,B=s.count('A'),s.count('B') 148 for i in range(q): 149 if(B==0): 150 print(a[i]) 151 else: 152 ans=0 153 while(a[i]): 154 for j in s: 155 if(a[i]==0):break 156 ans+=1 157 if(j=='A'):a[i]-=1 158 else: a[i]//=2 159 print(ans) 160 161 for _ in range(int(input())): 162 solve() 163 ``` 164 165 **Bonus Hints** 166 167 **Hint 1** 168 169 Compress the string $s$ into sequence of "Move Blocks" that's for $s=\mathtt{AABBBABAAA}$ the sequence of moves will be 170 171 $\{[\mathtt{A},2],[\mathtt{B},3],[\mathtt{A},1],[\mathtt{B},1],[\mathtt{A},3]\}$ 172 173 **Hint 2** 174 175 Be careful in simulation 176 177 **Solution 2 (Bonus) : O(n+qlog^2 A)** 178 179 **Observation :** The consuming part of processing the operations where a segment of $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ because we're processing one by one which is inefficient and answering query will take $\mathcal{O}(nq \log_2(10^9))$ , why ? , because processing $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ operation-by-operation is slow , for example consider the sequence $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}} \color{blue}{\mathtt{B}}}_{}$ 180 181 This case will take $\mathcal{O}(nq \log_2(10^9))$ at worst case , which is inefficient. 182 183 A good way to optimize is by compress the blocks of same type of operations as $(\mathrm{type},\mathrm{count})$ that way all long blocks of $\color{red}{\mathtt{A}}$ will be performed much faster , For blocks of $\color{blue}{\mathtt{B}}$ it's already fast to process them in order because of $\mathcal{O}(\log_2(a))$ and it reduces $a$ to $0$ in $\mathcal{O}(\log_2(10^9)) \sim 30$ at most , However compressing the operations is still better to compose the operations. 184 185 That's we're going to process at most $\sim 60$ blocks , because if we started with $\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\ldots $ assuming $a=10^9$ , which is the worst case of the algorithm. 186 187 Now after composing the blocks as $(\mathrm{type},\mathrm{count})$ , you should iterate through them : 188 189 * If $s_i=\color{red}{\mathtt{A}}$ then we perform $a_i=a_i-\min(\mathrm{count},a_i)$ 190 * If $s_i=\color{blue}{\mathtt{B}}$ then we perform $\displaystyle a_i=\left \lfloor \frac{a_i}{\displaystyle 2^{\min(\text{count},\lceil \log_2(n) \rceil)}} \right \rfloor$ 191 192 make sure to update number of operations accordingly. 193 194 Complexity $\sim \mathcal{O}(n+q \log^2(10^9))$. 195 196 **Implementation 2 (MathModel)** 197 198 ``` 199 def solve(): 200 n,q=map(int,input().split()) 201 s=input() 202 a=list(map(int,input().split())) 203 A=s.count('A') 204 B=s.count('B') 205 last=s[0] 206 seq=[] 207 cur=1 208 for i in range(1,n): 209 if(s[i]==last): cur+=1 210 else: 211 seq.append([last,cur]) 212 cur=1 213 last=s[i] 214 if(cur!=0): seq.append([last,cur]) 215 if(B==0): 216 for i in a: print(i) 217 else: 218 for i in range(q): 219 ans=0 220 while(a[i]>0): 221 for j in seq: 222 if(a[i]==0): break 223 if(j[0]=='A'): 224 mn=min(j[1],a[i]) 225 ans+=mn 226 a[i]-=mn 227 else: 228 if a[i]==0: break 229 x=a[i] 230 p=0 231 while(x): 232 x//=2 233 p+=1 234 mn=min(p,j[1]) 235 ans+=mn 236 a[i]//=(2**mn) 237 print(ans) 238 239 for _ in range(int(input())): 240 solve() 241 ``` 242 243 **Rate The Problem !** 244 245 Great 246 247 Good 248 249 Neutral 250 251 Bad 252 253 Didn't Solve 254 255 #### [2156C - Maximum GCD on Whiteboard](/contest/2156/problem/C "Codeforces Round 1061 (Div. 2)") 256 257 **Hints** 258 259 **Hint 1** 260 261 You can do all the **Erase** operations before the **Split** operations. 262 263 **Proof** 264 265 Suppose there exists an optimal solution where you do an **Erase** operation on an element that was produced from a **Split** operation. You can instead do an **Erase** operation on the original element that it was being **Split** from, which will result in the whiteboard containing a subset of the elements in the optimal solution. Hence, it will have a beauty of at least as much as the optimal solution. 266 267 **Hint 2** 268 269 Fix a target gcd $g$. Which numbers can be made divisible by $g$ using the **Split** operation? 270 271 **Hint 3** 272 273 If $x$ is a multiple of $g$, we do not need any **Split** operation. If $x\ge 4g$, one split can result in two multiples of $g$ (discard the middle). 274 275 **Proof** 276 277 Split $x$ into $(g, g + x\bmod g, x - 2g - x\bmod g)$. Both $g$ and $x - 2g - x\bmod g$ are divisible by $g$. 278 279 * If $x \lt 5g$, $x - 2g - x\bmod g = 2g$. $g + x\bmod g \le 2g = x - 2g - x\bmod g$, hence, $x_1 \le x_2 \le x_3$ is satisfied. 280 * Otherwise, $x \ge 5g$. $x - 2g - x\bmod g \ge 5g - 2g - g = 2g \ge g + x\bmod g$, hence, $x_1 \le x_2 \le x_3$ is satisfied. 281 282 **Hint 4** 283 284 Conversely, if $x\lt 4g$ and $x$ is not divisible by $g$, you can’t make it good by splits → it must be erased. 285 286 **Proof** 287 288 We will prove this by strong induction. 289 290 Let $P_i$ be the statement: $i$ cannot be made divisible by $g$ using any number of splits if $i \lt 4g$ and $i$ is not divisible by $g$. 291 292 Base case: $P_1$ is true as $1$ cannot be split. 293 294 Suppose $P_i$ is true for all $i \lt K$ for some $K \ge 2$. We will prove that $P_K$ is also true. 295 296 If $K \ge 4g$ or $K$ is divisible by $g$, $P_K$ is vacuously true. From here on, we will assume that $K \lt 4g$ and $K$ is not divisible by $g$. 297 298 Suppose we split $K$ into $x_1\le x_2\le x_3 \lt K$. If either $x_1$ or $x_3$ is not divisible by $g$, $P_{x_1}$ and $P_{x_3}$ implies that they can never be made divisible by $g$ using any number of splits. Hence, if we want to make $K$ divisible by $g$, $x_1$ and $x_3$ have to both be divisible by $g$. 299 300 If $x_1 \ge 2g$, $x_3 \ge x_2 \ge x_1 \ge 2g$, which means that $K = x_1 + x_2 + x_3 \ge 2g + 2g + 2g = 6g$, which contradicts $K \lt 4g$. Hence, $x_1 = g$ is the only possibility. 301 302 * If $x_3 = g$, $x_1 \le x_2 \le x_3 \rightarrow g \le x_2 \le g$. Hence, $x_2 = g$ as well, and $K = x_1 + x_2 + x_3 = g + g + g = 3g$, contradicting that $K$ is not divisible by $g$. 303 * If $x_3 \ge 2g$, $K = x_1 + x_2 + x_3 \le g + g + 2g = 4g$, contradicting $K \lt 4g$. 304 305 Hence, it is not posible to make $K$ divisible by $g$ using any number of splits. 306 307 **Hint 5** 308 309 So $g$ is good if 310 311 $ \#\{x\ge 4g\}+\#\{x=g\}+\#\{x=2g\}+\#\{x=3g\}\ \ge\ n-k. $ 312 313 **Hint 6** 314 315 Count with a frequency array / map and a prefix sum for $g=1,2,\ldots ,n$ 316 317 **Solution** 318 319 We want the maximum gcd $g$ achievable after $\le k$ erases and any splits. 320 321 For a fixed $g$, the elements that won’t consume an erase are: 322 323 * all multiples of $g$ (already good), and 324 * any $x\ge 4g$ (can be made good via one split using the construction in hint 3). 325 326 Thus, the only "bad" numbers (that would have to be erased) are those with $x\lt 4g$ that are not multiples of $g$. Therefore $g$ is good if 327 328 $\text{good}(g)=\#\{x\ge 4g\}+\#\{x=g\}+\#\{x=2g\}+\#\{x=3g\}\ \ge\ n-k.$ 329 330 Since $1\le a_i\le n$, precompute a frequency array and prefix sums $p[v]=\sum_{u\le v}f[u]$. Then 331 332 $ \#\{x\ge 4g\}=n-p[\min(n,4g-1)]. $ 333 334 Iterate through $g=1,2,3,\ldots ,n$ and keep the largest good $g$. 335 336 Complexity : $\mathcal{O}(n)$. 337 338 **Implementation (MathModel)** 339 340 ``` 341 #include <bits/stdc++.h> 342 using namespace std; 343 #define int long long 344 345 void solve(){ 346 int n,k;cin>>n>>k; 347 vector<int>a(n),mp(n+1),p(n+1); 348 for(auto &i:a){ 349 cin>>i; 350 mp[i]++; 351 } 352 for(int i=1;i<=n;i++){ 353 p[i]=p[i-1]+mp[i]; 354 } 355 int ans=1; 356 for(int g=1;g<=n;g++){ 357 int t=min(n,4*g-1); 358 int good=n-p[t]; 359 if(g<=n)good+=mp[g]; 360 if(2*g<=n)good+=mp[2*g]; 361 if(3*g<=n)good+=mp[3*g]; 362 if(good>=n-k)ans=g; 363 } 364 cout<<ans<<"\n"; 365 } 366 367 signed main(){ 368 ios::sync_with_stdio(0); 369 cin.tie(0); 370 int t;cin>>t; 371 while(t--)solve(); 372 } 373 ``` 374 375 **Rate The Problem !** 376 377 Great 378 379 Good 380 381 Neutral 382 383 Bad 384 385 Didn't Solve 386 387 #### [2156D - Find the Last Number](/contest/2156/problem/D "Codeforces Round 1061 (Div. 2)") 388 389 **Hints** 390 391 **Hint 1** 392 393 We determine the $k$-th bit of $p_n$ for $k=0,1,\ldots,\lfloor\log_2 n\rfloor$. 394 395 **Hint 2** 396 397 Let $\text{bit}_k(i)$ denote the whether the $k$-th bit of $i$ is zero or one. How can we determine the $k$-th bit of $p_n$, i.e. $\text{bit}_k(p_n)$, from $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$? 398 399 **Hint 3** 400 401 $ \sum_{k=0}^{\lfloor \log_2(n) \rfloor} \left \lceil \frac{n-1}{2^k} \right \rceil =n-1 + \left \lceil \frac{n-1}{2} \right \rceil + \left \lceil \frac{n-1}{4} \right \rceil + \left \lceil \frac{n-1}{8} \right \rceil+\ldots \lt 2n $ 402 403 How can we achieve this halving? 404 405 **Solution** 406 407 Recall from Hint 2 that $\text{bit}_k(i)$ is defined as $k$-th bit of the integer $i$. A naive solution using $n\log_2 n$ queries is as follows: 408 409 * Compute $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$ for all $k=0,1,\ldots,\lfloor\log_2 n\rfloor$. 410 411 + $\text{bit}_k(p_i)$ can be computed with a single query $p_i \ \mathtt{AND} \ 2^k$ ($1\le i\le n - 1$). 412 * If $\text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) = \text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$, it means that the $k$-th bit of $p_n$ is zero. Otherwise, it is one. 413 414 + This works due to the fact that $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1}) = \text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) - \text{bit}_k(p_n)$. 415 416 To optimise this, we will half the search space after each step. Starting from $k = 0$, we still use $n - 1$ queries to calculate $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$. After using this to determine the value of the $0$-th bit of $p_n$, we can discard all $p_i$ that has a different $0$-th bit from $p_n$. 417 418 More formally, let $S_0$ denote the set of elements $i$ such that $i$ has the same $0$-th bit as $p_n$, and $P_0$ denote the set of elements $i$ ($1\le i\le n - 1$) such that $p_i$ has the same $0$-th bit as $p_n$. $\sum_{i\in P_0} \text{bit}_1(p_i) = \left(\sum_{i\in S_0} \text{bit}_1(i)\right) - \text{bit}_1(p_n)$, so the $1$-st bit of $p_n$ is zero if $\sum_{i\in P_0} \text{bit}_1(p_i) = \sum_{i\in S_0} \text{bit}_1(i)$. 419 420 In general, we can let $S_k$ denote the set of elements $i$ such that $i$ has the same $0$-th, $1$-st, $\ldots$ , $k$-th bit as $p_n$, and $P_k$ denote the set of elements $i$ ($1\le i\le n - 1$) such that $p_i$ has the same $0$-th, $1$-st, $\ldots$ , $k$-th bit as $p_n$. Then, the $k$-th bit of $p_n$ is zero if $\sum_{i\in P_{k-1}} \text{bit}_k(p_i) = \sum_{i\in S_{k-1}} \text{bit}_k(i)$. 421 422 Observe that $|P_k| \le \left\lceil \frac{|P_{k - 1}|}{2} \right\rceil$ for all $k\ge 1$. Hence, the total number of queries used is 423 424 $n - 1 + \sum_{k=1}^{\lfloor \log_2(n) \rfloor} |P_{k - 1}| \le n-1 + \left \lceil \frac{n-1}{2} \right \rceil + \left \lceil \frac{n-1}{4} \right \rceil + \left \lceil \frac{n-1}{8} \right \rceil+\ldots \lt 2n$ 425 426 **Implementation (hxu10)** 427 428 ``` 429 def query(index,num): 430 print("?",index,num) 431 return int(input()) 432 433 def main(): 434 n = int(input()) 435 rest = set() 436 likely = set() 437 for i in range(1,n): 438 rest.add(i) 439 for i in range(1,n+1): 440 likely.add(i) 441 D = len(bin(n)[2:]) 442 ans = 0 443 for d in range(D): 444 index_0 = set() 445 index_1 = set() 446 likely_0 = set() 447 likely_1 = set() 448 for index in rest: 449 res = query(index, 1<<d) 450 if res == 0: 451 index_0.add(index) 452 else: 453 index_1.add(index) 454 zeros = 0 455 ones = 0 456 for num in likely: 457 if num & (1<<d): 458 ones += 1 459 likely_1.add(num) 460 else: 461 zeros += 1 462 likely_0.add(num) 463 if zeros == len(index_0): 464 ans += 1 << d 465 rest = index_1 466 likely = likely_1 467 elif ones == len(index_1): 468 rest = index_0 469 likely = likely_0 470 else: 471 print("Error") 472 return 473 print("!",ans) 474 475 T = int(input()) 476 t = 1 477 while t <= T: 478 main() 479 t += 1 480 ``` 481 482 **Rate The Problem !** 483 484 Great 485 486 Good 487 488 Neutral 489 490 Bad 491 492 Didn't Solve 493 494 #### [2156E - Best Time to Buy and Sell Stock](/contest/2156/problem/E "Codeforces Round 1061 (Div. 2)") 495 496 **Hints** 497 498 **Hint 1** 499 500 Consider the simplified version of the game where Alex moves first. 501 502 **Hint 1.1** 503 504 Suppose Alex wants to ensure a beauty of at least $g$ (the goal), while Hao tries to keep it below $g$. Which indices should Alex lock to achieve this goal? 505 506 **Hint 1.2** 507 508 We can binary search on the goal $g$. 509 510 **Hint 1.3** 511 512 For a given $g$ and an index $i$, we define $f_g(a, i)$ as the number of indices $j\neq i$ satisfying $a_{\max(i, j)} - a_{\min(i, j)} \ge g$. 513 514 If there exists an index $i$ such that $f_g(a, i) \ge 2$, then Alex can lock index $i$ on the first move. No matter which index Hao removes next, there will still exist at least one $j$ such that $|a_i - a_j| \ge g$. Thus, Alex can secure that pair and guarantee a beauty of at least $g$. 515 516 **Hint 1.4** 517 518 If $f_g(a, i) \le 1$ for all indices $i$, Alex cannot achieve his goal. Whichever index $i$ Alex locks first, Hao can remove the single $j$ such that $|a_i - a_j| \ge g$. Hence, Alex will never be able to lock two indices with a difference $\ge g$, and the resulting beauty will be strictly less than $g$. 519 520 **Hint 2** 521 522 Now return to the original problem, where Hao moves first. 523 524 To keep the final beauty below $g$, Hao must remove an index such that after the removal, $f_g(a, i) \lt 2$ for all $i$. Otherwise, Alex will have a winning move as shown in Hint 1.3. 525 526 **Hint 3** 527 528 For each $i$, we only need to track whether $f_g(a, i)$ is $0$, $1$, $2$, or greater than $2$. This is because if there are any index $i$ with $f_g(a, i) \gt 2$, Hao has to remove index $i$ on his first move. Otherwise, we will have $f_g(a, i) \ge 2$ after Hao's first move, allowing Alex to have a beauty of at least $g$ as mentioned in Hint 2. 529 530 This observation allows us to compute $f_g(a, i)$ efficiently. 531 532 **Solution** 533 534 Read the above hints before continuing. 535 536 As noted in Hint 1.2, we can binary search on the target beauty $g$. 537 538 For each index $1 \le i \le n$, recall that $f_g(a, i)$ is the number of indices $j\neq i$ satisfying $a_{\max(i, j)} - a_{\min(i, j)} \ge g$. 539 540 As mentioned in Hint 3, we only care whether $f_g(a, i)$ is $0$, $1$, $2$, or greater than $2$. We iterate through $i = 1, \ldots, n$, and maintain the three smallest previous values $a_j$ (for $j \lt i$). For each of these, we check whether the condition holds and increment both $f_g(a, i)$ and $f_g(a, j)$ if it does. This leads to an $\mathcal{O}(3n) = \mathcal{O}(n)$ computation per $g$. 541 542 We simulate each possible first move $p$ by Hao. Let array $b$ be array $a$ after removing index $p$. When Hao removes index $p$, only the $f_g(a, p)$ indices $q$ satisfying $|a_p - a_q| \ge g$ will have their $f_g(b, q) = f_g(a, q) - 1$, while all others remain unchanged. 543 544 Hao succeeds in keeping the beauty below $g$ if and only if removing index $p$ results in all $f_g(b, i) \le 1$. Equivalently, the indices $q$ paired with $p$ must include all indices that initially had $f_g(a, i) = 2$. 545 546 If no such removal $p$ works, Alex can achieve his goal of keeping the beauty at least $g$. 547 548 Checking each first move $p$ requires $\mathcal{O}(f_g(a, p))$ time, and summing up over $\sum_{1\le p\le n} f_g(a, p) \le 2(3n) = \mathcal{O}(n)$ since we only maintain at most three previous values of $a_j$ (for $j \lt i$) during the calculation of $f_g(a, i)$. 549 550 The total time complexity is $\mathcal{O}(n \log_2 10^9)$ since we perform a binary search over $g$ and compute $f_g(a, i)$ in linear time per iteration. 551 552 **Implementation (hxu,PyPy)** 553 554 ``` 555 def main(): 556 n = int(input()) 557 arr = list(map(int,input().split())) 558 559 # calculate the number of j for each i that satisfy arr[max(i,j)] - arr[min(i,j)] >= target 560 def measurecount(arr,target): 561 m = len(arr) 562 count = [0]*m 563 minimum = [] 564 for i in range(m): 565 for j in range(len(minimum)): 566 if minimum[j] + target <= arr[i]: 567 count[i] += 1 568 minimum.append(arr[i]) 569 minimum.sort() 570 if len(minimum) > 3: 571 minimum.pop() 572 maximum = [] 573 for i in range(m-1,-1,-1): 574 for j in range(len(maximum)): 575 if maximum[j] - target >= arr[i]: 576 count[i] += 1 577 maximum.append(arr[i]) 578 maximum.sort(reverse=True) 579 if len(maximum) > 3: 580 maximum.pop() 581 return count 582 583 # binary search to judge if we can find such pair 584 def judge(target): 585 count = measurecount(arr,target) 586 if max(count) <= 1: 587 return False 588 pick = [] 589 if max(count) > 2: 590 for i in range(n): 591 if count[i] > 2: 592 pick = [i] 593 break 594 else: 595 for i in range(n): 596 if count[i] != 2: 597 continue 598 for j in range(n): 599 if j==i: 600 pick.append(j) 601 elif j < i and arr[j] + target <= arr[i]: 602 pick.append(j) 603 elif j > i and arr[i] + target <= arr[j]: 604 pick.append(j) 605 break 606 607 for p in pick: 608 count2 = measurecount(arr[:p]+arr[p+1:], target) 609 if max(count2) <= 1: 610 return False 611 return True 612 613 front = -10**9 - 10 614 rear = 10**9 + 10 615 while front < rear: 616 mid = front + (rear-front)//2 617 res = judge(mid) 618 if res: 619 front = mid + 1 620 else: 621 rear = mid 622 ans = front - 1 623 print(ans) 624 625 T = int(input()) 626 t = 1 627 while t <= T: 628 main() 629 t += 1 630 ``` 631 632 **Implementation (maomao90,C++)** 633 634 ``` 635 #include "bits/stdc++.h" 636 using namespace std; 637 638 const int MAXN = 200005; 639 const int INF = 1000000005; 640 641 inline int fdiv(int num, int denom) { 642 return num / denom - ((num ^ denom) < 0 && num % denom); 643 } 644 inline int cdiv(int num, int denom) { return fdiv(num + denom - 1, denom); } 645 646 int t; 647 int n; 648 int a[MAXN]; 649 650 vector<int> adj[MAXN]; 651 void add_edge(int u, int v) { 652 adj[u].push_back(v); 653 adj[v].push_back(u); 654 } 655 bool check(int x) { 656 for (int i = 1; i <= n; i++) { 657 adj[i].clear(); 658 } 659 set<pair<int, int>> st; 660 for (int i = 1; i <= n; i++) { 661 int cnt = 0; 662 for (auto [prv, prv_id] : st) { 663 if (a[i] - prv >= x) { 664 add_edge(prv_id, i); 665 } 666 } 667 st.insert({a[i], i}); 668 if ((int) st.size() > 3) { 669 st.erase(prev(st.end())); 670 } 671 } 672 673 int bad_cnt = 0; 674 for (int i = 1; i <= n; i++) { 675 if ((int)adj[i].size() >= 2) { 676 bad_cnt++; 677 } 678 } 679 for (int i = 1; i <= n; i++) { 680 int delta = (int)adj[i].size() >= 2; 681 for (int v : adj[i]) { 682 if (adj[v].size() == 2) { 683 delta++; 684 } 685 } 686 if (delta == bad_cnt) { 687 return false; 688 } 689 } 690 return true; 691 } 692 693 int main() { 694 cin >> t; 695 while (t--) { 696 cin >> n; 697 for (int i = 1; i <= n; i++) { 698 cin >> a[i]; 699 } 700 int lo = -INF, hi = INF; 701 while (lo < hi) { 702 int mid = cdiv(lo + hi, 2); 703 if (check(mid)) { 704 lo = mid; 705 } else { 706 hi = mid - 1; 707 } 708 } 709 cout << lo << '\n'; 710 } 711 return 0; 712 } 713 ``` 714 715 **Rate The Problem !** 716 717 Great 718 719 Good 720 721 Neutral 722 723 Bad 724 725 Didn't Solve 726 727 #### [2156F1 - Strange Operation (Easy Version)](/contest/2156/problem/F1 "Codeforces Round 1061 (Div. 2)") 728 729 **hxu10's Solution** 730 731 **Hints** 732 733 **Hint 1** 734 735 What will the first element of permutation be for the final result? 736 737 **Hint 2** 738 739 If the first element is odd, we can always reduce it to $1$, otherwise, we can always reduce it to $2$. 740 741 **Hint 3** 742 743 If the first element is even, before reducing the first element to $2$, we must reduce some element to $1$ at first. Which one to choose? 744 745 **Hint 4** 746 747 You should choose the leftmost odd elements that all elements to the left is greater than it. 748 749 **Hint 5** 750 751 Treat the rest of elements as a new permutation 752 753 **Solution** 754 755 Since we need to find the lexicographically smallest permutation, our goal is to make the numbers on the left as small as possible. 756 757 Suppose we have a permutation $[p_1, p_2, \ldots , p_n]$. 758 The first question we would like to answer is: where will the number $1$ appear in the final lexicographically smallest permutation? 759 760 **Case 1: $p_1$ is odd.** 761 762 In this case, the answer is straightforward — $p_1$ can always be decreased to $1$. Hence, $1$ will appear at the first position. 763 764 **Case 2: $p_1$ is even.** 765 766 This case is more complicated. For a number $p_i$ to be reduced to $1$, two conditions must hold: 767 768 1. $p_i$ is odd. 769 2. All numbers $1, 2, \ldots, p_i - 1$ appear to the right of index $i$. 770 In other words, for every $j \lt i$, we must have $p_j \gt p_i$. 771 772 We find the minimum possible index $i$ that satisfies both of the above condition, and reduce $p_i$ to $1$. 773 After that, since $p_1$ is even, we reduce $p_1$ to $2$. 774 775 It can be proven that choosing the smallest such index $i$ and performing these two reductions, first decreasing $p_i$ to $1$, then decreasing $p_1$ to $2$, will always yield the lexicographically smallest permutation. A formal proof will be given later. 776 777 **Recursive construction:** 778 779 * If $p_1$ is odd, reducing $p_i$ to $1$ transforms the remaining multiset $[p_2, p_3, \ldots , p_n]$ into $[2, 3, \ldots, n]$. This can be treated as a new permutation problem of size $n - 1$. 780 * If $p_1$ is even, after reducing $p_i$ to $1$ and $p_1$ to $2$, 781 the remaining multiset $[p_2, p_3, \ldots, p_{i-1}, p_{i+1}, \ldots, p_n]$ becomes $[3, 4, \ldots, n]$, which again forms a smaller permutation problem of size $n - 2$. 782 783 Thus, the process can be applied recursively. 784 785 **Complexity Analysis:** 786 787 The overall time complexity is $\mathcal{O}(n^2)$, which is efficient enough to pass the first subtask (F1). 788 789 **Proof** 790 791 Now let's prove that this solution always lead the permutation to smallest lexigraphically possible. 792 793 Suppose we have permutation $[p_1, p_2, \ldots, p_n]$ 794 795 When $p_1$ is odd, the conclusion is straightforward. We can always decrease $p_1$ to $1$ and treat the remaining elements as a new permutation. 796 797 When $p_1$ is even, let $i$ be the minimum possible index such that $p_i$ can be decreased to $1$. In other words, $i$ is the smallest index such that $\min(p_1, p_2, \ldots, p_{i - 1}) \gt p_i$ and $p_i$ is odd. We need to prove that decreasing $p_i$ ($1 \lt i \le n$) to $1$ does not affect the lexicographically smallest possible prefix $[p_1, p_2, \ldots, p_{i-1}]$ that can be formed. 798 799 Transforming $[p_1, p_2, \ldots, p_{i-1}]$ into its lexicographically smallest possible form involves three types of operations. Suppose an operation chooses indices $x \lt y \lt z$ and performs the following steps: 1) item subtract $2$ from $p_x$, 2) add $1$ to $p_y$, and 3) add $1$ to $p_z$. 800 801 We analyze each possible case relative to $i$: 802 803 Case 1: $x \lt y \lt z \lt i$ 804 805 * This case is trivial. Changing $p_i$ to $1$ only affects indices greater than $i$, so these operations remain completely valid. 806 807 Case 2: $x \lt y \lt i \lt z$ 808 809 * Suppose $p_z$ is within the subarray $[p_i, \ldots, p_n]$. After changing $p_i$ to $1$, the element $p_z$ (or its value) still exists, perhaps at a different position, but the multiset of values in $[p_i, \ldots, p_n]$ remains unchanged. Therefore, the operation can still be performed. 810 811 Case 3: $x \lt i \lt y \lt z$ 812 813 * Since the operation does not depend on the relative order or values of $p_y$ and $p_z$, and the multiset $[p_i, \ldots, p_n]$ is preserved, we can still find suitable $p_y$ and $p_z$ to perform the operation. Hence, this case also remains valid. 814 815 Case 4: $y = i$ or $z = i$ 816 817 * If $p_i \gt 1$, then after decreasing $p_i$ to $1$, there must exist some index $j \gt i$ such that $p_j$ equals the original value of $p_i$. Thus, the operation can still be performed using $p_j$. 818 * If $p_i = 1$, then it is impossible for any $j \lt i$ to have $p_j = 1$, as that would violate the rule of minimality. This is precisely why we must choose the smallest possible index $i$ for which $p_i$ can be reduced to $1$; otherwise, the prefix could incorrectly contain $1$. 819 820 Therefore, if there exists a sequence of operations that transforms $[p_1, p_2, \ldots, p_{i-1}]$ into the lexicographically smallest possible prefix, none of these operations will be affected by decreasing $p_i$ to $1$ beforehand. 821 822 Hence, we can always decrease $p_i$ to $1$ without affecting the lexicographically smallest prefix. 823 824 **Implementation (PyPy)** 825 826 ``` 827 def main(): 828 n = int(input()) 829 p = list(map(int,input().split())) 830 for i in range(n): 831 p[i] -= 1 832 seq = [] 833 indexes = [i for i in range(n)] 834 def update(indexes): 835 count = 0 836 for i in range(n): 837 if indexes[i] < 0: continue 838 indexes[i] = count 839 count += 1 840 curr = 1 841 ans = [-1]*n 842 for i in range(n): 843 if ans[i] > 0: 844 continue 845 if indexes[p[i]] % 2 == 0: 846 ans[i] = curr 847 curr += 1 848 indexes[p[i]] = -1 849 update(indexes) 850 continue 851 prefix = p[i] 852 pick = -1 853 for j in range(i+1,n): 854 if ans[j] > 0: 855 continue 856 if p[j] > prefix or indexes[p[j]] % 2 > 0: 857 prefix = min(prefix,p[j]) 858 continue 859 pick = j 860 break 861 ans[j] = curr 862 curr += 1 863 ans[i] = curr 864 curr += 1 865 indexes[p[j]] = -1 866 indexes[p[i]] = -1 867 update(indexes) 868 print(*ans) 869 T = int(input()) 870 for _ in range(T): 871 main() 872 ``` 873 874 **Tester's Solution** 875 876 **Hints** 877 878 **Hint 1** 879 880 Each move only shuffles the triple of **consecutive values** ${a,a+1,a+2}$ and places the **smallest** among them at the **leftmost** of the three chosen positions. 881 882 **Hint 2** 883 884 Think in terms of a value’s **rank** among the not-yet-fixed values: one move on a value is like moving it **two places to the left** in that order. A value at rank $r$ can move at most $\lfloor r/2\rfloor$ steps. 885 886 **Hint 3** 887 888 To minimize lexicographically, process positions from left to right and push the current choice as far left as allowed. Parity matters: when the current rank is odd, you must “pair” with a smaller value to make the plan realizable. 889 890 **Solution** 891 892 We want the lexicographically smallest permutation reachable by the triple move. Focus on the **first position** : 893 894 * If the first value is **odd**, we can keep applying moves that reduce it by $2$ until it becomes **$1$**. 895 * If it is **even**, we can keep reducing by $2$ until it becomes **$2$**. 896 897 Why? Each move that subtracts $2$ from some position $i$ uses two positions $j,k$ to its right that currently hold the two consecutive values just below it. In a permutation these exist until you reach $1$ (odd start) or $2$ (even start). Using them only increases those right-side values by $1$, so they never block making the first value as small as parity allows. 898 899 Now suppose the first value is even and we set it to $2$. The next question is: **where should $1$ go?** The correct choice is the **leftmost** value that can be reduced to $1$. 900 901 Two simple facts characterize when a value $v$ can be reduced to a target $cnt$: 902 903 1. **Parity:** moves change a value by $\pm 2$ overall, so $v \equiv cnt \pmod 2$ is necessary. 904 2. **No smaller blockers to the left:** to reduce $v$ down step by step, for each intermediate step you must pick the pair ${x,x+1}$ with $x \in {cnt,cnt+1,\dots,v-1}$ to the **right** of $v$. So $v$ must lie to the **left** of **all** values in $[cnt, v-1]$. 905 906 This gives a clean greedy: at step $cnt=1,2,\dots,n$, among values $i\in[cnt\ldots n]$, scan by increasing $i$ and keep the running **minimum position** seen so far. Every time that minimum improves (a “record minimum”), if $i \equiv cnt \pmod 2$ then value $i$ is feasible to reduce to $cnt$; among all feasible ones, the final record minimum is **leftmost** and is the one we must take. 907 908 Why lexicographically optimal? The array first differs where we place $cnt$. Picking the **leftmost feasible** position ensures the smallest possible number at that index. Any alternative that puts $cnt$ strictly to the right makes the prefix strictly larger and cannot be beaten later. 909 910 After choosing the index `cur` where we install $cnt$, we conceptually “pull down” the current value $val=p[cur]$ to $cnt$ by a chain of moves. Each such move also raises exactly one of the values in ${cnt,\ldots,val-1}$ by $1$. Over the whole chain, **every** number in ${cnt,\dots,val-1}$ gets raised exactly once. So, in one shot, we can **set** $p[cur]=cnt$ and **increase** all values in $[cnt \ldots val-1]$ by $1$. The remaining numbers still form a permutation of ${cnt+1,\dots,n}$, and we repeat with $cnt+1$. 911 912 Because each step is just a linear scan over values and a few local updates, this runs in $\mathcal{O}(n^2)$ per test. 913 914 **Implementation (C++)** 915 916 ``` 917 #include <iostream> 918 #include <vector> 919 #include <algorithm> 920 #include <numeric> 921 #include <tuple> 922 #include <map> 923 #include <set> 924 #include <deque> 925 #include <queue> 926 #include <functional> 927 #include <cassert> 928 #include <immintrin.h> 929 930 using namespace std; 931 932 #define int long long 933 934 int p[100005]; 935 int pos[100005]; 936 937 signed main() 938 { 939 #if _LOCAL_ 940 freopen("case.txt", "r", stdin); 941 #endif 942 943 int t; 944 cin >> t; 945 946 while(t--) { 947 int n; 948 cin >> n; 949 for(int i = 0; i < n; ++i) { 950 cin >> p[i]; 951 } 952 for(int i = 0; i < n; ++i) { 953 pos[p[i]] = i; 954 } 955 for(int cnt = 1; cnt <= n; ++cnt) { 956 int cur = n; 957 for(int i = cnt, mn = n; i <= n; ++i) { 958 if(pos[i] < mn) { 959 mn = pos[i]; 960 if((i & 1) == (cnt & 1)) { 961 cur = pos[i]; 962 } 963 } 964 } 965 int val = p[cur]; 966 p[cur] = cnt; 967 for(int i = cnt; i < val; ++i) { 968 p[pos[i]]++; 969 } 970 for(int i = val; i > cnt; --i) { 971 pos[i] = pos[i-1]; 972 } 973 pos[cnt] = cur; 974 } 975 for(int i = 0; i < n; ++i) { 976 cout << p[i] << ' '; 977 } 978 cout << endl; 979 } 980 981 return 0; 982 } 983 ``` 984 985 **MathModel's Solution (Bonus/Challenge)** 986 987 **Hints** 988 989 **Hint 1** 990 991 A move is only possible on three consecutive values: there must exist an $m$ such that the values involved are exactly ${m,m+1,m+2}$ at indices $i\lt j\lt k$. 992 993 **Hint 2** 994 995 $p_i=\max(p_j,p_k)+1$ and $p_i=\min(p_j,p_k)+2$ 996 997 Those equations force the three values to be consecutive and the largest to sit at the leftmost index, which is exactly $c\lt \min(a,b)$ with values ${m,m+1,m+2}$. 998 999 **Hint 3** 1000 1001 Each move strictly decreases lexicographic order: the first changed index is $i=c$, whose value drops from $m+2$ to $m$; earlier indices remain unchanged. 1002 1003 **Hint 4** 1004 1005 Each move removes at least two inversions among the triple (and never adds inversions before $i$), so the process is acyclic and must terminate. 1006 1007 **Hint 5** 1008 1009 Number of operations is $\le \mathcal{O}(n^2)$ (each removes $\ge2$ inversions). The pointer-walk advances by $+1$ when no operations, and jumps back by at most $2$ per op. Total steps are $\mathcal{O}(n+\text{ops})=\mathcal{O}(n^2)$ overall. 1010 1011 **Solution** 1012 1013 **Please Read Hints** 1014 1015 Maintain $pos[v]$. Iterate $m$ from $0$ to $n-3$: 1016 1017 * Let 1018 1019 $ a=pos[m],\quad b=pos[m+1],\quad c=pos[m+2]. $ 1020 1021 * If $c\lt \min(a,b)$, apply the operation on indices ${a,b,c}$: 1022 1023 + Set $i=c$, $j=\min(a,b)$, $k=\max(a,b)$. 1024 + If $a\lt b$, write $(m,m+1,m+2)$ to $(i,j,k)$ and set $(pos[m],pos[m+1],pos[m+2])=(i,j,k)$. 1025 + Else write $(m,m+2,m+1)$ to $(i,j,k)$ and set $(pos[m],pos[m+2],pos[m+1])=(i,j,k)$. 1026 + Then set $m\leftarrow\max(m-2,0)$. 1027 * Otherwise, set $m\leftarrow m+1$. 1028 1029 This process terminates when $m=n-2$, at which point every triple satisfies $pos[m+2]\ge\min(pos[m],pos[m+1])$, so no legal move exists anywhere. Because each step is lexicographically decreasing (when an operation is performed) and the space of permutations is finite and acyclic under these moves, the result is the lexicographically smallest reachable permutation. The pointer-walk guarantees total time $\mathcal{O}(n^2)$. 1030 1031 **Challenge: Can you prove the solution?** 1032 1033 **Implementation** 1034 1035 ``` 1036 for _ in range(int(input())): 1037 n=int(input()) 1038 p=list(map(int,input().split())) 1039 pos=[0]*n 1040 for i in range(n): 1041 pos[p[i]-1]=i 1042 ch=1 1043 while ch: 1044 ch=0 1045 for m in range(n-2): 1046 a,b,c=pos[m],pos[m+1],pos[m+2] 1047 if(c<min(a,b)): 1048 i=c 1049 if(a<b): 1050 j,k=a,b 1051 p[i],p[j],p[k]=m+1,m+2,m+3 1052 pos[m],pos[m+1],pos[m+2]=i,j,k 1053 else: 1054 j,k=b,a 1055 p[i],p[j],p[k]=m+1,m+3,m+2 1056 pos[m],pos[m+2],pos[m+1]=i,j,k 1057 ch=1 1058 print(*p) 1059 ``` 1060 1061 **Rate The Problem !** 1062 1063 Great 1064 1065 Good 1066 1067 Neutral 1068 1069 Bad 1070 1071 Didn't Solve 1072 1073 #### [2156F2 - Strange Operation (Hard Version)](/contest/2156/problem/F2 "Codeforces Round 1061 (Div. 2)") 1074 1075 **Hints** 1076 1077 **Hint 1** 1078 1079 Suppose the operation changes indices $i, j, k$, other than $i$, all the other indices relative position doesn't change. 1080 1081 **Hint 2** 1082 1083 Use segment tree and fenwick tree 1084 1085 **Hint 3** 1086 1087 Iterate from $1$ to $n$, during the $t$-th iteration, find the leftmost element that can be decreased by $t$. 1088 1089 **Hint 4** 1090 1091 Acclerate the procedure by finding next smaller element. 1092 1093 **Solution** 1094 1095 **You should Read Editorial of F1 First** 1096 1097 Let the initial permutation be $p=(p_1,p_2,\dots,p_n)$, and let the final array be $q=(q_1,q_2,\dots,q_n)$. Initialize $q_i=0$ for all $i$, meaning every position in the output is still undetermined. During the $t$-th iteration, find the smallest index $i$ whose value can be decreased to $t$. Repeatedly choose this $i$, locate indices $j,k$ such that $p_i=\max(p_j,p_k)+1$ and $p_i=\min(p_j,p_k)+2$, and perform the updates $p_i\leftarrow p_i-2$, $p_j\leftarrow p_j+1$, $p_k\leftarrow p_k+1$. This is equivalent to removing $p_i$ and setting $q_i\gets t$. After removing $p_i$, the remaining elements $p_1,\dots,p_{i-1},p_{i+1},\dots,p_n$ close the gap (preserving relative order), forming a permutation of length $n-1$. 1098 1099 This remove-and-assign simulation can be supported by a Fenwick tree or a segment tree so that each update and query runs in $\mathcal{O}(\log n)$ time; however, naively finding the correct index $i$ could still cost $\mathcal{O}(n)$ per step. Define the rank of $p_i$ as the number of alive (not yet removed) elements that are not greater than $p_i$, including $p_i$ itself. 1100 1101 To speed up the process, keep a pointer at the smallest alive index $i$ and check its rank. If the rank is odd, remove this element immediately. If the rank is even, move the pointer to the next smaller element to its right, that is, to the smallest $ j \gt i$ with $p_j \lt p_i$. Continue until you reach an element with odd rank. 1102 1103 Although a single "move to the next smaller on the right" step may look linear, the total number of such moves over the whole algorithm is at most $2n$. If an element is first visited when its rank is even, after some element to its right is removed, its rank becomes odd the next time it is visited; if an element’s rank is already odd, it is removed immediately upon visit. Therefore each index is visited at most twice. 1104 1105 To implement this, we maintain two data structures: 1106 1107 1. A Fenwick tree over values, where a $1$ at position $p_i$ indicates that the value $p_i$ is still alive (and $0$ otherwise). This lets you query the current rank of $p_i$ in $\mathcal{O}(\log n)$ time. 1108 2. Let $ip$ denote the array that is the inverse of $p$, i.e., $ip_{p_i} = i$. Store a range-min segment tree over the array $ip$ . When the value $p_i$ is removed, set $ip_{p_i}=\infty$. If the current visited index is $i$, then a range-min query on $[1,p_i-1]$ returns the minimum position $j$ such that $j \gt i$ and $p_j \lt p_i$ (the next smaller element on the right by value). Each query and update costs $\mathcal{O}(\log n)$, and each index is examined at most twice, so the overall complexity is $\mathcal{O}(n\log n)$, which is sufficient for the F2 constraints. 1109 1110 **Implementation (hxu10,PyPy)** 1111 1112 ``` 1113 inf = 10**9 1114 1115 class fenwick(object): 1116 def __init__(self, n): 1117 self.n = n 1118 self.cul = [0]*n 1119 self.maxd = len(bin(n))-3 1120 def update(self,index,diff): 1121 i = index 1122 while i<self.n: 1123 self.cul[i] += diff 1124 i += (i+1)&(-i-1) 1125 def getaccu(self,index): 1126 output = 0 1127 i = index 1128 while i>=0: 1129 output += self.cul[i] 1130 i -= (i+1)&(-i-1) 1131 return output 1132 1133 class segment_tree(object): 1134 def merge(self,num,accu): 1135 return min(accu,num) 1136 def __init__(self,n,initial): 1137 self.n = n 1138 self.inf = inf 1139 self.arr = [self.inf]*(2*n) 1140 for i in range(2*n-1,0,-1): 1141 if i>=n: self.arr[i] = initial[i-n] 1142 else: self.arr[i] = self.merge(self.arr[2*i],self.arr[2*i+1]) 1143 1144 def update(self,index,target): 1145 index += self.n 1146 self.arr[index] = target 1147 while index > 0: 1148 if index & 1: 1149 nexttarget = self.merge( self.arr[index], self.arr[index-1]) 1150 else: 1151 nexttarget = self.merge( self.arr[index], self.arr[index+1]) 1152 self.arr[index>>1] = nexttarget 1153 index = index >> 1 1154 1155 def addnum(self,index,diff): 1156 self.update(index, self.arr[index+self.n] + diff) 1157 1158 def query(self,left,right): 1159 i,j = self.n+left, self.n+right+1 1160 output = self.inf # initial output should be changed if you want to change the merge function 1161 while i<j: 1162 if i&1: 1163 output = self.merge(self.arr[i],output) 1164 i += 1 1165 if j&1: 1166 j -= 1 1167 output = self.merge(self.arr[j],output) 1168 i = i >> 1 1169 j = j >> 1 1170 return output 1171 1172 def main(t): 1173 n = int(input()) 1174 p = list(map(int,input().split())) 1175 location = [0]*n 1176 for i in range(n): 1177 p[i] -= 1 1178 location[p[i]] = i 1179 seg = segment_tree(n, location) 1180 fen = fenwick(n) 1181 for i in range(n): 1182 fen.update(i,1) 1183 ans = [-1]*n 1184 curr = 1 1185 for i in range(n): 1186 if ans[i] >= 0: 1187 continue 1188 index = fen.getaccu(p[i]) - 1 1189 if index % 2 == 0: 1190 fen.update(p[i],-1) 1191 seg.update(p[i],inf) 1192 ans[i] = curr 1193 curr += 1 1194 continue 1195 j = i 1196 while True: 1197 j = seg.query(0,p[j]-1) 1198 nextindex = fen.getaccu(p[j]) - 1 1199 if nextindex % 2 > 0: 1200 continue 1201 break 1202 ans[j] = curr 1203 ans[i] = curr + 1 1204 curr += 2 1205 seg.update(p[i],inf) 1206 seg.update(p[j],inf) 1207 fen.update(p[i],-1) 1208 fen.update(p[j],-1) 1209 print(*ans) 1210 1211 T = int(input()) 1212 for t in range(T): 1213 main(t) 1214 ``` 1215 1216 **Rate The Problem !** 1217 1218 Great 1219 1220 Good 1221 1222 Neutral 1223 1224 Bad 1225 1226 Didn't Solve