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>↵
↵
↵
[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>↵
↵
