cpp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub michirakara/cpp-library

:heavy_check_mark: verify/aoj/implicit-treap.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508"

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

#include "../../binary-search-tree/implicit-treap.hpp"

using T = long long;
using F = long long;

const T INF = 8e18;
const F ID = 8e18;

T op(T a, T b){ return std::min(a, b); }
T e(){ return INF; }
T mapping(F f, T x){ return (f == ID ? x : f); }
F composition(F f, F g){ return g==ID ? f : g; }
F id(){ return ID; }

int main(){
    int n,q;
    cin>>n>>q;
    
    vector<long long> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    ImplicitTreap<T,op,e,F,mapping,composition,id> set(a);
    while(q--){
        long long x,y,z;
        cin>>x>>y>>z;
        if(x==0){
            set.rotate(y,z,z+1);
        }else if(x==1){
            cout<<set.prod(y,z+1)<<endl;
        }else{
            set.apply(y,y+1,z);
        }
    }
}
#line 1 "verify/aoj/implicit-treap.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508"

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

#line 1 "binary-search-tree/implicit-treap.hpp"
//参考 https://xuzijian629.hatenablog.com/entry/2018/12/08/000452
//Treap<T,op,e,F,mapping,composition,id> hoge;で初期化
#line 5 "binary-search-tree/implicit-treap.hpp"

template<class T,T(*op)(T,T),T(*e)(),class F,T(*mapping)(F f,T x),F(*composition)(F f,F g),F(*id)()>
class ImplicitTreap{
    struct Node{
        T val,acc=e();
        int priority;
        int cnt=1;
        F lazy=id();
        bool rev=false;
        Node *l, *r;
        Node(T val,int priority):val(val),priority(priority),l(nullptr),r(nullptr){};
    }
    *root=nullptr;
    using Tree=Node *;

    int cnt(Tree t) {
        return t ? t->cnt : 0;
    }

    T acc(Tree t){
        return t ? t->acc : e();
    }

    void update(Tree t){
        if(t){
            t->cnt=1+cnt(t->l)+cnt(t->r);
            t->acc=op(t->val,op(acc(t->l),acc(t->r)));
        }
    }

    void pushdown(Tree t){
        if(t && t->rev){
            t->rev=false;
            std::swap(t->l,t->r);
            if(t->l)t->l->rev^=1;
            if(t->r)t->r->rev^=1;
        }
        if(t && t->lazy!=id()){
            if(t->l){
                t->l->lazy=composition(t->l->lazy,t->lazy);
                t->l->acc=mapping(t->lazy,t->l->acc);
            }
            if(t->r){
                t->r->lazy=composition(t->r->lazy,t->lazy);
                t->r->acc=mapping(t->lazy,t->r->acc);
            }
            t->val=mapping(t->lazy,t->val);
            t->lazy=id();
        }
        update(t);
    }

    void split(Tree t, int key, Tree& l,Tree& r){
        if(!t){
            l=r=nullptr;
            return;
        }
        pushdown(t);
        int implicit_key=cnt(t->l)+1;
        if(key<implicit_key){
            split(t->l,key,l,t->l),r=t;
        }else{
            split(t->r,key-implicit_key,t->r,r),l=t;
        }
        update(t);
    }

    void insert(Tree& t,int key,Tree item){
        Tree t1,t2;
        split(t,key,t1,t2);
        merge(t1,t1,item);
        merge(t,t1,t2);
    }

    void merge(Tree& t, Tree l, Tree r){
        pushdown(l);
        pushdown(r);
        if(!l || !r){
            t=l?l:r;
        }else if(l->priority>r->priority){
            merge(l->r,l->r,r),t=l;
        }else{
            merge(r->l,l,r->l),t=r;
        }
        update(t);
    }

    void erase(Tree& t,int key){
        Tree t1,t2,t3;
        split(t,key+1,t1,t2);
        split(t1,key,t1,t3);
        merge(t,t1,t2);
    }

    T prod(Tree t,int l,int r){
        Tree t1,t2,t3;
        split(t,l,t1,t2);
        split(t2,r-l,t2,t3);
        T ret=t2->acc;
        merge(t2,t2,t3);
        merge(t,t1,t2);
        return ret;
    }

    void apply(Tree t,int l,int r,F x){
        Tree t1,t2,t3;
        split(t,l,t1,t2);
        split(t2,r-l,t2,t3);
        t2->lazy=composition(t2->lazy,x);
        t2->acc=mapping(x,t2->acc);
        merge(t2,t2,t3);
        merge(t,t1,t2);
    }

    void reverse(Tree t,int l,int r){
        if(l>r)return;
        Tree t1,t2,t3;
        split(t,l,t1,t2);
        split(t2,r-l,t2,t3);
        t2->rev^=1;
        merge(t2,t2,t3);
        merge(t,t1,t2);
    }

    void rotate(Tree t,int l,int m,int r){
        reverse(t,l,r);
        reverse(t,l,l+r-m);
        reverse(t,l+r-m,r);
    }

    void dump(Tree t) {
        if (!t) return;
        pushdown(t);
        dump(t->l);
        std::cout << t->val << " ";
        dump(t->r);
    }

public:
    ImplicitTreap() {}
    ImplicitTreap(std::vector<T> as){
        std::reverse(as.begin(),as.end());
        for(T a:as){
            insert(0,a);
        }
    }

    void insert(int pos,T val){
        //valをposの場所に追加する O(log N)
        insert(root,pos,new Node(val,rand()));
    }

    void erase(T pos){
        //posにある要素を消す O(log N)
        erase(root,pos);
    }

    int size(){
        return cnt(root);
    }

    T operator[](int pos) {
        Tree t1, t2, t3;
        split(root, pos + 1, t1, t2);
        split(t1, pos, t1, t3);
        T ret = t3->acc;
        merge(t1, t1, t3);
        merge(root, t1, t2);
        return ret;
    }

    T prod(int l, int r){
        //[l,r)の区間 O(log N)
        return prod(root,l,r);
    }

    void apply(int l,int r,F x){
        apply(root,l,r,x);
    }

    void reverse(int l,int r){
        reverse(root,l,r);
    }

    void rotate(int l,int m,int r){
        rotate(root,l,m,r);
    }

    void dump(){
        dump(root);std::cout<<std::endl;
    }
};
#line 7 "verify/aoj/implicit-treap.test.cpp"

using T = long long;
using F = long long;

const T INF = 8e18;
const F ID = 8e18;

T op(T a, T b){ return std::min(a, b); }
T e(){ return INF; }
T mapping(F f, T x){ return (f == ID ? x : f); }
F composition(F f, F g){ return g==ID ? f : g; }
F id(){ return ID; }

int main(){
    int n,q;
    cin>>n>>q;
    
    vector<long long> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    ImplicitTreap<T,op,e,F,mapping,composition,id> set(a);
    while(q--){
        long long x,y,z;
        cin>>x>>y>>z;
        if(x==0){
            set.rotate(y,z,z+1);
        }else if(x==1){
            cout<<set.prod(y,z+1)<<endl;
        }else{
            set.apply(y,y+1,z);
        }
    }
}
Back to top page