AOJ 2359 - Range Minimum Query

問題: 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;
}