問題: AOJ 2359 - Range Minimum Query
宮村さんによる解説スライド: Rmq
昔立命館合宿で解けなかった問題.
WAするので解説スライド読んで自分のソースの間違いを見つけた. スライドあまり理解できていないけど, ほとんどスライドと同じだと思う.
解法:
この問題は大きく3つの作業をすることに分けることができて,
- 適切に座標圧縮する.
- 妥当な初期値を決める.
- その初期値を元に実際にシミュレーションする.
となる.
「適切な座標圧縮」
スライドにもあるように[40, 55], [55, 70], [40, 70]を[1,2],[2,3],[1,3]と見なしてはいけないので, 「クエリで与えられる座標」だけでなく, 「クエリで与えられる座標+1」も座標圧縮に加味する.
なぜ駄目かというと, それぞれの値の隙間に最小値があると結果が変わってくるから.
「妥当な初期値を決める」
- 確認クエリ(t_i=0のクエリ)で,その時点でのある区間[a_i,b_i]の下限が得られるので, それを更新する.
- 代入クエリ(t_i=1のクエリ)が来た時, その区間の現在の下限で初期値を確定させる. ただしそれぞれの位置について1回目のみ.
- 最後に確定してないやつを全部その時の下限で更新する.
とかいう手法で実現できる.
下限の更新は区間内の最大を更新セグメントツリーを書けば良い. 今回の場合,取得クエリが点に対してという性質を利用して, シンプルなセグメントツリーで実装できる. (ソース参照)
確定については, それぞれの位置について1回しか更新しないので,僕はset使って, 更新した値の座標を削除していくとかいう手法で誤魔化した.
「その初期値を元に実際にシミュレーションする」
前の記事で説明したようなセグメントツリーを使うと,チョロく実装できる.なのでそれを実装してシミュレーションする.
ソース
割と頭悪い実装してるのに0.15sとかでテストケース弱いのかもしれない.
#include <iostream> #include <vector> #include <cstdio> #include <queue> #include <cstdlib> #include <set> #include <algorithm> using namespace std; #define N (1<<18) //シミュレーション用のセグメントツリー struct Node{ int minimum; int lazy; Node(){ minimum = lazy = 0; } }; Node seg[2*N]; void update(int l,int r,int v,int k=1,int a=1,int b=N){ if( seg[k].lazy && k < N ){ seg[k*2].minimum = seg[k].lazy; seg[k*2+1].minimum = seg[k].lazy; seg[k*2].lazy = seg[k].lazy; seg[k*2+1].lazy = seg[k].lazy; } seg[k].lazy = 0; if( b < l || r < a ) return; if( l <= a && b <= r ){ seg[k].minimum = v; seg[k].lazy = v; return; } int m = (a+b)>>1; update(l,r,v,k*2,a,m); update(l,r,v,k*2+1,m+1,b); seg[k].minimum = min( seg[k*2].minimum , seg[k*2+1].minimum ); } int get(int l,int r,int k=1,int a=1,int b=N){ if( seg[k].lazy && k < N ){ seg[k*2].minimum = seg[k].lazy; seg[k*2+1].minimum = seg[k].lazy; seg[k*2].lazy = seg[k].lazy; seg[k*2+1].lazy = seg[k].lazy; } seg[k].lazy = 0; if( b < l || r < a ) return 2e9; if( l <= a && b <= r ){ return seg[k].minimum; } int m = (a+b)>>1; int vl = get(l,r,k*2,a,m); int vr = get(l,r,k*2+1,m+1,b); seg[k].minimum = min( seg[k*2].minimum , seg[k*2+1].minimum ); return min(vl,vr); } //初期配列構築用のセグメントツリー int seg2[2*N]; void update2(int l,int r,int v,int k=1,int a=1,int b=N){ if( b < l || r < a ) return; if( l <= a && b <= r ){ seg2[k] = max(seg2[k],v); return; } int m = (a+b)>>1; update2(l,r,v,k*2,a,m); update2(l,r,v,k*2+1,m+1,b); } int get2(int i){ i += N - 1; int ans = 0; while(i){ ans = max( ans , seg2[i]); i /= 2; } return ans; } int Q,n; struct Query{ int t,a,b,y; }; Query que[50000]; set<int> next; vector<int> u; int main(){ scanf("%d",&Q); for(int i = 0 ; i < Q ; i++){ scanf("%d%d%d%d",&que[i].t,&que[i].a,&que[i].b,&que[i].y); } //座標圧縮 for(int i = 0 ; i < Q ; i++){ u.push_back(que[i].a); u.push_back(que[i].a+1); u.push_back(que[i].b); u.push_back(que[i].b+1); } u.push_back(0); sort(u.begin(),u.end()); u.erase(unique(u.begin(),u.end()),u.end()); n = u.size(); for(int i = 0 ; i < Q ; i++){ que[i].a = lower_bound(u.begin(),u.end(),que[i].a) - u.begin(); que[i].b = lower_bound(u.begin(),u.end(),que[i].b) - u.begin(); } //初期値配列構築 for(int i = 1 ; i < n ; i++) next.insert(i); vector<int> arr(n); for(int i = 0 ; i < Q ; i++){ if( que[i].t == 0 ){ update2(que[i].a,que[i].b,que[i].y); }else{ set<int>::iterator it = next.lower_bound(que[i].a); while(it != next.end()){ if( *it > que[i].b ) break; arr[*it] = get2(*it); next.erase(it++); } } } for(set<int>::iterator it = next.begin(); it != next.end(); ++it){ arr[*it] = get2(*it); } //シミュレーション for(int i = 1 ; i < n ; i++) update(i,i,arr[i]); for(int i = 0 ; i < Q ; i++){ if( que[i].t == 0 ){ if( que[i].y != get(que[i].a,que[i].b) ){ cout << "NO" << endl; return 0; } }else{ update(que[i].a,que[i].b,que[i].y); } } cout << "YES" << endl; }