what happens when you take the XOR of whole array with an element

what to do in the case when the XOR of the array is zero

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 is X the X^a[i]=0 then X=a[i] because 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

If a element doesn't divide x now will it ever divide it again.

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)

what about the case in which y==1

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.

when y==1 then just skip the operation because it will not updated any number.

what about when y is not zero and also and element is not updated because x%a[i]!=0. If when x%a[i]!=0 then will it ever be divisible after any update.. No

so now we can save all the indx which divides x and remove them when they will no longer divides x

to remove indx from x is o(n) if a[i] divides x then o(32*n)(x is <=2e9) if y>1 if y==1 skip the operation as the distinct unique value of x is <= 500 it will work.

think from the back

now when you add x can you know what value it will get converted to at the end.

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.

this the question of invariance

multiply the x and the y coordinate

if you see for x that the toggles happens in pair (x,x,x+1,x+1) the xor of the x coordinate will never change

If you multiply the x and the y coordinate then

(x,y(x+1)) = x*y*(x+1)

(x,(x+1)(y+1)) = x*(y+1)*(x+1)

(x+1,y*x)) = (x+1)*y*x

(x+1,(y+1)*x) = x*(y+1)*(x+1)

as you can see that the same hold true for (x*y) as they are toggled in pair so their XOR will not also change.

try to convert the tree in an array

euler tour(remove the 2nd occurence)

now you have a path in what range will the subtree of i lies

Randomized Algorithm

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

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

can you just remove the vertices for the current colour and put it in the new colour

use ordered_set instead of vector

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

try to do it with Misra-Gries Algorithm.