[contest](https://mirror.codeforces.com/group/NAwpFRpBCY/)↵
↵
[Announcement](https://mirror.codeforces.com/blog/entry/151621)↵
↵
[problem:675587A]↵
↵
<spoiler summary="hint1">↵
what happens when you take the XOR of whole array with an element.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="hint2">↵
what to do in the case when the XOR of the array is zero.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="solution">↵
Compute the XOR of the whole array, what happen when the XOR of the whole array is ZERO the ans is YES.↵
↵
If the XOR is not zero then from which number we should XOR that it becames zero.↵
↵
If XOR of the whole array is X if X^a[i]=0 then X=a[i] as removing the element for the array is same as XORing it again.↵
↵
↵
Then if X (XOR of the whole array) is present in the array then we can remove it and then make the XOR zero else the ans is NO.↵
</spoiler>↵
↵
[submission:365825144]↵
<spoiler summary="code">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
void solve(){↵
int n;cin>>n;↵
vector<int> v(n);↵
for(int i=0;i<n;i++) cin>>v[i];↵
int X=0;↵
// taking the xor of all the elements↵
for(int i=0;i<n;i++) X^=v[i];↵
if(X==0) {↵
// when it is already zero↵
cout<<"YES\n";↵
} else {↵
for(int i=0;i<n;i++) {↵
// finding an element to remove↵
if((X^v[i])==0) {↵
cout<<"YES\n";return;↵
}↵
}↵
cout<<"NO\n";↵
}↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t=1;↵
cin>>t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:675587B]↵
↵
<spoiler summary="hint1">↵
If an element doesn't divide x now, will it ever ?↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
if it divides x now and get multiplied with y at max how many times it will get updated (Remember then the element will never exceed 1e18 limit).↵
</spoiler>↵
↵
↵
<spoiler summary="hint3">↵
what about the case in which y==1.↵
</spoiler>↵
↵
↵
<spoiler summary="solution">↵
lets assume their is a magical x which is divisible by every number then how many times a single element will get updated if y>1 -- at max 60(if y=2 and $a[i]$ = 1then it can multiple 60 times till it becomes more then 1e18). ↵
↵
when y==1 then just skip the operation because it will not updated any number.↵
↵
what about when y is not one and also and element is not updated because x%a[i]!=0.↵
↵
If initially x%a[i]!=0 then it will never be divisible after any update.↵
↵
<spoiler summary="proof">↵
lets assume two number X and Y if X%Y==0 then every factor of Y will also divides X,↵
↵
but if a factor of Y doesn't divides X then will Y also not divide X.↵
↵
If a is not a factor of X then a*b will also be not the factor of X.↵
</spoiler>↵
↵
For every distinct value $x$, we store all indices $i$ where $x$ is divisible by $a[i]$.↵
↵
We remove an index $i$ from the set once $x$ is no longer divisible by $a[i]$.↵
↵
The total complexity to remove indices across all operations is $O(n)$.↵
↵
If $x$ is divisible by $a[i]$, the total complexity is $O(32 \cdot n)$ for $y > 1$ (since $x \le 2 \cdot 10^9$, an element can be divided at most 31 times).↵
↵
If $y = 1$, we skip the operation entirely.Since the number of distinct values of $x$ is $\le 500$, this approach is efficient and stays within time limits.↵
↵
</spoiler>↵
↵
[submission:365842486]<spoiler summary="code">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
void solve(){↵
int n,q;cin>>n>>q;↵
vector<int> v(n);↵
for(int i = 0;i <n;i++)cin>>v[i];↵
map<int,int>mp;↵
while(q--){↵
int i,x,y;↵
cin>>i>>x>>y;↵
--i;↵
// skip the y=1 operation as it will not change anything↵
if(y == 1)continue;↵
if(!mp.count(x))↵
{↵
// when x comes for the first time include all the indxs↵
mp[x] = n;↵
}↵
for(int j = i;j< mp[x];j++)↵
{↵
if(x % v[j] == 0)v[j]*= y;↵
}↵
for(int j = mp[x]-1;j>=0;j--)↵
{↵
if(x % v[j]){↵
mp[x]--;//once we remove it there is no coming back↵
}↵
else{↵
break;↵
}↵
}↵
}↵
for(auto &x:v)cout<<x<<' ';cout<<'\n';↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t=1;↵
cin>>t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:675587C]↵
↵
<spoiler summary="hint1">↵
think from the back.↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
now when you add x, can you know what value it will get converted to at the end.↵
</spoiler>↵
↵
↵
↵
↵
<spoiler summary="solution">↵
The trick lies in processing the queries in reverse.Think about it: an element added at query $i$ is only affected by Type 2 operations that occur after query $i$. If we know what a value $v$ "eventually becomes" by the end of all queries, we can immediately determine the final value of any number we append.↵
↵
Create an array (let's call it parent or f) where f[v] represents what the value $v$ currently transforms into. Initially, f[v] = v for all $v$ up to the maximum possible value ($3 \cdot 10^5$).↵
↵
Start from the $q$-th query and work back to the 1st.↵
↵
Process Type 2 ($2, x, y$): In reverse, this operation means that any $x$ existing before this point will eventually be treated as $x + y$.Update the mapping: f[x] = f[x + y].↵
↵
Process Type 1 ($1, x$):When we "add" $x$ (in reverse, this is the moment the element was born), its final value is whatever f[x] is at that moment.Store f[x] in a result list.↵
↵
Since we processed Type 1 queries from last to first, reverse your result list and print it.↵
</spoiler>↵
↵
[submission:365845846]<spoiler summary="code">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
const int N = 3e5 + 5;↵
↵
↵
void solve()↵
{↵
int q; cin >> q; ↵
vector<pair<int,int>> vp;↵
int n = 3e5 + 10;↵
↵
while(q--){↵
int a; cin >> a;↵
if(a == 1){↵
int x; cin >> x;↵
vp.push_back({x, n}); // Type 1: Add element x (using n as a marker)↵
}↵
else {↵
int x, y; cin >> x >> y;↵
vp.push_back({x, y}); // Type 2: Replace x with x + y logic↵
}↵
}↵
↵
vector<int> p(n + 1);↵
for(int i = 1; i <= n; i++) p[i] = i; // Initialize parent array for mapping↵
↵
vector<int> v;↵
int m = vp.size();↵
↵
// Process queries in reverse to handle replacements offline↵
for(int i = m - 1; i >= 0; i--){↵
int x = vp[i].first, y = vp[i].second;↵
if(y != n){↵
p[x] = p[x + y]; // Map current value x to its future replaced value↵
}↵
else {↵
v.push_back(p[x]); // Store the final mapped value of the added element↵
}↵
}↵
↵
reverse(v.begin(), v.end()); // Restore original order of additions↵
for(auto i : v) cout << i << " "; ↵
cout << endl;↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false); ↵
cin.tie(0);↵
↵
int t = 1;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:675587D]↵
↵
<spoiler summary="hint1">↵
think of invariance in single operation.↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
multiply the x and the y coordinate.↵
</spoiler>↵
↵
↵
<spoiler summary="solution">↵
The problem asks us to find the initial active cell $(s, t)$ given the final state of a 2D grid after several "toggle" operations. Each operation affects four specific points. To solve this, we must find **invariants** — properties of the active cells that do not change when the operation is performed.↵
↵
#### 1. The Invariant for $s$↵
Let's consider the function $f(x, y) = x$. When we perform an operation at $(x, y)$, the XOR sum of the $x$-coordinates of the four toggled cells is:↵
↵
$$x \oplus x \oplus (x+1) \oplus (x+1) = 0$$↵
↵
Since every operation contributes $0$ to the total XOR sum, the XOR sum of $x$-coordinates of all active cells remains constant. Initially, only $(s, t)$ was active, so:↵
↵
$$s = x_1 \oplus x_2 \oplus \dots \oplus x_n$$↵
↵
#### 2. The Invariant for $t$↵
To find $t$, we use the function $g(x, y) = x \cdot y$. The four points toggled are:↵
↵
* $P_1 = (x, y(x+1))$ which gives $g(P_1) = x \cdot y(x+1)$↵
* $P_2 = (x, (y+1)(x+1))$ which gives $g(P_2) = x \cdot (y+1)(x+1)$↵
* $P_3 = (x+1, yx)$ which gives $g(P_3) = (x+1) \cdot yx$↵
* $P_4 = (x+1, (y+1)x)$ which gives $g(P_4) = (x+1) \cdot (y+1)x$↵
↵
Notice that $g(P_1) = g(P_3)$ and $g(P_2) = g(P_4)$. When we XOR these four values together:↵
↵
$$(g(P_1) \oplus g(P_3)) \oplus (g(P_2) \oplus g(P_4)) = 0 \oplus 0 = 0$$↵
↵
This means the XOR sum of the products $(x_i \cdot y_i)$ is also an invariant!↵
↵
$$s \cdot t = (x_1 \cdot y_1) \oplus (x_2 \cdot y_2) \oplus \dots \oplus (x_n \cdot y_n)$$↵
↵
#### 3. Final Calculation↵
1. Calculate the XOR sum of all $x_i$ to get $s$.↵
2. Calculate the XOR sum of all $(x_i \cdot y_i)$ to get a value $V$.↵
3. The initial $t$ is calculated as:↵
↵
$$t = V / s$$↵
↵
**Complexity:** $O(n)$ time and $O(1)$ extra space.↵
</spoiler>↵
↵
[submission:365827860]<spoiler summary="code">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
void solve()↵
{↵
int n;cin>>n;↵
int X=0,Y=0;↵
while(n--) {↵
int x,y;cin>>x>>y;↵
X^=x;↵
// xor of x*y↵
Y^=(x*y);↵
}↵
cout<<X<<" "<<(Y/X)<<endl;↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t=1;↵
cin>>t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:675587E1]↵
[problem:675587E2]↵
↵
<spoiler summary="hint1">↵
try to convert the tree in an array.↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
euler tour.↵
</spoiler>↵
↵
↵
<spoiler summary="hint3">↵
now you have a path in what range will the subtree of i lies?↵
</spoiler>↵
↵
↵
<spoiler summary="hint4">↵
Randomized Algorithm.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="solution(easy version)">↵
By performing a DFS Traversal, we can assign each vertex an entry time (tin) and exit time (tout).The subtree rooted at $i$ now corresponds to a contiguous range in the DFS-order array: [tin[i], tout[i]].The size of the subtree $sz$ is simply tout[i] — tin[i] + 1.↵
↵
now the range of subtree of $i$ will lies in range pos[i] to pos[i]+subtree[i];↵
↵
now we can apply a randomize search in this range .↵
↵
<spoiler summary="randomize approach">↵
if their exist a colour which is more then 1/3rd of the time if we randomly check the colour the probability that it will not be chosen is 2/3 .↵
↵
The probability of not picking a vertex of this specific color in a single random check is at most $1 - 1/3 = 2/3$.↵
↵
if we perform this operation 50 times then its very low that we may not choose a vertices whose colour appears more then 1/3 time↵
</spoiler>↵
↵
now for every query do 50+ times randomize approach then for the colour of random vertices see the freq. of that colour in the range which can be done by binary search.↵
↵
you will store the tin tout time of the vertices for every colour then sort the vector .↵
↵
then do ↵
↵
$$\text{count}(C, L, R) = \text{upper_bound}(pos[C], R) - \text{lower_bound}(pos[C], L)$$↵
</spoiler>↵
↵
↵
<spoiler summary="hint4">↵
can you just remove the vertices for the current colour and put it in the new colour .↵
</spoiler>↵
↵
↵
<spoiler summary="hint5">↵
use ordered_set instead of vector .↵
</spoiler>↵
↵
↵
<spoiler summary="solution(hard version) ">↵
read the solution for the easy version.↵
↵
now for the 2nd type of query you can use ordered set instead of the vector and then can erase and insert the colour according to the update and to count the frequency use this ,↵
↵
$$\text{count} = \text{ordered_set.order_of_key}(R + 1) - \text{ordered_set.order_of_key}(L)$$↵
</spoiler>↵
↵
↵
<spoiler summary="bonus">↵
try to do it with Misra-Gries Algorithm.↵
</spoiler>↵
↵
[submission:365846891]↵
[submission:365846928]<spoiler summary="code(easy version)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
#define dbg(x) cout<<#x<<' '<<x<<endl;↵
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());↵
int get(int l,int r)↵
{↵
return l + RNG()%(r - l + 1);↵
}↵
↵
const int N = 2e5+ 3;↵
vector<int>adj[N],col(N),IN(N),OUT(N),H[N],sz(N),tn(N);↵
↵
int timer = 1;↵
// euler tour↵
int dfs(int node,int par)↵
{↵
tn[timer] = node;↵
IN[node] = timer++;↵
sz[node] = 1;↵
for(auto &x:adj[node])↵
{↵
if(x == par)continue;↵
sz[node] += dfs(x,node);↵
}↵
OUT[node] = timer-1;↵
return sz[node];↵
}↵
↵
void solve()↵
{↵
int n, q;↵
cin>>n>>q;↵
map<int,int>mp,pm;↵
for(int i = 1;i<= n;i++){↵
cin>>col[i];↵
if(!mp.count(col[i])){↵
mp[col[i]] = mp.size();↵
pm[mp.size()-1] = col[i];↵
}↵
col[i] = mp[col[i]];↵
}↵
for(int i = 1;i<n;i++)↵
{↵
int a, b;cin>>a>>b;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
dfs(1,-1);↵
for(int i = 1;i<= n;i++)↵
{↵
H[col[i]].push_back(IN[i]);↵
}↵
for(int i = 0;i<= n;i++){↵
sort(H[i].begin(),H[i].end());↵
}↵
while(q--)↵
{↵
int node;cin>>node;↵
int l = IN[node],r = OUT[node];↵
//now i have the range.↵
set<int>st;↵
for(int i = 0;i< 50;i++)↵
{↵
int g = get(l,r);// random search↵
g = tn[g];//this is the node itsefl↵
int val = col[g];//this is the color itself.↵
int cnt = upper_bound(H[val].begin(),H[val].end(),r) - lower_bound(H[val].begin(),H[val].end(),l);// freq. count↵
if(cnt > (sz[node])/3)st.insert(pm[val]);↵
}↵
if(st.empty())cout<<"-1\n";↵
else{↵
cout<<st.size()<<' ';for(auto &x:st)cout<<x<<' ';cout<<'\n';↵
}↵
↵
}↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false), cin.tie(NULL);↵
int t = 1;↵
// cin>>t;↵
while(t--)solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(hard version)">↵
~~~~~↵
#include<bits/stdc++.h>↵
// PBDS headers for ordered_set↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds; //namespace for PBDS↵
↵
#define int long long↵
#define dbg(x) cout<<#x<<' '<<x<<endl;↵
↵
//Definition of ordered_set↵
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());↵
int get(int l,int r)↵
{↵
return l + RNG()%(r - l + 1);↵
}↵
↵
↵
const int N = 2e5+ 3;↵
const int MAXC = 4e5 + 5;↵
↵
ordered_set<int> H[MAXC];↵
vector<int>adj[N],col(N),IN(N),OUT(N),sz(N),tn(N);↵
↵
int timer = 1;↵
// euler tour↵
int dfs(int node,int par)↵
{↵
tn[timer] = node;↵
IN[node] = timer++;↵
sz[node] = 1;↵
for(auto &x:adj[node])↵
{↵
if(x == par)continue;↵
sz[node] += dfs(x,node);↵
}↵
OUT[node] = timer-1;↵
return sz[node];↵
}↵
↵
void solve()↵
{↵
int n, q;↵
cin>>n>>q;↵
map<int,int>mp,pm;↵
↵
for(int i = 1;i<= n;i++){↵
cin>>col[i];↵
if(!mp.count(col[i])){↵
mp[col[i]] = mp.size();↵
pm[mp.size()-1] = col[i];↵
}↵
col[i] = mp[col[i]];↵
}↵
↵
for(int i = 1;i<n;i++)↵
{↵
int a, b;cin>>a>>b;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
↵
dfs(1,-1);↵
↵
for(int i = 1;i<= n;i++)↵
{↵
H[col[i]].insert(IN[i]);↵
}↵
↵
while(q--)↵
{↵
int c;cin>>c;↵
if(c == 2)↵
{↵
int node, clr; cin >> node >> clr;↵
// Step A: Normalize the new color if it's completely new↵
if(!mp.count(clr)){↵
mp[clr] = mp.size();↵
pm[mp.size()-1] = clr;↵
}↵
↵
int new_clr_id = mp[clr];↵
int old_clr_id = col[node];↵
↵
// Erase the node's IN-time from the old color's set↵
H[old_clr_id].erase(IN[node]);↵
// Insert the node's IN-time into the new color's set↵
H[new_clr_id].insert(IN[node]);↵
// Update the color array↵
col[node] = new_clr_id;↵
}↵
else{↵
int node;cin>>node;↵
int l = IN[node],r = OUT[node];↵
↵
set<int>st;↵
for(int i = 0;i< 50;i++)↵
{↵
int g = get(l,r);↵
g = tn[g]; //this is the node itsefl↵
int val = col[g]; //this is the mapped color itself.↵
↵
// Use order_of_key to efficiently count elements in range [l, r]↵
// order_of_key(x) returns the number of elements strictly less than x.↵
// So, elements <= r minus elements < l gives elements in [l, r].↵
int cnt = H[val].order_of_key(r + 1) - H[val].order_of_key(l);↵
↵
if(cnt > (sz[node])/3) st.insert(pm[val]);↵
}↵
if(st.empty()) cout<<"-1\n";↵
else{↵
cout<<st.size()<<' ';↵
for(auto &x:st) cout<<x<<' ';↵
cout<<'\n';↵
}↵
}↵
}↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false), cin.tie(NULL);↵
int t = 1;↵
// cin>>t;↵
while(t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[Announcement](https://mirror.codeforces.com/blog/entry/151621)↵
↵
[problem:675587A]↵
↵
<spoiler summary="hint1">↵
what happens when you take the XOR of whole array with an element.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="hint2">↵
what to do in the case when the XOR of the array is zero.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="solution">↵
Compute the XOR of the whole array, what happen when the XOR of the whole array is ZERO the ans is YES.↵
↵
If the XOR is not zero then from which number we should XOR that it becames zero.↵
↵
If XOR of the whole array is X if X^a[i]=0 then X=a[i] as removing the element for the array is same as XORing it again.↵
↵
↵
Then if X (XOR of the whole array) is present in the array then we can remove it and then make the XOR zero else the ans is NO.↵
</spoiler>↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
void solve(){↵
int n;cin>>n;↵
vector<int> v(n);↵
for(int i=0;i<n;i++) cin>>v[i];↵
int X=0;↵
// taking the xor of all the elements↵
for(int i=0;i<n;i++) X^=v[i];↵
if(X==0) {↵
// when it is already zero↵
cout<<"YES\n";↵
} else {↵
for(int i=0;i<n;i++) {↵
// finding an element to remove↵
if((X^v[i])==0) {↵
cout<<"YES\n";return;↵
}↵
}↵
cout<<"NO\n";↵
}↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t=1;↵
cin>>t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:675587B]↵
↵
<spoiler summary="hint1">↵
If an element doesn't divide x now, will it ever ?↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
if it divides x now and get multiplied with y at max how many times it will get updated (Remember then the element will never exceed 1e18 limit).↵
</spoiler>↵
↵
↵
<spoiler summary="hint3">↵
what about the case in which y==1.↵
</spoiler>↵
↵
↵
<spoiler summary="solution">↵
lets assume their is a magical x which is divisible by every number then how many times a single element will get updated if y>1 -- at max 60(if y=2 and $a[i]$ = 1then it can multiple 60 times till it becomes more then 1e18). ↵
↵
when y==1 then just skip the operation because it will not updated any number.↵
↵
what about when y is not one and also and element is not updated because x%a[i]!=0.↵
↵
If initially x%a[i]!=0 then it will never be divisible after any update.↵
↵
<spoiler summary="proof">↵
lets assume two number X and Y if X%Y==0 then every factor of Y will also divides X,↵
↵
but if a factor of Y doesn't divides X then will Y also not divide X.↵
↵
If a is not a factor of X then a*b will also be not the factor of X.↵
</spoiler>↵
↵
For every distinct value $x$, we store all indices $i$ where $x$ is divisible by $a[i]$.↵
↵
We remove an index $i$ from the set once $x$ is no longer divisible by $a[i]$.↵
↵
The total complexity to remove indices across all operations is $O(n)$.↵
↵
If $x$ is divisible by $a[i]$, the total complexity is $O(32 \cdot n)$ for $y > 1$ (since $x \le 2 \cdot 10^9$, an element can be divided at most 31 times).↵
↵
If $y = 1$, we skip the operation entirely.Since the number of distinct values of $x$ is $\le 500$, this approach is efficient and stays within time limits.↵
↵
</spoiler>↵
↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
void solve(){↵
int n,q;cin>>n>>q;↵
vector<int> v(n);↵
for(int i = 0;i <n;i++)cin>>v[i];↵
map<int,int>mp;↵
while(q--){↵
int i,x,y;↵
cin>>i>>x>>y;↵
--i;↵
// skip the y=1 operation as it will not change anything↵
if(y == 1)continue;↵
if(!mp.count(x))↵
{↵
// when x comes for the first time include all the indxs↵
mp[x] = n;↵
}↵
for(int j = i;j< mp[x];j++)↵
{↵
if(x % v[j] == 0)v[j]*= y;↵
}↵
for(int j = mp[x]-1;j>=0;j--)↵
{↵
if(x % v[j]){↵
mp[x]--;//once we remove it there is no coming back↵
}↵
else{↵
break;↵
}↵
}↵
}↵
for(auto &x:v)cout<<x<<' ';cout<<'\n';↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t=1;↵
cin>>t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:675587C]↵
↵
<spoiler summary="hint1">↵
think from the back.↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
now when you add x, can you know what value it will get converted to at the end.↵
</spoiler>↵
↵
↵
↵
↵
<spoiler summary="solution">↵
The trick lies in processing the queries in reverse.Think about it: an element added at query $i$ is only affected by Type 2 operations that occur after query $i$. If we know what a value $v$ "eventually becomes" by the end of all queries, we can immediately determine the final value of any number we append.↵
↵
Create an array (let's call it parent or f) where f[v] represents what the value $v$ currently transforms into. Initially, f[v] = v for all $v$ up to the maximum possible value ($3 \cdot 10^5$).↵
↵
Start from the $q$-th query and work back to the 1st.↵
↵
Process Type 2 ($2, x, y$): In reverse, this operation means that any $x$ existing before this point will eventually be treated as $x + y$.Update the mapping: f[x] = f[x + y].↵
↵
Process Type 1 ($1, x$):When we "add" $x$ (in reverse, this is the moment the element was born), its final value is whatever f[x] is at that moment.Store f[x] in a result list.↵
↵
Since we processed Type 1 queries from last to first, reverse your result list and print it.↵
</spoiler>↵
↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
const int N = 3e5 + 5;↵
↵
↵
void solve()↵
{↵
int q; cin >> q; ↵
vector<pair<int,int>> vp;↵
int n = 3e5 + 10;↵
↵
while(q--){↵
int a; cin >> a;↵
if(a == 1){↵
int x; cin >> x;↵
vp.push_back({x, n}); // Type 1: Add element x (using n as a marker)↵
}↵
else {↵
int x, y; cin >> x >> y;↵
vp.push_back({x, y}); // Type 2: Replace x with x + y logic↵
}↵
}↵
↵
vector<int> p(n + 1);↵
for(int i = 1; i <= n; i++) p[i] = i; // Initialize parent array for mapping↵
↵
vector<int> v;↵
int m = vp.size();↵
↵
// Process queries in reverse to handle replacements offline↵
for(int i = m - 1; i >= 0; i--){↵
int x = vp[i].first, y = vp[i].second;↵
if(y != n){↵
p[x] = p[x + y]; // Map current value x to its future replaced value↵
}↵
else {↵
v.push_back(p[x]); // Store the final mapped value of the added element↵
}↵
}↵
↵
reverse(v.begin(), v.end()); // Restore original order of additions↵
for(auto i : v) cout << i << " "; ↵
cout << endl;↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false); ↵
cin.tie(0);↵
↵
int t = 1;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:675587D]↵
↵
<spoiler summary="hint1">↵
think of invariance in single operation.↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
multiply the x and the y coordinate.↵
</spoiler>↵
↵
↵
<spoiler summary="solution">↵
The problem asks us to find the initial active cell $(s, t)$ given the final state of a 2D grid after several "toggle" operations. Each operation affects four specific points. To solve this, we must find **invariants** — properties of the active cells that do not change when the operation is performed.↵
↵
#### 1. The Invariant for $s$↵
Let's consider the function $f(x, y) = x$. When we perform an operation at $(x, y)$, the XOR sum of the $x$-coordinates of the four toggled cells is:↵
↵
$$x \oplus x \oplus (x+1) \oplus (x+1) = 0$$↵
↵
Since every operation contributes $0$ to the total XOR sum, the XOR sum of $x$-coordinates of all active cells remains constant. Initially, only $(s, t)$ was active, so:↵
↵
$$s = x_1 \oplus x_2 \oplus \dots \oplus x_n$$↵
↵
#### 2. The Invariant for $t$↵
To find $t$, we use the function $g(x, y) = x \cdot y$. The four points toggled are:↵
↵
* $P_1 = (x, y(x+1))$ which gives $g(P_1) = x \cdot y(x+1)$↵
* $P_2 = (x, (y+1)(x+1))$ which gives $g(P_2) = x \cdot (y+1)(x+1)$↵
* $P_3 = (x+1, yx)$ which gives $g(P_3) = (x+1) \cdot yx$↵
* $P_4 = (x+1, (y+1)x)$ which gives $g(P_4) = (x+1) \cdot (y+1)x$↵
↵
Notice that $g(P_1) = g(P_3)$ and $g(P_2) = g(P_4)$. When we XOR these four values together:↵
↵
$$(g(P_1) \oplus g(P_3)) \oplus (g(P_2) \oplus g(P_4)) = 0 \oplus 0 = 0$$↵
↵
This means the XOR sum of the products $(x_i \cdot y_i)$ is also an invariant!↵
↵
$$s \cdot t = (x_1 \cdot y_1) \oplus (x_2 \cdot y_2) \oplus \dots \oplus (x_n \cdot y_n)$$↵
↵
#### 3. Final Calculation↵
1. Calculate the XOR sum of all $x_i$ to get $s$.↵
2. Calculate the XOR sum of all $(x_i \cdot y_i)$ to get a value $V$.↵
3. The initial $t$ is calculated as:↵
↵
$$t = V / s$$↵
↵
**Complexity:** $O(n)$ time and $O(1)$ extra space.↵
</spoiler>↵
↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
#include <array>↵
#include <climits>↵
using namespace std;↵
↵
void solve()↵
{↵
int n;cin>>n;↵
int X=0,Y=0;↵
while(n--) {↵
int x,y;cin>>x>>y;↵
X^=x;↵
// xor of x*y↵
Y^=(x*y);↵
}↵
cout<<X<<" "<<(Y/X)<<endl;↵
}↵
↵
signed main(){↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int t=1;↵
cin>>t;↵
while(t--){↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:675587E1]↵
[problem:675587E2]↵
↵
<spoiler summary="hint1">↵
try to convert the tree in an array.↵
</spoiler>↵
↵
↵
<spoiler summary="hint2">↵
euler tour.↵
</spoiler>↵
↵
↵
<spoiler summary="hint3">↵
now you have a path in what range will the subtree of i lies?↵
</spoiler>↵
↵
↵
<spoiler summary="hint4">↵
Randomized Algorithm.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="solution(easy version)">↵
By performing a DFS Traversal, we can assign each vertex an entry time (tin) and exit time (tout).The subtree rooted at $i$ now corresponds to a contiguous range in the DFS-order array: [tin[i], tout[i]].The size of the subtree $sz$ is simply tout[i] — tin[i] + 1.↵
↵
now the range of subtree of $i$ will lies in range pos[i] to pos[i]+subtree[i];↵
↵
now we can apply a randomize search in this range .↵
↵
<spoiler summary="randomize approach">↵
if their exist a colour which is more then 1/3rd of the time if we randomly check the colour the probability that it will not be chosen is 2/3 .↵
↵
The probability of not picking a vertex of this specific color in a single random check is at most $1 - 1/3 = 2/3$.↵
↵
if we perform this operation 50 times then its very low that we may not choose a vertices whose colour appears more then 1/3 time↵
</spoiler>↵
↵
now for every query do 50+ times randomize approach then for the colour of random vertices see the freq. of that colour in the range which can be done by binary search.↵
↵
you will store the tin tout time of the vertices for every colour then sort the vector .↵
↵
then do ↵
↵
$$\text{count}(C, L, R) = \text{upper_bound}(pos[C], R) - \text{lower_bound}(pos[C], L)$$↵
</spoiler>↵
↵
can you just remove the vertices for the current colour and put it in the new colour .↵
</spoiler>↵
↵
↵
<spoiler summary="hint5">↵
use ordered_set instead of vector .↵
</spoiler>↵
↵
↵
<spoiler summary="solution(hard version) ">↵
read the solution for the easy version.↵
↵
now for the 2nd type of query you can use ordered set instead of the vector and then can erase and insert the colour according to the update and to count the frequency use this ,↵
↵
$$\text{count} = \text{ordered_set.order_of_key}(R + 1) - \text{ordered_set.order_of_key}(L)$$↵
</spoiler>↵
↵
↵
<spoiler summary="bonus">↵
try to do it with Misra-Gries Algorithm.↵
</spoiler>↵
↵
[submission:365846928]
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
#define dbg(x) cout<<#x<<' '<<x<<endl;↵
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());↵
int get(int l,int r)↵
{↵
return l + RNG()%(r - l + 1);↵
}↵
↵
const int N = 2e5+ 3;↵
vector<int>adj[N],col(N),IN(N),OUT(N),H[N],sz(N),tn(N);↵
↵
int timer = 1;↵
// euler tour↵
int dfs(int node,int par)↵
{↵
tn[timer] = node;↵
IN[node] = timer++;↵
sz[node] = 1;↵
for(auto &x:adj[node])↵
{↵
if(x == par)continue;↵
sz[node] += dfs(x,node);↵
}↵
OUT[node] = timer-1;↵
return sz[node];↵
}↵
↵
void solve()↵
{↵
int n, q;↵
cin>>n>>q;↵
map<int,int>mp,pm;↵
for(int i = 1;i<= n;i++){↵
cin>>col[i];↵
if(!mp.count(col[i])){↵
mp[col[i]] = mp.size();↵
pm[mp.size()-1] = col[i];↵
}↵
col[i] = mp[col[i]];↵
}↵
for(int i = 1;i<n;i++)↵
{↵
int a, b;cin>>a>>b;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
dfs(1,-1);↵
for(int i = 1;i<= n;i++)↵
{↵
H[col[i]].push_back(IN[i]);↵
}↵
for(int i = 0;i<= n;i++){↵
sort(H[i].begin(),H[i].end());↵
}↵
while(q--)↵
{↵
int node;cin>>node;↵
int l = IN[node],r = OUT[node];↵
//now i have the range.↵
set<int>st;↵
for(int i = 0;i< 50;i++)↵
{↵
int g = get(l,r);// random search↵
g = tn[g];//this is the node itsefl↵
int val = col[g];//this is the color itself.↵
int cnt = upper_bound(H[val].begin(),H[val].end(),r) - lower_bound(H[val].begin(),H[val].end(),l);// freq. count↵
if(cnt > (sz[node])/3)st.insert(pm[val]);↵
}↵
if(st.empty())cout<<"-1\n";↵
else{↵
cout<<st.size()<<' ';for(auto &x:st)cout<<x<<' ';cout<<'\n';↵
}↵
↵
}↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false), cin.tie(NULL);↵
int t = 1;↵
// cin>>t;↵
while(t--)solve();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="code(hard version)">↵
~~~~~↵
#include<bits/stdc++.h>↵
// PBDS headers for ordered_set↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds; //namespace for PBDS↵
↵
#define int long long↵
#define dbg(x) cout<<#x<<' '<<x<<endl;↵
↵
//Definition of ordered_set↵
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());↵
int get(int l,int r)↵
{↵
return l + RNG()%(r - l + 1);↵
}↵
↵
↵
const int N = 2e5+ 3;↵
const int MAXC = 4e5 + 5;↵
↵
ordered_set<int> H[MAXC];↵
vector<int>adj[N],col(N),IN(N),OUT(N),sz(N),tn(N);↵
↵
int timer = 1;↵
// euler tour↵
int dfs(int node,int par)↵
{↵
tn[timer] = node;↵
IN[node] = timer++;↵
sz[node] = 1;↵
for(auto &x:adj[node])↵
{↵
if(x == par)continue;↵
sz[node] += dfs(x,node);↵
}↵
OUT[node] = timer-1;↵
return sz[node];↵
}↵
↵
void solve()↵
{↵
int n, q;↵
cin>>n>>q;↵
map<int,int>mp,pm;↵
↵
for(int i = 1;i<= n;i++){↵
cin>>col[i];↵
if(!mp.count(col[i])){↵
mp[col[i]] = mp.size();↵
pm[mp.size()-1] = col[i];↵
}↵
col[i] = mp[col[i]];↵
}↵
↵
for(int i = 1;i<n;i++)↵
{↵
int a, b;cin>>a>>b;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
↵
dfs(1,-1);↵
↵
for(int i = 1;i<= n;i++)↵
{↵
H[col[i]].insert(IN[i]);↵
}↵
↵
while(q--)↵
{↵
int c;cin>>c;↵
if(c == 2)↵
{↵
int node, clr; cin >> node >> clr;↵
// Step A: Normalize the new color if it's completely new↵
if(!mp.count(clr)){↵
mp[clr] = mp.size();↵
pm[mp.size()-1] = clr;↵
}↵
↵
int new_clr_id = mp[clr];↵
int old_clr_id = col[node];↵
↵
// Erase the node's IN-time from the old color's set↵
H[old_clr_id].erase(IN[node]);↵
// Insert the node's IN-time into the new color's set↵
H[new_clr_id].insert(IN[node]);↵
// Update the color array↵
col[node] = new_clr_id;↵
}↵
else{↵
int node;cin>>node;↵
int l = IN[node],r = OUT[node];↵
↵
set<int>st;↵
for(int i = 0;i< 50;i++)↵
{↵
int g = get(l,r);↵
g = tn[g]; //this is the node itsefl↵
int val = col[g]; //this is the mapped color itself.↵
↵
// Use order_of_key to efficiently count elements in range [l, r]↵
// order_of_key(x) returns the number of elements strictly less than x.↵
// So, elements <= r minus elements < l gives elements in [l, r].↵
int cnt = H[val].order_of_key(r + 1) - H[val].order_of_key(l);↵
↵
if(cnt > (sz[node])/3) st.insert(pm[val]);↵
}↵
if(st.empty()) cout<<"-1\n";↵
else{↵
cout<<st.size()<<' ';↵
for(auto &x:st) cout<<x<<' ';↵
cout<<'\n';↵
}↵
}↵
}↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false), cin.tie(NULL);↵
int t = 1;↵
// cin>>t;↵
while(t--) solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
