# TREAP
## 特性
treap=tree+heap
### tree
指binary search tree
可以直接在上面二分搜
### heap
每個節點都比他的子節點大(或小)
### treap
每個節點會有:
pri值(縱軸): heap特性，為了保持平衡而隨機決定
key值(橫軸): tree特性，其實就是原序列中的位置
以及其他你想維護的資訊

struct treap{
    int pri,key,val;
    treap *lc,*rc;
    treap(int _key,int _val):key(_key),val(_val){
        pri=rand();
        lc=rc=nullptr;
    }
};

treap 的操作都是把要做事的區間split 出來，詢問或操作完成後再merge回去
## split

void split(treap* t,int k,treap*& l,treap*& r){
    //把t中key值小於等於k的分到l，其他分到r
    if(!t) l=r=nullptr;
    else if(t->key<=k){
        l=t;
        split(t->rc, k, l->rc, r);
    }
    else{
        r=t;
        split(t->lc, k, l, r->lc);
    }
}

## merge

treap* merge(treap* a,treap* b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        a->rc=merge(a->rc,b);
        return a;
    }
    else{
        b->lc=merge(a,b->lc);
        return b;
    }
}

只要在用的時候確保a->key小於b->key，就只要檢查heap的特性就好(即pri值的大小)
## 應用
反正就記住把要做事的區間split 出來，詢問或操作完成後再merge回去
:::warning
:warning:常數通常比線段樹大，斟酌使用
:::
### 插入

treap insert(treap *t,int idx,int k){
    treap *a,*b;
    split(t,idx,a,b);
    return merge(a,merge(new treap(idx,k),b));
}

### 刪除

treap remove(treap *t,int idx){
    treap *a,*b;
    split(t,idx-1,a,t);
    split(t,0,t,b);
    return merge(a,b);
}

### RMQ
[Dynamic Range Minimum Queries](https://cses.fi/problemset/task/1649)
加個pull就好了
sum, XOR, gcd也都差不多
:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
struct treap{
    int pri,key,val,mn;
    treap *lc,*rc;
    treap(int _key,int _val):key(_key),val(_val){
    	mn=val;
        pri=rand();
        lc=rc=nullptr;
    }
};
void pull(treap *&a){
	a->mn=a->val;
	if(a->lc) a->mn=min(a->mn,a->lc->mn);
	if(a->rc) a->mn=min(a->mn,a->rc->mn);
}
void split(treap *t,int k,treap *&l,treap *&r){
    if(!t) l=r=nullptr;
    else if(t->key<=k){
        l=t;
        split(t->rc, k, l->rc, r);
        pull(l);//注意這邊
    }
    else{
        r=t;
        split(t->lc, k, l, r->lc);
        pull(r);//注意這邊
    }
}
treap* merge(treap *a,treap *b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        a->rc=merge(a->rc,b);
        pull(a);//注意這邊
        return a;
    }
    else{
        b->lc=merge(a,b->lc);
        pull(b);//注意這邊
        return b;
    }
}
void upd(treap *&t,int idx,int k){
	treap *a,*b;
	split(t,idx-1,a,t);
	split(t,idx,t,b);
	t->val=t->mn=k;
	t=merge(a,merge(t,b));
}
int query(treap *&t,int l,int r){
	treap *a,*b;
	split(t,l-1,a,t);
	split(t,r,t,b);
	int ret=t->mn;
	t=merge(a,merge(t,b));
	return ret;
}
int main(){
	int n,q;
	cin>>n>>q;
	treap *tr=NULL;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		tr=merge(tr,new treap(i,a));
	}
	while(q--){
		int a,b,c;
		cin>>a>>b>>c;
		if(a==1){
			b--;
			upd(tr,b,c);
		}
		else{
			b--;
			c--;
			cout<<query(tr,b,c)<<endl;
		}
	}
	return 0;
}

:::
### 關於key
如果要做的操作會改變節點在原序列的位置怎麼辦，這樣key不就亂掉了嗎

每次移動就更改key?
如果要搬一大段就會需要每一個都改，太麻煩了，需要一個更好維護並且可以推出key的資訊
沒錯就是size

key就是整個**treap中有多少人比他小**
以根節點為例，他的key就是左子節點的size
如果在左邊，就直接遞迴往下
如果在右邊，key就是根節點的左子節點的size + 1 + 遞迴往下做的答案
:::spoiler 利用size:

struct treap{
	int pri,sz,val;
    treap *lc,*rc;
    treap(int _val):val(_val){
        pri=rand();
        sz=1;
        lc=rc=nullptr;
    }
};
void pull(treap *t){
    t->sz=1;
    if(t->lc) t->sz+=t->lc->sz;
    if(t->rc) t->sz+=t->rc->sz;
}
void split(treap *t,int idx,treap *&l,treap *&r){
    int lsize=t->lc? t->lc->sz:0;
    if(!t) l=r=NULL;
    else if(lsize<=idx){
        l=t;
        split(t->rc,idx-lsize-1,l->rc,r);
        pull(l);
    }
    else{
        r=t;
        split(t->lc,idx,l,r->lc);
        pull(r);
    }
}
treap* merge(treap* a,treap* b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else{
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

:::
### 懶標
和線段樹一樣，紀錄**該節點已經做完，子節點還沒**的操作
在此以區間加值，區間求和為例

void push(treap *t){
    if(t->lz==0) return;
    if(t->lc){
        t->lc->val+=t->lz;
        t->lc->sum+=t->lz*t->lc->sz;
        t->lc->lz+=t->lz;
    }
    if(t->rc){
        t->rc->val+=t->lz;
        t->rc->sum+=t->lz*t->rc->sz;
        t->rc->lz+=t->lz;
    }
}
void split(treap *t,int k,treap *&l,treap *&r){
    if(!t) l=r=nullptr;
    else if(t->key<=k){
        l=t;
        push(l);//注意這邊
        split(t->rc, k, l->rc, r);
        pull(l);
    }
    else{
        r=t;
        push(r);//注意這邊
        split(t->lc, k, l, r->lc);
        pull(r);
    }
}
treap* merge(treap *a,treap *b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        push(a);//注意這邊
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else{
        push(b);//注意這邊
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

### 區間反轉
區間反轉就是把要轉的區間split出來，然後把左右子樹對調，子樹也遞迴做一樣的事
然後再加上懶標就好了

## 題目

[Cut and Paste](https://cses.fi/problemset/task/2072)
:::spoiler code(先自己寫看看)

#include<bits/stdc++.h>
using namespace std;
struct treap{
    int pri,sz,val;
    treap *lc,*rc;
    treap(int _val):val(_val){
        pri=rand();
        sz=1;
        lc=rc=nullptr;
    }
};
void pull(treap *t){
    t->sz=1;
    if(t->lc) t->sz+=t->lc->sz;
    if(t->rc) t->sz+=t->rc->sz;
}
void split(treap *t,int idx,treap *&l,treap *&r){
    if(!t) l=r=NULL;
    else{
        int lsize=t->lc? t->lc->sz:0;
        if(lsize<=idx){
            l=t;
            split(t->rc,idx-lsize-1,l->rc,r);
            pull(l);
        }
        else{
            r=t;
            split(t->lc,idx,l,r->lc);
            pull(r);
        }
    }
}
treap* merge(treap* a,treap* b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else{
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}
int main(){
    int n,q;
    cin>>n>>q;
    treap *tr=NULL;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        tr=merge(tr,new treap(s[i]-'A'));
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        treap *left,*right;
        split(tr,a-1,left,tr);
        split(tr,b-a,tr,right);
        tr=merge(left,merge(right,tr));
    }
    for(int i=0;i<n;i++){
        treap *ans;
        split(tr,0,ans,tr);
        char c='A'+ans->val;
        cout<<c;
    }
    return 0;
}

:::
---
[Substring Reversals](https://cses.fi/problemset/task/2073)
:::spoiler code(先自己寫看看)

#include<bits/stdc++.h>
using namespace std;
struct treap{
    int pri,sz,val;
    bool lz;
    treap *lc,*rc;
    treap(int _val):val(_val){
        lz=0;
        pri=rand();
        sz=1;
        lc=rc=nullptr;
    }
};
void push(treap *t){
    if(!t->lz) return;
    if(t->lc){
        swap(t->lc->lc,t->lc->rc);
        t->lc->lz^=1;
    }
    if(t->rc){
        swap(t->rc->lc,t->rc->rc);
        t->rc->lz^=1;
    }
    t->lz=0;
}
void pull(treap *t){
    t->sz=1;
    if(t->lc) t->sz+=t->lc->sz;
    if(t->rc) t->sz+=t->rc->sz;
}
void split(treap *t,int idx,treap *&l,treap *&r){
    if(!t) l=r=NULL;
    else{
        int lsize=t->lc? t->lc->sz:0;
        if(lsize<=idx){
            l=t;
            push(l);
            split(t->rc,idx-lsize-1,l->rc,r);
            pull(l);
        }
        else{
            r=t;
            push(r);
            split(t->lc,idx,l,r->lc);
            pull(r);
        }
    }
}
treap* merge(treap* a,treap* b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        push(a);
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else{
        push(b);
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}
int main(){
    int n,q;
    cin>>n>>q;
    treap *tr=NULL;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        tr=merge(tr,new treap(s[i]-'A'));
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        treap *left,*right;
        split(tr,l-1,left,tr);
        split(tr,r-l,tr,right);
        swap(tr->lc,tr->rc);
        tr->lz^=1;
        tr=merge(left,merge(tr,right));
    }
    for(int i=0;i<n;i++){
        treap *ans;
        split(tr,0,ans,tr);
        char c='A'+ans->val;
        cout<<c;
    }
    return 0;
}

:::
---
[Reversals and Sums](https://cses.fi/problemset/task/2074)
:::spoiler code(先自己寫看看)
我還沒寫
2023.05.16 更 寫完了，我也不知道為什麼拖這麼久

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct treap{
    int pri,sz,val,sum;
    bool lz;
    treap *lc,*rc;
    treap(int _val):val(_val){
        lz=0;
        sum=val;
        pri=rand();
        sz=1;
        lc=rc=nullptr;
    }
};
void push(treap *t){
    if(!t->lz) return;
    if(t->lc){
        swap(t->lc->lc,t->lc->rc);
        t->lc->lz^=1;
    }
    if(t->rc){
        swap(t->rc->lc,t->rc->rc);
        t->rc->lz^=1;
    }
    t->lz=0;
}
void pull(treap *t){
    t->sum=t->val;
    t->sz=1;
    if(t->lc){
        t->sz+=t->lc->sz;
        t->sum+=t->lc->sum;
    }
    if(t->rc){
        t->sz+=t->rc->sz;
        t->sum+=t->rc->sum;
    }
}
void split(treap *t,int idx,treap *&l,treap *&r){
    if(!t) l=r=NULL;
    else{
        int lsize=t->lc? t->lc->sz:0;
        if(lsize<=idx){
            l=t;
            push(l);
            split(t->rc,idx-lsize-1,l->rc,r);
            pull(l);
        }
        else{
            r=t;
            push(r);
            split(t->lc,idx,l,r->lc);
            pull(r);
        }
    }
}
treap* merge(treap* a,treap* b){
    if(!a||!b) return a? a:b;
    if(a->pri>b->pri){
        push(a);
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else{
        push(b);
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}
signed main(){
    int n,q;
    cin>>n>>q;
    treap* tr=NULL;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        tr=merge(tr,new treap(a));
    }
    while(q--){
        int a;
        cin>>a;
        if(a==1){
            int l,r;
            cin>>l>>r;
            l--;
            r--;
            treap *left,*right;
            split(tr,l-1,left,tr);
            split(tr,r-l,tr,right);
            swap(tr->lc,tr->rc);
            tr->lz^=1;
            tr=merge(left,merge(tr,right));
        }
        else{
            int l,r;
            cin>>l>>r;
            l--;
            r--;
            treap *left,*right;
            split(tr,l-1,left,tr);
            split(tr,r-l,tr,right);
            cout<<tr->sum<<endl;
            tr=merge(left,merge(tr,right));
        }
    }
    return 0;
}

:::

---
[SuperMemo](https://vjudge.net/problem/POJ-3580) 序列操作大雜燴