codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]) &mdash; 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 ```