# 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);
}
}
};
```
Sign in with Wallet
Connect another wallet