Count connected component after range edge queries.

Revision en1, by Sammmmmmm, 2023-08-11 05:58:00

Given an empty graph of n vertices and q queries.

Each queries is in the form of (x, y, l) which means you add edges (x + i, y + i) for 0 <= i <= l — 1

Report the number of connected components after q queries.

If I'm not mistaken, I remember there's a trick involving creating log2(n) DSU but I can't make out the details.

Can someone help? Thanks.

N <= 1e5

Q <= 1e5

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Sammmmmmm 2023-08-11 05:58:00 449 Initial revision (published)