Submission #59869623

---

Source Code Expand

use ac_library::{dsu, Dsu};
use itertools::Itertools;
use proconio::{input, marker::Usize1};
fn main() {
    input! {
        n: usize,
        q: usize,
    }

    let mut uf = Dsu::new(n);
    let mut color = (0..n).collect_vec();
    let mut r = (0..n).map(|i| (i, i)).collect_vec();
    let mut ans = vec![1; n];

    for _ in 0..q {
        input! {
            t: u8,
        }
        match t {
            1 => {
                input! {
                    x: Usize1,
                    c: Usize1,
                }

                ans[color[uf.leader(x)]] -= uf.size(x);
                ans[c] += uf.size(x);
                color[uf.leader(x)] = c;

                // 右へ
                let mut right = r[uf.leader(x)].1;
                let mut left = r[uf.leader(x)].0;

                while right + 1 < n && color[uf.leader(right + 1)] == c {
                    let max_r = r[uf.leader(right + 1)].1;

                    uf.merge(right, right + 1);
                    right = max_r;
                    r[uf.leader(x)] = (left, right);
                }

                while left >= 1 && color[uf.leader(left - 1)] == c {
                    let max_l = r[uf.leader(left - 1)].0;
                    uf.merge(left, left - 1);
                    left = max_l;
                    r[uf.leader(x)] = (left, right);
                }
            }
            2 => {
                input! {
                    c: Usize1,
                }
                println!("{}", ans[c]);
            }
            _ => {
                unreachable!()
            }
        }
    }
}

Submission Info

Compile Error

warning: unused import: `dsu`
 --> src/main.rs:1:18
  |
1 | use ac_library::{dsu, Dsu};
  |                  ^^^
  |
  = note: `#[warn(unused_imports)]` on by default

Judge Result