---
# System prepended metadata

title: codebook 25頁

---

# codebook 25頁

## 目錄
* 常用函式
* LIS
* 背包
* 線段樹 lazy tag
* priorty queue 自訂排序
* matrix乘法 
* Floyd-Warshall 
* dijkstra
* treap 持久化
## iomanip IO manipulation：控制輸出格式
setbase() setbase(8) setbase(10) setbase(16) 輸出的進位制
setprecision() 輸出的位數 搭配fixed輸出小數點後的位數
setw()設定列出寬度
setfill()寬度不足填的字元' ' '0'

## 常用函式
#include<bits/stdc++.h>
fill(a,a+n,0);fill(v.begin(),v.end(),0);填入0
accumulate(v.begin,v.end(),0);
adjacent_difference(v.begin(),v.end(),t.begin());
partial_sum(v.begin(),v.end(),t.begin());前綴和
max_element(v.begin(),v.end())回傳最大元素的位子
min_element(v.begin(),v.end())回傳最小元素的位子

auto it = binary_search(v.begin(), v.end(), val);
auto it = under_bound(v.begin(), v.end(), val); 回傳<val的位子=lower_bound-1
auto it = lower_bound(v.begin(), v.end(), val); 回傳大於等於val的位子
auto it = upper_bound(v.begin(), v.end(), val); 回傳>val的位子


# LIS
```cpp=
vector<int> LIS(const vector<int>& s) {
    vector<int> v;
    v.push_back(s[0]);
    for (int i{1}; i < s.size(); ++i)
        if (s[i] > v.back()) v.push_back(s[i]);
        else *lower_bound(v.begin(), v.end(), s[i]) = s[i];
    return v;
}
```
# 背包
```cpp=
int n,m;//n item weigh limit
int v[n],w[n];
for(int i=0;i<n;++i)
{
    cin>>v[i]>>w[i];
}
int dp[m+1];
fill(dp,dp+m+1,0);
for(int i=0;i<n;++i)
{
    for(int j=m;j>=v[i];--j)
    {
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}
cout<<dp[w];

```
## 線段樹 lazy tag
```cpp=
class segment{
    class node{
        public:
            long long val = 0;
            long long lazy=0;
            long long leaf=1ll;
    };
    vector<node> tree;
    int n;
    public:
    segment(vector<long long>& a){
        n=a.size();
        tree.resize(n<<1);
        for(int i=0; i<n; ++i)
            tree[i+n].val=a[i];

        for(int i=n-1; i>0; --i)
        {
            tree[i].val=tree[i<<1].val+tree[i<<1|1].val;
            tree[i].leaf=tree[i<<1].leaf+tree[i<<1|1].leaf;
        }
            
    }
    void apply(int now,long long& inc)
    {
        tree[now].lazy += inc;
        tree[now].val += inc*tree[now].leaf;
    }
    void push(int now)//push down
    {
        if(now>=n)
            return;
        if(tree[now].lazy)
        {
            apply(now<<1,tree[now].lazy);
            apply(now<<1|1,tree[now].lazy);
            tree[now].lazy = 0;
        }
    }
    void pull(int& now)//pull up
    {
        for (int i_Op = now; i_Op;i_Op>>=1)
        {
            push(i_Op>>1);
            tree[i_Op>>1].val=tree[i_Op].val+tree[i_Op^1].val;
        }
    }

    void modify(int l,int r,long long& inc)
    {
        for (int i_Op = l + n, i_Ed = r + n; i_Op < i_Ed;i_Op>>=1,i_Ed>>=1)
        {
            if(i_Op&1)
            {
                apply(i_Op,inc);
                pull(i_Op);
                i_Op++;
            }
            if(i_Ed&1)
            {
                --i_Ed;
                apply(i_Ed,inc);
                pull(i_Ed);
            }
        }
    }
    void pushPath(int& p) {
        for (int h = __lg(n); h > 0; h--) {
            int i = p >> h;
            push(i);
        }
    }
    long long query(int l, int r) {
        // 推送懶人標記
        

        long long res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                pushPath(l);
                res += tree[l].val;
                l++;
            }
            if (r & 1) {
                r--;
                pushPath(r);
                res += tree[r].val;
            }
        }
        return res;
    }

};
```
## priorty queue 自訂排序
```cpp=
class Class {
public:
    int a, b, c;
    Class(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
};

int main() {
    auto comp = [](const Class& lhs, const Class& rhs) {
        if (lhs.b != rhs.b) return lhs.b > rhs.b;  // 按b的升序排序
        if (lhs.a != rhs.a) return lhs.a > rhs.a;  // 如果b相同，則按a的升序排序
        return lhs.c > rhs.c;                      // 如果a和b都相同，則按c的升序排序
    };

    priority_queue<Class, vector<Class>, decltype(comp)> pq(comp);

```

## matrix
```cpp=
vector<vector<int>> operator*(const vector<std::vector<int>>& A, const vector<vector<int>>& B) {
    int m = A.size();
    int n = A[0].size();
    int p = B[0].size();

    vector<vector<int>> C(m,vector<int>(p, 0));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < p; ++j) {
            for (int k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }

    return C;
}
```

## dijkstra
```cpp=
vector<long long> dijkstra(vector<vector<pair<int,long long>>>& v)
    vector<long long> dist(n,(1ll<<60));
    dist[0] = 0;
    priority_queue < tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
    pq.push({0, 0, 0});
    while(!pq.empty())
    {
        auto [d,now,dis] = pq.top();
        pq.pop();
        if (d > dist[now]) continue;
        for (auto& i:v[now]){
            if (dist[i.first] > d + i.second)
            {
                dist[i.first] = d + i.second;
                pq.push({dist[i.first], i.first, dis});
            }
        }
    }
    return v;
}
```


## Floyd-Warshall 
```cpp=
vector<vector<long long>> dis(n,vector<long long>(n,(1ll<<60)));
for (int i=0,u,v,w; i<m; i++)
        cin >> u >> v >> w, dis[u][v] = w;
for (int k=0; k<n; k++)
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
```



## treap

```cpp=
class node{
    public:
        long long index, pri;
        long long val, sum;
        shared_ptr<node> l, r;
        node(long long k, long long v) : index(k), pri(rand()), val(v), sum(v), l(nullptr), r(nullptr){
 
        }
        node(shared_ptr<node> t): index(t->index), pri(t->pri), val(t->val), sum(t->sum), l(t->l), r(t->r){
 
        }
};
 
class Treap
{
public:
    vector<shared_ptr<node>> root;
    int n=0;
    Treap()
    {
        root.push_back(nullptr);
    }
    void insert(long long v)
    {
        shared_ptr<node> node_tmp(new node(n, v));
        root[0]=merge(root[0], node_tmp);
        ++n;
        
    }
 
    long long get_Sum(shared_ptr<node>t)
    {
        return t ? t->sum : 0ll;
    }
    void update(int v,int k,int u)
    {
        root[v]=update(root[v],k,u);
    }
    shared_ptr<node> update(shared_ptr<node> t,int k,long long u)
    {
        if(!t)
        {
            return nullptr;
        }
        shared_ptr<node> new_Node( new node(t));
        if(t->index<k)
        {
            new_Node->r=update(t->r,k,u);
 
        }
        else if(t->index>k)
        {
            new_Node->l=update(t->l,k,u);
            
        }
        else //if(t->index==k)
        {
            //shared_ptr<node> new_Node= new node(t);
            new_Node->val = u;
            
        }
        pull(new_Node);
        return new_Node;
 
    }
    long long query(int v,int l,int r)
    {
        
        shared_ptr<node> a,b,c;
        split_By_Index(root[v], l - 1, a, b);
        split_By_Index(b, r, b, c);
        long long ans = get_Sum(b);
        root[v] = merge(a, merge(b, c));
        return ans;
    }
    void copy_Back(int k)
    {
        root.push_back(shared_ptr<node>(new node(root[k])));
    }
 
    private: void pull(shared_ptr<node> t)
    {
        t->sum = t->val + get_Sum(t->l) + get_Sum(t->r);
    }
 
    private: shared_ptr<node> merge(shared_ptr<node> a,shared_ptr<node> b)
    {
        if(!a || !b)
            return a ? a : b;
        if(a->pri > b->pri)
        {
            a->r=merge(a->r,b);
            pull(a);
            return a;
        }
        else
        {
            b->l=merge(a,b->l);
            pull(b);
            return b;
        }
 
    }
    private: void split_By_Index(shared_ptr<node>t,int k,shared_ptr<node>&a,shared_ptr<node>&b)
    {
        if(!t)
        {
            a=b= nullptr;
            return;
        }
        if(t->index<=k)
        {
            a = t;
            
            split_By_Index(t->r,k,a->r,b);
            pull(a);
            
        }
        else
        {
            b = t;
            
            split_By_Index(t->l, k, a, b->l);
            pull(b);
            
        }
    }
};
```
