Count connected component after range edge queries.

Правка en1, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Sammmmmmm 2023-08-11 05:58:00 449 Initial revision (published)