結果

問題 No.1441 MErGe
コンテスト
ユーザー mtsd
提出日時 2021-03-26 23:09:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 906 ms / 1,000 ms
コード長 5,447 bytes
コンパイル時間 2,573 ms
コンパイル使用メモリ 187,404 KB
実行使用メモリ 15,872 KB
最終ジャッジ日時 2024-11-29 01:23:18
合計ジャッジ時間 18,873 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}
template <typename T> class RBST {
private:
    struct node{
        T val;
        node *left, *right;
        int st_size;   // 部分木のサイズ
        node(){}
        node(T v) : val(v), left(nullptr), right(nullptr), st_size(1){}
        ~node() { delete left; delete right; }
    };
    node *root;
    using pnn = pair<node*,node*>;
    int size(node* t) { return t ? t->st_size : 0; }
    node* update(node *t) {
        node* l = t->left; node* r = t->right;
        t->st_size = size(l) + size(r) + 1;
        return t;
    }
    unsigned rnd(){
        static unsigned x = 123456789, y = 362436069, z = 521288629, w = 86675123;
        unsigned t = (x^(x<<11));
        x = y,y = z,z = w;
        return (w = (w^(w>>19))^(t^(t>>8)));
    }
    node* merge(node* l, node* r){
        if (!l || !r) return (!l) ? r : l;
        if(rnd() % (size(l) + size(r)) < (unsigned)size(l)){
            l->right = merge(l->right, r);
            return update(l);
        }else{
            r->left = merge(l, r->left);
            return update(r);
        }
    }
    pnn split(node* t, int k){   //木のサイズが(k,n-k)となるように分割する
        if(!t) return pnn(nullptr, nullptr);
        if(k <= size(t->left)){
            pnn s = split(t->left, k);
            t->left = s.second;
            return pnn(s.first,update(t));
        }else{
            pnn s = split(t->right, k-size(t->left)-1);
            t->right = s.first;
            return pnn(update(t), s.second);
        }
    }
    int lower_bound(node *t, const T k){
        if(!t) return 0;
        if(t->val < k){
            return size(t->left) + lower_bound(t->right,k) + 1;
        }else{
            return lower_bound(t->left,k);
        }
    }
    void lower_value(node *t, const T k, T& res){
        if(!t) return;
        if(t->val < k){
            lower_value(t->right,k,res);
        }else{
            lower_value(t->left,k,res=t->val);
        }
    }
    int upper_bound(node *t, const T k){
        if(!t) return 0;
        if(t->val <= k){
            return size(t->left) + upper_bound(t->right,k) + 1;
        }else{
            return upper_bound(t->left,k);
        }
    }
    void upper_value(node *t, const T k, T& res){
        if(!t) return;
        if(t->val <= k){
            upper_value(t->right,k,res);
        }else{
            upper_value(t->left,k,res=t->val);
        }
    }
    T get(node *t, int k){
        if(!t) assert(false);
        int s = size(t->left);
        if(s > k)       return get(t->left,k);
        else if(s < k)  return get(t->right,k-s-1);
        else            return t->val;
    }
    node* insert(node* t, int k, node* u){
        pnn s = split(t, k);
        return merge(merge(s.first, u), s.second);
    }
    pnn erase(node* t, int k){
        pnn sr = split(t, k+1);
        pnn sl = split(sr.first, k);
        return pnn(merge(sl.first, sr.second), sl.second);
    }
public:
    RBST() : root(nullptr){}
    //k以上の数の最小インデックス
    int lower_bound(const T k){ return lower_bound(root,k); }
    //k以上の最小の数
    T lower_value(const T k){
        T res = numeric_limits<T>::max();
        lower_value(root,k,res);
        return res;
    }
    //kを超える数の最小インデックス
    int upper_bound(const T k){ return upper_bound(root,k); }
    //kを超える最小の数
    T upper_value(const T k){
        T res = numeric_limits<T>::max();
        upper_value(root, k, res);
        return res;
    }
    //値valを挿入
    void insert(T val){
        root = insert(root, upper_bound(val), new node(val));
    }
    //値valを削除
    void erase(T val){
        node *p;
        tie(root, p) = erase(root, lower_bound(val));
        p->left = p->right = nullptr;
        delete p;
    }
    //k番目の値を返す
    T get(int k){ return get(root,k); }
    void print(){
        int sz = size(root);
        rep(i,sz) cout << get(i) << " ";
        cout << "\n";
    }
};
int main(){
    int n,q;
    cin >> n >> q;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<ll> s(n+1);
    rep(i,n){
        s[i+1] += a[i];
        s[i+1] += s[i];
    }
    RBST<int> st;
    rep(i,n)st.insert(i);
    rep(zz,q){
        int t,l,r;
        cin >> t >> l >> r;
        l--;r--;
        if(t==1){
            vector<int> p;
            for(int i=l;i<r;i++){
                p.push_back(st.get(i));
            }
            for(auto x:p){
                st.erase(x);
            }
        }else{
            l--;
            if(l<0){
                l = -1;
            }else{
                l = st.get(l);
            }
            r = st.get(r);
            // cerr << l << " " << r << endl;
            cout << s[r+1]-s[l+1] << "\n";
        }
    }
    return 0;
}
0