Dynamic Range Minimum Queries

input/code.cpp: In function 'void Test()':
input/code.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen("temp\\in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
input/code.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
input/code.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf("%d%d%d", &k, &a, &b);
      |         ~~~~...

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
const int N=10005, INF=0x3f3f3f3f;

/*----------------------------------------------------------------------------*/
template<typename Value, typename Tag>
struct Node
{
    int id, l, r;
    Value val;
    Tag tag;

    inline int length()const
    {
        return r-l+1;
    }
    inline bool disjoint(const int& l_bor, const int& r_bor)const
    {
        return l_bor>r || r_bor<l;
    }// (l, r<l_bor)/(r_bor>l, r)
    inline bool subset(const int& l_bor, const int& r_bor)const
    {
        return l_bor<=l && r_bor>=r;
    }// [l_bor, l, r, r_bor]
};

template<typename Value, typename Tag>
class SegmentTree
{
  public:
    typedef Value (*FucMer)(Value, Value);
    typedef void (*FucCov)(Node<Value, Tag>*, Tag);
    SegmentTree(const FucMer f1, const FucCov f2, Value val, Tag tag)
        : Merge(f1), Cover(f2), val_zero_(val), tag_zero_(tag) {}
    void Init(const int& size, const vector<Value>& v)
    {
        l_range_=1, r_range_=size;
        nodes_.resize(size<<2);
        Build(1, l_range_, r_range_, v);
    }

    inline Node<Value, Tag>* identify(const int& p)
    {
        return &nodes_[p];
    }
    inline Node<Value, Tag>* l_child(const Node<Value, Tag>* p)
    {
        return &nodes_[p->id<<1];
    }// 2*id for the left child
    inline Node<Value, Tag>* r_child(const Node<Value, Tag>* p)
    {
        return &nodes_[p->id<<1|1];
    }// 2*id+1 for the right child

    void Modify(const int& pos, const Tag& tag)
    {
        Modify(identify(1), pos, pos, tag);
    }// point change
    void Modify(const int& l_bor, const int& r_bor, const Tag& tag)
    {
        Modify(identify(1), l_bor, r_bor, tag);
    }// section change
    Value Query(const int& pos)
    {
        return Query(identify(1), pos, pos);
    }// point query
    Value Query(const int& l_bor, const int& r_bor)
    {
        return Query(identify(1), l_bor, r_bor);
    }// section query

  private:
    const FucMer Merge;
    const FucCov Cover;
    const Value val_zero_;
    const Tag tag_zero_;
    int l_range_, r_range_;
    vector<Node<Value, Tag>> nodes_;

    inline void PushUp(Node<Value, Tag>* p)
    {
        p->val=Merge(l_child(p)->val, r_child(p)->val);
    }
    inline void PushDown(Node<Value, Tag>* p)
    {
        Cover(l_child(p), p->tag);
        Cover(r_child(p), p->tag);
        p->tag=tag_zero_;
    }

    void Build(int cur, int l_cur, int r_cur, const vector<Value>& v)
    {
        Node<Value, Tag> *p=identify(cur);
        p->id=cur, p->l=l_cur, p->r=r_cur;
        p->tag=tag_zero_;
        if(l_cur>r_cur) return;
        if(l_cur==r_cur) { p->val=v[l_cur]; return; }
        int mid=(l_cur+r_cur)>>1;
        Build(cur<<1, l_cur, mid, v);
        Build(cur<<1|1, mid+1, r_cur, v);
        PushUp(p);
    }

    void Modify(Node<Value, Tag> *p, const int& l_bor, const int& r_bor,
                const Tag& tag)
    {
        if(p->disjoint(l_bor, r_bor)) return;
        if(p->subset(l_bor, r_bor)) { Cover(p, tag); return; }
        if(p->tag!=tag_zero_) PushDown(p);
        Modify(l_child(p), l_bor, r_bor, tag);
        Modify(r_child(p), l_bor, r_bor, tag);
        PushUp(p);
    }

    Value Query(Node<Value, Tag>* p, const int& l_bor, const int& r_bor)
    {
        if(p->disjoint(l_bor, r_bor)) return val_zero_;
        if(p->subset(l_bor, r_bor))   return p->val;
        if(p->tag!=tag_zero_) PushDown(p);
        return Merge(Query(l_child(p), l_bor, r_bor), 
                     Query(r_child(p), l_bor, r_bor));
    } 
};
/*----------------------------------------------------------------------------*/

auto h1=[](int a, int b) -> int { return a<b? a:b; };
auto h2=[](Node<int, int>* p, int x) { p->val=x; };
SegmentTree<int, int> h_min(h1, h2, INF, INF);

void Test()
{
    freopen("temp\\in.txt", "r", stdin);
}
int main()
{
    // Test();
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> v;
    v.push_back(0);
    for(int i=1, x; i<=n; i++)
    {
        scanf("%d", &x);
        v.push_back(x);
    }
    h_min.Init(n, v);
    while(q--)
    {
        int k, a, b;
        scanf("%d%d%d", &k, &a, &b);
        if(k==1)
            h_min.Modify(a, b);
        else
            printf("%d\n", h_min.Query(a, b));
    }
    

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED