test/segtree2.test.cpp

• View this file on GitHub
• Last update: 2024-03-09 16:51:27+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

Depends on

• セグメント木 (C++/ds/SegmentTree.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A"
#include <iostream>
#include <limits>
#include "C++/ds/SegmentTree.hpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    SegTree<int> seg(n, [](const int x, const int y) -> int { return std::min(x, y); }, std::numeric_limits<int>::max());
    while(q--) {
        int com, x, y;
        std::cin >> com >> x >> y;
        if(com == 0) {
            seg.update(x, y);
        } else {
            std::cout << seg.query(x, y + 1) << '\n';
        }
    }
}

#line 1 "test/segtree2.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A"
#include <iostream>
#include <limits>
#line 2 "C++/ds/SegmentTree.hpp"

#pragma GCC diagnostic ignored "-Wreorder"

#include <vector>

#include <functional>

template <class T> struct SegTree {
private:
    using F = std::function<T(T, T)>;
    int n, rank, fine;
    const F f;
    const T e;
    std::vector<T> dat;
public:
    SegTree(const int n_, const F f_, const T& e_): f(f_), e(e_), fine(n_) {
        n=1,rank=0;
        while(fine>n) n<<=1LL,rank++;
        dat.assign(2*n,e_);
    }
    SegTree(const std::vector<T> &v, const F f_, const T e_): f(f_), e(e_), fine(v.size()) {
        n=1,rank=0;
        while(fine>n) n<<=1LL,rank++;
        dat.assign(2*n,e_);
        for(size_t i=0; i<v.size(); ++i) update(i,v[i]);
    }
    T operator[](int i) const { return dat[i+n]; }
    void update(int i, const T& x) {
        i+=n;
        dat[i]=x;
        while(i>>=1LL) dat[i]=f(dat[2*i],dat[2*i+1]);
    }
    void add(int i, const T& x) {
        i+=n;
        dat[i]+=x;
        while(i>>=1LL) dat[i]=f(dat[2*i],dat[2*i+1]);
    }
    T query(int a, int b) const {
        T l=e,r=e;
        for(a+=n, b+=n; a<b; a>>=1LL,b>>=1LL) {
            if(a&1) l=f(l,dat[a++]);
            if(b&1) r=f(dat[--b],r);
        }
        return f(l,r);
    }
    T alle() const { return dat[1]; }
    template <class Boolean=bool> inline int find_left(int r, const Boolean &fn) {
        if(!r) return 0;
        int h=0,i=r+n;
        T val=e;
        for(; h <= rank; h++) if(i>>h&1){
            T val2=f(val,dat[i>>h^1]);
            if(fn(val2)){
                i -= 1<<h;
                if(i==n) return 0;
                val=val2;
            }
            else break;
        }
        for(; h--;){
            T val2 = f(val,dat[(i>>h)-1]);
            if(fn(val2)){
                i-=1<<h;
                if(i==n) return 0;
                val=val2;
            }
        }
        return i-n;
    }
    template <class Boolean=bool> inline int find_right(int l, const Boolean &fn) {
        if(l==fine) return fine;
        int h=0,i=l+n;
        T val=e;
        for(; h<=rank; h++) if(i>>h&1){
            T val2=f(val,dat[i>>h]);
            if(fn(val2)){
                i+=1LL<<h;
                if(i==n*2) return fine;
                val=val2;
            }
            else break;
        }
        for(; h--;){
            T val2=f(val, dat[i>>h]);
            if(fn(val2)){
                i+=1LL<<h;
                if(i==n*2) return fine;
                val=val2;
            }
        }
        return std::min(i-n,fine);
    }
};
/**
 * @brief セグメント木
 * @see https://github.com/tatyam-prime/kyopro_library/blob/master/SegmentTree.cpp
 */
#line 5 "test/segtree2.test.cpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    SegTree<int> seg(n, [](const int x, const int y) -> int { return std::min(x, y); }, std::numeric_limits<int>::max());
    while(q--) {
        int com, x, y;
        std::cin >> com >> x >> y;
        if(com == 0) {
            seg.update(x, y);
        } else {
            std::cout << seg.query(x, y + 1) << '\n';
        }
    }
}

Back to top page