So what? Same thing could be said about countless other problems. One could say the same thing whenever he encounters an MST or shortest path problem.

You have to extend the set of vertices where degree is bigger than N/2 to its maximal, since vertices of degree no more then N/2 may also in the set.

Thank you very much for this explanation.

Now I got E

Sorry, I don't get this part:

but the sum of N-deg(v) is at most 2M, hence their sum of degrees is at most 2M as well

Why "N-deg(v) is at most 2M", and what does "N-deg(v)" imply? and how we can derive "their sum of degrees is at most 2M" from that?

Nice idea

can you share your code for this logic. ?

Here's another method you can use with similar bounding logic but perhaps an even lazier insight: take the vertex $$$v$$$ with minimum degree. Note that $$$d(v) \leq \frac{2m}{n}$$$. You can use union-find on all the vertices $$$v$$$ is actually connected to, and then repeat the process for the all the vertices $$$v$$$ is not actually connected to. Since you have to do this for at most $$$\frac{2m}{n}$$$ vertices, and each one has less than $$$n$$$ real edges, you won't have to call dsu join more than $$$2m$$$ times.

As an aside, it appears I tried this problem (unsuccessfully) 7 years ago, and after solving it now I came to look at the comments, and found that I had already upvoted yours! So perhaps your logic was floating somewhere in the back of my mind

I belive its because you should not keep using the iterator it after you erased it from the set

Could someone explain it in a better way/more understandable way? Or Can someone provide the Implementation?

Thanks.

Unfortunately, I'm not sure what to write there additionaly.

The algorithm is just typical DFS, but instead of iterating on adjacency list of current vertex and trying to find an unvisited vertex, we have it backwards: we iterate on the set of unvisited vertices and try to find the one that can be reached from current vertex.

Perhaps my implementation can help to understand it better.

What is p, x and k in the editorial?

Поищи knapsack problem.

if you cant add edge 1->2 it means you can add 2->1 ,so if the still add the edge 1->2,because the probelm is asking component so it doesnt matter. I think so...

Thank you, fixed.

Here's my implementation of this idea with a segment tree and a set: 45337647. Hope it helps anyone looking to implement the problem this way as its much easier than the 2 segment trees idea in the editorial.

I'd finally fixed it. In update procedure added one more verification. If somebody needs, here is my final solution

Well, the main difficulty is that you have to be familiar with inclusion-exclusion principle.

Let's use binary search to find the answer. Then we need to somehow calculate the number of good integers (good integers are coprime with p) from integer x to integer mid (the middle element in binary search). It's better to rewrite it as count(mid) - count(x), where count(x) is the number of good integers not exceeding x.

Now we somehow have to calculate this count(x). We need to find all good integers from [1, x]; these are all integers from [1, x] excluding those that are divisible by some prime divisor of p. To find the latter, we use inclusion-exclusion principle: let our sets A₁, A₂, ..., A_n be the sets of integers divisible by the first, the second, ..., the n-th prime divisor of p. And then we apply inclusion-exclusion formula as it is — since the maximum number of primes in factorization of p is 7, then we can just iterate through all possible combinations of these sets A₁ ... A_n.

Well, actually if we set in A(p, y) mentioned in editorial p = y, then we will get exactly φ(p). So I believe Euler's function can be calculated using inclusion/exclusion, it's just not convenient to do it this way.

The thing is that you can't just try updating each of the indices from [l, r] if you have REPLACE query.

You have to use the segment tree for your updates. It is difficult for me to explain. You have to make the queries in a similar manner to mass change queries in segment trees, but instead of pushing some values you need to do the following if you have to update the whole segment:

1) If the maximum element on this segment is 1 or 2, then just stop updating the segment, you don't need to do anything in it.

2) Otherwise, if the segment contains more than one element, divide it into two segments (just the way segment tree does it) and try updating these segments.

I think that our implementation may help. Take a look at how we have written upd function.

I'm getting TLE with this logic(35463032). Could you help me out? UPD: solved

Thanks for this solution. It helped me a lot

Can u elaborate your approach? i am curious to find a solutio using dsu