Masking Tape の解説

"あとから塗られたもので全て上書きされる"

という性質からうしろから見ればうまくいくと安直に考える。

ただ、"今タイルが置かれているか"というフラグは持っておきたいので、 一度前から見てタイルの情報をさらってから、逆順で答えを求める。

#[derive(Debug, Clone, Copy)]
enum Query {
    Tile(usize),
    Color(char),
}

fn main() {
    input! {
        n: usize, q: usize
    }
    let query = (0..q)
        .map(|_e| {
            input! {
                t: usize
            }
            if t == 1 {
                input! {
                    x: Usize1
                }
                Query::Tile(x)
            } else {
                input! {
                    c: char
                }
                Query::Color(c)
            }
        })
        .collect_vec();
    let mut isopen = vec![true; n];
    for &q in query.iter() {
        match q {
            Query::Tile(v) => {
                isopen[v] = !isopen[v];
            }
            _ => {}
        }
    }
    let mut set = (0..n).filter(|&e| isopen[e]).collect::<BTreeSet<usize>>();
    let mut ans = vec!['a'; n];
    let mut det = vec![false; n];
    for &q in query.iter().rev() {
        match q {
            Query::Tile(x) => {
                if det[x] {
                    continue;
                }
                if set.contains(&x) {
                    set.remove(&x);
                } else {
                    set.insert(x);
                }
            },
            Query::Color(c) => {
                while !set.is_empty() {
                    let pop = set.pop_first().unwrap();
                    ans[pop] = c;
                    det[pop] = true;
                }
            }
        }
    }
    println!("{}", ans.iter().join(""));
}