---
tags: 卓越盃程式競賽
---

# pF. Safe Sequence(Hard)

## 題目敘述 :

你是一家銀行負責保管保險箱的保險箱管理處處長，由於最近銀行生意並不是非常好，因此銀行行長決定跟員工玩一個遊戲。以下為遊戲會用到的操作。

1. 新增一個保險箱到保險箱序列第 $x$ 個後面，且該保險箱此時已經有 $y$ 個金條

vector<int> a(5,0);
int x=3,y=1;
a.insert(a.begin()+x+1,y);

2. 反轉 $[l,r]$ 的保險箱 ~註1~ `reverse(a.begin()+l+1,a.begin()+r+1)`
3. 詢問區間 $[l,r]$ 的金條總數 `for(l,r) ->`
4. 從目前保險箱序列中的第 $x$ 個位置拿出 $y$ 個金條 `a[x]-y;`
5. 在目前保險箱序列中的第 $x$ 個位置放入 $y$ 個金條 `a[x]+y`

## 輸入說明 :

- 第一行輸入 $1$ 個數字 $t$ ，代表有 $t$ 比測試資料
- 每筆測資第一行輸入 $2$ 個數字 $n,q$ ，表示一開始的保險箱有幾個
- 第二行輸入 $n$ 個數字 $a_1,a_2...a_n$ ， $a_i$ 代表第 $i$ 個保險箱原來有幾塊金條
- 接下來有 $q$ 行，分別對應一個操作(以下說明)

對應題目敘述的第 $k$ 項操作

1. 輸入 $1$ $x$ $y$
2. 輸入 $2$ $l$ $r$
3. 輸入 $3$ $l$ $r$
4. 輸入 $4$ $x$ $y$
5. 輸入 $5$ $x$ $y$

$t \le 100$
$n$ $,$ $q$ $,$ $a_i$ $,$ $x$ $,$ $y$ $\leq 10^4$

**保證不會戳到不該戳的項！**

## 輸出說明 :

僅有操作 $3$ 需要輸出區間 $[l,r]$ 的金條總數

## 範例輸入1 :

1
4 2
1 2 3 4
2 1 4
3 1 3

## 範例輸出1 :

9

## 子題組與配分

- 第一子題組 : 只會出現操作 $1$ 或 $3$ ，占 50%
- 第二子題組 : 無其他限制，占 50%

> [color=blue]註1 : 由於銀行裝備有"量子軌道位移系統"，因此無須擔心保險箱管理處員工因搬運過多保險箱而導致橫紋肌溶解，或是出現保險箱太重而搬不動的問題。

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

using ll=int;

unsigned seed=chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 gen=mt19937_64(seed);

struct Treap{
    struct node{
        ll sz,val,sum,pri;
        bool rev_tag;

        node *lch,*rch;

        node(ll _val){
            val=sum=_val;
            lch=rch=nullptr;
            pri=gen(); sz=1;
            rev_tag=false;
        }

        void rev(){
            swap(lch,rch);
            rev_tag=!rev_tag;
        }

        void push(){
            if(rev_tag){
                if(lch) lch->rev();
                if(rch) rch->rev();
                rev_tag=false;
            }
        }

        void pull(){
            sz=1;
            sum=val;
            
            if(lch){
                sum+=lch->sum;
                sz+=lch->sz;
            }

            if(rch){
                sum+=rch->sum;
                sz+=rch->sz;
            }
        }
    };

    node *rt=nullptr;

    int fs(node *t){
        return t ? t->sz : 0;
    }

    int size(){
        return fs(rt);
    }

    bool empty(){
        return size()==0;
    }

    node *merge(node *a,node *b){
        if(!a || !b) return a ? a : b;

        if(a->pri < b->pri){
            a->push();
            a->rch=merge(a->rch,b);
            a->pull();
            return a;
        }else{
            b->push();
            b->lch=merge(a,b->lch);
            b->pull();
            return b;
        }
    }

    void splitSz(node *T,node *&a,node *&b,int k){
        if(!T){
            a=b=nullptr;
            return;
        }

        T->push();
        if(fs(T->lch)<k){
            a=T;
            splitSz(T->rch,a->rch,b,k-fs(T->lch)-1);
            a->pull();
        }else{
            b=T;
            splitSz(T->lch,a,b->lch,k);
            b->pull();
        }
    }

    void insert(ll v,int k){
        node *a=new node(v),*b;
        splitSz(rt,rt,b,k);
        rt=merge(rt,a);
        rt=merge(rt,b);
    }

    void erase(int k){
        node *a,*b;
        splitSz(rt,rt,a,k);
        splitSz(rt,rt,b,k-1);
        delete(b);
        rt=merge(rt,a);
    }

    void modify(int k,ll x){
        node *a,*b;
        splitSz(rt,rt,a,k);
        splitSz(rt,rt,b,k-1);
        b->val=x;
        b->pull();
        rt=merge(rt,b);
        rt=merge(rt,a);
    }

    void reverse(int l,int r){
        node *a,*b;
        splitSz(rt,rt,a,r);
        splitSz(rt,rt,b,l-1);
        b->rev();
        rt=merge(rt,b);
        rt=merge(rt,a);
    }

    ll query_sum(int l,int r){
        node *a,*b;
        splitSz(rt,rt,a,r);
        splitSz(rt,rt,b,l-1);
        ll ret=b->sum;
        rt=merge(rt,b);
        rt=merge(rt,a);
        return ret;
    }

    ll operator[](int k){
        if(k>size()) return 0;

        node *a,*b;
        splitSz(rt,rt,a,k);
        splitSz(rt,rt,b,k-1);
        ll ret=b->val;
        rt=merge(rt,b);
        rt=merge(rt,a);
        return ret;
    }
};

void solve(){
    Treap tp;

    int n,q;
    cin>>n>>q;

    for(int i=1;i<=n;++i){
        int v;
        cin>>v;
        tp.insert(v,i);
    }

    for(int i=0;i<q;++i){
        int op;
        cin>>op;

        if(op==1){
            int x,y;
            cin>>x>>y;
            tp.insert(y,x);
        }else if(op==2){
            int l,r;
            cin>>l>>r;
            tp.reverse(l,r);
        }else if(op==3){
            int l,r;
            cin>>l>>r;
            cout<<tp.query_sum(l,r)<<"\n";
        }else if(op==4){
            int x,y;
            cin>>x>>y;
            if(tp[x]<y){
                tp.modify(x,0);
            }else{
                tp.modify(x,tp[x]-y);
            }
        }else if(op==5){
            int x,y;
            cin>>x>>y;
            tp.modify(x,tp[x]+y);
        }else{// op==6
            int x;
            cin>>x;
            tp.erase(x);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int t;
    cin>>t;
    while(t--){
        solve();
    }
}