競技プログラミングが趣味でそこそこに勉強しているのですが、その備忘録です。
【競プロ】セグメント木のお勉強
最近、競プロYouTuberとして有名なかつっぱさんのチャンネルの「木マスター養成講座」を見てセグメント木の勉強をしていました。
AtCoderのD問題やE問題を埋めている最中なのですが、解けない問題がセグメント木を使う問題だったことが何回かあり、そろそろ自分もセグメント木を習得するタイミングかな…と思った次第です。
セグメント木は名前しか聞いたことがなかったですが、めっちゃわかりやすかったです。
他のwebサイトでは結構難しく説明していて、初見ではなかなか理解しにくかったのですが、かつっぱさんの解説ではスラリと頭に入ってきました。
「ぴよぴよ級」ならソラで書けそうです。
AOJ DSL_2_D Range Update Queryを解く
かつっぱさんの動画ではRMQとRSQとRAQしか解説がなかったので、取り組むことにした。
問題設定
数列 A = {a0,a1 ,…,an−1} に対し、次の2つの操作を行うプログラムを作成せよ。
- update(s,t,x): as,as+1,…,at をxに変更する。
- find(i): ai の値を出力する。
ただし、ai (i=0,1,…,n−1)は、231-1で初期化されているものとする。
考えたこと・思ったこと
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した。セグメント木初心者の自分にとっては変化球だったので、すこし戸惑ったが…
コメントを残す