[Sprout OJ] No.80 RMQ練習

題目來源:https://neoj.sprout.tw/problem/80/

這題只是單純的RMQ問題，只要好好地維護遞迴的性質並且只要單點修改(不須推下去)，因此就變成了普通的模板題。

#pragma gcc optimize("o2")
#include<bits/stdc++.h>
#define int long long int 
#define IOS ios_base::sync_with_stdio(false)
#define TO cin.tie(NULL)
#define MAXN 1000000
using namespace std;
struct Node{
    int l,r;
    int lson,rson;
    int data;
};
Node segtr[MAXN*2];
int str[MAXN];
int ptr=0;
void build(int l,int r,int index)
{
    segtr[index].l=l;
    segtr[index].r=r;
    int mid=(l+r)/2;
    if(l==r-1)
        segtr[index].data=str[l];

    else
    {
        int lson=segtr[index].lson=++ptr;

        int rson=segtr[index].rson=++ptr;

        build(l,mid,lson);

        build(mid,r,rson);

        segtr[index].data=min(segtr[lson].data,segtr[rson].data);

    }
}
void modify(int x,int val,int index)
{
    if(segtr[index].l==segtr[index].r-1)
        segtr[index].data=val;

    else
    {

        int lson=segtr[index].lson;

        int rson=segtr[index].rson;

        int mid=(segtr[index].l+segtr[index].r)/2;

        if(x<mid) modify(x,val,lson);

        else modify(x,val,rson);

        segtr[index].data=min(segtr[lson].data,segtr[rson].data);

    }
}
int query(int l,int r,int index)
{
    if(segtr[index].l==l && segtr[index].r==r)

    return segtr[index].data;
    else
    {
        //cout << segtr[index].l << " " << segtr[index].r <<endl;

        int mid=(segtr[index].l+segtr[index].r)/2;

        int lson=segtr[index].lson;

        int rson=segtr[index].rson;

        //cout << mid <<endl;

        //cout << l << " " << r << endl;

        //cout << segtr[index].l << " " << segtr[index].r <<endl; 

        if(r<=mid) return query(l,r,lson);

        else if(l>=mid) return query(l,r,rson);

        else return min(query(l,mid,lson),query(mid,r,rson));

    }
}
signed main()
{
    IOS;TO;
    int T,N,deter,x,y;
    cin >> T >> N;
    for(int i=0;i<N;i++)
        cin >> str[i];

    build(0,N,0);
    //cout << segtr[0].l <<endl;
    //cout << segtr[0].r <<endl;
    while(T--)
    {
        cin >> deter >> x >> y;

        if(deter==1)

            cout << query(x,y+1,0) << endl;

        else

        modify(x,y,0);

    }
    return 0;
}

我有時會發現自己翻舊題目刷時都會耍向，我尤其是把++ptr開心地寫成ptr++讓我DE了快2個小時，我好垃圾。
這題只是單純的裸RMQ模板題，這時我才發現我不會指標......