UVa12299 - RMQ with Shifts (Segment Tree)

2020-03-23

UVa

字數統計： 767 | 閱讀時間≈ 4分鐘

題目大意：
分析：
1. 注意：
備註：

題目大意：

給予一個數組，有兩種操作

query l r : 查詢 l 到 r 的最小值

shift x1 , x2 , x3 : 原本的值都往前循環一個位置

分析：

透過線段樹來維護最小值查詢，加上 shift 的數字最多只有 30 位，透過單點修改的方式即可完成。

注意：

shift 給的是位置，並不是數值，也不一定給你的位置會是照順序，所以必須要進行 sort

備註：

要是不知道 RMQ (Range Minimum/Maximum Query)) 就看 Tushar Roy - Coding Made Simple

~~印度人教程式真的強，不知道為甚麼感覺看中文的教學影片都比較沒辦法聽得懂阿，難道真的是語言的關係嗎QQ~~

#include <iostream>
#include <bits/stdc++.h>
#include <string>
#define LOCAL
#define Lson(x) ((x << 1) +1)
#define Rson(x) ((x << 1) +2)
#define INF 99999999
using namespace std;
const int N = 100005 ;
int shift[35] , num[N] , len_shift ;
string strLine ;


struct Node{
    int left , right , Min_Value  ;
}node[4 * N ];


void build(int left , int right , int x = 0 ){
    node[x].left = left ;
    node[x].right = right ;
    if(left == right){
        node[x].Min_Value = num[left] ;
        return ;
    }
    int mid = (left + right ) / 2 ;

    //debug
    //cout << mid << '\n' ;
    //cout << x << ' ' << node[x].left << ' ' << node[x].right << ' ' << '\n' ;

    build(left , mid , Lson(x)) ;
    build(mid + 1 , right , Rson(x)) ;
    node[x].Min_Value = min(node[Lson(x)].Min_Value  , node[Rson(x)].Min_Value ) ;
}


void handle(){
    len_shift = 0 ;
    shift[len_shift] = 0;
    for(int i = 6 ; i < strLine.length() ; i++){
        if(strLine[i] >= '0' && strLine[i] <= '9' ){
            shift[len_shift] = shift[len_shift] * 10 + (int) (strLine[i] - '0' ) ;
        }
        else{
            shift[++len_shift ] = 0 ;
        }
    }
    //finaly char is ')' , so len_shift is right
    sort(shift , shift + len_shift ) ;

    //debug
    /**<
    for(int i = 0 ; i < len_shift ; i++)
        cout << shift[i] << ' ' ;
    cout << '\n' ;
    */
}


int query(int left , int right , int x = 0 ){
    if(node[x].left >= left && node[x].right <= right)
        return node[x].Min_Value ;
    int mid = (node[x].left + node[x].right ) / 2 ;
    int ans = INF ;

    //debug
    //cout << x << ' ' << node[x].left << ' ' << node[x].right << ' ' << node[x].Min_Value << '\n' ;

    if( left <= mid )
        ans = min(ans , query(left , right , Lson(x))) ;
    if(mid < right )
        ans = min(ans , query(left , right , Rson(x))) ;
    return ans ;
}


void set_num(int position , int value , int x = 0 ){
    if(node[x].left == position && node[x].right == position ){
       node[x].Min_Value = value ;
       return ;
    }
    int mid = (node[x].left + node[x].right ) / 2 ;
    if(position <= mid )
        set_num(position , value , Lson(x) );
    if(mid < position )
        set_num(position , value , Rson(x)) ;
    node[x].Min_Value = min(node[Lson(x)].Min_Value , node[Rson(x)].Min_Value );

}


int main()
{
    int n , q , intTemp ;
    ios::sync_with_stdio(0);
#ifdef LOCAL
    freopen("out.txt" , "w" , stdout ) ;
    freopen("in1.txt" , "r" , stdin ) ;
#endif // LOCAL
    cin >> n >> q ;
    for(int i = 1 ; i <= n ; i++)
        cin >> num[i] ;
    build(1,n);

    //debug
    /**<
    for(int i = 0 ; i < 13 ; i++){
        cout << node[i].left << ' ' << node[i].right << ' ' << node[i].Min_Value << '\n' ;
    }
    return 0 ;
    */

    while(q--){
        cin >> strLine ;
        if(strLine[0] == 'q'){
            handle();
            cout << query(shift[0] , shift[1] ) << '\n' ;
        }
        else if (strLine[0] == 's'){
            handle();
            intTemp = num[shift[0]] ;

            for(int i = 1 ; i < len_shift ; i++){
                set_num(shift[i-1] , num[shift[i]]) ;
                num[shift[i-1]] = num[shift[i]] ;
            }
            num[shift[len_shift-1]] = intTemp ;
            set_num(shift[len_shift-1] , intTemp );

            //debug
            //cout << intTemp << ' ' << shift[len_shift-1] << '\n' ;
            //for(int i = 1 ; i <= n ; i++)
             //   cout << num[i] << ' ' ;
        }
    }
    return 0;
}

版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！