Codeforces Round #837 (Div. 2) Editorial
Difference between en1 and en2, changed 2 character(s)
We apologize for the delay in editorial of the tasks.↵

[A. Hossam and Combinatorics](https://mirror.codeforces.com/contest/1771/problem/A)↵

Idea: [user:_HossamYehia_,2022-12-14]↵

<spoiler summary="Tutorial">↵
[tutorial:1771A]↵
</spoiler>↵

<spoiler summary="Solution(_HossamYehia_)">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int N = 1e5 + 5;↵

int n, a[N];↵

int main()↵
{↵
#ifndef ONLINE_JUDGE↵
    freopen("input.in", "r", stdin);↵
#endif↵
    int t;↵
    scanf("%d", &t);↵
    while(t--){↵
        scanf("%d", &n);↵
        for(int i = 0 ; i < n ; ++i)↵
            scanf("%d", a + i);↵
    ↵
        sort(a, a + n);↵
    ↵
        if(a[0] == a[n - 1]){↵
            printf("%lld\n", (1LL * n * (n - 1LL)));↵
            continue;↵
        }↵
    ↵
        int mn = 0, mx = n - 1;↵
    ↵
        while(a[0] == a[mn])↵
            ++mn;↵
    ↵
        while(a[n - 1] == a[mx])↵
            --mx;↵
    ↵
        long long l = mn;↵
        long long r = n - mx - 1;↵
    ↵
    ↵
        printf("%lld\n", 2LL * l * r);↵
    }↵
}↵

~~~~~↵

</spoiler>↵

[B. Hossam and Friends](https://mirror.codeforces.com/contest/1771/problem/B)↵

Idea: [user:_HossamYehia_,2022-12-14]↵

<spoiler summary="Tutorial">↵
[tutorial:1771B]↵
</spoiler>↵

<spoiler summary="Solution(_HossamYehia_)">↵

~~~~~↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define ld long double↵
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
using namespace std;↵
const int N = 1e5 + 5, M = 1e5 + 5;↵

int n, m;↵
int mn[N];↵

int main()↵
{↵
#ifndef ONLINE_JUDGE↵
    freopen("input.in", "r", stdin);↵
#endif↵
    int t;↵
    scanf("%d", &t);↵
    while(t--){↵
        scanf("%d %d", &n, &m);↵
        for(int i = 1 ; i <= n ; ++i)↵
            mn[i] = n;↵
    ↵
        for(int i = 0 ; i < m ; ++i){↵
            int x, y;↵
            scanf("%d %d", &x, &y);↵
            ↵
            if(x > y)↵
                swap(x, y);↵
                ↵
            mn[x] = min(mn[x], y - 1);↵
        }↵
    ↵
        for(int i = n - 1 ; i ; --i)↵
            mn[i] = min(mn[i], mn[i + 1]);↵
    ↵
        ll ans = n;↵
        for(int i = 0 ; i < n ; ++i)↵
            ans += (mn[i] - i);↵
    ↵
        printf("%lld\n", ans);↵
    }↵
}↵

~~~~~↵


</spoiler>↵

[C. Hossam and Trainees](https://mirror.codeforces.com/contest/1771/problem/C)↵

Idea: [user:_HossamYehia_,2022-12-14]↵

<spoiler summary="Tutorial">↵
[tutorial:1771C]↵
</spoiler>↵

<spoiler summary="Solution(_HossamYehia_)">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int N = 1e5 + 5, M = 2 * N + 5;↵

bool vis[N], ans;↵

void Sieve(){↵
    memset(vis, true, sizeof(vis));↵
    ↵
    vis[0] = vis[1] = false;↵
    for(int i = 4 ; i < N ; i += 2)↵
        vis[i] = false;↵
    for(int i = 3 ; i < N / i ; i += 2){↵
        if(!vis[i])continue;↵
        for(int j = i * i ; j < N ; j += i + i)↵
            vis[j] = false;↵
    }↵
}↵

int in[N], vid;↵
vector<int> primes;↵

void Gen(){↵
    for(int i = 2 ; i < N ; ++i)↵
        if(vis[i])↵
            primes.emplace_back(i);↵
}↵

set<int> st;↵

void check(int x){↵
    if(in[x] == vid){↵
        ans = true;↵
        return;↵
    }↵

    in[x] = vid;↵
}↵

void fact(int x){↵

    if(x < N && vis[x] == true){↵
        check(x);↵
        return;↵
    }↵

    int idx = 0, sz = primes.size();↵

    while(x > 1 && idx < sz && x / primes[idx] >= primes[idx]){↵

        if(x % primes[idx] == 0){↵
            check(primes[idx]);↵
            while(x % primes[idx] == 0)x /= primes[idx];↵
        }↵

        ++idx;↵
    }↵

    if(x > 1){↵
        if(x < N)↵
            return check(x), void();↵

        if(st.find(x) != st.end()){↵
            ans = true;↵
            return;↵
        }↵

        st.emplace(x);↵
    }↵
}↵

void pre(){↵
    ++vid;↵
    st.clear();↵
}↵

int main(){↵
    Sieve();↵
    Gen();↵

    int t;↵
    scanf("%d", &t);↵
    while(t--){↵
        pre();↵
        ↵
        int n;↵
        scanf("%d", &n);↵
        ↵
        ans = false;↵
        ↵
        while(n--){↵
            int x;↵
            scanf("%d", &x);↵
            fact(x);↵
        }↵
        ↵
        puts(ans ? "YES" : "NO");↵
    }↵
    ↵
}↵
~~~~~↵


</spoiler>↵

[D. Hossam and (sub-)palindromic tree](https://mirror.codeforces.com/contest/1771/problem/D)↵

Idea: [user:4qqqq,2022-12-14]↵

<spoiler summary="Tutorial">↵
[tutorial:1771D]↵
</spoiler>↵

<spoiler summary="Solution(4qqqq)">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

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){↵
    if(len == 1)↵
        t = v;↵

    if(len > 1)↵
        go[s][v] = t;↵

    kek[len].push_back({s, v});↵

    for(int u : g[v])↵
        if(u != p)↵
            dfs(u, g, go, kek, s, t, v, len + 1);↵
}↵

void Solve(){↵
    int n; cin >> n;↵
    string a; cin >> a;↵

    vector<vector<int>> g(n);↵
    vector<vector<int>> go(n, vector<int>(n));↵
    vector<vector<pair<int, int>>> kek(n);↵
    vector<vector<int>> dp(n, vector<int>(n));↵

    for(int i = 0; i < n - 1; i++){↵
        int v, u;↵
        cin >> v >> u;↵
        g[--v].push_back(--u);↵
        g[u].push_back(v);↵
    }↵

    for(int v = 0; v < n; v++)↵
        dfs(v, g, go, kek, v);↵

    for(int len = 0; len < n; len++){↵
        for(auto p : kek[len]){↵
            int v = p.first;↵
            int u = p.second;↵

            if(len == 0){↵
                dp[v][u] = 1;↵
            }else if(len == 1){↵
                dp[v][u] = 1 + (a[v] == a[u]);↵
            }else{↵
                int x = dp[v][go[u][v]];↵
                int y = dp[go[v][u]][u];↵
                int z = dp[go[v][u]][go[u][v]] + ((a[v] == a[u]) << 1);↵
                dp[v][u] = max({x, y, z});↵
            }↵
        }↵
    }↵

    int ans = 0;↵

    for(int v = 0; v < n; v++)↵
        for(int u = 0; u < n; u++)↵
            ans = max(ans, dp[v][u]);↵

    cout << ans << '\n';↵
}↵

signed main(){↵
    ios_base::sync_with_stdio(NULL);↵
    cin.tie(NULL);↵
    cout.tie(NULL);↵

    int test = 1;↵
    cin >> test;↵
 ↵
    for(int i = 1; i <= test; i++)↵
        Solve();↵
}↵
~~~~~↵
</spoiler>↵

[E. Hossam and a Letter](https://mirror.codeforces.com/contest/1771/problem/E)↵

Idea: [user:_HossamYehia_,2022-12-14]↵

Tutorial will be soon.↵

[F. Hossam and Range Minimum Query](https://mirror.codeforces.com/contest/1771/problem/F)↵

Idea: [user:4qqqq,2022-12-14]↵

<spoiler summary="Tutorial">↵
[tutorial:1771F]↵
</spoiler>↵

<spoiler summary="Solution(4qqqq, trie)">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int p1 = 31;↵
const int p2 = 53;↵

unsigned long long pow1[32];↵
unsigned long long pow2[32];↵

struct Node{↵
    unsigned long long hsh = 0;↵
    Node *l = 0, *r = 0;↵
    bool was = false;↵
};↵

const int max_memory = 13e7;↵

int pos_memory = 0;↵
char memory[max_memory];↵
 ↵
void* operator new(size_t n) {↵
    char *res = memory + pos_memory;↵
    pos_memory += n;↵
    assert(pos_memory <= max_memory);↵
    return (void*) res;↵
}↵
 ↵
void operator delete(void *){}↵

Node * upd(Node *v, unsigned long long x, int i = 18){↵
    if(i == -1){↵
        Node *u = new Node();↵

        if(!v || v && !v->was){↵
            u->hsh = ((int(1e9) + 345) ^ x) * (3 * x + 654);↵
            u->was = true;↵
        }↵

        return u;↵
    }↵

    if(x & (1 << i)){↵
        Node *res = new Node();↵
        res->l = (v ? v->l : 0);↵
        res->r = upd((v ? v->r : 0), x, i - 1);↵
        unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0);↵
        unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0);↵
        res->hsh = a + b;↵
        return res;↵
    }else{↵
        Node *res = new Node();↵
        res->l = upd((v ? v->l : 0), x, i - 1);↵
        res->r = (v ? v->r : 0);↵
        unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0);↵
        unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0);↵
        res->hsh = a + b;↵
        return res;↵
    }↵
}↵

int get(Node *l, Node *r, int i = 18, int now = 0){↵
    if((l ? l->hsh : 0) == (r ? r->hsh : 0))↵
        return -1;↵

    if(i == -1)↵
        return now;↵

    if((l && l->l ? l->l->hsh : 0) == (r && r->l ? r->l->hsh : 0))↵
        return get((l ? l->r : 0), (r ? r->r : 0), i - 1, now + (1 << i));↵

    return get((l ? l->l : 0), (r ? r->l : 0), i - 1, now);↵
}↵

void Solve(){↵
    pow1[0] = 1;↵
    pow2[0] = 1;↵

    for(int i = 1; i <= 31; i++){↵
        pow1[i] = p1 * pow1[i - 1];↵
        pow2[i] = p2 * pow2[i - 1];↵
    }↵

    int n; cin >> n;↵
    vector<pair<int, int>> a(n);↵
    vector<int> mp(n + 1);↵

    {↵
        for(int i = 0; i < n; i++){↵
            cin >> a[i].first;↵
            a[i].second = i;↵
        }↵

        sort(a.begin(), a.end());↵
        map<int, int> kek;↵
        int now = 0;↵

        for(int i = 0; i < n; i++){↵
            if(a[i].first != (i ? a[i - 1].first : -1))↵
                now++;↵

            kek[a[i].first] = now;↵
        }↵

        sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y){ return x.second < y.second; });↵

        for(int i = 0; i < n; i++){↵
            int x = kek[a[i].first];↵
            mp[x] = a[i].first;↵
            a[i].first = x;↵
        }↵
    }↵

    vector<Node *> t(n + 1);↵

    t[0] = new Node();↵

    for(int i = 1; i <= n; i++){↵
        int x = a[i - 1].first;↵
        t[i] = upd(t[i - 1], x);↵
    }↵

    int q; cin >> q;↵
    ↵
    int last = 0;↵

    while(q--){↵
        int a, b;↵
        cin >> a >> b;↵

        int l = (last ^ a);↵
        int r = (last ^ b);↵

        int kek = get(t[l - 1], t[r]);↵
        int ans = (kek != -1 ? mp[kek] : 0);↵
        cout << ans << '\n';↵
        last = ans;↵
    }↵
}↵

signed main(){↵
    ios_base::sync_with_stdio(NULL);↵
    cin.tie(NULL);↵
    cout.tie(NULL);↵

    Solve();↵
}↵
~~~~~↵


</spoiler>↵

<spoiler summary="Solution(Aleks5d, bitset)">↵

~~~~~↵
#pragma optimize("SEX_ON_THE_BEACH")↵
#pragma GCC optimize("unroll-loops")↵
#pragma GCC optimize("unroll-all-loops")↵
#pragma GCC optimize("O3")↵
 ↵
#pragma GCC optimize("Ofast")↵
#pragma GCC optimize("fast-math")↵
//#define _FORTIFY_SOURCE 0 ↵
#pragma GCC optimize("no-stack-protector")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") ↵

#include<bits/stdc++.h>↵
#include <x86intrin.h>↵

using uint = unsigned int;↵
using ll = long long int;↵
using ull = unsigned long long int;↵
using dd = double;↵
using ldd = long double;↵
using pii = std::pair<int, int>;↵
using pll = std::pair<ll, ll>;↵
using pdd = std::pair<dd, dd>;↵
using pld = std::pair<ldd, ldd>;↵

namespace fast {↵
    template<typename T>↵
    T gcd(T a, T b) {↵
        return gcd(a, b);↵
    }↵

    template<>↵
    unsigned int gcd<unsigned int>(unsigned int u, unsigned int v) {↵
        int shift;↵
        if (u == 0)↵
            return v;↵
        if (v == 0)↵
            return u;↵
        shift = __builtin_ctz(u | v);↵
        u >>= __builtin_ctz(u);↵
        do {↵
            unsigned int m;↵
            v >>= __builtin_ctz(v);↵
            v -= u;↵
            m = (int)v >> 31;↵
            u += v & m;↵
            v = (v + m) ^ m;↵
        } while (v != 0);↵
        return u << shift;↵
    }↵

    template<>↵
    unsigned long long gcd<unsigned long long>(unsigned long long u, unsigned long long v) {↵
        int shift;↵
        if (u == 0)↵
            return v;↵
        if (v == 0)↵
            return u;↵
        shift = __builtin_ctzll(u | v);↵
        u >>= __builtin_ctzll(u);↵
        do {↵
            unsigned long long m;↵
            v >>= __builtin_ctzll(v);↵
            v -= u;↵
            m = (long long)v >> 63;↵
            u += v & m;↵
            v = (v + m) ^ m;↵
        } while (v != 0);↵
        return u << shift;↵
    }↵
}↵
 ↵
namespace someUsefull {↵
    template<typename T1, typename T2>↵
    inline void checkMin(T1& a, T2 b) {↵
        if (a > b)↵
            a = b;↵
    }↵
 ↵
    template<typename T1, typename T2>↵
    inline void checkMax(T1& a, T2 b) {↵
        if (a < b)↵
            a = b;↵
    }↵

    template<typename T1, typename T2>↵
    inline bool checkMinRes(T1& a, T2 b) {↵
        if (a > b) {↵
            a = b;↵
            return true;↵
        }↵
        return false;↵
    }↵

    template<typename T1, typename T2>↵
    inline bool checkMaxRes(T1& a, T2 b) {↵
        if (a < b) {↵
            a = b;↵
            return true;↵
        }↵
        return false;↵
    }↵
}↵
 ↵
namespace operators {↵
    template<typename T1, typename T2>↵
    std::istream& operator>>(std::istream& in, std::pair<T1, T2>& x) {↵
        in >> x.first >> x.second;↵
        return in;↵
    }↵
 ↵
    template<typename T1, typename T2>↵
    std::ostream& operator<<(std::ostream& out, std::pair<T1, T2> x) {↵
        out << x.first << " " << x.second;↵
        return out;↵
    }↵
 ↵
    template<typename T1>↵
    std::istream& operator>>(std::istream& in, std::vector<T1>& x) {↵
        for (auto& i : x) in >> i;↵
        return in;↵
    }↵
 ↵
    template<typename T1>↵
    std::ostream& operator<<(std::ostream& out, std::vector<T1>& x) {↵
        for (auto& i : x) out << i << " ";↵
        return out;↵
    }↵
}↵
 ↵
//name spaces↵
using namespace std;↵
using namespace operators;↵
using namespace someUsefull;↵
//end of name spaces↵
 ↵
//defines↵
#define ff first↵
#define ss second↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
#define NO {cout << "NO"; return;}↵
#define YES {cout << "YES"; return;}↵
 ↵
//end of defines↵
//#undef HOME↵
//debug defines↵
#ifdef HOME↵
    #define debug(x) cerr << #x << " " << (x) << endl;↵
    #define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}↵
    #define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.ff << " " << ioi.ss << ']'; cerr << endl;}↵
    #define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}↵
    int jjj;↵
    #define wait() cin >> jjj;↵
    #define PO cerr << "POMELO" << endl;↵
    #define OL cerr << "OLIVA" << endl;↵
    #define gen_clock(x) cerr << "Clock " << #x << " created" << endl; ll x = clock(); ↵
    #define check_clock(x) cerr << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();↵
    #define reset_clock(x) x = clock();↵
    #define say(x) cerr << x << endl;↵
#else↵
    #define debug(x) 0;↵
    #define debug_v(x) 0;↵
    #define debug_vp(x) 0;↵
    #define debug_v_v(x) 0;↵
    #define wait() 0;↵
    #define PO 0;↵
    #define OL 0;↵
    #define gen_clock(x) 0;↵
    #define check_clock(x) 0;↵
    #define reset_clock(x) 0;↵
    #define say(x) 0;↵
#endif // HOME↵

const int SIZE = 200000;↵
const int block = 64;↵
const int _size = (SIZE + 63) / 64;↵

struct bs {↵
    ull arr[_size];↵

    bs() {↵
        for (int i = 0; i < _size; ++i) arr[i] = 0;↵
    }↵

    bs& operator^=(bs &other) {↵
        #pragma GCC ivdep↵
        for (int i = 0; i < _size; ++i)↵
            arr[i] ^= other.arr[i];↵
        return *this;↵
    }↵

    int _Find_first_in_xor(bs& other) {↵
        ull t;↵
        for (int i = 0; i < _size; ++i) {↵
            if (t = arr[i] ^ other.arr[i]) {↵
                return (i << 6) + __builtin_ctzll(t);↵
            }↵
        }↵
        return SIZE;↵
    }↵

    int _Find_first() {↵
        for (int i = 0; i < _size; ++i) {↵
            if (arr[i]) {↵
                return (i << 6) + __builtin_ctzll(arr[i]);↵
            }↵
        }↵
        return SIZE;↵
    }↵

    void flip(int id) {↵
        ull &x = arr[id >> 6];↵
        id &= 63;↵
        x ^= ((ull)1 << id);↵
    }↵

    int size() {↵
        return SIZE;↵
    }↵

};↵


ostream& operator<<(ostream &os, bs &x) {↵
    for (int i = 0; i < _size; ++i) {↵
        os << x.arr[i] << " ";↵
    }↵
    return os;↵
}↵

void solve(int test) {↵
    int n;↵
    cin >> n;↵
    vector<int> arr(n);↵
    cin >> arr;↵
    vector<int> to(n);↵
    {↵
        map<int, int> have;↵
        for (int i : arr) have[i] = 0;↵
        int cnt = 0;↵
        for (auto &i : have) {↵
            i.ss = cnt;↵
            to[cnt] = i.ff;↵
            cnt++;↵
        }↵
        for (int &i: arr) i = have[i];↵
    }↵

    vector<vector<int>> blocks;↵
    for (int i = 0; i < n; i += block) {↵
        blocks.push_back({});↵
        for (int j = 0; i + j < n && j < block; ++j) {↵
            blocks.back().push_back(arr[i + j]);↵
        }↵
    }↵

    vector<bs> blocks_bs(blocks.size());↵
    for (int i = 0; i < blocks.size(); ++i) {↵
        for (int j : blocks[i]) {↵
            blocks_bs[i].flip(j);↵
        }↵
    }↵
    for (int i = 1; i < blocks.size(); ++i) {↵
        blocks_bs[i] ^= blocks_bs[i - 1];↵
    }↵

    int q;↵
    cin >> q;↵
    bs have;↵
    int last = 0;↵
    for (int i = 0; i < q; ++i) {↵
        int a, b;↵
        cin >> a >> b;↵

        int l = (last ^ a);↵
        int r = (last ^ b);↵

        // cin >> l >> r;↵
        --l;↵
        --r;↵
        int lb = l / block;↵
        int rb = r / block;↵
        if (rb - lb <= 1) {↵
            int L = l;↵
            while (l <= r) {↵
                have.flip(arr[l]);↵
                ++l;↵
            }↵
            int id = have._Find_first();↵

            int ans = (id == have.size() ? 0 : to[id]);↵
            last = ans;↵
            cout << ans << '\n';↵
            l = L;↵
            while (l <= r) {↵
                have.flip(arr[l]);↵
                ++l;↵
            }↵
        } else {↵
            int L = (lb + 1) * block;↵
            int old_l = l;↵
            int R = (rb + 1) * block;↵
            checkMin(R, n);↵
            int old_r = r;↵
            ++r;↵
            while (r < R) {↵
                blocks_bs[rb].flip(arr[r]);↵
                ++r;↵
            }↵
                        while (l < L) {↵
                blocks_bs[lb].flip(arr[l]);↵
                ++l;↵
            }↵
            int id = blocks_bs[rb]._Find_first_in_xor(blocks_bs[lb]);↵
            int ans = (id == have.size() ? 0 : to[id]);↵
            last = ans;↵
            cout << ans << '\n';↵
            r = old_r;↵
            ++r;↵
            while (r < R) {↵
                blocks_bs[rb].flip(arr[r]);↵
                ++r;↵
            }↵
            l = old_l;↵
            while (l < L) {↵
                blocks_bs[lb].flip(arr[l]);↵
                ++l;↵
            }↵
        }↵
    }↵
}↵
 ↵
signed main() {↵
    ios_base::sync_with_stdio(false);↵
    cout.tie(0);↵
    cin.tie(0);↵
    //freopen("file.in", "r", stdin);↵
    //freopen("file.out", "w", stdout);↵
 ↵
    int t = 1;↵
    //cin >> t;↵
    for (int i = 0; i < t; ++i) {↵
        solve(i+1);↵
        //cout << '\n';↵
        //PO;↵
    }↵
    return 0;↵
}↵
/*↵
*/↵
~~~~~↵


</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English 4qqqq 2022-12-21 17:33:46 14
en3 English 4qqqq 2022-12-21 17:26:58 2950
en2 English 4qqqq 2022-12-14 13:42:50 2 (published)
en1 English 4qqqq 2022-12-14 13:40:47 19054 Initial revision (saved to drafts)