### 離散化
```cpp=
template <typename T>
auto get_unique_sorted(vector<T> arr) {
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
return arr;
}
template <typename T>
auto get_rank(const vector<T> &unique_sorted, const T &x) {
return lower_bound(unique_sorted.begin(), unique_sorted.end(), x) - unique_sorted.begin();
}
```
### 二分搜
```cpp=
//不符合條件的最小值
template <class Ty, class FuncTy>
Ty find_min_false(Ty L, Ty R, FuncTy check){
while (L < R) {
Ty mid = L + (R - L) / 2;
if (check(mid))
L = mid + 1;
else
R = mid;
}
return L;
}
//符合條件的最大值
template <class Ty, class FuncTy>
Ty find_max_true(Ty L, Ty R, FuncTy check){
while (L < R) {
Ty mid = L + (R - L + 1) / 2;
if (check(mid))
L = mid;
else
R = mid - 1;
}
return L;
}
```
### 矩陣計算
```cpp=
template <typename T>
struct Matrix
{
using rt = std::vector<T>;
using mt = std::vector<rt>;
using matrix = Matrix<T>;
int r, c;
mt m;
Matrix(int r, int c) : r(r), c(c), m(r, rt(c)) {}
rt &operator[](int i) { return m[i]; }
matrix operator+(const matrix &a)
{
matrix rev(r, c);
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
rev[i][j] = m[i][j] + a.m[i][j];
return rev;
}
matrix operator-(const matrix &a)
{
matrix rev(r, c);
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
rev[i][j] = m[i][j] - a.m[i][j];
return rev;
}
matrix operator*(const matrix &a)
{
matrix rev(r, a.c);
matrix tmp(a.c, a.r);
for (int i = 0; i < a.r; ++i)
for (int j = 0; j < a.c; ++j)
tmp[j][i] = a.m[i][j];
for (int i = 0; i < r; ++i)
for (int j = 0; j < a.c; ++j)
for (int k = 0; k < c; ++k)
rev.m[i][j] += m[i][k] * tmp[j][k];
return rev;
}
bool inverse()
{
Matrix t(r, r + c);
for (int y = 0; y < r; y++)
{
t.m[y][c + y] = 1;
for (int x = 0; x < c; ++x)
t.m[y][x] = m[y][x];
}
if (!t.gas())
return false;
for (int y = 0; y < r; y++)
for (int x = 0; x < c; ++x)
m[y][x] = t.m[y][c + x] / t.m[y][y];
return true;
}
};
```
### 線性篩 O(n)
```cpp=
vector<int> primes;
vector<bool> isPrime;
void find_prime(int n) {
primes.clear();
isPrime.assign(n + 1, true);
isPrime[0] = isPrime[1] = false;
for(int i = 2; i < n; ++i) {
if(isPrime[i])
primes.emplace_back(i);
for(const auto &p: primes){
if(1LL * i * p > n) break;
isPrime[i * p] = false;
if(i % p == 0) break;
}
}
}
```
### 線性篩 O(n) + 質因數分解 O(logx)
```cpp=
vector<int> primes;
vector<int> LPFs(n + 1, 1);
void find_prime(){
for(int i = 2; i < n; ++i) {
if(LPFs[i] == 1) {
LPFs[i] = i;
primes.emplace_back(i);
}
for(auto p: primes) {
if(1LL * i * p > n) break;
LPFs[i * p] = p;
if(i % p == 0) break;
}
}
}
void print_prime_factor(int x){
while(x != 1){
int factor = LPFs[x], cnt = 0;
for (; x % factor == 0; ++cnt)
x /= factor;
cout<<factor<<": "<<cnt<<endl;
}
}
```
### 拓展歐基里德
```cpp=
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b,y,x);
y-=a/b*x;
return gcd;
}
```
### BIT
```cpp=
int lowbit(int x) { return x & -x; }
class BIT{
int n;
vector<long long> bit;
public:
void init(int _n) {
n = _n;
bit.resize(n);
for (auto&b: bit) b= 0;
}
long long query(int x) const{
long long sum= 0;
for (; x; x-= lowbit(x))
sum += bit[x];
return sum;
}
void modify(int x, int val) {
for (; x <= n; x+= lowbit(x))
bit[x] += val;
}
};
```
### 二維 BIT
```cpp=
class BIT2D {
int m;
vector<BIT> bit1D;
public:
void init(int _m, int _n) {
m = _m;
bit1D.resize(m);
for (auto&b: bit1D) b.init(_n);
}
long long query(int x, int y) const{
long long sum= 0;
for (; x; x-= lowbit(x))
sum += bit1D[x].query(y);
return sum;
}
void modify(int x, int y, int val) {
for (; x <= m; x+= lowbit(x))
bit1D[x].modify(y, val);
}
long long query2D(int x1, int y1, int x2, int y2) {
return query(x2, y2)
- query(x1 - 1, y2)
- query(x2, y1 - 1)
+ query(x1 - 1, y1 - 1);
}
};
```
### 區間修改 + 查詢 BIT
```cpp=
class RangeAddBIT {
int n;
BIT D, xD;
public:
void init(int _n) {
n = _n;
D.init(n);
xD.init(n);
}
void add(int ql, int qr, int val) { // [ql, qr] 加值
D.modify(ql, val);
xD.modify(ql, ql * val);
if (qr < n) {
D.modify(qr + 1, -val);
xD.modify(qr + 1, -(qr + 1) * val);
}
}
long long query(int x) { // 查詢 [1,x] 總和
return (x + 1) * D.query(x) - xD.query(x);
}
};
```
### 常用函式
```cpp=
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
ordered_set.order_of_key(n)//找有幾個數小於n
ordered_set.find_by_order(n)//找第n小的數
#include<sstream>string s; stringstream ss(s);//ss<<input
ss.str(""),ss.clear();//clear
while(getline(ss,str,'m'))//以m分割
cout << str << endl;
int a,b; char c;
while(ss>>a>>c>>b)//處理像是-2/9+9/7
cout<<a<<" "<<c<<" "<<b<<endl;
//輸出 -2 / 9 endl 9 / 7
do {cout << s << "\n";}//排列組合(需sort)
while(next_permutation(s.begin(), s.end()));
prev_permutation()//逆向排列
#include<cstring>memset()//可用 0 -1 0x3F(1e9左右)
```
### 自訂隨機哈希(防卡常)
```cpp=
#include<chrono>
struct custom_hash {//Key只能放整數
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
```
### 快速冪 O(logn)
```cpp=
int qpow(int a,int b){
int res=1;
while(b){
if(b&1)
res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
```
### 線段樹
```cpp=
constexpr int N=5e5+5;
int n;
int seg[N<<2],tag[N<<2];
//線段樹與懶惰標記
void merge(int idx){
seg[idx]=seg[idx<<1]+seg[idx<<1|1];
//區間最大要把return x+y改成max(x,y)
}
void build(int idx=1,int l=1,int r=n){//創建線段樹
if(l==r){
cin>>seg[idx];
return;
}
int mid=(l+r)>>1;
build(idx<<1,l,mid);
build(idx<<1|1,mid+1,r);
merge(idx);
}
void push_tag(int idx,int l,int r){
if(tag[idx]){
int mid=(l+r)>>1;
seg[idx<<1]+=(mid-l+1)*tag[idx];//區間最大只需要seg[idx<<1]+=tag[idx];
seg[idx<<1|1]+=(r-mid)*tag[idx];//區間最大只需要seg[idx<<1|1]+=tag[idx];
tag[idx<<1]+=tag[idx];
tag[idx<<1|1]+=tag[idx];
tag[idx]=0;
}
}
void update_range(int ql,int qr,int val,int idx=1,int l=1,int r=n){//區間加值
if(l!=r)
push_tag(idx,l,r);
if(ql<=l&&r<=qr){
seg[idx]+=(r-l+1)*val;
tag[idx]+=val;
return;
}
int mid=(l+r)>>1;
if(qr<=mid)
update_range(ql,qr,val,idx<<1,l,mid);
else if(ql>mid)
update_range(ql,qr,val,idx<<1|1,mid+1,r);
else{
update_range(ql,qr,val,idx<<1,l,mid);
update_range(ql,qr,val,idx<<1|1,mid+1,r);
}
merge(idx);
}
int query(int ql,int qr,int idx=1,int l=1,int r=n){//區間查詢
if(l!=r)
push_tag(idx,l,r);
//ql~qr為欲查詢的範圍
if(ql<=l&&r<=qr)
return seg[idx];
int mid=(l+r)>>1;
if(mid>=qr)
return query(ql,qr,idx<<1,l,mid);
else if(ql>mid)
return query(ql,qr,idx<<1|1,mid+1,r);
else
return query(ql,qr,idx<<1,l,mid)+query(ql,qr,idx<<1|1,mid+1,r);
//區間最大要把return x+y改成max(x,y)
}
void update(int pos,int val,int idx=1,int l=1,int r=n){//單點更新
if(l==r){
seg[idx]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
update(pos,val,idx<<1,l,mid);
else
update(pos,val,idx<<1|1,mid+1,r);
merge(idx);
}
```
### 01背包問題 O(n)
```cpp=
for(int i=1;i<=n;i++){
for(int j=x;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
```
### 無限背包問題 O(n)
```cpp=
for(int i=1;i<=W;i++){ // 從小到大遍歷重量
for(int j=1;j<=n;j++){ // 遍歷每個物品
if(i>=w[j]) dp[i]=max(dp[i],dp[i-w[j]]+v[j]);
}
}
```
### LIS 最長遞增子序列
```cpp=
for(const auto &i:num){
if(ans.empty()||ans.back()<=i)
ans.push_back(i);
else
*upper_bound(all(ans),i)=i;
}
```
### LIS 最長遞增子序列(DP為求得LIS實際子序列)
```cpp=
for(int i=0;i<num.size();i++){
if(lis.empty()||lis.back()<num[i]){
lis.push_back(num[i]);
dp[i]=lis.size();
}
else{
auto iter=lower_bound(all(lis),num[i]);
dp[i]=iter-lis.begin()+1;
*iter=num[i];
}
}
int length=lis.size();
for(int i=num.size()-1;i>=0;i--){
if(dp[i]==length){
ans.push_back(num[i]);
length--;
}
}
```
### 拓樸排序 O(V+E)
```cpp=
void Topological_sorting(){
queue<int> que;
for(int i=1;i<=n;i++){
if(!in[i]){
que.push(i);
}
}
while(!que.empty()){
int cur=que.front();
que.pop();
ans.push_back(cur);
for(const auto &i:out[cur]){
in[i]--;
if(!in[i])
que.push(i);
}
}
}
```
### 樹直徑
```cpp=
constexpr int N = 2e5 + 5;
vi routes[N];
int D1[N], D2[N]; // 最遠、次遠距離
int ans = 0; // 直徑長度
void DFS(int u = 1, int parent = -1) {
D1[u] = D2[u] = 0;
for (int v : routes[u]) {
if (v == parent) continue;
DFS(v, u);
int dis = D1[v] + 1;
if(dis > D1[u]){
D2[u] = D1[u];
D1[u] = dis;
}
else
D2[u] = max(D2[u], dis);
}
ans = max(ans, D1[u] + D2[u]);
}
```
### 樹重心
```cpp=
constexpr int MAXN = 2e5 + 5;
vi routes[MAXN];
int subtree_size[MAXN], ans, n;
void DFS(int cur = 1, int last = -1){
subtree_size[cur] = 1;
int max_subtree = 0;
for(const auto &i: routes[cur]){
if(i == last)
continue;
DFS(i, cur);
subtree_size[cur] += subtree_size[i];
max_subtree = max(max_subtree, subtree_size[i]);
}
max_subtree = max(max_subtree, n - subtree_size[cur]);
if(max_subtree <= n / 2)
ans = cur;
}
```
### 並查集
```cpp=
int f(int cur){
return num[cur]==cur?cur:num[cur]=f(num[cur]);
}
void merge(int a,int b){
a=f(a),b=f(b);
if(a!=b){
num[b]=a;
}
}
for(int i=0;i<n;i++)//初始化
num[i]=i;
```
### 並查集(連通塊與最大連接數)
```cpp=
int f(int cur){
return num[cur]<0?cur:num[cur]=f(num[cur]);
}
void connect(int a,int b){
a=f(a),b=f(b);
if(a!=b){
num[a]+=num[b];
mx=max(mx,-num[a]);
num[b]=a;
heap--;
}
}
```
### 最小生成樹 MST
```cpp=
sort(all(cost),cmp);//a.cost<b.cost
for(const auto &i:cost){
int a=f(i.a),b=f(i.b);//使用一般並查集
if(a!=b){
num[b]=a;
counter--;
ans+=i.cost;
}
}
```
### Dijkstra
```cpp=
void Dijkstra(){
priority_queue<pii,vector<pii>,greater<>> pq;
pq.push({0,1}),ans[1]=0;
while(!pq.empty()){
pii cur=pq.top();
pq.pop();
if(cur.first>ans[cur.second])
continue;
for(const auto &i:routs[cur.second]){
if(ans[i.second]>cur.first+i.first){
ans[i.second]=cur.first+i.first;
pq.push({ans[i.second],i.second});
}
}
}
}
```
### Bellman Ford
```cpp=
struct Edge{
int start, end, cost;
};
vll Bellman_Ford(const vector<Edge> &routes, int n, int start = 1){
vll ans(n + 1, LONG_LONG_MAX);
ans[start] = 0;
auto relax = [&](const Edge &a){
if(ans[e.start] != LONG_LONG_MAX && ans[a.end] > ans[a.start] + a.cost){
ans[a.end] = ans[a.start] + a.cost;
return 1;
}
return 0;
};
for(int t = 1; t <= n; t++){
bool update = 0;
for(const auto &e: routes)
update |= relax(e);
if(t == n && update)
return {};//有負權環
}
return ans;
}
```
### Floyd Warshall(DP)
```cpp=
void Floyd_warshall(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
}
}
}
}
```
### 單調隊列(求最大最小)
```cpp=
deque<int> mx,mn;
for(int i=0;i<n;i++){
if(!mx.empty()&&i-mx.front()>=window)
mx.pop_front();
if(!mn.empty()&&i-mn.front()>=window)
mn.pop_front();
while(!mx.empty()&&num[mx.back()]<num[i])
mx.pop_back();
while(!mn.empty()&&num[mn.back()]>num[i])
mn.pop_back();
mx.push_back(i),mn.push_back(i);
if(i>=window-1){
ans_max.push_back(num[mx.front()]);
ans_min.push_back(num[mn.front()]);
}
}
```
### 字串編輯距離(DP)
```cpp=
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1];
else
dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
}
}
```
### LCS 最長公共子序列(DP)
```cpp=
for(int i=1;i<=s1.size();i++){
for(int j=1;j<=s2.size();j++){
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
```
### 二元樹(以preorder和inorder建成)
```cpp=
class Node{
public:
char data;
Node* left;
Node* right;
Node(char value){
data=value;
right=nullptr;
right=nullptr;
}
};
class Tree{
public:
Node* root;
Tree(){
root=nullptr;
}
Node* build_tree(vector<char>& preorder,vector<char>& inorder){
if(preorder.empty()||inorder.empty()){
return nullptr;
}
Node* point=new Node(preorder[0]);
auto findit=find(all(inorder),preorder[0]);
int length=findit-inorder.begin();
vector<char> inorder_left(inorder.begin(),findit);
vector<char> inorder_right(findit+1,inorder.end());
vector<char> preorder_left(preorder.begin()+1,preorder.begin()+1+length);
vector<char> preorder_right(preorder.begin()+1+length,preorder.end());
point->left=build_tree(preorder_left,inorder_left);
point->right=build_tree(preorder_right,inorder_right);
return point;
}
void Postorder(Node* x){
if(x){
Postorder(x->left);
Postorder(x->right);
cout<<x->data;
}
}
void del_tree(Node* x){
if(x==nullptr)
return;
del_tree(x->left);
del_tree(x->right);
delete x;
}
};
```
### 線段樹上二分搜
```cpp=
void st_bsearch(int pos,int idx=1,int l=1,int r=n){
if(l==r&&seg[idx]>=pos){
seg[idx]-=pos;
ans=l;
return;
}
int mid=(l+r)>>1;
if(seg[idx<<1]>=pos)
st_bsearch(pos,idx<<1,l,mid);
else if(seg[idx<<1|1]>=pos)
st_bsearch(pos,idx<<1|1,mid+1,r);
merge(idx);
}
```
### KMP演算法
```cpp=
string a; // 文本串
string b; // 模板串(将被匹配的子串)
int kmp_next[N]; // next数组
void getNext(int m=b.size()){//初始化
int j = 0;
kmp_next[0] = 0;
for(int i=1; i<m; ++i){
while(j>0 && b[i]!=b[j]) j=kmp_next[j-1];
if(b[i]==b[j]) ++j;
kmp_next[i] = j;
}
}
int kmp(int n=a.size(),int m=b.size()){//使用KMP寻找匹配位置
int i, j = 0;
int p = -1;
getNext(m);
for(i=0; i<n; ++i){
while(j>0 && b[j]!=a[i]) j=kmp_next[j-1];
if(b[j]==a[i]) ++j;
if(j==m){
p = i - m + 1;
break;
}
}
return p;
}
int kmp(int n=a.size(),int m=b.size()){//使用KMP计算匹配次数
int i, j = 0, res = 0;
getNext(m);
for(i=0; i<n; ++i){
while(j>0 && b[j]!=a[i]) j=kmp_next[j-1];
if(b[j]==a[i]) ++j;
if(j==m) ++res;
}
return res;
}
```
### 動態開點+懶惰標記線段樹
```cpp=
//註解部分為修改為 max 要改動的地方
class Node {
public:
Node* left;
Node* right;
int l;
int r;
int mid;
int v;
int add;
Node(int l, int r) {
this->l = l;
this->r = r;
this->mid = (l + r) >> 1;
this->left = this->right = nullptr;
v = add = 0;
}
};
class SegmentTree {
private:
Node* root;
public:
SegmentTree() {
root = new Node(1, 1e9);
}
void modify(int l, int r, int v) {
modify(l, r, v, root);
}
void modify(int l, int r,int v, Node* node) {
if(node->l>r||node->r<l) return;
if (node->l >= l && node->r <= r)
{
node->v += (node->r - node->l + 1) * v;//node->v += v;
node->add += v;
return;
}
pushdown(node);
modify(l, r, v, node->left);
modify(l, r, v, node->right);
merge(node);
}
int query(int l, int r) {
return query(l, r, root);
}
int query(int l, int r, Node* node) {
if(node->l>r||node->r<l) return 0;//return INT_MIN;
if (node->l >= l && node-> r <= r) return node->v;
pushdown(node);
return query(l, r, node->left)+query(l, r, node->right);//取max
}
void merge(Node* node) {
node->v = node->left->v+node->right->v;//取max，就改到這
}
void pushdown(Node* node) {
if (!node->left) node->left = new Node(node->l, node->mid);
if (!node->right) node->right = new Node(node->mid + 1, node->r);
if (node->add)
{
Node* left = node->left;
Node* right = node->right;
left->v += node->add;
left->add += node->add;
right->v += node->add;
right->add += node->add;
node->add = 0;
}
}
};
```
### SPFA(用於判斷負權環)
```cpp=
vector<pii> routs[N];
int dis[N],n,cnt[N];
bool SPFA(const int &start){
fill(dis,dis+n,1e9);
memset(cnt,0,sizeof(cnt));
dis[start]=0;
queue<int> que;
bitset<N> in_que;
que.push(start);
while(!que.empty()){
int cur=que.front();
que.pop();
cnt[cur]++;
if(cnt[cur]>n){
return 1;
}
in_que[cur]=0;
for(const auto &i:routs[cur]){
if(dis[i.second]>dis[cur]+i.first){
dis[i.second]=dis[cur]+i.first;
if(!in_que[i.second]){
que.push(i.second);
in_que[i.second]=1;
}
}
}
}
return 0;
}
```
### 稀疏表
```cpp=
constexpr int N=500;
int dp[N+5][32];
int a[N]={1,2,3,4,5};
//稀疏表 idx 從 1 開始
void build(){
for(int i=1;i<=N;i++)
dp[i][0]=a[i-1];
for(int k=1;k<32;k++){
for(int i=1;i+(1<<(k-1))<=N;i++){
dp[i][k]=max(dp[i][k-1],dp[i+(1<<(k-1))][k-1]);
}
}
}
int query(int l,int r){
int idx=__lg(r-l+1);
return max(dp[l][idx],dp[r-(1<<idx)+1][idx]);
}
```
### Z-Function
```cpp=
string s="123_123456789";
const int n=s.size();
vi z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (z[i - l] < r - i + 1)
z[i] = z[i - l];
else {
z[i] = max(r - i + 1, 0);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
z[i]++;
l = i, r = i + z[i] - 1;
}
}
```
### Trie
```cpp=
struct TrieNode {
int nxt[26]; //遇到a~z時的節點編號(idx)
int cnt; //以此結尾的字串個數
} node[1000005];
int idx = 2; //root = 1
void insert(string s){
int cur = 1; //從root開始
for(auto i:s) {
if(node[cur].nxt[i-'a'] == 0){
node[cur].nxt[i-'a'] = idx; //開一個新的node
cur = idx;
idx++;
}
else {
cur = node[cur].nxt[i-'a'];
}
}
node[cur].cnt++;
}
int query(string s){
int cur = 1;
for(auto i:s) {
if(node[cur].nxt[i-'a'] == 0){
return 0;
}
else {
cur = node[cur].nxt[i-'a'];
}
}
return node[cur].cnt;
}
```
Sign in with Wallet
Connect another wallet