1208.md (24527B)
1 Source: https://codeforces.com/blog/entry/69357 2 3 ### [1208A — XORinacci](https://codeforces.com/contest/1208/problem/A) 4 5 The sequence is $a$, $b$, $a\oplus b$, $a$, $b$, $a\oplus b$ $\cdots$ 6 7 Since, the sequence has a period of $3$, $f[i] = f[i \mod 3]$. 8 9 **Code** 10 11 ``` 12 #include<bits/stdc++.h> 13 using namespace std; 14 int main() 15 { 16 int test,a,b,n; 17 cin>>test; 18 while(test--){ 19 cin>>a>>b>>n; 20 switch (n%3){ 21 case 0: 22 cout<<a<<endl; 23 break; 24 case 1: 25 cout<<b<<endl; 26 break; 27 default: 28 cout<<(a^b)<<endl; 29 } 30 } 31 return 0; 32 } 33 ``` 34 35 ### [1208B — Uniqueness](https://codeforces.com/contest/1208/problem/B) 36 37 After removing a sub-segment, a prefix and a suffix remain, possibly of length $0$. Let us fix the prefix which does not contain any duplicate elements and find the maximum suffix we can get without repeating the elements. We can use map/set to keep track of the elements. 38 39 Time complexity: $O(n^2 \cdot log(n))$ 40 41 **Code** 42 43 ``` 44 #include <bits/stdc++.h> 45 46 using namespace std; 47 48 const int N = 2e3 + 5; 49 int a[N]; 50 51 int main(){ 52 int n; 53 scanf("%d", &n); 54 for(int i = 0; i < n; ++i){ 55 scanf("%d", &a[i]); 56 } 57 58 int ans = n - 1; 59 map<int, int> freq; 60 for(int i = 0; i < n; ++i){ 61 bool validPrefix = true; 62 for(int j = 0; j < i; ++j){ 63 freq[a[j]]++; 64 if(freq[a[j]] == 2){ 65 validPrefix = false; 66 break; 67 } 68 } 69 int min_index_suffix = n; 70 for(int j = n - 1; j >= i; --j){ 71 freq[a[j]]++; 72 if(freq[a[j]] == 1){ 73 min_index_suffix = j; 74 } 75 else break; 76 } 77 if(validPrefix){ 78 ans = min(ans, min_index_suffix - i); 79 } 80 81 freq.clear(); 82 } 83 cout << ans << '\n'; 84 ``` 85 86 **Bonus** 87 88 Try to solve this problen in $O(n \cdot log(n))$ 89 90 ### [1208C — Magic Grid](https://codeforces.com/contest/1208/problem/C) 91 92 Divide the grid into four quadrants. Assign distinct integers to the first quadrant from $0$ to $(\frac{N^2}{4} - 1)$. Copy this quadrant to the other three. This way XOR of each row and column becomes $0$. 93 94 Now, to make numbers distinct among the quadrants, multiply the numbers by $4$. Add $1$, $2$, and $3$ to the numbers in $1^{st}$, $2^{nd}$ and $3^{rd}$ quadrants respectively. The XOR of each row and column would still remain $0$ as $N/2$ is also even but the elements will become distinct while being in the range $[0, N^2-1].$ 95 96 Another approach in this problem is to use a $ 4 \times 4$ grid given in the sample itself and replicate it in $N \times N$ grid by adding $16, 32, 48 \cdots $ to make the elements distinct. 97 98 Of course, there are multiple ways to solve the problem. These are just a few of them. 99 100 **Code** 101 102 ``` 103 #include <bits/stdc++.h> 104 using namespace std; 105 #define int long long 106 #define ld long double 107 #define pii pair<int ,int> 108 #define pld pair<ld ,ld> 109 #define F first 110 #define S second 111 #define mod 1000000007 112 #define pb push_back 113 #define mp make_pair 114 #define all(x) x.begin(),x.end() 115 #define mset(x) memset(x, 0, sizeof(x)); 116 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 117 118 const int N = 1000; 119 120 int n, grid[N][N]; 121 void run(){ 122 cin >> n; 123 124 /* 125 Divide Grid into Quandrants as follows: 126 1 | 2 127 ----- 128 3 | 4 129 */ 130 131 int fill = 0; 132 for(int i = 0; i < n/2; i++){ 133 for(int j = 0; j < n/2; j++){ 134 135 grid[i][j] = 4*fill + 1; // 1st quadrant 136 grid[i][j + n/2] = 4*fill + 2; // 2nd quadrant 137 grid[i + n/2][j] = 4*fill + 3; // 3rd quadrant 138 grid[i + n/2][j + n/2] = 4*fill; // 4th quadrant 139 140 fill++; 141 142 } 143 } 144 for(int i = 0; i < n; i++){ 145 for(int j = 0; j < n; j++){ 146 cout << grid[i][j] << " "; 147 } 148 cout << endl; 149 } 150 } 151 152 signed main(){ 153 int tests = 1; 154 // cin >> tests; 155 for(int i = 1; i <= tests; i++) run(); 156 return 0; 157 } 158 ``` 159 160 ### [1208D — Restore Permutation](https://codeforces.com/contest/1208/problem/D) 161 162 ##### **Approach 1** 163 164 Let us fill the array with numbers from $1$ to $N$ in increasing order. 165 166 $1$ will lie at the last index $i$ such that $s_{i} = 0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_{i}$ values by $1$. Repeat this process for numbers $2, 3, ...N$. In the $i^{th}$ turn, reduce the elements by $i$. 167 168 To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation. 169 170 Time complexity: $O(N \cdot log(N))$ 171 172 **Code** 173 174 ``` 175 #pragma GCC optimize("Ofast") 176 #include <iostream> 177 #include <vector> 178 #include <map> 179 #include <set> 180 #include <queue> 181 #include <algorithm> 182 #include <string> 183 #include <cmath> 184 #include <cstdio> 185 #include <iomanip> 186 #include <fstream> 187 #include <cassert> 188 #include <cstring> 189 #include <unordered_set> 190 #include <unordered_map> 191 #include <numeric> 192 #include <ctime> 193 #include <bitset> 194 #include <complex> 195 196 using namespace std; 197 198 typedef long long ll; 199 200 const ll INF = 1e16 + 239; 201 const int MAXN = 1e6 + 239; 202 203 ll a[MAXN]; 204 205 namespace SegmentTree { 206 int n; 207 ll t[4 * MAXN]; 208 ll mod[4 * MAXN]; 209 210 void pull(int v) { 211 t[v] = min(t[2 * v + 1], t[2 * v + 2]); 212 } 213 214 void apply(int v, ll val) { 215 t[v] += val; 216 mod[v] += val; 217 } 218 219 void push(int v) { 220 if (mod[v] != 0) { 221 apply(2 * v + 1, mod[v]); 222 apply(2 * v + 2, mod[v]); 223 mod[v] = 0; 224 } 225 } 226 227 void build(int v, int l, int r) { 228 if (l + 1 == r) { 229 t[v] = a[l]; 230 } else { 231 int m = (r + l) >> 1; 232 build(2 * v + 1, l, m); 233 build(2 * v + 2, m, r); 234 pull(v); 235 } 236 } 237 238 void add(int v, int l, int r, int ql, int qr, ll val) { 239 if (r <= ql || qr <= l) { 240 return; 241 } else if (ql <= l && r <= qr) { 242 apply(v, val); 243 } else { 244 push(v); 245 int m = (r + l) >> 1; 246 add(2 * v + 1, l, m, ql, qr, val); 247 add(2 * v + 2, m, r, ql, qr, val); 248 pull(v); 249 } 250 } 251 252 int go_down(int v, int l, int r) { 253 if (l + 1 == r) { 254 return l; 255 } else { 256 push(v); 257 int m = (r + l) >> 1; 258 int res = -1; 259 if (t[2 * v + 2] == 0) { 260 res = go_down(2 * v + 2, m, r); 261 } else { 262 res = go_down(2 * v + 1, l, m); 263 } 264 pull(v); 265 return res; 266 } 267 } 268 269 void init(int n_) { 270 n = n_; 271 build(0, 0, n); 272 } 273 274 void add(int l, int r, ll val) { 275 add(0, 0, n, l, r, val); 276 } 277 278 void add(int pos, ll val) { 279 add(0, 0, n, pos, pos + 1, val); 280 } 281 282 int last_zero() { 283 return go_down(0, 0, n); 284 } 285 } 286 287 signed main() { 288 ios_base::sync_with_stdio(false); 289 cin.tie(0); 290 291 int n; 292 cin >> n; 293 for (int i = 0; i < n; i++) { 294 cin >> a[i]; 295 } 296 SegmentTree::init(n); 297 vector<int> ans(n, -1); 298 for (int i = 1; i <= n; i++) { 299 int pos = SegmentTree::last_zero(); 300 ans[pos] = i; 301 SegmentTree::add(pos, INF); 302 SegmentTree::add(pos + 1, n, -i); 303 } 304 for (auto t : ans) { 305 cout << t << ' '; 306 } 307 cout << endl; 308 } 309 ``` 310 311 ##### **Approach 2** 312 313 For every i from $N$ to 1, let's say the value of the $s_{i}$ is x. So it means there are $k$ smallest unused numbers whose sum is $x$. We simply put the $k+1$st number in the output permutation at this $i$, and continue to move left. This can be implemented using BIT and binary lifting. 314 315 Thanks to [izoomrood](/profile/izoomrood "Expert izoomrood") for expressing the solution in the above words. 316 317 **Code** 318 319 ``` 320 #include<bits/stdc++.h> 321 using namespace std; 322 323 const int N = 2e5 + 5; 324 long long BIT[N], s[N]; 325 int n; 326 int ans[N]; 327 328 void update(int x, int delta){ 329 for(; x <= n; x += x&-x) 330 BIT[x] += delta; 331 } 332 333 long long query(int x){ 334 long long sum = 0; 335 for(; x > 0; x -= x&-x) 336 sum += BIT[x]; 337 return sum; 338 } 339 340 int searchNumber(long long prefSum){ 341 342 int num = 0; 343 long long sum = 0; 344 for(int i = 21; i>=0 ; --i){ 345 if((num + (1<<i) <= n) && (sum + BIT[num + (1<<i)] <= prefSum)){ 346 num += (1<<i); 347 sum += BIT[num]; 348 } 349 } 350 return num + 1; 351 } 352 353 int main(){ 354 scanf("%d",&n); 355 for(int i = 1; i <= n; ++i){ 356 update(i, i); 357 scanf("%lld", &s[i]); 358 } 359 for(int i = n; i >= 1; --i){ 360 ans[i] = searchNumber(s[i]); 361 update(ans[i], -ans[i]); 362 } 363 for(int i = 1; i <= n; ++i){ 364 printf("%d", ans[i]); 365 if(i < n){ 366 printf(" "); 367 } 368 else printf("\n"); 369 } 370 } 371 ``` 372 373 ### [1208E — Let them slide](https://codeforces.com/contest/1208/problem/E) 374 375 For every array $i$ from $1$ to $N$, let us maintain 2 pointers $L[i]$ and $R[i]$, representing the range of elements in $i_{th}$ array, that can be accessed by the current column index $j$. 376 377 Initially all $L[i]$ and $R[i]$ would be set equal to 0. 378 379 As we move from $j_{th}$ index to $(j+1)_{th}$ index, some $L[i]$ and $R[i]$ would change. Specifically, all those arrays which have $size \ge min(j,W-j-1)$ would have their $L[i]$ and $R[i]$ change. 380 381 Since overall movement of $L[i]$ and $R[i]$ would be equal to $2 \cdot$ size_of_array($i$). Overall change would be of order of $O(\sum a[i])$. For every array we need range max query in $(L[i], R[i])$. 382 383 We can use multisets/ segment trees/ deques to update the answers corresponding to an array if its $L[i], R[i]$ changes. This way we can get complexity $O(N)$ or $O(N \cdot log(N))$ depending upon implementation. 384 385 **Code** 386 387 ``` 388 #include<bits/stdc++.h> 389 using namespace std; 390 391 const int N = 1e6 + 5; 392 long long ans[N]; 393 vector<pair<int, int> > add_element[N], remove_element[N]; 394 multiset<int> global_ms[N]; 395 396 int main(){ 397 int n,w; 398 scanf("%d %d", &n, &w); 399 for(int i = 0; i < n; ++i){ 400 int cnt; 401 scanf("%d", &cnt); 402 for(int j = 0; j < cnt; ++j){ 403 int x,l,r; 404 scanf("%d", &x); 405 add_element[j].push_back(make_pair(x, i)); 406 remove_element[j + w - cnt].push_back(make_pair(x, i)); 407 } 408 if(cnt < w){ 409 add_element[cnt].push_back(make_pair(0, i)); 410 remove_element[w - 1].push_back(make_pair(0, i)); 411 add_element[0].push_back(make_pair(0, i)); 412 remove_element[w - 1 - cnt].push_back(make_pair(0, i)); 413 } 414 } 415 for(int i = 0; i < w; ++i){ 416 417 for(auto j:add_element[i]){ 418 int idx = j.second; 419 int val = j.first; 420 ans[i] -= (global_ms[idx].empty()? 0: *global_ms[idx].rbegin()); 421 global_ms[idx].insert(val); 422 ans[i] += *global_ms[idx].rbegin(); 423 } 424 425 if(i < w - 1){ 426 ans[i + 1] = ans[i]; 427 for(auto j:remove_element[i]){ 428 int idx = j.second; 429 int val = j.first; 430 ans[i + 1] -= (*global_ms[idx].rbegin()); 431 global_ms[idx].erase(global_ms[idx].find(val)); 432 ans[i + 1] += (global_ms[idx].empty()? 0: *global_ms[idx].rbegin()); 433 } 434 } 435 printf("%lld ",ans[i]); 436 } 437 printf("\n"); 438 } 439 ``` 440 441 ### [1208F — Bits And Pieces](https://codeforces.com/contest/1208/problem/F) 442 443 The idea is to first fix some $a[i]$ and try to get the bits which are off in $a[i]$ from any $2$ elements to the right of $i$. Since, we need to maximize the value, we will try to get higher bits first. What we need now is, for every number $x$ from $0$ to $2^{21}-1$, the $2$ right most positions such that the bits present in $x$ are also present in the elements on those positions. This can be done by iterating over submasks(slow) or SOS-DP(fast). 444 445 Once we process the positions for every $x$, let us fix some $a[i]$ and iterate over the bits which are off in $a[i]$ from the highest to the lowest. Lets say the current maximum we have got is $w$ and we are going to consider the $y^{th}$ bit. We can get this bit if the $2$ positions for $w|2^{y}$ are to the right of $i$ else we can not. 446 447 The final answer would be the maximum of $a[i]|w$ over all $i$ from $1$ to $N$. 448 449 Time complexity $O((M+N)\cdot logM)$ where $M$ is the max element in the array. 450 451 **Code** 452 453 ``` 454 #include <bits/stdc++.h> 455 456 #define ll long long 457 #define pb push_back 458 #define pii pair<int,int> 459 #define vi vector<int> 460 #define vii vector<pii> 461 #define mi map<int,int> 462 #define mii map<pii,int> 463 #define all(a) (a).begin(),(a).end() 464 #define x first 465 #define y second 466 #define sz(x) (int)x.size() 467 #define endl '\n' 468 #define hell 1000000007 469 #define rep(i,a,b) for(int i=a;i<b;i++) 470 using namespace std; 471 472 int n,a[1000006],ans,bits; 473 pii dp[1<<21]; 474 475 void add(int mask,int w){ 476 if(dp[mask].x==-1) dp[mask].x=w; 477 else if(dp[mask].y==-1){ 478 if(dp[mask].x==w) return; 479 dp[mask].y=w; 480 if(dp[mask].x>dp[mask].y) swap(dp[mask].x,dp[mask].y); 481 } 482 else{ 483 if(dp[mask].y<w){ 484 dp[mask].x=dp[mask].y; 485 dp[mask].y=w; 486 } 487 else if(dp[mask].x<w and dp[mask].y!=w) dp[mask].x=w; 488 } 489 } 490 491 void merge(int m1,int m2){ 492 if(dp[m2].x!=-1) add(m1,dp[m2].x); 493 if(dp[m2].y!=-1) add(m1,dp[m2].y); 494 } 495 496 void solve(){ 497 memset(dp,-1,sizeof dp); 498 cin>>n; 499 rep(i,0,n){ 500 cin>>a[i]; 501 add(a[i],i); 502 bits=max((int)log2(a[i]),bits); 503 } 504 bits++; 505 rep(i,0,bits){ 506 rep(mask,0,1<<bits){ 507 if(mask&(1<<i)){ 508 merge(mask^(1<<i),mask); 509 } 510 } 511 } 512 rep(i,0,n){ 513 int cur=(1<<bits)-1-a[i]; 514 int opt=0; 515 for(int j=bits-1;j>=0;j--){ 516 if((cur>>j)&1){ 517 if(dp[opt^(1<<j)].y!=-1 and dp[opt^(1<<j)].x>i){ 518 opt^=(1<<j); 519 } 520 } 521 } 522 if(dp[opt].y!=-1 and dp[opt].x>i) ans=max(ans,a[i]^opt); 523 } 524 cout<<ans<<endl; 525 } 526 527 signed main(){ 528 ios::sync_with_stdio(false); 529 cin.tie(0); 530 cout.tie(0); 531 int t=1; 532 // cin>>t; 533 while(t--){ 534 solve(); 535 } 536 return 0; 537 } 538 ``` 539 540 ### [1208G — Polygons](https://codeforces.com/contest/1208/problem/G) 541 542 If we choose a polygon with side length $l$, it is profitable to choose polygons with side lengths as divisors of $l$ as well, because this will not increase the answer. 543 544 So our final set would be such that for every polygon with side length $l$, we would have polygons with side length as divisors of $l$ as well. 545 546 All polygons should have at least one common point in the final arrangement, say $P$ or else we can rotate them and get such $P$. For formal proof, please refer [this comment](https://codeforces.com/blog/entry/69357?#comment-538545) by [orz](/profile/orz "International Master orz"). 547 548 Let us represent points on the circle as the distance from point $P$. Like for $k$ sided polygon, $0$,$\frac{1}{k} ,\frac{2}{k} ,…\frac{k-1}{k}$. 549 550 Now the number of unique fractions over all the polygons would be our answer, which is equal to sum of $ \phi (l)$ over all side lengths $l$ of the polygons because for $l$ sided polygon there will be $\phi(l)$ extra points required by it as compared to its divisors. 551 552 One observation to get to the final solution is $\phi(l) \ge \phi(divisor(l))$. So, we can sort the side lengths by their $\phi$ values and take the smallest $k$ of them. This will minimize the number of points as well as satisfy the property of our set. 553 554 **NOTE:** We can not consider polygon of side length $2$. This can be handled easily. 555 556 **Code** 557 558 ``` 559 #include <bits/stdc++.h> 560 using namespace std; 561 int phi[1000006]; 562 void process_phis(int n){ 563 iota(phi,phi+n+1,0); 564 for(int i = 2 ; i<=n;i++){ 565 if(phi[i]==i){ 566 phi[i]=i-1; 567 for(int j=2*i;j<=n;j+=i){ 568 phi[j]=(phi[j]/i)*(i-1); 569 } 570 } 571 } 572 } 573 int main(){ 574 int n,k; 575 cin>>n>>k; 576 if(k==1){ 577 cout<<3<<endl; 578 return 0; 579 } 580 process_phis(n); 581 k+=2; 582 sort(phi+1,phi+n+1); 583 cout<<accumulate(phi+1,phi+k+1,0LL)<<endl; 584 return 0; 585 } 586 ``` 587 588 Tutorial is loading... 589 590 **Code** 591 592 ``` 593 /** 594 * This line was copied from template 595 * This is nk_sqrt_300.cpp 596 * 597 * @author: Nikolay Kalinin 598 * @date: Fri, 23 Aug 2019 22:28:23 +0300 599 */ 600 #include <bits/stdc++.h> 601 602 using namespace std; 603 604 #ifdef LOCAL 605 #define eprintf(...) fprintf(stderr, __VA_ARGS__) 606 #else 607 #define eprintf(...) 42 608 #endif 609 610 using ll = long long; 611 using ld = long double; 612 using D = double; 613 using uint = unsigned int; 614 template<typename T> 615 using pair2 = pair<T, T>; 616 using pii = pair<int, int>; 617 using pli = pair<ll, int>; 618 using pll = pair<ll, ll>; 619 620 #define pb push_back 621 #define mp make_pair 622 #define all(x) (x).begin(),(x).end() 623 #define fi first 624 #define se second 625 626 const int maxn = 100005; 627 const int infk = maxn; 628 629 const int BSZ = 700; 630 631 vector<int> gr[maxn]; 632 vector<int> dead_ends[maxn]; 633 int th[maxn][2]; 634 int threshold[maxn]; 635 int up[maxn], fastup[maxn]; 636 bool isleaf[maxn]; 637 int curcnt[maxn]; 638 int was[maxn]; 639 int curk, curkid; 640 int n; 641 int timer; 642 int c[maxn]; 643 bool isinteresting[maxn]; 644 vector<int> interesting; 645 pair2<int> qs[BSZ]; 646 vector<int> at[2 * BSZ]; 647 queue<int> q; 648 int path[maxn]; 649 vector<int> ks; 650 vector<int> cntdead[2 * BSZ]; 651 int intid[maxn]; 652 vector<int> order; 653 int newid[maxn]; 654 vector<int> grinit[maxn]; 655 int compk[2 * infk + 5]; 656 657 void leavedesc(int cur, int pr) 658 { 659 newid[cur] = order.size(); 660 up[newid[cur]] = newid[pr]; 661 order.pb(cur); 662 for (int i = 0; i < (int)grinit[cur].size(); i++) 663 { 664 if (grinit[cur][i] == pr) 665 { 666 swap(grinit[cur][i], grinit[cur].back()); 667 grinit[cur].pop_back(); 668 i--; 669 } else 670 { 671 leavedesc(grinit[cur][i], cur); 672 } 673 } 674 } 675 676 inline void computecolor(int cur) 677 { 678 if (was[cur] != timer) curcnt[cur] = 0; 679 int cntred = curcnt[cur]; 680 cntred += (int)cntdead[intid[cur]].size() <= curkid ? cntdead[intid[cur]].back() : cntdead[intid[cur]][curkid]; 681 int cntblue = (int)gr[cur].size() - cntred; 682 if (cntblue - cntred >= curk) c[cur] = 1; 683 else c[cur] = 0; 684 } 685 686 inline void pushtoparent(int cur) 687 { 688 if (cur == 0) return; 689 int par = fastup[cur]; 690 691 int colorup = 1 - (curk >= th[cur][c[cur]]); 692 693 if (was[par] != timer) 694 { 695 was[par] = timer; 696 curcnt[par] = 0; 697 } 698 curcnt[par] += 1 - colorup; 699 } 700 701 int main() 702 { 703 scanf("%d%d", &n, &curk); 704 for (int i = 0; i < n - 1; i++) 705 { 706 int u, v; 707 scanf("%d%d", &u, &v); 708 u--, v--; 709 grinit[u].pb(v); 710 grinit[v].pb(u); 711 } 712 leavedesc(0, -1); 713 714 for (int i = 0; i < n; i++) 715 { 716 for (auto t : grinit[i]) gr[newid[i]].pb(newid[t]); 717 } 718 719 for (int i = 0; i < n; i++) scanf("%d", &c[newid[i]]); 720 721 for (int i = 0; i < n; i++) if (c[i] != -1) isleaf[i] = true; 722 int nq; 723 scanf("%d", &nq); 724 for (int lq = 0; lq < nq; lq += BSZ) 725 { 726 int rq = min(nq, lq + BSZ); 727 memset(isinteresting, 0, sizeof isinteresting); 728 ks.clear(); 729 ks.pb(curk); 730 for (int q = lq; q < rq; q++) 731 { 732 int t; 733 scanf("%d", &t); 734 if (t == 1) 735 { 736 int v; 737 scanf("%d", &v); 738 v--; 739 v = newid[v]; 740 isinteresting[v] = true; 741 qs[q - lq] = {v, -1}; 742 } else if (t == 2) 743 { 744 int v, newc; 745 scanf("%d%d", &v, &newc); 746 v--; 747 v = newid[v]; 748 isinteresting[v] = true; 749 qs[q - lq] = {v, newc}; 750 } else 751 { 752 int newk; 753 scanf("%d", &newk); 754 qs[q - lq] = {-1, newk}; 755 ks.pb(newk); 756 } 757 } 758 759 sort(all(ks)); 760 ks.resize(unique(all(ks)) - ks.begin()); 761 int kssz = ks.size(); 762 ks.pb(infk); 763 int curcompkid = 0; 764 for (int i = -infk; i <= infk; i++) 765 { 766 compk[i + infk] = curcompkid; 767 if (curcompkid < kssz && ks[curcompkid] == i) curcompkid++; 768 } 769 770 isinteresting[0] = true; 771 interesting.clear(); 772 773 for (int i = 0; i <= kssz; i++) at[i].clear(); 774 775 for (int cur = 0; cur < n; cur++) 776 { 777 dead_ends[cur].clear(); 778 path[cur] = -1; 779 if (isinteresting[cur]) 780 { 781 path[cur] = -2; 782 } 783 } 784 785 for (int cur = n - 1; cur >= 0; cur--) 786 { 787 int ret = -1; 788 if (isinteresting[cur]) 789 { 790 intid[cur] = interesting.size(); 791 interesting.pb(cur); 792 cntdead[intid[cur]].clear(); 793 cntdead[intid[cur]].pb(0); 794 } 795 if (path[cur] == -1) 796 { 797 if (isleaf[cur]) 798 { 799 if (c[cur] == 0) at[compk[-infk + infk]].pb(cur); 800 else at[compk[infk + infk]].pb(cur); 801 } else 802 { 803 curcnt[cur] = 0; 804 int cntred = 0; 805 int cntblue = gr[cur].size(); 806 at[compk[cntblue - cntred + 1 + infk]].pb(cur); 807 } 808 } else if (path[cur] == -2) 809 { 810 ret = cur; 811 } else 812 { 813 ret = path[cur]; 814 } 815 if (cur == 0) break; 816 if (ret == -1) continue; 817 818 if (path[up[cur]] == -1) path[up[cur]] = ret; 819 else if (path[up[cur]] >= 0) 820 { 821 isinteresting[up[cur]] = true; 822 fastup[path[up[cur]]] = up[cur]; 823 fastup[ret] = up[cur]; 824 path[up[cur]] = -2; 825 } else 826 { 827 fastup[ret] = up[cur]; 828 } 829 } 830 831 timer++; 832 for (int i = 0; i <= kssz; i++) 833 { 834 for (auto t : at[i]) q.push(t); 835 while (!q.empty()) 836 { 837 int cur = q.front(); 838 q.pop(); 839 if (was[cur] == timer) continue; 840 was[cur] = timer; 841 if (path[up[cur]] == -1) 842 { 843 curcnt[up[cur]]++; 844 int cntred = curcnt[up[cur]]; 845 int cntblue = gr[up[cur]].size() - cntred; 846 if (cntblue - cntred + 1 <= ks[i]) q.push(up[cur]); 847 else at[compk[cntblue - cntred + 1 + infk]].pb(up[cur]); 848 } else if (path[up[cur]] == -2) 849 { 850 int id = intid[up[cur]]; 851 while ((int)cntdead[id].size() <= i) cntdead[id].pb(cntdead[id].back()); 852 cntdead[id].back()++; 853 } else { // in path 854 dead_ends[up[cur]].pb(ks[i]); 855 } 856 } 857 } 858 859 for (int cur = n - 1; cur >= 0; cur--) if (path[cur] != -1) 860 { 861 int cntchildren = gr[cur].size(); 862 if (path[cur] == -2) 863 { 864 th[cur][0] = -infk; 865 th[cur][1] = +infk; 866 } else 867 { 868 th[cur][0] = cntchildren + 1; 869 th[cur][1] = cntchildren + 1; 870 th[cur][0] = min(th[cur][0], max(th[path[cur]][0], cntchildren - 1 - 1 + 1)); 871 th[cur][1] = min(th[cur][1], max(th[path[cur]][1], cntchildren - 1 - 1 + 1)); 872 for (int i = 0; i < (int)dead_ends[cur].size(); i++) 873 { 874 int cntred = i + 1; 875 int cntblue = cntchildren - cntred; 876 th[cur][0] = min(th[cur][0], max(dead_ends[cur][i], cntblue - cntred + 1)); 877 th[cur][1] = min(th[cur][1], max(dead_ends[cur][i], cntblue - cntred + 1)); 878 879 cntred = i + 1 + 1; 880 cntblue = cntchildren - cntred; 881 th[cur][0] = min(th[cur][0], max(max(th[path[cur]][0], dead_ends[cur][i]), cntblue - cntred + 1)); 882 th[cur][1] = min(th[cur][1], max(max(th[path[cur]][1], dead_ends[cur][i]), cntblue - cntred + 1)); 883 } 884 th[path[cur]][0] = th[cur][0]; 885 th[path[cur]][1] = th[cur][1]; 886 } 887 } 888 889 890 ::curkid = lower_bound(all(ks), curk) - ks.begin(); 891 for (int q = 0; q < rq - lq; q++) 892 { 893 timer++; 894 if (qs[q].fi == -1) 895 { 896 curk = qs[q].se; 897 ::curkid = lower_bound(all(ks), curk) - ks.begin(); 898 } else if (qs[q].se != -1) c[qs[q].fi] = qs[q].se; 899 else 900 { 901 for (auto v : interesting) 902 { 903 if (!isleaf[v]) computecolor(v); 904 pushtoparent(v); 905 } 906 printf("%d\n", c[qs[q].fi]); 907 } 908 } 909 } 910 return 0; 911 } 912 ```