【競プロ】Range Update Queryを解く(AOJ DSL_2_D)｜セグメント木

競技プログラミングが趣味でそこそこに勉強しているのですが、その備忘録です。

【競プロ】セグメント木のお勉強

最近、競プロYouTuberとして有名なかつっぱさんのチャンネルの「木マスター養成講座」を見てセグメント木の勉強をしていました。

AtCoderのD問題やE問題を埋めている最中なのですが、解けない問題がセグメント木を使う問題だったことが何回かあり、そろそろ自分もセグメント木を習得するタイミングかな…と思った次第です。

セグメント木は名前しか聞いたことがなかったですが、めっちゃわかりやすかったです。

他のwebサイトでは結構難しく説明していて、初見ではなかなか理解しにくかったのですが、かつっぱさんの解説ではスラリと頭に入ってきました。

「ぴよぴよ級」ならソラで書けそうです。

AOJ DSL_2_D Range Update Queryを解く

かつっぱさんの動画ではRMQとRSQとRAQしか解説がなかったので、取り組むことにした。

問題設定

数列 A = {a₀,a₁ ,…,a_n−1} に対し、次の２つの操作を行うプログラムを作成せよ。

update(s,t,x): a_s,a_s+1,…,a_t をxに変更する。

find(i): a_i の値を出力する。

ただし、a_i (i=0,1,…,n−1)は、2³¹-1で初期化されているものとする。

Aizu Online Judge　DSL_2_Dより

考えたこと・思ったこと

updateクエリの実装はRAQに準じて以下のようなコードでいいだろうと考えた。

/* 失敗例 */
void update(int l,int r,int x){
    l += SEG_LEN;
    r += SEG_LEN;
    while(l < r){
        if(l % 2 == 1){
            seg[l] = x;
            l++;
        }
        l /= 2;
        if(r % 2 == 1){
            seg[r-1] = x;
            r--;
        }
        r /= 2;
    }
}

次にfindクエリを実装するか…とキーボードに手を伸ばしたが、次の瞬間手が止まる。

最小値や合計を取得する場合、最下層の該当する(i+SEG_LEN番目の)ノードをmin演算していったり、プラス演算していくことで所望の値を得られる。

しかし、単純にi番目の値が欲しい場合はmin演算をするわけにもプラス演算をするわけにもいかない。

findクエリが与えられたときに取得したいのは、1番最近に更新した値なので、min演算をしてもプラス演算をしていってもi番目の要素の1番最近更新した値が取れるわけではない。

少し考えて、1番最近に更新した値をとりたいなら、値とともに「時間」の情報を持たせれば良いかも？と妄想する。

というわけで、セグメント木に「更新した時間」と「更新する値」の2つをpairとして記録していくことにした。

findクエリではi+SEG_LEN番目の値から上にさかのぼって行き、最も「時間」の値が大きいものを返せば答えが得られそうである。

提出コード


#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define INF (1LL<<31)-1
#define SEG_LEN (1LL<<18)
int t = 0;
pair<int,int> seg[SEG_LEN * 2];

void update(int l,int r,int x){
    t++;
    l += SEG_LEN;
    r += SEG_LEN;
    while(l < r){
        if(l % 2 == 1){
            seg[l] = make_pair(t,x);
            l++;
        }
        l /= 2;
        if(r % 2 == 1){
            seg[r-1] = make_pair(t,x);
            r--;
        }
        r /= 2;
    }
}

int find(int i){
    i += SEG_LEN;
    int ret;
    int time = -1;
    while(true){
        int s,v;
        if(i == 0) break;
        tie(s,v) = seg[i];
        if(time < s){
             time = s; 
             ret = v; 
        } 
        i /= 2; 
    } 
    return ret; 
} 

signed main(){ 
    int n,q; cin >> n >> q;
    rep(i,2 * SEG_LEN) seg[i] = make_pair(0,INF);
    rep(i,q){
        int query;
        cin >> query;
        if(query == 0){
            int s,t,x;
            cin >> s >> t >> x;
            update(s,t+1,x);
        }else{
            int j;
            cin >> j;
            cout << find(j) << endl;
        }
    }
}

無事ACした。セグメント木初心者の自分にとっては変化球だったので、すこし戸惑ったが…