#376689 (C++14) No.878 Range High-Element Query

• 問題: No.878 Range High-Element Query
• ユーザー: pazzle1230
• 提出日時: 2019-09-06 22:53:27
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 262 ms / 2,000 ms
• コード長: 11,116 bytes
• コンパイル時間: 2,178 ms
• コンパイル使用メモリ: 188,608 KB
• 実行使用メモリ: 13,856 KB
• 最終ジャッジ日時: 2024-06-24 20:28:38
• 合計ジャッジ時間: 4,971 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	4 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	249 ms; 12,452 KB
testcase_12	AC	162 ms; 11,688 KB
testcase_13	AC	199 ms; 10,632 KB
testcase_14	AC	151 ms; 9,056 KB
testcase_15	AC	163 ms; 11,200 KB
testcase_16	AC	242 ms; 13,416 KB
testcase_17	AC	262 ms; 13,836 KB
testcase_18	AC	258 ms; 13,856 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

template<class ValueMonoid, template<class...> class Container=::std::vector>
class SegTree{
public:
    using value_structure = ValueMonoid;
    using value_type = typename value_structure::value_type;
    using const_reference = const value_type &;
    using container_type = Container<value_type>;
    using size_type = typename container_type::size_type;

private:
    ::std::vector<value_type> tree;
    size_type size_;

    static size_type getsize(const size_type x){
        size_type ret = 1;
        while(ret < x)
            ret <<= 1;
        return ret;
    }

    inline value_type calc(const value_type a, const value_type b){
        return value_structure::operation(a, b);
    }

    inline void calc_node(const size_type index){
        if(tree.size() <= (index << 1 | 1)) return;
        tree[index] = value_structure::operation(tree[index<<1], tree[index<<1 | 1]);
    }
public:
    SegTree() : size_(0), tree(){}
    SegTree(const size_type size)
            : size_(size), tree(size << 1, value_structure::identity()){}
    template<class InputIterator>
    SegTree(InputIterator first, InputIterator last)
            : size_(::std::distance(first, last)){
        tree = container_type(size_, value_structure::identity());
        tree.insert(tree.end(), first, last);
        for(size_type i = size_;i > 0;i--){
            calc_node(i);
        }
    }

    size_type size() const { return size_; }
    const_reference operator[](const size_type k) const {
        assert(k < size_);
        return tree[k+size_];
    }

    value_type query(size_type l, size_type r){
        assert(l <= r);
        assert(0 <= l && l < size_);
        assert(0 <= r && r <= size_);
        value_type retl = value_structure::identity(), retr = value_structure::identity();
        for(l += size_, r += size_; l < r ; l >>= 1, r >>= 1){
            if(l&1) retl = calc(retl, tree[l++]);
            if(r&1) retr = calc(tree[--r], retr);
        }
        return calc(retl, retr);
    }

    template<class F>
    void update(size_type index, const F& f){
        assert(0 <= index && index < size());
        index += size_;
        tree[index] = f(::std::move(tree[index]));
        while(index >>= 1)
            calc_node(index);
    }

    /*
    template<class F>
    size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not.
        if(f(value_structure::identity()))
            return 0;
        if(!f(tree[1]))
            return size_+1;
        value_type acc = value_structure::identity();
        size_type i = 1;
        while(i <
    }
    */
};


template<class ValueMonoid, class OperatorMonoid, class Modifier,
        template<class...> class Container=::std::vector>
class LazySegTree{
public:
    using value_structure = ValueMonoid;
    using value_type = typename value_structure::value_type;
    using operator_structure = OperatorMonoid;
    using operator_type = typename operator_structure::value_type;
    using modifier = Modifier;
    using const_reference = const value_type &;
    using container_value_type = Container<value_type>;
    using container_operator_type = Container<operator_type>;
    using size_type = typename container_value_type::size_type;

private:
    container_value_type tree;
    container_operator_type lazy;
    size_type size_, height;

    static size_type getsize(const size_type x){
        size_type ret = 1;
        while(ret < x)
            ret <<= 1;
        return ret;
    }

    static size_type getheight(const size_type x){
        size_type ret = 0;
        while((static_cast<size_type>(1) << ret) < x){
            ret++;
        }
        return ret;
    }

    inline static value_type calc(const value_type a, const value_type b){
        return value_structure::operation(a, b);
    }

    inline static void apply(operator_type &data, const operator_type a){
        data = operator_structure::operation(data, a);
    }

    inline static value_type reflect(const value_type v, const operator_type o){
        return modifier::operation(v, o);
    }

    void push(const size_type index){
        tree[index] = reflect(tree[index], lazy[index]);
        apply(lazy[index << 1], lazy[index]);
        apply(lazy[index << 1 | 1], lazy[index]);
        lazy[index] = operator_structure::identity();
    }

    void calc_node(const size_type index){
        if(tree.size() <= (index << 1 | 1)) return;
        assert(0 < index);
        tree[index] = calc(reflect(tree[index << 1],  lazy[index << 1]),
                           reflect(tree[index << 1 | 1], lazy[index << 1 | 1]));
    }

    void build(size_type index){
        while(index >>= 1){
            calc_node(index);
        }
    }

    void propagate(const size_type index){
        for(size_type shift = height; shift ; --shift){
            push(index >> shift);
        }
    }

    void rebuild(){
        for(size_type i = size_-1;i > 0;--i){
            calc_node(i);
        }
    }
public:
    LazySegTree() : size_(0), height(0), tree(), lazy(){}
    LazySegTree(const size_type size)
            : size_(size), height(getheight(size)),
              tree(size << 1, value_structure::initializer()),
              lazy(size << 1, operator_structure::identity()){
        rebuild();
    }
    template<class InputIterator>
    LazySegTree(InputIterator first, InputIterator last)
            : size_(::std::distance(first, last)){
        height = getheight(size_);
        tree = container_value_type(size_, value_structure::identity());
        lazy = container_operator_type(size_ << 1, operator_structure::identity());
        tree.insert(tree.end(), first, last);
        rebuild();
    }

    size_type size() const { return size_; }
    const_reference operator[](const size_type k){
        assert(k < size_);
        propagate(k+size_);
        tree[k+size_] = reflect(tree[k+size_], lazy[k+size_]);
        lazy[k+size_] = operator_structure::identity();
        return tree[k+size_];
    }

    value_type query(size_type l, size_type r){
        assert(l <= r);
        assert(0 <= l && l < size_);
        assert(0 <= r && r <= size_);
        value_type retl = value_structure::identity(),
                retr = value_structure::identity();
        l += size_;
        r += size_;
        propagate(l);
        propagate(r-1);
        for(; l < r ; l >>= 1, r >>= 1){
            if(l&1){
                retl = calc(retl, reflect(tree[l], lazy[l]));
                l++;
            }
            if(r&1){
                r--;
                retr = calc(reflect(tree[r], lazy[r]), retr);
            }
        }
        return calc(retl, retr);
    }

    void update(size_type l, size_type r, const operator_type& data){
        assert(l <= r);
        assert(0 <= l && l < size_);
        assert(0 <= r && r <= size_);
        l += size_;
        r += size_;
        propagate(l);
        propagate(r - 1);
        for(size_type l_ = l, r_ = r; l_ < r_ ; l_ >>= 1, r_ >>= 1){
            if(l_ & 1) apply(lazy[l_++], data);
            if(r_ & 1) apply(lazy[--r_], data);
        }
        build(l);
        build(r - 1);
    }

    template<class F>
    void update(size_type index, const F& f){
        assert(0 <= index && index < size());
        index += size_;
        propagate(index);
        tree[index] = f(::std::move(tree[index]));
        lazy[index] = operator_structure::identity();
        build(index);
    }

    /*
    template<class F>
    size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not.
        if(f(value_structure::identity()))
            return 0;
        if(!f(tree[1]))
            return size_+1;
        value_type acc = value_structure::identity();
        size_type i = 1;
        while(i <
    }
    */
};

//class f_v {
//public:
//    using value_type = int64;
//    static value_type identity() { return 0; }
//    static value_type initializer() { return identity(); }
//    static value_type operation(const value_type& a, const value_type& b) {
//        return a + b;
//    }
//};
//
//class f_o {
//public:
//    using value_type = int64;
//    static value_type identity() { return 0; }
//    static value_type init
//};

class v_1 {
public:
    using value_type = PLL;
    static value_type identity() { return PLL(-INF_LL, -INF_LL); }
    static value_type initializer() { return identity(); }
    static value_type operation(const value_type& a, const value_type& b) {
        return max(a, b);
    }
};

class v_2 {
public:
    using value_type = int64;
    static value_type identity() { return 0; }
    static value_type initializer() { return 0; }
    static value_type operation(const value_type& a, const value_type& b) {
        return a + b;
    }
};

int main(void) {
    int64 N, Q;
    cin >> N >> Q;
    vector<int64> a(N), idx(N, -1);
    vector<PLL> b(N);
    priority_queue<PLL, vector<PLL>, greater<>> pq;
    REP(i, N) {
        cin >> a[i];
        b[i] = PLL(a[i], i);
    }
    SegTree<v_1> sg(all(b));
//    REP(i, N) {
//        PLL ret = sg.query(0, i);
//        if (ret.fs > a[i]) {
//            idx[i] = ret.sc;
//        }
    for (int64 i = N-1; i >= 0; i--) {
        pq.push(b[i]);
        while (pq.top().fs < a[i]) {
            idx[pq.top().sc] = i;
            pq.pop();
        }
    }
    SegTree<v_2> sg2(N);
    using T = tuple<int64, int64, int64>;
    vector<T> q(Q);
    REP(i, Q) {
        int64 sf;
        int64 l, r;
        cin >> sf >> l >> r; l--;
        q[i] = T(r, l, i);
    }
    sort(all(q));
    int64 now = 0;
    vector<int64> res(Q);
    REP(i, Q) {
        int64 l, r, id;
        tie(r, l, id) = q[i];
        while (now < r) {
            sg2.update(now, [](int64 x) { return x+1; });
            if (idx[now] != -1) {
                sg2.update(idx[now], [](int64 x) {return x-1; });
            }
            now++;
        }
        res[id] = sg2.query(l, r);
    }
    REP(i, Q) {
        cout << res[i] << endl;
    }
}