---
tags: codebook
---
{%hackmd theme-dark %}
# treap

## persistent

#include<random>
mt19937 mt(hash<string>()(":poop:"));
struct node{
    int p,v;ll val,sum;
    node *l,*r;
    node(int x=0,ll y=0):p(x),v(mt()),val(y),sum(y){
        l=r=nullptr;
    }
    node(node* cur){*this=*cur;}
    void pull(){
        sum=val;
        for(auto i:{l,r})
            if(i) sum+=i->sum;
    }
}pool[maxn],*ptr=&pool[0];
node* merge(node* a,node* b){
    if(!a||!b) return new(ptr++) node(a?:b);
    if(a->v<b->v){
        node* ret=new(ptr++) node(a);
        ret->r=merge(a->r,b),ret->pull();
        return ret;
    }else{
        node* ret=new(ptr++) node(b);
        ret->l=merge(a,b->l),ret->pull();
        return ret;
    }
}
P<node*> split(node* cur,int k){
    if(!cur) return {nullptr,nullptr};
    node* ret=new(ptr++) node(cur);
    if(cur->p<k){
        auto [a,b]=split(cur->r,k);
        ret->r=a,ret->pull();
        return {ret,b};
    }else{
        auto [a,b]=split(cur->l,k);
        ret->l=b,ret->pull();
        return {a,ret};
    }
}

## with lazy propagation

#include<random>
mt19937 mt(hash<string>()(":poop:"));
struct node{
    int p,v,sz; ll val,sum,inc,set;
    node *l,*r;
    node(int x,ll y):p(x),v(mt()),sz(1),val(y),sum(y),inc(0),set(LINF){
        l=r=nullptr;
    }
    void pull(){
        sz=1;
        for(auto i:{l,r})
            if(i) sz+=i->sz;
        sum=val;
        for(auto i:{l,r}){
            if(!i) continue;
            if(i->set!=LINF)
                sum+=i->set*i->sz;
            else
                sum+=i->sum;
            if(i->inc)
                sum+=i->inc*i->sz;
        }
    }
    void push(){
        if(set!=LINF){
            sum=set*sz,val=set;
            for(auto i:{l,r})
                if(i) i->inc=0,i->set=set;
            set=LINF;
        }
        if(inc){
            sum+=inc*sz,val+=inc;
            for(auto i:{l,r})
                if(i) i->inc+=inc;
            inc=0;
        }
    }
};
node* merge(node* a,node* b){
    if(!a||!b) return a?:b; 
    a->push(),b->push();
    if(a->v<b->v)
        return a->r=merge(a->r,b),a->pull(),a;
    return b->l=merge(a,b->l),b->pull(),b;
}
void split(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}
    cur->push();
    if(cur->p<k)
        a=cur,split(a->r,k,a->r,b),a->pull();
    else
        b=cur,split(b->l,k,a,b->l),b->pull();
}

## split by size

#include<random>
mt19937 mt(hash<string>()(":poop:"));
struct node{
    int v,sz; char val;
    node *l,*r;
    node(char ch):v(mt()),sz(1),val(ch){
        l=r=nullptr;
    }
    void pull(){
        sz=1;
        for(auto i:{l,r})
            if(i) sz+=i->sz;
    }
};
node* merge(node* a,node* b){
    if(!a||!b) return a?:b; 
    if(a->v<b->v)
        return a->r=merge(a->r,b),a->pull(),a;
    return b->l=merge(a,b->l),b->pull(),b;
}
inline int size(node* p){return p?p->sz:0;};
void split(node* cur,int k,node*& a,node*& b){
    if(!cur){a=b=nullptr;return;}
    if(size(cur->l)+1<=k)
        a=cur,split(a->r,k-size(cur->l)-1,a->r,b),a->pull();
    else
        b=cur,split(b->l,k,a,b->l),b->pull();
}

## old

//#include"iostreambuf"
#include<iostream>
#include<vector>
#include<random>
#define size_t unsigned
using namespace std;
mt19937 rd;
template<typename T>
struct treap{
    struct node{
        using nptr=node*;
        T k;int v;nptr l,r;
        node(const T& x):k(x),v(rd()){l=r=nullptr;}
    } *root;
    using nptr=node*;
    void print(ostream& os,nptr cur){
        if(!cur) return;
        print(os,cur->l);
        os<<cur->k<<' ';
        print(os,cur->r);
    }
    void print(ostream& os){print(os,root);}
    nptr merge(nptr a,nptr b){
        if(!a) return b;
        if(!b) return a;
        if(a->v<b->v){
            a->r=merge(a->r,b);return a;
        }else{
            b->l=merge(a,b->l);return b;}
    } 
    treap merge(treap b){
        root=merge(root,b.root);return *this;
    }
    void split(nptr cur,const T& x,nptr& a,nptr& b){
        if(!cur){a=b=nullptr;return;}
        if(cur->k<x)
            a=cur,split(a->r,x,a->r,b);
        else
            b=cur,split(b->l,x,a,b->l);
    }
    auto split(const T& x){
        treap a,b;
        split(root,x,a.root,b.root);
        return make_pair(a,b);
    }
    void insert(const T& x){
        nptr l,m,r;
        split(root,x,l,r);
        split(r,x+1,m,r);
        root=merge(merge(l,new node(x)),r);
    }
    void erase(const T& x){
        nptr l,m,r;
        split(root,x,l,r);
        split(r,x+1,m,r);
        root=merge(l,r);
    }
    bool count(const T& x,node* cur){
        if(!cur) return false;
        else if(cur->v==x) return true;
        else return count(x,(x<cur->k?cur->l:cur->r));
    } 
    bool count(const T& x){return count(x,root);}
    treap(const vector<T>& v={}):root(nullptr){
        for(const auto& i:v)
            insert(i);
    }
};
template<typename T>
ostream& operator<<(ostream& os,treap<T> t){
    t.print(os);return os;
}
int main(){
	cin.tie(nullptr);cout.tie(nullptr);
	ios::sync_with_stdio(false);
	treap<int> tree;
	for(int n=0;n!=1e5;n++)
		tree.insert(n);
	cout<<tree<<endl;
	return 0;
}

## toxic ver

#include"./template/template.hpp"

//#define MULTI_TASKCASE
using namespace rit;
using namespace wit;
using namespace abb;
using namespace output;

inline void init() {

}

mt19937 mt;
constexpr int maxn=1e5;
static int k[maxn],v[maxn],l[maxn],r[maxn],top=0;

inline node(int x){
    k[top]=x,v[top]=mt();
    l[top]=r[top]=-1;
    return top++;
}

int merge(int a,int b){
    int rt=-1,*cur=&rt;
    while(~a&&~b){
        if(v[a]<v[b])
            *cur=a,cur=&r[a],a=r[a];
        else
            *cur=b,cur=&l[b],b=l[b];
    }
    *cur=~a?a:b;
    return rt;
}

void split(int t,int x,int *a,int *b){
    while(~t){
        if(k[t]<x)
            t=r[*a=t],a=&r[*a];
        else
            t=l[*b=t],b=&l[*b];
    }
    *a=*b=-1;
}

void insert(int& t,int x){
    int l,r;
    split(t,x,&l,&r);
    t=merge(merge(l,node(x)),r);
}

void print(int t){
    if(!~t) return;
    print(l[t]);
    cout<<k[t]<<' ';
    print(r[t]);
}

inline void solve() {
    int tree=-1;
    for(auto i:{1,5,4,2,0,3,6,9,7,8}){
        insert(tree,i);
        // for(int i=0;i<top;i++)
        //     cout<<'('<<k[i]<<' '<<l[i]<<' '<<r[i]<<')';
        // cout<<endl;
    }
    print(tree);
}

main() {
    // ios::sync_with_stdio(false);
    init();
    int t = 1;
#ifdef MULTI_TASKCASE
    cin >> t; cin.ignore();
#endif
    while (t--) solve();
    return 0;
}

## return value split

mt19937 mt(hash<string>()(":poop:"));
struct node {
	node *l, *r;
	int p, v; ll val, minval;
	node(int x, ll y): p(x), v(mt()), val(y), minval(y) {
		l = r = nullptr;
	}
	node* pull() {
		minval = val;
		for (auto i : {l, r})
			if (i) minval = min(minval, i->minval);
		return this;
	}
};
node* merge(node* a, node* b) {
	if (!a || !b) return a ? : b;
	if (a->v < b->v)
		return a->r = merge(a->r, b), a->pull();
	else
		return b->l = merge(a, b->l), b->pull();
}
P<node*> split(node* p, int k) {
	if (!p) return {nullptr, nullptr};
	if (p->p < k) {
		// a = p, split(a->r, k, a->r, b), a->pull();
		auto [x, y] = split(p->r, k);
		p->r = x, p->pull();
		return {p, y};
	}
	else {
		// b = p, split(b->l, k, a, b->l), b->pull();
		auto [x, y] = split(p->l, k);
		p->l = y, p->pull();
		return {x, p};
	}
}
inline void solve() {
	int n, q, k; cin >> n >> q;
	node* root = nullptr;
	for (int i = 0; i < n; i++)
		cin >> k, root = merge(root, new node(i, k));
	while (q--) {
		int op, a, b;
		node *l, *m, *r;
		switch (cin >> op >> a >> b, op) {
		case 1:
			tie(l, r) = split(root, a);
			tie(l, m) = split(l, a - 1);
			m->val = b, m->pull();
			break;
		case 2:
			tie(l, r) = split(root, b);
			tie(l, m) = split(l, a - 1);
			cout << m->minval << endl;
		}
		root = merge(merge(l, m), r);
	}
}