1771.md (20845B)
1 Source: https://codeforces.com/blog/entry/110092 2 3 We apologize for the delay in editorial of the tasks. 4 5 [A. Hossam and Combinatorics](https://codeforces.com/contest/1771/problem/A) 6 7 Idea: [_HossamYehia_](/profile/_HossamYehia_ "Expert _HossamYehia_") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution(_HossamYehia_)** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 const int N = 1e5 + 5; 21 22 int n, a[N]; 23 24 int main() 25 { 26 #ifndef ONLINE_JUDGE 27 freopen("input.in", "r", stdin); 28 #endif 29 int t; 30 scanf("%d", &t); 31 while(t--){ 32 scanf("%d", &n); 33 for(int i = 0 ; i < n ; ++i) 34 scanf("%d", a + i); 35 36 sort(a, a + n); 37 38 if(a[0] == a[n - 1]){ 39 printf("%lld\n", (1LL * n * (n - 1LL))); 40 continue; 41 } 42 43 int mn = 0, mx = n - 1; 44 45 while(a[0] == a[mn]) 46 ++mn; 47 48 while(a[n - 1] == a[mx]) 49 --mx; 50 51 long long l = mn; 52 long long r = n - mx - 1; 53 54 55 printf("%lld\n", 2LL * l * r); 56 } 57 } 58 ``` 59 60 [B. Hossam and Friends](https://codeforces.com/contest/1771/problem/B) 61 62 Idea: [_HossamYehia_](/profile/_HossamYehia_ "Expert _HossamYehia_") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution(_HossamYehia_)** 69 70 ``` 71 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math") 72 #include <bits/stdc++.h> 73 #define ll long long 74 #define ld long double 75 #define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); 76 using namespace std; 77 const int N = 1e5 + 5, M = 1e5 + 5; 78 79 int n, m; 80 int mn[N]; 81 82 int main() 83 { 84 #ifndef ONLINE_JUDGE 85 freopen("input.in", "r", stdin); 86 #endif 87 int t; 88 scanf("%d", &t); 89 while(t--){ 90 scanf("%d %d", &n, &m); 91 for(int i = 1 ; i <= n ; ++i) 92 mn[i] = n; 93 94 for(int i = 0 ; i < m ; ++i){ 95 int x, y; 96 scanf("%d %d", &x, &y); 97 98 if(x > y) 99 swap(x, y); 100 101 mn[x] = min(mn[x], y - 1); 102 } 103 104 for(int i = n - 1 ; i ; --i) 105 mn[i] = min(mn[i], mn[i + 1]); 106 107 ll ans = n; 108 for(int i = 0 ; i < n ; ++i) 109 ans += (mn[i] - i); 110 111 printf("%lld\n", ans); 112 } 113 } 114 ``` 115 116 [C. Hossam and Trainees](https://codeforces.com/contest/1771/problem/C) 117 118 Idea: [_HossamYehia_](/profile/_HossamYehia_ "Expert _HossamYehia_") 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution(_HossamYehia_)** 125 126 ``` 127 #include <bits/stdc++.h> 128 129 using namespace std; 130 131 const int N = 1e5 + 5, M = 2 * N + 5; 132 133 bool vis[N], ans; 134 135 void Sieve(){ 136 memset(vis, true, sizeof(vis)); 137 138 vis[0] = vis[1] = false; 139 for(int i = 4 ; i < N ; i += 2) 140 vis[i] = false; 141 for(int i = 3 ; i < N / i ; i += 2){ 142 if(!vis[i])continue; 143 for(int j = i * i ; j < N ; j += i + i) 144 vis[j] = false; 145 } 146 } 147 148 int in[N], vid; 149 vector<int> primes; 150 151 void Gen(){ 152 for(int i = 2 ; i < N ; ++i) 153 if(vis[i]) 154 primes.emplace_back(i); 155 } 156 157 set<int> st; 158 159 void check(int x){ 160 if(in[x] == vid){ 161 ans = true; 162 return; 163 } 164 165 in[x] = vid; 166 } 167 168 void fact(int x){ 169 170 if(x < N && vis[x] == true){ 171 check(x); 172 return; 173 } 174 175 int idx = 0, sz = primes.size(); 176 177 while(x > 1 && idx < sz && x / primes[idx] >= primes[idx]){ 178 179 if(x % primes[idx] == 0){ 180 check(primes[idx]); 181 while(x % primes[idx] == 0)x /= primes[idx]; 182 } 183 184 ++idx; 185 } 186 187 if(x > 1){ 188 if(x < N) 189 return check(x), void(); 190 191 if(st.find(x) != st.end()){ 192 ans = true; 193 return; 194 } 195 196 st.emplace(x); 197 } 198 } 199 200 void pre(){ 201 ++vid; 202 st.clear(); 203 } 204 205 int main(){ 206 Sieve(); 207 Gen(); 208 209 int t; 210 scanf("%d", &t); 211 while(t--){ 212 pre(); 213 214 int n; 215 scanf("%d", &n); 216 217 ans = false; 218 219 while(n--){ 220 int x; 221 scanf("%d", &x); 222 fact(x); 223 } 224 225 puts(ans ? "YES" : "NO"); 226 } 227 228 } 229 ``` 230 231 [D. Hossam and (sub-)palindromic tree](https://codeforces.com/contest/1771/problem/D) 232 233 Idea: [4qqqq](/profile/4qqqq "Candidate Master 4qqqq") 234 235 **Tutorial** 236 237 Tutorial is loading... 238 239 **Solution(4qqqq)** 240 241 ``` 242 #include <bits/stdc++.h> 243 244 using namespace std; 245 246 void dfs(int v, vector<vector<int>> &g, vector<vector<int>> &go, vector<vector<pair<int, int>>> &kek, int s, int t = -1, int p = -1, int len = 0){ 247 if(len == 1) 248 t = v; 249 250 if(len > 1) 251 go[s][v] = t; 252 253 kek[len].push_back({s, v}); 254 255 for(int u : g[v]) 256 if(u != p) 257 dfs(u, g, go, kek, s, t, v, len + 1); 258 } 259 260 void Solve(){ 261 int n; cin >> n; 262 string a; cin >> a; 263 264 vector<vector<int>> g(n); 265 vector<vector<int>> go(n, vector<int>(n)); 266 vector<vector<pair<int, int>>> kek(n); 267 vector<vector<int>> dp(n, vector<int>(n)); 268 269 for(int i = 0; i < n - 1; i++){ 270 int v, u; 271 cin >> v >> u; 272 g[--v].push_back(--u); 273 g[u].push_back(v); 274 } 275 276 for(int v = 0; v < n; v++) 277 dfs(v, g, go, kek, v); 278 279 for(int len = 0; len < n; len++){ 280 for(auto p : kek[len]){ 281 int v = p.first; 282 int u = p.second; 283 284 if(len == 0){ 285 dp[v][u] = 1; 286 }else if(len == 1){ 287 dp[v][u] = 1 + (a[v] == a[u]); 288 }else{ 289 int x = dp[v][go[u][v]]; 290 int y = dp[go[v][u]][u]; 291 int z = dp[go[v][u]][go[u][v]] + ((a[v] == a[u]) << 1); 292 dp[v][u] = max({x, y, z}); 293 } 294 } 295 } 296 297 int ans = 0; 298 299 for(int v = 0; v < n; v++) 300 for(int u = 0; u < n; u++) 301 ans = max(ans, dp[v][u]); 302 303 cout << ans << '\n'; 304 } 305 306 signed main(){ 307 ios_base::sync_with_stdio(NULL); 308 cin.tie(NULL); 309 cout.tie(NULL); 310 311 int test = 1; 312 cin >> test; 313 314 for(int i = 1; i <= test; i++) 315 Solve(); 316 } 317 ``` 318 319 [E. Hossam and a Letter](https://codeforces.com/contest/1771/problem/E) 320 321 Idea: [_HossamYehia_](/profile/_HossamYehia_ "Expert _HossamYehia_") 322 323 **Tutorial** 324 325 Tutorial is loading... 326 327 **Solution(_HossamYehia_)** 328 329 ``` 330 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math") 331 #include <bits/stdc++.h> 332 #define ll long long 333 #define ld long double 334 #define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); 335 using namespace std; 336 337 const int N = 4e2 + 5; 338 339 int n, m; 340 char a[N][N]; 341 342 int upM[N][N]; 343 int upB[N][N]; 344 345 int downM[N][N]; 346 int downB[N][N]; 347 348 int _get(int I, int j, int incI, char ch){ 349 int i = I + incI; 350 351 while(i >= 0 && i < n){ 352 if(a[i][j] == '#') 353 break; 354 355 if(a[i][j] == ch) 356 break; 357 358 i += incI; 359 } 360 361 return i; 362 } 363 364 int _getCount(int i, int j){ 365 if(a[i][j] == 'm') 366 return 1; 367 368 return (a[i][j] == '.' ? 0 : 10); 369 } 370 371 /** 372 373 1 2 4 8 374 UL DL UR DR 375 376 */ 377 378 int getU(int i, int j, int bt){ 379 if(!bt) 380 return max(upM[i][j], upB[i][j]) + 1; 381 382 int cur = upM[i][j]; 383 384 if(cur == -1 || a[cur][j] == '#') 385 return cur + 1; 386 387 cur = upM[cur][j]; 388 389 return cur + 1; 390 } 391 392 int getD(int i, int j, int bt){ 393 if(!bt) 394 return min(downM[i][j], downB[i][j]) — 1; 395 396 int cur = downM[i][j]; 397 398 if(cur == n || a[cur][j] == '#') 399 return cur - 1; 400 401 cur = downM[cur][j]; 402 403 return cur - 1; 404 } 405 406 int solve(int i, int l, int r, int msk){ 407 int upL = getU(i, l, (msk & 1)); 408 int downL = getD(i, l, (msk & 2)); 409 410 int upR = getU(i, r, (msk & 4)); 411 int downR = getD(i, r, (msk & 8)); 412 413 int up = max(upL, upR); 414 int down = min(downL, downR); 415 416 if(up < i && down > i) 417 return 2 * (down - up + 1) + (r - l - 1); 418 419 return 0; 420 } 421 422 int main() 423 { 424 #ifndef ONLINE_JUDGE 425 freopen("input.in", "r", stdin); 426 #endif 427 scanf("%d %d", &n, &m); 428 for(int i = 0 ; i < n ; ++i) 429 scanf("%s", a + i); 430 431 for(int i = 0 ; i < n ; ++i){ 432 for(int j = 0 ; j < m ; ++j){ 433 if(a[i][j] == '#') 434 continue; 435 436 upM[i][j] = _get(i, j, -1, 'm'); 437 upB[i][j] = _get(i, j, -1, '#'); 438 439 downM[i][j] = _get(i, j, 1, 'm'); 440 downB[i][j] = _get(i, j, 1, '#'); 441 } 442 } 443 444 int mx = 0; 445 for(int i = 0 ; i < n ; ++i){ 446 for(int j = 0 ; j + 2 < m ; ++j){ 447 448 int cnt = _getCount(i, j) + _getCount(i, j + 1); 449 for(int k = j + 2 ; k < m ; ++k){ 450 if((cnt += _getCount(i, k)) > 1) 451 break; 452 453 mx = max(mx, solve(i, j, k, 0)); 454 455 if(cnt == 1) 456 continue; 457 458 mx = max(mx, solve(i, j, k, 1)); 459 mx = max(mx, solve(i, j, k, 2)); 460 mx = max(mx, solve(i, j, k, 4)); 461 mx = max(mx, solve(i, j, k, 8)); 462 } 463 464 } 465 } 466 467 printf("%d\n", mx); 468 } 469 ``` 470 471 [F. Hossam and Range Minimum Query](https://codeforces.com/contest/1771/problem/F) 472 473 Idea: [4qqqq](/profile/4qqqq "Candidate Master 4qqqq") 474 475 **Tutorial** 476 477 Tutorial is loading... 478 479 **Solution(4qqqq, trie)** 480 481 ``` 482 #include <bits/stdc++.h> 483 484 using namespace std; 485 486 const int p1 = 31; 487 const int p2 = 53; 488 489 unsigned long long pow1[32]; 490 unsigned long long pow2[32]; 491 492 struct Node{ 493 unsigned long long hsh = 0; 494 Node *l = 0, *r = 0; 495 bool was = false; 496 }; 497 498 const int max_memory = 13e7; 499 500 int pos_memory = 0; 501 char memory[max_memory]; 502 503 void* operator new(size_t n) { 504 char *res = memory + pos_memory; 505 pos_memory += n; 506 assert(pos_memory <= max_memory); 507 return (void*) res; 508 } 509 510 void operator delete(void *){} 511 512 Node * upd(Node *v, unsigned long long x, int i = 18){ 513 if(i == -1){ 514 Node *u = new Node(); 515 516 if(!v || v && !v->was){ 517 u->hsh = ((int(1e9) + 345) ^ x) * (3 * x + 654); 518 u->was = true; 519 } 520 521 return u; 522 } 523 524 if(x & (1 << i)){ 525 Node *res = new Node(); 526 res->l = (v ? v->l : 0); 527 res->r = upd((v ? v->r : 0), x, i - 1); 528 unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0); 529 unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0); 530 res->hsh = a + b; 531 return res; 532 }else{ 533 Node *res = new Node(); 534 res->l = upd((v ? v->l : 0), x, i - 1); 535 res->r = (v ? v->r : 0); 536 unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0); 537 unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0); 538 res->hsh = a + b; 539 return res; 540 } 541 } 542 543 int get(Node *l, Node *r, int i = 18, int now = 0){ 544 if((l ? l->hsh : 0) == (r ? r->hsh : 0)) 545 return -1; 546 547 if(i == -1) 548 return now; 549 550 if((l && l->l ? l->l->hsh : 0) == (r && r->l ? r->l->hsh : 0)) 551 return get((l ? l->r : 0), (r ? r->r : 0), i - 1, now + (1 << i)); 552 553 return get((l ? l->l : 0), (r ? r->l : 0), i - 1, now); 554 } 555 556 void Solve(){ 557 pow1[0] = 1; 558 pow2[0] = 1; 559 560 for(int i = 1; i <= 31; i++){ 561 pow1[i] = p1 * pow1[i - 1]; 562 pow2[i] = p2 * pow2[i - 1]; 563 } 564 565 int n; cin >> n; 566 vector<pair<int, int>> a(n); 567 vector<int> mp(n + 1); 568 569 { 570 for(int i = 0; i < n; i++){ 571 cin >> a[i].first; 572 a[i].second = i; 573 } 574 575 sort(a.begin(), a.end()); 576 map<int, int> kek; 577 int now = 0; 578 579 for(int i = 0; i < n; i++){ 580 if(a[i].first != (i ? a[i - 1].first : -1)) 581 now++; 582 583 kek[a[i].first] = now; 584 } 585 586 sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y){ return x.second < y.second; }); 587 588 for(int i = 0; i < n; i++){ 589 int x = kek[a[i].first]; 590 mp[x] = a[i].first; 591 a[i].first = x; 592 } 593 } 594 595 vector<Node *> t(n + 1); 596 597 t[0] = new Node(); 598 599 for(int i = 1; i <= n; i++){ 600 int x = a[i - 1].first; 601 t[i] = upd(t[i - 1], x); 602 } 603 604 int q; cin >> q; 605 606 int last = 0; 607 608 while(q--){ 609 int a, b; 610 cin >> a >> b; 611 612 int l = (last ^ a); 613 int r = (last ^ b); 614 615 int kek = get(t[l - 1], t[r]); 616 int ans = (kek != -1 ? mp[kek] : 0); 617 cout << ans << '\n'; 618 last = ans; 619 } 620 } 621 622 signed main(){ 623 ios_base::sync_with_stdio(NULL); 624 cin.tie(NULL); 625 cout.tie(NULL); 626 627 Solve(); 628 } 629 ``` 630 631 **Solution(Aleks5d, bitset)** 632 633 ``` 634 #pragma optimize("SEX_ON_THE_BEACH") 635 #pragma GCC optimize("unroll-loops") 636 #pragma GCC optimize("unroll-all-loops") 637 #pragma GCC optimize("O3") 638 639 #pragma GCC optimize("Ofast") 640 #pragma GCC optimize("fast-math") 641 //#define _FORTIFY_SOURCE 0 642 #pragma GCC optimize("no-stack-protector") 643 //#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 644 645 #include<bits/stdc++.h> 646 #include <x86intrin.h> 647 648 using uint = unsigned int; 649 using ll = long long int; 650 using ull = unsigned long long int; 651 using dd = double; 652 using ldd = long double; 653 using pii = std::pair<int, int>; 654 using pll = std::pair<ll, ll>; 655 using pdd = std::pair<dd, dd>; 656 using pld = std::pair<ldd, ldd>; 657 658 namespace fast { 659 template<typename T> 660 T gcd(T a, T b) { 661 return gcd(a, b); 662 } 663 664 template<> 665 unsigned int gcd<unsigned int>(unsigned int u, unsigned int v) { 666 int shift; 667 if (u == 0) 668 return v; 669 if (v == 0) 670 return u; 671 shift = __builtin_ctz(u | v); 672 u >>= __builtin_ctz(u); 673 do { 674 unsigned int m; 675 v >>= __builtin_ctz(v); 676 v -= u; 677 m = (int)v >> 31; 678 u += v & m; 679 v = (v + m) ^ m; 680 } while (v != 0); 681 return u << shift; 682 } 683 684 template<> 685 unsigned long long gcd<unsigned long long>(unsigned long long u, unsigned long long v) { 686 int shift; 687 if (u == 0) 688 return v; 689 if (v == 0) 690 return u; 691 shift = __builtin_ctzll(u | v); 692 u >>= __builtin_ctzll(u); 693 do { 694 unsigned long long m; 695 v >>= __builtin_ctzll(v); 696 v -= u; 697 m = (long long)v >> 63; 698 u += v & m; 699 v = (v + m) ^ m; 700 } while (v != 0); 701 return u << shift; 702 } 703 } 704 705 namespace someUsefull { 706 template<typename T1, typename T2> 707 inline void checkMin(T1& a, T2 b) { 708 if (a > b) 709 a = b; 710 } 711 712 template<typename T1, typename T2> 713 inline void checkMax(T1& a, T2 b) { 714 if (a < b) 715 a = b; 716 } 717 718 template<typename T1, typename T2> 719 inline bool checkMinRes(T1& a, T2 b) { 720 if (a > b) { 721 a = b; 722 return true; 723 } 724 return false; 725 } 726 727 template<typename T1, typename T2> 728 inline bool checkMaxRes(T1& a, T2 b) { 729 if (a < b) { 730 a = b; 731 return true; 732 } 733 return false; 734 } 735 } 736 737 namespace operators { 738 template<typename T1, typename T2> 739 std::istream& operator>>(std::istream& in, std::pair<T1, T2>& x) { 740 in >> x.first >> x.second; 741 return in; 742 } 743 744 template<typename T1, typename T2> 745 std::ostream& operator<<(std::ostream& out, std::pair<T1, T2> x) { 746 out << x.first << " " << x.second; 747 return out; 748 } 749 750 template<typename T1> 751 std::istream& operator>>(std::istream& in, std::vector<T1>& x) { 752 for (auto& i : x) in >> i; 753 return in; 754 } 755 756 template<typename T1> 757 std::ostream& operator<<(std::ostream& out, std::vector<T1>& x) { 758 for (auto& i : x) out << i << " "; 759 return out; 760 } 761 } 762 763 //name spaces 764 using namespace std; 765 using namespace operators; 766 using namespace someUsefull; 767 //end of name spaces 768 769 //defines 770 #define ff first 771 #define ss second 772 #define all(x) (x).begin(), (x).end() 773 #define rall(x) (x).rbegin(), (x).rend() 774 #define NO {cout << "NO"; return;} 775 #define YES {cout << "YES"; return;} 776 777 //end of defines 778 //#undef HOME 779 //debug defines 780 #ifdef HOME 781 #define debug(x) cerr << #x << " " << (x) << endl; 782 #define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;} 783 #define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.ff << " " << ioi.ss << ']'; cerr << endl;} 784 #define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;} 785 int jjj; 786 #define wait() cin >> jjj; 787 #define PO cerr << "POMELO" << endl; 788 #define OL cerr << "OLIVA" << endl; 789 #define gen_clock(x) cerr << "Clock " << #x << " created" << endl; ll x = clock(); 790 #define check_clock(x) cerr << "Time spent in " << #x << ": " << clock() - x << endl; x = clock(); 791 #define reset_clock(x) x = clock(); 792 #define say(x) cerr << x << endl; 793 #else 794 #define debug(x) 0; 795 #define debug_v(x) 0; 796 #define debug_vp(x) 0; 797 #define debug_v_v(x) 0; 798 #define wait() 0; 799 #define PO 0; 800 #define OL 0; 801 #define gen_clock(x) 0; 802 #define check_clock(x) 0; 803 #define reset_clock(x) 0; 804 #define say(x) 0; 805 #endif // HOME 806 807 const int SIZE = 200000; 808 const int block = 64; 809 const int _size = (SIZE + 63) / 64; 810 811 struct bs { 812 ull arr[_size]; 813 814 bs() { 815 for (int i = 0; i < _size; ++i) arr[i] = 0; 816 } 817 818 bs& operator^=(bs &other) { 819 #pragma GCC ivdep 820 for (int i = 0; i < _size; ++i) 821 arr[i] ^= other.arr[i]; 822 return *this; 823 } 824 825 int _Find_first_in_xor(bs& other) { 826 ull t; 827 for (int i = 0; i < _size; ++i) { 828 if (t = arr[i] ^ other.arr[i]) { 829 return (i << 6) + __builtin_ctzll(t); 830 } 831 } 832 return SIZE; 833 } 834 835 int _Find_first() { 836 for (int i = 0; i < _size; ++i) { 837 if (arr[i]) { 838 return (i << 6) + __builtin_ctzll(arr[i]); 839 } 840 } 841 return SIZE; 842 } 843 844 void flip(int id) { 845 ull &x = arr[id >> 6]; 846 id &= 63; 847 x ^= ((ull)1 << id); 848 } 849 850 int size() { 851 return SIZE; 852 } 853 854 }; 855 856 ostream& operator<<(ostream &os, bs &x) { 857 for (int i = 0; i < _size; ++i) { 858 os << x.arr[i] << " "; 859 } 860 return os; 861 } 862 863 void solve(int test) { 864 int n; 865 cin >> n; 866 vector<int> arr(n); 867 cin >> arr; 868 vector<int> to(n); 869 { 870 map<int, int> have; 871 for (int i : arr) have[i] = 0; 872 int cnt = 0; 873 for (auto &i : have) { 874 i.ss = cnt; 875 to[cnt] = i.ff; 876 cnt++; 877 } 878 for (int &i: arr) i = have[i]; 879 } 880 881 vector<vector<int>> blocks; 882 for (int i = 0; i < n; i += block) { 883 blocks.push_back({}); 884 for (int j = 0; i + j < n && j < block; ++j) { 885 blocks.back().push_back(arr[i + j]); 886 } 887 } 888 889 vector<bs> blocks_bs(blocks.size()); 890 for (int i = 0; i < blocks.size(); ++i) { 891 for (int j : blocks[i]) { 892 blocks_bs[i].flip(j); 893 } 894 } 895 for (int i = 1; i < blocks.size(); ++i) { 896 blocks_bs[i] ^= blocks_bs[i - 1]; 897 } 898 899 int q; 900 cin >> q; 901 bs have; 902 int last = 0; 903 for (int i = 0; i < q; ++i) { 904 int a, b; 905 cin >> a >> b; 906 907 int l = (last ^ a); 908 int r = (last ^ b); 909 910 // cin >> l >> r; 911 --l; 912 --r; 913 int lb = l / block; 914 int rb = r / block; 915 if (rb - lb <= 1) { 916 int L = l; 917 while (l <= r) { 918 have.flip(arr[l]); 919 ++l; 920 } 921 int id = have._Find_first(); 922 923 int ans = (id == have.size() ? 0 : to[id]); 924 last = ans; 925 cout << ans << '\n'; 926 l = L; 927 while (l <= r) { 928 have.flip(arr[l]); 929 ++l; 930 } 931 } else { 932 int L = (lb + 1) * block; 933 int old_l = l; 934 int R = (rb + 1) * block; 935 checkMin(R, n); 936 int old_r = r; 937 ++r; 938 while (r < R) { 939 blocks_bs[rb].flip(arr[r]); 940 ++r; 941 } 942 while (l < L) { 943 blocks_bs[lb].flip(arr[l]); 944 ++l; 945 } 946 int id = blocks_bs[rb]._Find_first_in_xor(blocks_bs[lb]); 947 int ans = (id == have.size() ? 0 : to[id]); 948 last = ans; 949 cout << ans << '\n'; 950 r = old_r; 951 ++r; 952 while (r < R) { 953 blocks_bs[rb].flip(arr[r]); 954 ++r; 955 } 956 l = old_l; 957 while (l < L) { 958 blocks_bs[lb].flip(arr[l]); 959 ++l; 960 } 961 } 962 } 963 } 964 965 signed main() { 966 ios_base::sync_with_stdio(false); 967 cout.tie(0); 968 cin.tie(0); 969 //freopen("file.in", "r", stdin); 970 //freopen("file.out", "w", stdout); 971 972 int t = 1; 973 //cin >> t; 974 for (int i = 0; i < t; ++i) { 975 solve(i+1); 976 //cout << '\n'; 977 //PO; 978 } 979 return 0; 980 } 981 /* 982 */ 983 ```