Submission #58005618

---

Source Code Expand

#include <bits/stdc++.h>

template<typename T>
class segmenttree{
    // Copyright (c) 2024 0214sh7
    // https://github.com/0214sh7/library/
    private:
    int n;
    int size_;
    std::vector<T> dat;
    std::function<T(T,T)> calc;
    T id;

    public:

    void init(int N, std::function<T(T,T)> func, T e){
        size_ = N;
        n = 1;
        while(n<N)n<<=1;
        calc = func;
        id = e;
        dat.assign(2*n-1,e);
    }

    void init(std::vector<T> a, std::function<T(T,T)> func, T e){
        init(a.size(),func,e);
        set(a);
    }

    segmenttree(int N, std::function<T(T,T)> func, T e){
        init(N,func,e);
    }

    segmenttree(std::vector<T> a, std::function<T(T,T)> func, T e){
        init(a,func,e);
    }

    void set(int k, T a){
        assert(0<=k && k<size_);
        k += n-1;
        dat[k] = a;
        while(k>0){
            k = (k-1)/2;
            dat[k] = calc(dat[2*k+1],dat[2*k+2]);
        }
    }

    void set(std::vector<T> a){
        assert((int)a.size()==size_);
        dat.assign(2*n-1,id);
        for(int k=0;k<size_;k++){
            dat[n+k-1] = a[k];
        }
        for(int k=n-2;k>=0;k--){
            dat[k] = calc(dat[2*k+1],dat[2*k+2]);
        }
    }

    T prod(int a,int b){
        assert(0<=a && a<=b && b<=size_);
        a += n-1;
        b += n-1;
        T L = id, R = id;
        while(a<b){
            if(a%2==0){
                L = calc(L,dat[a]);
                a++;
            }
            a = (a-1)/2;
            if(b%2==0){
                b--;
                R = calc(dat[b],R);
            }
            b = (b-1)/2;
        }
        return calc(L,R);
    }

    int max_right(int l, std::function<bool(T)> f){
        assert(0<=l && l<=size_);
        assert(f(id));

        l += n-1;
        int k = l;
        int sum = id;
        
        while(1){
            while(k%2==1)k=(k-1)/2;
            T newsum = calc(sum,dat[k]);
            if(f(newsum)){
                sum = newsum;
                if(((k+2) & -(k+2)) == (k+2)){
                    return size_;
                }
                k++;
            }else{
                break;
            }
        }

        while(k < n-1){
            T newsum = calc(sum,dat[2*k+1]);
            if(f(newsum)){
                sum = newsum;
                k = 2*k+2;
            }else{
                k = 2*k+1;
            }
        }

        return k-n+1;
    }
    
    int min_left(int r, std::function<bool(T)> f){
        assert(0<=r && r<=size_);
        assert(f(id));
        if(r==0)return 0;

        r += n-1;r--;
        int k = r;
        int sum = id;
        
        while(1){
            while(k%2==0)k=(k-1)/2;
            T newsum = calc(dat[k],sum);
            if(f(newsum)){
                sum = newsum;
                if(((k+1) & -(k+1)) == (k+1)){
                    return 0;
                }
                k--;
            }else{
                break;
            }
        }

        while(k < n-1){
            T newsum = calc(dat[2*k+2],sum);
            if(f(newsum)){
                sum = newsum;
                k = 2*k+1;
            }else{
                k = 2*k+2;
            }
        }

        return k-n+2;
    }

};

int main(void){
    
    int N,Q;
    std::cin >> N >> Q;

    std::vector<long long> A(N);
    for(int i=0;i<N;i++){
        std::cin >> A[N-1-i];
    }

    std::function<long long(long long,long long)> func = [](long long a,long long b){
        return std::max(a,b);
    };
    
    segmenttree<long long> segtree(A,func,-(1ll<<61));

    long long v;
    std::function<bool(long long)> f = [&](long long x){
        return (x<v);
    };
    
    for(int i=0;i<Q;i++){
        int t,l,r;
        std::cin >> t >> l >> r;
        if(t==1){
            l--;
            segtree.set(N-1-l,r);
        }else if(t==2){
            l--;r--;
            long long Ans = segtree.prod(N-1-r,N-1-l+1);
            std::cout << Ans << std::endl;
        }else{
            l--;
            v = r;
            long long Ans = segtree.min_left(N-1-l+1,f);
            std::cout << N+1-Ans << std::endl;
        }
    }
    
    return 0;
}

Submission Info

Judge Result