1810.md (29476B)
1 Source: https://codeforces.com/blog/entry/114521 2 3 [A. Beautiful Sequence](https://codeforces.com/contest/1810/problem/A) 4 5 **Hint** 6 7 What is the necessary and sufficient condition? 8 9 **Tutorial** 10 11 The necessary and sufficient condition for a beautiful sequence is that there exist one $i$, such that $a_{i} \le i$. Just check the sequence for the condition. 12 13 **Solution** 14 15 ``` 16 #include<bits/stdc++.h> 17 using namespace std; 18 int a[100005]; 19 void solve() 20 { 21 int n; 22 scanf("%d",&n); 23 for(int i =1;i <= n;i++) scanf("%d",&a[i]); 24 for(int i = 1;i <= n;i++) { 25 if(a[i] <= i) { 26 puts("YES"); 27 return; 28 } 29 } 30 puts("NO"); 31 } 32 int main() 33 { 34 int t;scanf("%d",&t); 35 while(t--) solve(); 36 } 37 ``` 38 39 [B. Candies](https://codeforces.com/contest/1810/problem/B) 40 41 **Hint** 42 43 How the binary representation changes after an operation? 44 45 **Tutorial** 46 47 First, we notice that after each operation, the number of candies is always a odd number. So even numbers can not be achieved. 48 49 Then consider how the binary representation changes for a odd number $x$, after turn it into $2x+1$ or $2x-1$. 50 51 * For the $2x + 1$ operation: $\overline{\dots 1}$ turns into $\overline{\dots 11}$. 52 * For the $2x - 1$ operation: $\overline{\dots 1}$ turns into $\overline{\dots 01}$. 53 54 So, the operation is just insert a $0/1$ before the last digit. And the answer for an odd $n$ is just the binary representation of $n$, after removing the last digit. 55 56 **Solution** 57 58 ``` 59 #include<bits/stdc++.h> 60 using namespace std; 61 void solve() 62 { 63 int n;scanf("%d",&n); 64 if(n % 2 == 0) { 65 puts("-1");return; 66 } 67 vector<int> v; 68 int f = 0; 69 for(int i = 29;i >= 1;i--) { 70 if((n >> i) & 1) { 71 f = 1; 72 v.push_back(2); 73 } 74 else if(f) { 75 v.push_back(1); 76 } 77 } 78 printf("%d\n",v.size()); 79 for(auto x : v) { 80 printf("%d ",x); 81 } 82 printf("\n"); 83 } 84 int main() 85 { 86 int t;scanf("%d",&t); 87 while(t--) solve(); 88 return 0; 89 } 90 ``` 91 92 [C.Make It Permutation](https://codeforces.com/contest/1810/problem/C) 93 94 **Hint 1** 95 96 Try the enumerate the length $n$ of permutation. 97 98 **Hint 2** 99 100 There're too many lengths to be checked. How to decrease the amount of $n$? 101 102 **Tutorial** 103 104 Firstly, we need to remove numbers such that each number appears at most once, this part of cost is unavoidable. Then, let's sort the array $a_{1},a_{2} \dots a_{m}$ ($1\le a_{i} \lt a_{2} \lt \dots \lt a_{m}$). 105 106 Secondly, assume we enumerate the length of the permutation $n$. We need to remove all the $a_{i}$ greater than $n$, and insert some numbers $x$ ($x \le n$) but does not appear in the array $a$. We can find some $i$ such that $a_{i} \le n \lt a_{i+1}$, the cost here is simply $(m-i)\cdot a + (n - i)\cdot b$. Here, $m$ is the length of array $a$, after removing the repeated numbers. 107 108 However, $n$ can up to $10^9$ and can not be enumerated. But for all the $n \in [a_{i} , a_{i+1})$, the smaller $n$ has a smaller cost. (see that $(m-i)\cdot a$ do not change, and $(n-i)\cdot b$ decreases). Thus, the possible $n$ can only be some $a_{i}$, and we can caculate the cost in $O(n)$ in total. 109 110 Don't forget the special case: remove all the numbers and add a $1$. 111 112 **Solution** 113 114 ``` 115 #include<bits/stdc++.h> 116 using namespace std; 117 int p[100005]; 118 typedef long long ll; 119 void solve() 120 { 121 int n,a,b;scanf("%d%d%d",&n,&a,&b); 122 set<int> st; 123 ll sol = 0 , ans = 2e18; 124 for(int i = 1;i <= n;i++) { 125 int x;scanf("%d",&x); 126 if(st.find(x) == st.end()) st.insert(x); 127 else sol += a; 128 } 129 int c = 0; 130 for(auto x : st) p[++c] = x; 131 for(int i = 1;i <= c;i++) { 132 ans = min(ans , 1LL*(p[i] - i)*b + 1LL*(c-i)*a); 133 } 134 ans = min(ans , 1LL*c*a + b) ; 135 printf("%lld\n",ans+sol); 136 } 137 int main() 138 { 139 int t;scanf("%d",&t); 140 while(t--) solve(); 141 } 142 ``` 143 144 [D.Climbing the Tree](https://codeforces.com/contest/1810/problem/D) 145 146 **Hint** 147 148 The possible $L$ is always an interval. How to maintain it? 149 150 **Tutorial** 151 152 The main idea is to that for each $a,b,n$, the possible $L$ is a interval $[l,r]$. We will show how to calculate that. 153 154 In the first $n-1$ days, the snail will climb $(n-1)\cdot (a-b)$ meters. And in the daytime of the $n$-th day, the snail will climb $a$ meters. So after $n$ days, the snail climbs at most $(n-1)\cdot (a-b) + a$ meters, which means $L \le (n-1)\cdot (a-b) + a$. Also, the snail can not reach $L$ before $n$ days, which means $L \gt (n-2)\cdot (a-b) + a$. So $L \in [(n-2)\cdot (a-b) + a + 1 , (n-1)\cdot (a-b) + a]$. $n=1$ is a special case, where $L \in [1,a]$ . 155 156 Now after each operation $1$, we can maintain a possible interval $[L_{min} , L_{max}]$. When a snail comes, we let the new $[L_{min}',L_{max}']$ be $[L_{min},L_{max}] \cap [l,r]$, where $[l,r]$ is the possible interval for the new snail. If the new interval is empty, we ignore this information, otherwise adopt it. 157 158 Now let's focus on another problem: for a fixed $L,a,b$, how to calculate the number of days the snail needs to climb? We can solve the equation $(n-2)(a-b) + a \lt L \le (n-1)(a-b) + a$, and get $n - 2 \lt \frac{L - a}{a - b} \le n - 1$, which means $n$ equals to $\lceil \frac{L-a}{a-b} \rceil + 1$. Still, special judge for $L \le a$, where $n=1$ in this case. 159 160 Then, for each query of type $2$, we just calculate the number of days we need for $L_{min}$ and $L_{max}$. If they are the same, output that number. Otherwise output $-1$. 161 162 **Solution** 163 164 ``` 165 #include<bits/stdc++.h> 166 using namespace std; 167 typedef long long ll; 168 void solve() 169 { 170 int q;scanf("%d",&q); 171 ll L = 1 , R = 1e18; 172 while(q--) { 173 int op;scanf("%d",&op) ; 174 if(op == 1) { 175 int a,b,n;scanf("%d%d%d",&a,&b,&n); 176 ll ql = 1LL*(n - 2)*(a - b) + a + 1, qr = 1LL*(n - 1)*(a - b) + a; 177 if(n == 1) ql = 1 , qr = a; 178 if(ql > R || qr < L) { 179 puts("0"); 180 } 181 else L = max(L , ql) , R = min(R , qr) , puts("1"); 182 } 183 else { 184 int a,b;scanf("%d%d",&a,&b); 185 ll ans1 = max(1LL,(L - b - 1) / (a - b) + 1) , ans2 = max(1LL,(R - b - 1) / (a - b) + 1); 186 if(ans1 == ans2) printf("%lld\n",ans1); 187 else puts("-1"); 188 } 189 } 190 return; 191 } 192 int main() 193 { 194 int t;scanf("%d",&t); 195 while(t--) solve(); 196 } 197 ``` 198 199 [E.Monsters](https://codeforces.com/contest/1810/problem/E) 200 201 **Hint 1** 202 203 How to check whether it is possible to defeat all the monsters, starting from a fixed vertex $u$? 204 205 **Hint 2** 206 207 Let $S(u)$ be the vertices set that can be reached, starting from vertex $u$. What's the relationship between $S(u)$ and $S(v)$, where $v\in S(u)$? 208 209 **Tutorial** 210 211 For some vertex set $T$, let's define $E(T)$ as the ''neighbours'' of vertex set $T$. Formally, $v \in E(T)$ if and only if $v \notin T$, but there exist some vertex $u$, such that there's an edge $(u,v)$ in the graph, and $u \in T$. 212 213 Now let's consider how to solve the problem for some fixed starting vertex $u$? Let's maintain the set $S(u)$ and $E(S(u))$. Initially, $S(u) = {u }$. We keep doing the procedure: choose a vertex $v \in E(S(u))$ with minimal value $a_{v}$. If $a_{v} \le |S(u)|$, we add $v$ into set $S(u)$, and update set $E(S(u))$ simultaneously. Since $S(u)$ is always connected during the procedure, we are actually doing such a thing: find a vertex $v$ that is ''reachable'' now with minimal value $a_{v}$, and try to defeat the monster on it. Our goal is to find some $u$ such that $|S(u)| = n$. 214 215 Then let's move to a lemma: if $v \in S(u)$, then $S(v) \subseteq S(u)$. 216 217 **Proof** 218 219 If it is not, consider the procedure above and the first time we add some vertex $x$ such that $x \notin S(u)$ into $S(v)$. At this moment, $|S(v)| \le |S(u)|$ must hold(since it's the first time we add some vertex not in $S(u)$). On the other side, $x \in E(S(u))$ must hold, and hence $a_{x} \gt |S(u)| \ge |S(v)|$. Thus, we can not add $x$ into $S(v)$. 220 221 Then we can tell, if $|S(u)| \lt n$, then for $v \in S(u)$, $|S(v)| \lt n$. So it's unnecessary to search starting from $v$. And we can construct such an algorithm: Search from $1,2,3,\dots n$ in order, if some $i$ has been included in some $S(j)$ before, do not search from it. 222 223 Surprisingly, this algorithm is correct. We can prove it's time complexity. For each vertex $v$, if $v \in S(u)$ now, and when searching from vertex $u'$, $v$ is add into $S(u')$ again, then $|S(u')| \gt 2|S(u)|$. Thus, one vertex can not be visited more than $log(n)$ times, which means the time complexity is $O(nlog^2(n))$. 224 225 This problem has many other methods to solve. This one I think is the easiest to implement. 226 227 **Solution** 228 229 ``` 230 #include<bits/stdc++.h> 231 using namespace std; 232 int vis[200005]; 233 int n , m; 234 vector<int> E[200005]; 235 int a[200005]; 236 int T = 1; 237 bool span(int u) 238 { 239 set<pair<int,int> > st; 240 st.insert(pair<int,int>{a[u] , u}); 241 int amt = 0 , df = 0; 242 while(st.size()) { 243 auto pa = (*st.begin()) ; vis[pa.second] = u; 244 if(pa.first > df) {return (amt == n);} 245 st.erase(st.begin()); 246 amt++ ; df++ ; 247 for(auto v : E[pa.second]) { 248 if(vis[v] < u) { 249 st.insert(pair<int,int>{a[v] , v}); 250 } 251 } 252 } 253 return (amt == n); 254 } 255 void solve() 256 { 257 scanf("%d%d",&n,&m); 258 for(int i= 1;i <= n;i++) scanf("%d",&a[i]) , vis[i] = 0, E[i].clear(); 259 for(int i = 1;i <= m;i++) { 260 int u,v;scanf("%d%d",&u,&v);E[u].push_back(v) ; E[v].push_back(u); 261 } 262 for(int i = 1;i <= n;i++) { 263 if(a[i] == 0 && !vis[i]) { 264 if(span(i)){puts("YES");return;} 265 } 266 } 267 puts("NO"); 268 } 269 int main() 270 { 271 int t;scanf("%d",&t); 272 while(t--) solve(); 273 } 274 ``` 275 276 [F.M-tree](https://codeforces.com/contest/1810/problem/F) 277 278 **Hint 1** 279 280 Can you solve a single query using binary search? How to check the answer? 281 282 **Hint 2** 283 284 Try to find a closed formula for this problem. 285 286 **Tutorial** 287 288 Let $num_{i}$ be the number of occurances of integer $i$ in the array $a$. To check whether the answer can be $\le x$ or not, we can do the following greedy: Starting with a single vertex written $x$, which is the root. For each $i$(from large ones to small ones), if the number of current leaves is smaller than $num_{i}$, then we can not make the answer $\le x$. Otherwise, let $num_{i}$ leaves stop, and other leaves ''grow'' $m$ children each(these vertices are no longer leaves, but their children are). We can discover that each round, the ''stopped'' vertices have $dep = x - i$, which represents their value is $x$. 289 290 We can use the following code to calculate it. 291 292 ``` 293 bool check(int x) 294 { 295 int d = 1; 296 for(int i = x;i >= 1;i--){ 297 if(d < num[i]) return 0; 298 d = (d - num[i]) * m; 299 } 300 return 1; 301 } 302 ``` 303 304 Since a negtive number multiplies $m$ is still a negtive number, the code can be as following: 305 306 ``` 307 bool check(int x) 308 { 309 int d = 1; 310 for(int i = x;i >= 1;i--){ 311 d = (d - num[i]) * m; 312 } 313 return d >= 0; 314 } 315 ``` 316 317 Find out something? The final $d$ is just $m^x - \sum_{i=1}^{x}{num_{i} \cdot m^i}$, which represents it's equivalent to checking $m^x \ge \sum_{i=1}^{n}{m^{a_{i}}}$! So now the answer is just $\lceil log_{m}{\sum_{i=1}^{n}{m^{a_{i}}}} \rceil$. This is the highest bit plus one of $\sum{m^{a_{i}}}$ in $m$-base representation(except for that it's just some $m^x$. In this case the answer is $x$ but not $x+1$). We can use a segment tree, supporting interval min/max query and interval covering to solve the question. 318 319 **Solution** 320 321 ``` 322 using namespace std; 323 int n , m , q; 324 const int N = 2e5 + 40; 325 int num[N]; 326 int a[N]; 327 int cov[N*4 + 5] , mx[N*4 + 5] , mn[N*4 + 5]; 328 void rec(int u) 329 { 330 mx[u] = max(mx[u<<1|1] , mx[u<<1]) ; mn[u] = min(mn[u<<1|1] , mn[u<<1]); 331 } 332 void pd(int u) 333 { 334 if(cov[u] != -1) { 335 cov[u<<1] = mn[u<<1] = mx[u<<1] = cov[u]; 336 cov[u<<1|1] = mn[u<<1|1] = mx[u<<1|1] = cov[u]; 337 cov[u] = -1; 338 } 339 return; 340 } 341 void build(int u,int l,int r) 342 { 343 cov[u] = -1; 344 if(l == r) {mn[u] = mx[u] = num[l] ; return;} 345 build(u<<1 , l , (l + r >> 1)) ; build(u<<1|1 , (l + r >> 1) + 1 , r); 346 rec(u) ; return; 347 } 348 void modify(int u,int l,int r,int ql,int qr,int v) 349 { 350 if(ql <= l && qr >= r) { 351 cov[u] = mn[u] = mx[u] = v; return; 352 } 353 pd(u); 354 int md = (l + r>> 1); 355 if(ql <= md) modify(u<<1 , l , md , ql , qr ,v); 356 if(qr > md) modify(u<<1|1 , md +1 , r , ql , qr , v); 357 rec(u); 358 return; 359 } 360 361 int qumax(int u,int l,int r,int ql) 362 { 363 if(mn[u] == m - 1) return -1; 364 if(l == r) return l; 365 pd(u); 366 int md = (l + r>> 1); 367 if(ql > md) return qumax(u<<1|1 , md + 1 , r , ql); 368 if(ql == l) { 369 if(mn[u<<1] < m - 1) return qumax(u<<1 , l , md , ql); 370 return qumax(u<<1|1 , md + 1 , r , md + 1); 371 } 372 int w = qumax(u<<1 , l , md , ql) ; 373 if(w == -1) return qumax(u<<1|1 , md + 1 , r , md + 1); 374 return w; 375 } 376 int qumin(int u,int l,int r,int ql) 377 { 378 if(mx[u] == 0) return -1; 379 if(l == r) return l; 380 pd(u); 381 int md = (l + r>> 1) ; 382 if(ql > md) return qumin(u<<1|1 , md + 1 , r , ql); 383 if(ql == l) { 384 if(mx[u<<1] > 0) return qumin(u<<1 , l , md , ql); 385 return qumin(u<<1|1 , md + 1 , r , md + 1); 386 } 387 int w = qumin(u<<1 , l , md , ql); 388 if(w == -1) return qumin(u<<1|1 , md + 1 , r , md + 1); 389 return w; 390 } 391 392 int qmax(int u,int l,int r,int ql,int qr) 393 { 394 if(ql <= l && qr >= r) { 395 return mx[u]; 396 } 397 pd(u); 398 int md = (l + r>> 1) , ans = 0; 399 if(ql <= md) ans = max(ans , qmax(u<<1 , l , md , ql , qr )); 400 if(qr > md) ans = max(ans , qmax(u<<1|1 , md +1 , r , ql , qr)); 401 return ans; 402 } 403 int qmin(int u,int l,int r,int ql,int qr) 404 { 405 if(ql <= l && qr >= r) { 406 return mn[u]; 407 } 408 pd(u); 409 int md = (l + r>> 1) , ans = 1e9; 410 if(ql <= md) ans = min(ans , qmin(u<<1 , l , md , ql , qr )); 411 if(qr > md) ans = min(ans , qmin(u<<1|1 , md +1 , r , ql , qr)); 412 return ans; 413 } 414 int ask(int u,int l,int r) 415 { 416 if(l == r) return l; 417 int md = (l + r >> 1); 418 pd(u); 419 if(mx[u<<1|1] == 0) return ask(u<<1 , l , md); 420 return ask(u<<1|1 , md + 1 , r) ; 421 } 422 int get() 423 { 424 int highbit = ask(1 , 1 , n+35); 425 if(highbit == 1 || qmax(1 , 1 , n+35 , 1 , highbit - 1) == 0) return highbit; 426 return highbit + 1; 427 } 428 void add(int u) 429 { 430 int l = qumax(1 , 1 , n + 35 , u); 431 if(l > u) modify(1 , 1 , n+35 , u , l - 1 , 0) ; 432 modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) + 1); 433 return; 434 } 435 void sub(int u) 436 { 437 int l = qumin(1 , 1 , n + 35 , u); 438 if(l > u) modify(1 , 1 , n+35 , u , l - 1 , m - 1) ; 439 modify(1 , 1 , n+35 , l , l , qmax(1 , 1 , n + 35 , l , l ) - 1); 440 return; 441 } 442 void solve() 443 { 444 scanf("%d%d%d",&n,&m,&q); 445 for(int i = 1;i <= n + 35;i++) num[i] = 0; 446 for(int i = 1;i <= n;i++) { 447 scanf("%d",&a[i]);num[a[i]]++; 448 } 449 for(int i = 1;i <= n + 35;i++) { 450 num[i + 1] += num[i] / m;num[i] %= m; 451 } 452 build(1 , 1 , n + 35); 453 while(q--) { 454 int u , v;scanf("%d%d",&u,&v); 455 sub(a[u]) ; a[u] = v; add(a[u]) ; 456 printf("%d%c",get(), " \n"[q == 0]); 457 } 458 return; 459 } 460 int main() 461 { 462 int t;scanf("%d",&t); 463 while(t--) solve(); 464 } 465 ``` 466 467 [G. The Maximum Prefix](https://codeforces.com/contest/1810/problem/G) 468 469 **Hint** 470 471 How to calculate the maximal prefix sum? One possible way is let $f_{n+1} = 0$ and $f_{i}=max(f_{i+1},0)+a_{i}$. 472 473 **Tutorial** 474 475 Consider this method to find maximal prefix sum: let $f_{n+1} = 0$ and $f_{i}=max(f_{i+1},0)+a_{i}$. We can discover that the only influence $[a_{i+1},a_{i+2} \dots a_{n}]$ has(to the whole array's maximal prefix sum) is its maximal prefix sum. Then we let $dp_{i,j}$ be : the expect score we can get, if we assume that the maximal prefix sum of $[a_{i+1},a_{i+2} \dots a_{n}]$ is $j$ (Read the definition carefully). The answer for each $k$ is $dp_{k,0}$, since if the maximal prefix sum for $[a_{k+1},a_{k+2} \dots a_{n}]$ is $0$, that is equivalent to removing them from the array. And also $dp_{0,j} = h_{j}$. 476 477 And we have $dp_{i,j} = p_{i}\cdot dp_{i-1,j+1} + (1 - p_{i})\cdot dp_{i-1,max(j-1,0)}$. The first section represents chosing $a_{i} = 1$ and the second one represents chosing $a_{i} = -1$. 478 479 We also have other solutions, using inclusion-exclusion or generate function. Actually all the testers' solutions differs from each other. 480 481 **Solution** 482 483 ``` 484 #include<bits/stdc++.h> 485 using namespace std; 486 const int mod = 1e9 + 7; 487 const int N = 5005; 488 int p[N] , q[N]; 489 int n; 490 int f[N][N]; 491 int h[N]; 492 int fpow(int a,int b) 493 { 494 int ans = 1; 495 while(b){ 496 if(b & 1) ans = 1LL*ans*a%mod; 497 a = 1LL*a*a%mod;b >>= 1; 498 } 499 return ans; 500 } 501 void solve() 502 { 503 scanf("%d",&n); 504 for(int i = 1;i <= n;i++) { 505 int a,b;scanf("%d%d",&a,&b); 506 p[i] = 1LL*a*fpow(b , mod - 2) % mod; 507 q[i] = (1 - p[i] + mod) % mod; 508 } 509 for(int i = 0;i <= n;i++) scanf("%d",&h[i]); 510 for(int i = 0;i <= n;i++) f[0][i] = h[i]; 511 for(int i = 1;i <= n;i++) { 512 for(int j = 0;j <= n;j++) { 513 f[i][j] = (1LL*p[i]*f[i - 1][j + 1] + 1LL*q[i]*f[i - 1][max(0 , j - 1)] ) % mod; 514 } 515 printf("%d ",f[i][0]); 516 } 517 printf("\n"); 518 return; 519 } 520 int main() 521 { 522 int t;scanf("%d",&t); 523 while(t--) solve(); 524 return 0; 525 } 526 ``` 527 528 [H.Last Number](https://codeforces.com/contest/1810/problem/H) 529 530 **Hint** 531 532 Actually I don't know how to hint. Try to find some rules related to $\frac{\sqrt{5}+1}{2}$, fibnacci or similar 533 534 **Tutorial** 535 536 Assume that the moment before the $x$-th operation(but after $x-1$-th), the first time we have $S_{max} \le 2S_{min}$. Let's divide the operation into two part: before $x$ and equal or after $x$. 537 538 Still, at the moment just before the $x$-th operation, let us sort the elements in the multiset in non-decreasing order, $S_{0},S_{1} \dots S_{k}$. We will show that the answer is $S_{0}\cdot (-1)^{k} + \sum_{i=1}^{k}{S_{i}\cdot (-1)^{i+1}}$. 539 540 **Proof** 541 542 This lemma is based on the fact that, after each operation(which is after $x$-th), $S_{1}$ to $S_{k-1}$ will not change, $S_{k}$ is removed, and $S_{0}$ turn to $S_{k}-S_{0}$. Which also means $S_{k} - S_{0} \le S_{1}$ always holds. 543 544 At the very beginning, $S_{k} - S_{0} \le S_{0} \le S_{1}$ obviously holds. And we can observe that either $S_{k} = S_{k-1}$ or $S_{k-1} = S_{k} - 1$. When $S_{k-1} = S_{k}$, the new $S_{0}$ after two operations is equal to the old $S_{0}$. When $S_{k-1} = S_{k} - 1$, the new $S_{0}$ after two operations is equal to the old $S_{0}$ minus one. So if we write the $S_{0}$ as an array $t_{0} , t_{1} \ldots t_{k}$ by time order, $t_{i+2} \le t_{i}$ always holds. Thus, $t_{i} \le S_{1}$ always holds. 545 546 Let $d_{i}$ be the $S_{max}$ value in the $i$-th operation. Let's prove that before the $x$-th operation, $d_{i} = n-\lceil \frac{i}{\phi} \rceil + 1$, where $\phi = \frac{\sqrt{5} + 1}{2}$. 547 548 **Proof** 549 550 We prove this by Mathematical induction. One fact should be known that during these operations, $S_{min} = i$ always holds for the $i$-th operation(since $S_{max} - S_{min} \gt S_{min}$). 551 552 For $i=1$, it is true because $d_{1} = n$ and $n - \lceil \frac{1}{\phi} \rceil + 1 = n$. 553 554 Assume for $i\le k$, it is true. Still use the fact that $d_{k+1} = d_{k}$ or $d_{k+1} = d_{k} + 1$. The necessary and sufficient condition for $d_{k+1} \gt d_{k}$ is all the numbers greater or equal to $d_{k}$ is ''used''. How many numbers are there? We have $n - d_{k} + 1$ numbers from the original multiset, and some numbers that occurs during the operations, which are the number of $j$ satisfying $d_{j} - j \ge d_{k}$. Thus, $d_{k+1} \gt d_{k}$ is equivalent to: 555 556 $ \space \space \space \space \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} + n - d_{k} + 1 = k$ 557 558 $ \Leftrightarrow \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} = k - \lceil \frac{k}{\phi} \rceil$ 559 560 $\Leftrightarrow \sum_{j=1}^{k}{[d_{j} - j \ge d_{k}]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$ 561 562 $\Leftrightarrow \sum_{j=1}^{k}{[\lceil \frac{j}{\phi} + j \rceil \le \lceil \frac{k}{\phi} \rceil]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$ 563 564 $\Leftrightarrow \sum_{j=1}^{k}{[\lceil \frac{j(\phi + 1)}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$ 565 566 Note that $\frac{j(\phi + 1)}{\phi}$ is always increasing, which means that formula $\lceil \frac{j(\phi + 1)}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil$ holds for $j = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$, but does not hold for $j = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor + 1$. 567 568 The first equation, $\lceil \lfloor \frac{k(\phi - 1)}{\phi} \rfloor \cdot \frac{\phi + 1}{\phi} \rceil \le \lceil \frac{k}{\phi} \rceil$ always holds. Because $\frac{\phi - 1}{\phi}\cdot \frac{\phi + 1}{\phi} = \frac{1}{\phi}$, and ofcourse $\lfloor ka \rfloor b \le kab$. 569 570 Let's do the research when the second equation does not hold. Let $m_{1} = \lbrace \frac{i(\phi - 1)}{\phi} \rbrace$, and $m_{2} = \lbrace \frac{i}{\phi} \rbrace $ ($\lbrace x \rbrace = x - \lfloor x \rfloor$). Note that $m_{1} + m_{2} = 1$, since $\lbrace \frac{i(\phi - 1)}{\phi} \rbrace = \lbrace i - \frac{i}{\phi} \rbrace$. The topic we are going to research is when $\lceil (\lfloor \frac{k(\phi - 1)}{\phi} \rfloor + 1) \cdot \frac{\phi + 1}{\phi}\rceil \gt \lceil \frac{k}{\phi} \rceil$ hold(which also means, $d_{k+1} \gt d_{k}$). 571 572 $\Leftrightarrow \lceil (\frac{i(\phi - 1)}{\phi} - m_{1}) \cdot \frac{\phi+1}{\phi} + \frac{\phi + 1}{\phi} \rceil \gt \lceil \frac{i}{\phi} \rceil$ 573 574 $\Leftrightarrow \lceil \frac{i}{\phi} - m_{1} \cdot \frac{\phi+1}{\phi} + \frac{\phi + 1}{\phi} \rceil \gt \lceil \frac{i}{\phi} \rceil$ 575 576 $\Leftrightarrow \lceil \frac{i}{\phi} - (1 - m_{1}) \cdot \frac{\phi+1}{\phi} \rceil \gt \lceil \frac{i}{\phi} \rceil$ 577 578 $\Leftrightarrow (1 - m_{1}) \cdot \frac{\phi+1}{\phi} \gt 1 - m_{2}$ 579 580 $\Leftrightarrow \frac{\phi+1}{\phi} \gt \frac{1}{m_{2}} - 1$ 581 582 $\Leftrightarrow m_{2} \gt \frac{\phi}{2\phi + 1}$ 583 584 Then let's focus on, if $d_{k+1} = n - \lceil \frac{k+1}{\phi} \rceil + 1$, when will $d_{k + 1} \gt d_{k}$ hold? It's easy to find when $m_{2} \gt 1 - \frac{1}{\phi}$, $d_{k+1} \gt d_{k}$ holds. And since $\phi = \frac{\sqrt{5} + 1}{2}$, we can tell $ \frac{\phi}{2\phi + 1} = 1 - \frac{1}{\phi}$. Thus, we proved the topic, for all $k \lt x$(before the $x$-th operation), $d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$. 585 586 Then, by solve $n - \lceil \frac{x}{\phi} \rceil + 1 \le 2x$, we can get $x = \lceil (n+1)\frac{\phi - 1}{\phi} \rceil$. Now let's prove for $k \ge x$, $d_{k} = n - \lceil \frac{k}{\phi} \rceil + 1$ also holds ! 587 588 **Proof** 589 590 Using the similar idea as lemma 2, find out when $d_{k + 1} \gt d_{k}$ holds. However, at this time, only $j \le x - 1$ will contribute(since for those $j \gt x - 1$, according to lemma 1, they become the minimal one and do not contribute to anything). Similarly, that is $\sum_{j=1}^{x - 1}{[d_{j} - j \ge d_{k}]} = \lfloor \frac{k(\phi - 1)}{\phi} \rfloor$. 591 592 Seems to be different this time, but actually they are the same, because $\lfloor \frac{k(\phi - 1)}{\phi} \rfloor \le x - 1$ holds(the proving is easy, leave it as a exercise). This condition holds means that we can use the same method in lemma 2 to prove it. 593 594 Till now, the lemmas told us the solving the problem is actually solving something like $\sum{(-1)^{i} \cdot (n- \lceil \frac{i}{\phi} \rceil + 1)}$. We can divide them into positive part and negtive part, and then solving $\sum{\lfloor C\cdot i \rfloor}$, where $i$ range from some $l$ to $r$, and $C$ is a irrational constant. Since $n$ is not very large, we can approximate $C$ by $\frac{a}{b}$, where $a,b$ are integers, and turn it into a traditional task. (Maybe it is called floor sum or something like, I'm not sure about the algorithm's english name). 595 596 The marvelous jiangly told me $a,b$ in long long range is enough. But the tester used int128. 597 598 We can dig more about the $\phi$. Let $b_{i} = S_{i+1} - S_{i}$ (sorted, before the $x$-th operation), and what we care is $b_{1} + b_{3} + b_{5}\dots$. We can find that array $b$ is actually a consecutive substring of [fibonacci string](https://oeis.org/A096270). More over, let $F_{n}$ be the starting point of array $b$ in the fibonacci string when the initial size is $n$, we have the conclusion for $n \ge 5$: 599 600 $F[5 \dots inf] = [3,0],[4,1],[8,0],[12,1] \dots [f_{i+3} + (-1)^{i+1} , 1 + (-1)^{i}]$, where $f_{i} = f_{i-1} + f_{i-2} , f_{1} = f_{2} = 1$ . $[r,l]$ represents a list of numbers $[r,r-1,r-2 \dots l+1,l]$. 601 602 Now the only left problem is to find the prefix sum of fibonacci string(of even positions, or of odd positions). This is quite a simple task by using any $log(n)$ or $log^2(n)$ solution. 603 604 **Solution 1(floor sum)** 605 606 ``` 607 #include <bits/stdc++.h> 608 609 void solve(__int128 n, __int128 a, __int128 b, __int128 c, __int128 &f) { 610 if (n < 0) { f = 0; return; } 611 if (a >= c || b >= c) { 612 solve(n, a % c, b % c, c, f); 613 f += (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1); 614 } else if (a) { 615 __int128 m = (a * n + b) / c; 616 solve(m - 1, c, c - b - 1, a, f); 617 f = n * m - f; 618 } 619 } 620 621 const long double k = (1 + sqrt((long double) 5)) / 2; 622 623 int n; 624 long long ans; 625 __int128 a, b, c, d; 626 627 int main() { 628 int T; 629 scanf("%d", &T); 630 __int128 x = (__int128) 2000000000000000000ll * 1000000000; 631 __int128 y = (__int128) 1000000000000000000ll * 1000000000; 632 __int128 z = (__int128) 1618033988749894848ll * 1000000000 + 204586834; 633 for (; T; T--) { 634 scanf("%d", &n); 635 int i = 0; 636 for (int l = 0, r = n - 1, mid; l <= r; ) { 637 mid = l + r >> 1; 638 if (n - floor(mid / k) <= mid + mid) { 639 i = mid; r = mid - 1; 640 } else { 641 l = mid + 1; 642 } 643 } 644 solve((n - 1) / 2, x, 0, z, a); 645 solve((i - 1) / 2, x, 0, z, b); 646 solve((n - 2) / 2, x, y, z, c); 647 solve((i - 2) / 2, x, y, z, d); 648 ans = i + (i % 2 ? -1 : 1) * ((a - b) - (c - d)); 649 if ((n - i) % 2) { ans = n - ans; } 650 printf("%lld\n", ans); 651 } 652 return 0; 653 } 654 ``` 655 656 **Solution 2(fibonacci)** 657 658 ``` 659 #include<bits/stdc++.h> 660 using namespace std; 661 int l[500]; 662 int fib[500]; 663 int evenfib[500]; 664 int getsum(int i,int n) ///1-index 665 { 666 if(n == 0) return 0; 667 if(i <= 1) return fib[i]; 668 if(n <= l[i - 2]) return getsum(i - 2, n); 669 return fib[i - 2] + getsum(i - 1 , n - l[i - 2]); 670 } 671 int getsum2(int i,int n,int p) ///n = 2*k+p, 0-index 672 { 673 if(i <= 0) return 0; 674 if(i <= 1) return 1^p; 675 676 if(n <= l[i - 2] - 1) return getsum2(i - 2 , n , p); 677 int L; 678 if(p) L = (l[i - 2] - !(l[i-2]&1)); 679 else L = (l[i- 2] - (l[i - 2] & 1)); 680 int ans ; 681 if(p) ans = fib[i - 2] - evenfib[i - 2]; 682 else ans = evenfib[i - 2]; 683 ans += getsum2(i - 1 , n - l[i - 2] , p ^ ((l[i - 2] & 1))); 684 return ans; 685 } 686 int getfib(int n) ///0-index 687 { 688 if(n <= 0) return 0; 689 n++; 690 int ans = 0; 691 int i; 692 for(i = 0;l[i] <= n;i++) { 693 ans += fib[i] ; n -= l[i]; 694 } 695 return ans + getsum(i , n); 696 } 697 int get_even(int n) ///n = 2*k 698 { 699 n++; 700 int ans = 0; 701 int i , lbefore = 0; 702 for(i = 0;l[i] <= n;i++) { 703 if(lbefore) ans += fib[i] - evenfib[i]; 704 else ans += evenfib[i]; 705 lbefore ^= (l[i]&1); 706 n -= l[i]; 707 } 708 if(n) ans += getsum2(i , n - 1, lbefore); 709 return ans; 710 } 711 const double phi = (3 - sqrt(5)) / 2; 712 const double eps = 1e-6; 713 int getstart(int n) 714 { 715 if(n == 3) return 0; 716 if(n == 4) return 1; 717 n -= 4; 718 int i; 719 for(i = 1;1;i++) { 720 int lft ; 721 if(i & 1) lft = fib[i + 3] + 1; 722 else lft = fib[i + 3] - 1; 723 if(n <= lft) break; 724 n -= lft; 725 } 726 int start ; 727 if(i & 1) start = fib[i + 3] - n + 1; 728 else start = fib[i + 3] - n; 729 return start; 730 } 731 typedef long long ll; 732 const int L = 95; 733 int a[120] = {8,0,6,0,1,8,5,9,7,2,9,7,2,9,2,0,5,5,7,9,0,1,8,1,7,3,5,9,3,7,4,9,2,7,7,3,1,5,5,4,6,8,7,3,1,7,3,2,4,9,1,0,2,8,0,9,6,9,7,2,2,8,8,1,6,3,4,3,6,5,6,1,3,1,4,5,9,7,1,5,1,5,0,1,0,5,2,1,1,0,6,6,9,1,8,3}; 734 ll b[120]; 735 double cal(int n) 736 { 737 memset(b,0,sizeof(b)); 738 for(int i = 0;i <= L;i++) b[i] = 1LL*n*a[i]; 739 for(int i = 0;i <= L + 15;i++) { 740 b[i + 1] += (b[i] / 10) ; b[i] %= 10; 741 } 742 int ans = 0; 743 for(int i = L + 11;i >= L + 1;i--) ans = (ans * 10 + b[i]) ; 744 return ans; 745 } 746 void solve(int n) 747 { 748 if(n <= 2) {puts("1");return;} 749 int v = cal(n); 750 int len = n - v;v++; 751 int start = getstart(n); 752 int ans = 0; 753 if(len & 1) { 754 ans = v; ///[start + 1 , start + 3...start + len - 2] 755 if(start & 1) ans -= (get_even(start + len - 2) - get_even(start - 1)); 756 else ans -= (getfib(start + len - 1) - get_even(start + len - 1) - getfib(start) + get_even(start)); 757 } 758 else { 759 ans = getfib(start + len - 2) - getfib(start - 1); 760 ///[start + 1 , start + len - 3] 761 if(start & 1) ans -= (get_even(start + len - 3) - get_even(start - 1)); 762 else ans -= (getfib(start + len - 2) - get_even(start + len - 2) - getfib(start) + get_even(start)); 763 } 764 printf("%d\n",ans);return; 765 } 766 int main() 767 { 768 l[0] = l[1] = 1; 769 fib[0] = 0 , fib[1] = 1; 770 evenfib[1] = 1; 771 for(int i = 2;l[i-1] <= 1000000000;i++) { 772 l[i] = l[i - 1] + l[i - 2]; 773 fib[i] = fib[i - 1] + fib[i - 2]; 774 if(l[i - 2] & 1) evenfib[i] = evenfib[i - 2] + fib[i - 1] - evenfib[i - 1]; 775 else evenfib[i] = evenfib[i - 2] + evenfib[i - 1]; 776 } 777 778 int t;scanf("%d",&t); 779 while(t--) { 780 int n;scanf("%d",&n);solve(n); 781 } 782 return 0; 783 } 784 ```