Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

yukicoder contest No.222 反省会

鬼のセグメントツリー祭。★の数的に頭の3問しか勝負にならなそうなので、これだけは解くぞと思って望んだが、Cが解けなかった。2完。順位は77/133

A

No.875 Range Mindex Query - yukicoder

ただ最小値を求めるだから簡単だが、そのインデックスを求めろという問題。単に、値からインデックスへの変換をメンテし続ければよい。

B

No.876 Range Compress Query - yukicoder

むしろ確実に解けたことに成長を感じる問題。

式からも明らかだが、サンプルをもとにして考えるとわかりやすい。サンプルの4つ目のクエリについて考えると、1773という状態を(1,1),(7,2),(3,1)とランレングス圧縮してあると考えて、所属するグループのインデックスの差分を考えればよい。(例えばこの場合であれば、1,4がクエリなら、1つ目は(1,1)に含まれていて、4つ目は(3,1)に含まれているから、3-1+1とする)

この情報を管理するために、BITがあればよい。例えば、1333の場合であれば、1100と立てる。1773であれば、1101と立てる。どの何番目のグループに所属しているかというのは、この区間和を求めるという話に帰着出来る。

もう一つ、遅延セグツリーで範囲更新をして、値を管理しておく。そうすると、例えば、1333から1773に変化した時には、1と3の境界は「同じか異なるか」の関係が変わっていないから11xxのままでよく、73の部分はもともと同じだったものが違うものになっているから、3のところに1加算して、1101とすればいい。こういう感じで更新境界面の状態に応じて、BITを更新していけばよい。

fn solve() {
    input!{
        new_stdin_parser = parser,
        N:usize,Q:usize, a:[usize;N],
    }
    let mut q=vec![];
    for _ in 0..Q {
        input!{
            parser=parser,
            t:usize,
        }
        if t==1 {
            input!{
                parser=parser,
                l:usize,r:usize,x:usize,
            }
            q.push(T::U(l,r,x));
        }
        else if t==2 {
            input!{
                parser=parser,
                l:usize,r:usize,
            }
            q.push(T::Q(l,r));
        }
    }
    let mut group = BIT::new(N);
    let mut value: SEG<RMQ_RAQ> = SEG::new(0,N+1);
    let mut acc=0;
    for i in 0..N {
        let ai=a[i];
        if ai!=acc {
            group.add(i+1, 1);
            acc=ai;
        }
        value.update(i+1, i+2, ai);
    }
    for qi in q {
        match qi {
            T::U(l,r,x) => {
                let mut left_eq = true;
                if l>=2 {
                    let al=value.query(l, l+1);
                    let all=value.query(l-1, l);
                    // dbg!(al,all);
                    if al!=all {
                        left_eq=false;
                    }
                }
                let mut right_eq = true;
                if r+1<=N {
                    let ar=value.query(r, r+1);
                    let arr=value.query(r+1, r+2);
                    if ar!=arr {
                        right_eq=false;
                    }
                }
                value.update(l, r+1, x);
                // dbg!(left_eq,right_eq);
                if l>=2 {
                    let al=value.query(l, l+1);
                    let all=value.query(l-1, l);
                    if left_eq && al!=all {
                        group.add(l,1);
                    }
                    else if !left_eq && al==all {
                        group.add(l,-1);
                    }
                }
                if r+1<=N {
                    let ar=value.query(r, r+1);
                    let arr=value.query(r+1, r+2);
                    if right_eq && ar!=arr {
                        group.add(r+1,1);
                    }
                    else if !right_eq && ar==arr {
                        group.add(r+1,-1);
                    }
                }
            },
            T::Q(l,r) => {
                let vl=group.sum(l);
                let vr=group.sum(r);
                // dbg!((vl,vr));
                println!("{}",vr-vl+1);
            }
        }
    }
}

C (WA)

No.877 Range ReLU Query - yukicoder

もし、値がソートされているならば解けるが、このまま解くのはどうやればいいのかわからなかった。

なんとなく特殊なセグツリーを定義するということなのではないかと思った。

たこやきのにおいがした。 D - タコヤキオイシクナール