常用的模板

我刷题常用的几个板子，因为敲一次代价太大，就给做成模板了!QAQ

万能模板1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define debug(ver) cout<<#ver<<" = "<<ver<<"\n";
#define debug2(ver,ver2) cout<<#ver<<" = "<<ver<< "  " << #ver2 << " = " << ver2 <<"\n";
#define endl "\n"
#define max(ver1,ver2) (ver1>ver2?ver1:ver2)
#define min(ver1,ver2) (ver1>ver2?ver2:ver1)
#define lowbit(ver) ver&(-ver)
#define pii pair<int,int>
//#define inf 0x3f3f3f3f
#define ull unsigned long long
#define int long long
#define i128 __int128
#define mod 1000000007
#define Mod 998244353
#define eps 1e-7
#define fl(i,l,r) for(int i=l;i<=r;i++)
#define fr(i,r,l) for(int i=r;i>=l;i--)
#define ef emplace_front
#define eb empalce_back
#define pb push_back
#define em emplace
#define se second
#define fi first
 
using namespace std;
 
inline void ikun();
inline int Read(){int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x * f;}
 
inline void Write(int x){if(x < 0){putchar('-');x=-x;}
if(x>9)Write(x/10);putchar(x%10+'0');return;}
inline void Write(int x,char c){Write(x),putchar(c);}
 
const int N = 2e5 + 10;
 
void solve() {
    
}
 
signed main() {
#ifdef MEGURINE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
    clock_t start = clock();
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1; //ikun();
//    cin >> T;
    cout << fixed << setprecision(12);
    while (T --) solve();
#ifdef MEGURINE
    clock_t end = clock();
    cout << "\nRunning Time: " << (double) (end - start) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
#endif
    return T ^ T;
}

万能模板2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define int long long
#define deb(x) cout << #x << " = " << x << '\n'
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define all1(f) f.begin() + 1, f.end()
#define here system("pause")
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define MOD 998244353
#define mod 1000000007
#define endl "\n"
#define X first
#define Y second

#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(...) "cyh2.2"
#define debug(...) "cyh2.2"
#endif

using namespace std;

template <class T> inline void read(T& x) {x = 0;char c = getchar();bool f = 0;for(; !isdigit(c); c = getchar()) f ^= (c == '-'); for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); x = f ? -x : x; }
template <class T> inline void write(T x) {if(x < 0) putchar('-'), x = -x;if(x < 10) putchar(x + 48);else write(x / 10), putchar(x % 10 + 48); }

inline int qmi(int a, int b, int p) {int ans = 1 % p;while(b){if(b & 1) ans = ans * a % p;a = a * a % p;b >>= 1;} return ans;}
inline int inv(int a, int p) {return qmi(a, p - 2, p) % p;}

const int N = 2e5 + 10, M = 150, maxn = 20;
const double pi = acos(-1);
const long double E = exp(1);
const double eps = 1e-8;
typedef pair<int, int> pii;

inline void solve() {

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    cout << fixed << setprecision(10);
    while(_ --) {
        solve();
    }
    return _ ^ _;
}

debug

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
// #define debug1(X) cout<<#X<<" = "<<X<<"\n"
// #define debug2(X,Y) cout<<#Y<<" = "<<Y<<", "<<#X<<" = "<<X<<"\n"
#undef _GLIBCXX_DEBUG
 
using namespace std;
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

// #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug(...) cerr << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define debug1(X) cout<<#X<<" = "<<X<<"\n"
#define debug2(X,Y) cout<<#Y<<" = "<<Y<<", "<<#X<<" = "<<X<<"\n"

排序板子

选择排序

稳定性：不稳定
时间复杂度：O(n * n)

1
2
3
4
5
6
7
8
9
inline void selection_sort(int a[], int n) {
    for(int i = 1; i < n; i ++) {
        int t = i;
        for(int j = i + 1; j <= n; j ++) {
            if(a[j] < a[t])
                t = j;
        } swap(a[i], a[t]);
    }
}

冒泡排序

稳定性：稳定
时间复杂度：O(n * n)

1
2
3
4
5
6
7
8
9
10
11
12
inline void bubble_sort(int a[], int n) {
    bool f = true;
    while(f) {
        f = false;
        for(int i = 1; i < n; i ++) {
            if(a[i] > a[i + 1]) {
                f = true;
                swap(a[i], a[i + 1]);
            }
        }
    }
}

插入排序

稳定性：稳定
时间复杂度：O(n * n)

1
2
3
4
5
6
7
8
inline void insertion_sort(int a[], int n) {
    for(int i = 1; i < n; i ++) {
        int t = a[i], j = i - 1;
        while(j >= 0&&a[j] > t) {
            a[j + 1] = a[j], j --;
        } a[j + 1] = t;
    }
}

折半插入排序

稳定性：不稳定
时间复杂度：O(nlog(n))

1
2
3
4
5
6
7
8
9
inline void inssertion_sort(int a[], int n) {
    if(n < 2) return ;
    for(int i = 1; i != n; i ++) {
        int t = a[i];
        auto j = upper_bound(a, a + i, t) - a;
        memmove(a + j + 1, a + j, (i - j) * sizeof(int));
        a[j] = t;
    }
}

计数排序

稳定性：稳定
时间复杂度：O(n + mx)

1
2
3
4
5
6
7
8
9
10
11
12
inline void counting_sort(int a[], int n) {
    int b[mx], s[mx];
    memset(s, 0, sizeof s);
    for(int i = 1; i <= n; i ++) {
        s[a[i]] ++;
    } for(int i = 1; i <= mx; i ++) {
        s[i] += s[i - 1];
    } for(int i = n; i >= 1; i --) {
        b[s[a[i]] --] = a[i];
    }
}

快速排序

稳定性：不稳定
时间复杂度：O(nlog(n))

1
2
3
4
5
6
7
8
9
10
inline void quick_sort(int a[], int l, int r) {
    if(l >= r) return ;
    int x = a[(l+r+1)/2], i = l - 1, j = r + 1;
    while(i < j) {
        while(a[++ i] < x);
        while(a[-- j] > x);
        if(i < j) swap(a[i], a[j]);
    } quick_sort(a, l, i - 1);
    quick_sort(a, i, r);
}

归并排序

稳定性：稳定
时间复杂度：O(nlog(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void merge_sort(int l, int r) {
    if(l >= r) {
        return ;
    } int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid&&j <= r) {
        if(f[i] < f[j]) {
            t[k ++] = f[i ++];
        } else {
            t[k ++] = f[j ++];
        }
    } while(i <= mid) {
        t[k ++] = f[i ++];
    } while(j <= r) {
        t[k ++] = f[j ++];
    } for(int i = l, k = 0; i <= r; i ++, k ++) {
        f[i] = t[k];
    }
}

二分

1
2
3
4
5
6
while(l < r)//模板一：找最左边的那个与目标值相等的下标
{
    mid = l + r >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
}
1
2
3
4
5
6
while(l < r)//模板二：找最右边的那个与目标值相等的下标
{
    mid = l + r + 1 >> 1;
    if(check(mid)) l = mid;
    else r = mid - 1;
}

高精度

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void solve() {
    string aa, bb;
    int a[N], b[N], c[N];
    cin >> aa >> bb;
    int la = aa.size(), lb = bb.size(), mx = max(la, lb);
    for(int i = 0; i < la; i ++) {
        a[la - i - 1] = aa[i] - '0';
    } for(int i = 0; i < lb; i ++) {
        b[lb - i - 1] = bb[i] - '0';
    } for(int i = 0; i < mx; i ++) {
        c[i] += a[i] + b[i];
        if(c[i] > 9) {
            c[i + 1] ++, c[i] -= 10;
        }
    } while(!c[mx]&&mx >= 1) {
        mx --;
    } while(mx >= 0) {
        printf("%d", c[mx --]);
    }
}

减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
inline void solve() {
    string aa, bb;
    int a[N], b[N], c[N];
    cin >> aa >> bb;
    int la = aa.size(), lb = bb.size(), mx = max(la, lb);
    for(int i = 0; i < la; i ++) {
        a[la - i - 1] = aa[i] - '0';
    } for(int i = 0; i < lb; i ++) {
        b[lb - i - 1] = bb[i] - '0';
    } for(int i = 0; i < mx; i ++) {
        c[i] += a[i] - b[i];
        if(c[i] < 0) {
            c[i + 1] --, c[i] += 10;
        }
    } if(c[mx] < 0) {
        cout << '-';
        for(int i = 0; i <= mx; i ++) {
            c[i] = 0;
        } for(int i = 0; i < mx; i ++) {
            c[i] += b[i] - a[i];
            if(c[i] < 0) {
                c[i + 1] --, c[i] += 10;
            }
        }
    } while(!c[mx]&&mx >= 1) {
        mx --;
    } while(mx >= 0) {
        cout << c[mx --];
    }
}

乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline vector<int > mul(vector<int> a, int b, int x) {
    int t = 0;
    vector<int> c;
    reverse(c.begin(), c.end());
    for(int i = 0; i < a.size()||t; i ++) {
        if(i < a.size())
            t += a[i] * b;
        if(!i) t += x;
        c.push_back(t % 10);
        t /= 10;
    } while(!c.back() && c.size() > 1){
        c.pop_back();
    } return c;
}

除法

1
2
3
4
5
6
7
8
9
10
11
inline vector<int> div(vector<int> &A, int &B, int &r) {
    vector<int> C;
    for(int i = 0; i < A.size(); i ++) {
        r = r * 10 + A[i];
        C.push_back(r / B);
        r %= B;
    } reverse(C.begin(), C.end());
    while(C.size() > 1&&C.back() == 0) {
        C.pop_back();
    } return C;
}

前缀和

1
2
3
f[i] = f[i - 1] + a[i];
f[i] += f[i - 1];

二位前缀和

1
2
3
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i] [j];
ans = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];

差分

1
2
f[i] = a[i] - a[i - 1];
f[i] += f[i - 1];

二维差分

1
2
3
4
5
f[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
f[x1][y1] += c, f[x1][y2+1] -= c;
f[x2+1][y1] -= c, f[x2+1][y2+1] += c;
f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];

双指针

1
2
3
4
5
6
for(int l = 0, r = 0, s = 0; l < n; l ++) {
    while((l >= r||checn(s))&&r < n) {
        r ++, s += f[r];
    } s -= f[l];
}

图论

DFS

1
2
3
4
5
6
7
8
9
inline void dfs(int u) {
    st[u] = 1;
    for(int i = 0; i < e[u].size(); i ++) {
        int v = e[u][i], ww = w[u][i];
        if(!st[u]) {
            dfs(v);
        }
    }
}

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void bfs(int u)
{
    queue<int> q;
    q.push(u);
    st[u] = true;
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        for(int i = 0; i < e[t].size(); i ++) {
            int j = e[t][i];
            if(!st[j]) {
                st[j] = true;
                q.push(j);
            }
        }
    }
}

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
inline void LCA_init() {
    int hh = 0, tt = -1;
    ce[root] = 1;
    q[++ tt] = root;
    while(hh <= tt) {
        int t = q[hh ++];
        for(int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(ce[j] == 0) {
                ce[j] = ce[t] + 1;
                dist[j] = dist[t] + w[i];
                q[++ tt] = j;
                fa[j][0] = t;
                for(int k = 1; k < 15; k ++) {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}
 
inline int query(int a, int b) {
    if(ce[a] < ce[b]) swap(a, b);
    for(int i = 14; i >= 0; i --) {
        if(ce[fa[a][i]] >= ce[b])
            a = fa[a][i];
    } if(a == b) return a;
    for(int i = 14; i >= 0; i --) {
        if(fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    } return fa[a][0];
}

最短路

多源汇Floyd

1
2
3
4
5
6
7
8
9
inline void floyd() {
    for(int k = 1; k <= n; k ++) {
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
            }
        }
    }
}

单源堆优化Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pii, vector<pii>, greater<pii> > heap;
    dist[1] = 0;
    heap.push({0, 1});
    while(heap.size()) {
        auto t = heap.top();
        heap.pop();
        int y = t.second;
        if(st[y]) continue;
        st[y] = true;
        for(int i = h[y]; ~i; i = ne[i]) {
            int j = e[i];
            if(dist[j] > dist[y] + w[i]) {
                dist[j] = dist[y] + w[i];
                heap.push({dist[j], j});
            }
        }
    } if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline int spfa() {
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    dist[1] = 0; st[1] = true;
    q.push(1);
    while(q.size()) {
        int t = q.front(); q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if(!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    } return dist[n];
}

最小生成树

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int prim() {
    memset(dist, inf, sizeof(dist));
    int res = 0;
    for(int i = 0; i < n; i ++) {
        int t = -1;
        for(int j = 1; j <= n; j ++) {
            if(!st[j]&&(t == -1||dist[t] > dist[j]))
                t = j;
        } if(i&&dist[t] == inf) return inf;
        if(i) res += dist[t];
        st[t] = true;
        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], g[t][j]);
    } return res;
}

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DSU

inline int kruskal() {
    sort(s + 1,s + m + 1, cmp);
    int res = 0, cnt = 0;
    for(int i = 1; i <= m; i ++) {
        int a = s[i].a, b = s[i].b, w = s[i].w;
        if(find(a) != find(b)) {
            fa[find(a)] = find(b);
            cnt ++;
            res += w;
        }
    } if(cnt == n - 1) return res;
    return inf;
}

二分图

二分图判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
inline bool dfs(int u, int c) {
    color[u] = c;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(!color[j]) {
            if(!dfs(j, 3 - c)) {
                return false;
            }
        } else if(color[j] == c) {
            return false;
        }
    } return true;
}

inline void check() {
    for(int i = 1; i <= n; i ++) {
        if(!color[i]) {
            if(!dfs(i, 1)) {
                ok = false;
                break;
            }
        }
    }
}

匈牙利算二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
inline bool find(int x) {
    for(int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        if(!st[j]) {
            st[j] = true;
            if(!b[j]||find(b[j])) {
                b[j] = x;
                return true;
            }
        }
    } return false;
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline bool topsort() {
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++) {
        if(!d[i]) {
            q[++ tt] = i;
        }
    } while(hh <= tt) {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i =ne[i]) {
            int j = e[i];
            d[j] --;
            if(d[j] == 0) {
                q[++ tt] = j;
            }
        }
    } return tt == n - 1;
}

Tarjan算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++ top] = u, in_stk[u] = true;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if(in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    } if(dfn[u] == low[u]) {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top --];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        }while(y != u);
    }
}

强连通分量的建边缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
inline void solve() {
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        int a, b, x;
        while(cin >> a, a) {
            add(i, a);
        }
    } for(int i = 1; i <= n; i ++) {
        if(!dfn[i]) {
            tarjan(i);
        }
    } for(int i = 1; i <= n; i ++) {
        for(int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if(a != b) {
                dout[a] ++, in[b] ++;
            }
        }
    } int p = 0, q = 0;
    for(int i = 1; i <= scc_cnt; i ++) {
        if(!dout[i]) p ++;
        if(!in[i]) q ++;
    } cout << q << '\n';
    if(scc_cnt == 1) p = q = 0;
    cout << max(p, q) << '\n';
}

倍增

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
inline void LCA_init() {
    int hh = 0, tt = -1;
    ce[root] = 1;
    q[++ tt] = root;
    while(hh <= tt) {
        int t = q[hh ++];
        for(int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(ce[j] == 0) {
                ce[j] = ce[t] + 1;
                dist[j] = dist[t] + w[i];
                q[++ tt] = j;
                fa[j][0] = t;
                for(int k = 1; k < 15; k ++) {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}
 
int LCA(int a, int b) {
    if(ce[a] < ce[b]) swap(a, b);
    for(int i = 14; i >= 0; i --) {
        if(ce[fa[a][i]] >= ce[b]) {
            a = fa[a][i];
        }
    } if(a == b) return a;
    for(int i = 14; i >= 0; i --) {
        if(fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    } return fa[a][0];
}

RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void init_RMQ() {
    for(int j = 0; j < M; j ++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i ++) {
            if(!j) {
                mn[i][j] = a[i];
            } else {
                mn[i][j] = max(mn[i][j - 1], mn[(i + (1 << j - 1))][j - 1]);
            }
        }
    }
}
 
int RMQ(int l, int r)
{
    int k = r - l + 1;
    k = log(k) / log(2);
    return max(mn[l][k], mn[r - (1 << k) + 1][k]);
}

网络流Dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct Dinic {
    vector<int> q, f, ne, e, h, d, cur;
    int idx, n, m, S, T, inf;
    Dinic(int n_, int m_, int S_, int T_) : n(n_) {
        idx = 0, n = n_, m = m_, S = S_, T = T_, inf = 1e8;
        e.resize(m_, 0), f.resize(m_, 0);
        ne.resize(m_, 0), h.resize(n_, -1);
        q.resize(n_, 0), d.resize(n_, 0);
        cur.resize(n_, 0);
    }
    inline void add(int a, int b, int c) {
        e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
        e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
    }
    inline bool bfs() {
        for(int i = 0; i < n; i ++) {
            d[i] = -1;
        } int hh = 0, tt = 0;
        q[0] = S, d[S] = 0, cur[S] = h[S];
        while(hh <= tt) {
            int t = q[hh ++];
            for(int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if(d[j] == -1&&f[i]) {
                    d[j] = d[t] + 1;
                    cur[j] = h[j];
                    if(j == T) return true;
                    q[++ tt] = j;
                }
            }
        } return false;
    }
    inline int find(int u, int limit) {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i&&flow < limit; i = ne[i]) {
            cur[u] = i;
            int j = e[i];
            if(d[j] == d[u] + 1&&f[i]) {
                int t = find(j, min(f[i], limit - flow));
                if(!t) d[j] = -1;
                f[i] -= t, f[i ^ 1] += t, flow += t;
            }
        } return flow;
    }
    inline int dinic() {
        int r = 0, flow;
        while(bfs()) while(flow = find(S, inf)) r += flow;
        return r;
    }
};

数学

素数

素数判断

1
2
3
4
5
6
7
inline bool is_prime(int x) {
    for(int i = 2; i <= x / i; i ++) {
        if(x % i == 0) {
            return false;
        }
    } return true;
}

素数分解

1
2
3
4
5
6
7
8
9
10
inline void getdiv(int x) {
    for(int i = 2; i <= x / i; i ++) {
        if(x % i == 0) {
            int s = 0;
            while(x % i == 0) {
                s ++, x /= i;
            }
        }
    }
}

素数筛

埃氏筛

1
2
3
4
5
6
7
8
9
10
inline void init_prime(int n) {
    for(int i = 2; i <= n; i ++) {
        if(!st[i]) {
            prime[cnt ++] = i;
            for(int j = i * i; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
}

欧拉筛(线性筛)

1
2
3
4
5
6
7
8
9
10
inline void init_prime(int n) {
    for(int i = 2; i <= n; i ++) {
        if(!st[i]) {
            prime[cnt ++] = i;
            for(int j = i * i; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
}

试除法求约数

1
2
3
4
5
6
7
8
9
10
11
inline vector<int> get_x(int x) {
    vector<int> s;
    for(int i = 2; i <= x / i; i ++) {
        if(x % i == 0) {
            s.push_back(i);
            if(x / i != i) {
                s.push_back(x / i);
            }
        }
    } return s;
}

欧拉函数

欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int eular(int x) {
    int ans = x;
    for(int i = 2; i * i <= x; i ++) {
        if(x % i == 0) {
            ans = ans * (i - 1) / i;
            while(x % i == 0) {
                x /= i;
            }
        }
    } if(x > 1) {
        ans = ans * (x - 1) / x;
    } return ans;
}

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void get_eular() {
    vector<int> phi(n + 1, 0), p;
    vector<bool> st(n + 1, false);
    st[0] = st[1] = true;
    phi[1] = 1;
    for(int i = 2; i <= n; i ++) {
        if(!st[i]) {
            p.emplace_back(i);
            phi[i] = i - 1;
        } for(int j = 0; j < p.size()&&i * p[j] <= n; j ++) {
            st[i * p[j]] = true;
            if(i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            } phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    } for(int i = 1; i <= n; i ++) {
        phi[i] += phi[i - 1];
    } cout << phi[n] << '\n';
}

快速幂

快速幂

1
2
3
4
5
6
7
8
9
inline int qmi(int a, int b, int p) {
    int ans = 1;
    while(b) {
        if(b & 1) {
            ans = ans * a % p;
        } a = a * a % p;
        b >>= 1;
    } return ans;
}

快速幂求逆元

1
2
3
4
5
6
7
8
inline int qminv(int a, int p) {
    int ans = 1, b = p - 2;
    while(b) {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    } return ans;
}

组合数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
namespace Combination {
    int fc[1010];
    inline void inti_fc(int mod) {
        fc[0] = 1;
        for(int i = 1; i <= 1001; i ++) {
            fc[i] = fc[i - 1] * i % mod;
        }
    }
    inline int pow(int a, int b, int mod) {
        int ans = 1 % mod;
        while(b) {
            if(b & 1) ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        } return ans;
    }
    inline int C(int a, int b, int mod) {
        int x = 1, y = 1;
        for(int i = 1, j = a; i <= b; i ++, j --)
            y = y * i % mod,
            x = x * j % mod;
        return x * pow(y, mod - 2, mod) % mod;
    }
    //卢卡斯定理：
    // b    (b mod p)     [b/p]
    // C  ≡   C   *   C  (mod p)
    // a    (a mod p)     [a/p]
    int Lucas(int a, int b, int mod){
        if(a < mod && b < mod) return C(a, b, mod);
        return C(a % mod, b % mod, mod) * Lucas(a / mod, b / mod, mod) % mod;
    }
};
using namespace Combination;

矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void mul(int c[][N], int b[][N], int a[][N]) {
    int t[N][N];
    memset(t, 0, sizeof t);
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            for(int k = 0; k < N; k ++) {
                t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod1;
            }
        }
    } memcpy(c, t, sizeof t);
}

inline void qmi() {
    while(n) {
        if(n & 1) {
            mul(f, a, f);
        } mul(a, a, a);
        n >>= 1;
    }
}

扩展欧几里得

1
2
3
4
5
6
7
8
inline int exgcd(int a, int b, int &x, int &y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    } int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

高斯消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
inline int gauss() {
    int c, r;
    for(c = 0, r = 0; c < n; c ++) {
        int t = r;
        for(int i = r; i < n; i ++) {
            if(fabs(a[i][c]) > fabs(a[t][c])) {
                t = i;
            }
        } if(abs(a[t][c]) < eps) continue;
        for(int i = c; i < n + 1; i ++) {
            swap(a[t][i], a[r][i]);
        } for(int i = n; i >= c; i --) {
            a[r][i] /= a[r][c];
        } for(int i = r + 1; i < n; i ++) {
            if(abs(a[i][c]) > eps) {
                for(int j = n; j >= c; j --) {
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        } r ++;
    } if(r < n) {
        for(int i = r; i < n; i ++)
            if(fabs(a[i][n]) > eps)
                return 2;
        return 1;
    } for(int i = n - 1; i >= 0; i --) {
        for(int j = i + 1; j < n; j ++) {
            a[i][n] -= a[j][n] * a[i][j];
        }
    } return 0;
}

斯特林数

第一类斯特林数

1
2
3
4
5
6
7
8
inline void Strustal() {
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j]) % mod;
        }
    }
}

第二类斯特林数

1
2
3
4
5
6
7
8
inline void Strustal() {
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            f[i][j] = (f[i - 1][j - 1] + j * f[i - 1][j]) % mod;
        }
    }
}

线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void xianxing() {
    int k = 0;
    for(int i = 63; i >= 0; i --) {
        for(int j = k; j < n; j ++) {
            if(f[j] >> i & 1) {
                swap(f[j], f[k]);
                break;
            }
        } if((f[k] >> i & 1) == 0) {
            continue;
        } for(int j = 0; j < n; j ++) {
            if(j != k&&f[j] >> i & 1) {
                f[j] ^= f[k];
            }
        } k ++;
        if(k == n) break;
    } int ans = 0;
    for(int i = 0; i < n; i ++) {
        ans ^= f[i];
    } cout << ans << '\n';
}

动态规划DP

背包

01背包

1
2
3
4
5
for(int i = 1; i <= n; i ++) {
    for(int j = m; j >= v[i]; j --) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

完全背包

1
2
3
4
5
for(int i = 1; i <= n; i ++) {
    for(int j = v[i]; j <= m; j ++) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}

多重背包

1
2
3
4
5
6
7
for(int i = 1; i <= n; i ++){
    for(int j = 0; j <= m; j ++) {
        for(int k = 0; k <= s[i]&&k * v[i] <= j; k ++) {
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);
        }
    }
}

二进制背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 1; i <= n; i ++) {
    cin >> w >> v >> s;
    int k = 1;
    while(s > k) {
        s -= k;
        p[cnt ++] = {w * k, v * k};
        k *= 2;
    } p[cnt ++] = {w * s, v * s};
} for(int i = 0; i < cnt; i ++) {
    for(int j = m; j >= p[i].w; j --) {
        f[j] = max(f[j], f[j - p[i].w] + p[i].v);
    }
}

单调队列背包

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= n; i ++) {
    for(int r = 0; r < v[i]; r ++) {
        int hh = 0, tt = -1;
        for(int j = r; j <= m; j += v[i]) {
            while(hh <= tt&&j - q[hh] > v[i] * s[i]) hh ++;
            while(hh <= tt&&f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) tt --;
            q[++ tt] = j;
            f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
        }
    }
}

二维背包

1
2
3
4
5
6
7
for(int i = 0; i < n; i ++) {
    for(int j = V; j >= v[i]; j --) {
        for(int l = W; l >= w[i]; l --) {
            f[j][l] = max(f[j][l], f[j - v[i]][l - w[i]] + a[i]);
        }
    }
}

分组背包

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i ++) {
    for(int j = m; j >= 0; j --) {
        for(int  k = 1; k <= s[i]; k ++) {
            if(j >= v[i][k]) {
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }
}

线性DP

1
2
3
4
5
for(int i = n - 1; i >= 1; i --) {
    for(int j = i; j >= 1; j --) {
        f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];}
    }
}

区间DP

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int len = 1; len <= n; len ++) {
    for(int i = 0; i + len - 1 < n; i ++) {
        int j = i + len - 1;
        int mx = 0;
        for(int k = i + 1; k <= j; k ++) {
            int a = ff[k][0] - ff[i][0];
            int b = ff[j + 1][1] - ff[k][1];
            if (L <= abs(a - b)&&abs(a - b) <= R) {
                f[i][j] = max(f[i][j], f[i][k - 1] + f[k][j] + 1);
            }
        }
    }
}

最长上升序列

1
2
3
4
5
6
7
8
9
for(int i = 0; i < n; i ++) {
    int l = 0, r = len;
    while(l < r) {
        int m = l + r + 1 >> 1;
        if(f[m] < a[i]) l = m;
        else r = m - 1;
    } f[r + 1] = a[i];
    if(r + 1 > len) len ++;
}

状态机

1
2
3
4
5
for(int i = 1; i <= n; i ++) {
    f[i][0] = max(f[i - 1][0], f[i - 1][2]);
    f[i][1] = max(f[i - 1][1], f[i - 1][0] - a[i]);
    f[i][2] = f[i - 1][1] + a[i];
}

字符串

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 1, j = -1; i < n; i ++) {
    while(j != -1&&a[i] != a[j + 1]) {
        j = ne[j];
    } if(a[i] == a[j + 1]) {
        j ++;
    } ne[i] = j;
} for(int i = 0, j = -1; i < m; i ++) {
    while(j != -1&&b[i] != a[j + 1]) {
        j = ne[j];
    } if(b[i] == a[j + 1]) {
        j ++;
    } if(j == n - 1) {
        cout << i - j << ' ';
        j = ne[j];
    }
}

Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Trie {
    vector<vector<int> > son;
    vector<int> cnt;
    int n, idx;
    Trie(int m_, int n_) : n(n_) {
        idx = 0;
        son.assign(m_, vector<int> (150, 0));
        cnt.assign(m_, 0);
    }
    void insert(string &s) {
        int p = 0, n = s.size();
        for(int i = 0; s[i]; i ++) {
            int u = s[i];
            if(!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        cnt[p] ++;
    }
    int query(string &s) {
        int p = 0;
        for(int i = 0; s[i]; i ++) {
            int u = s[i];
            if(!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
};

AC自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
inline void Insert() {
    int p = 0;
    for(int i = 0; s[i]; i ++) {
        int u = s[i] - 'a';
        if(!tr[p][u]) tr[p][u] = ++ idx;
        p = tr[p][u];
    } cnt[p] ++;
}

inline void build() {
    int hh = 0, tt = -1;
    for(int i = 0; i < 26; i ++) {
        if(tr[0][i]) {
            q[++ tt] = tr[0][i];
        }
    } while(hh <= tt) {
        int t = q[hh ++];
        for(int i = 0; i < 26; i ++) {
            int p = tr[t][i];
            if(!p) tr[t][i] = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q[++ tt] = p;
            }
        }
    }
}

Manachar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Manachar {
    vector<char> ss;
    string s;
    vector<int> p;
    int n;
    Manachar(string s_) {
        n = s_.size(), s = s_;
    }
    inline void init() {
        int l = 0;
        ss.resize(n * 2 + 10);
        ss[l ++] = '$', ss[l ++] = '#';
        for(int i = 0; i < n; i ++) {
            ss[l ++] = s[i];
            ss[l ++] = '#';
        } ss[l ++] = '^';
        n = l;
    }
    inline int manachar() {
        init();
        p.resize(n + 10);
        int mr = 0, mid, mx = 0;
        for(int i = 1; i < n; i ++) {
            if(i < mr) p[i] = min(p[mid * 2 - i], mr - i);
            else p[i] = 1;
            while(ss[i - p[i]] == ss[i + p[i]]) {
                p[i] ++;
            } if(i + p[i] > mr) {
                mr = i + p[i];
                mid = i;
            } mx = max(mx, p[i]);
            // cout << p[i] << ' ';
        } return mx - 1;
    }
};

最小表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline int get_min(char s[]) {
    int i = 0, j = 1;
    while(i < n&&j < n) {
        int k = 0;
        while(k < n&&s[i + k] == s[j + k]) {
            k ++;
        } if(s[i + k] > s[j + k]) {
            i += k + 1;
        } else {
            j += k + 1;
        } if(i == j) {
            j ++;
        }
    } int k = min(i, j);
    s[k + n] = 0;
    return k;
}

数据结构

并查集DSU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

namespace DSU {
    struct dsu {
        vector<size_t> pa, size, sum;
        explicit dsu(size_t siz) : pa(siz * 2), size(siz * 2, 1), sum(siz * 2) {
            iota(pa.begin(), pa.begin() + siz, siz);
            iota(pa.begin() + siz, pa.end(), siz);
            iota(sum.begin() + siz, sum.end(), 0);
        }
        inline void unite(size_t x, size_t y) {
            x = find(x), y = find(y);
            if(x == y) return;
            if(size[x] < size[y]) swap(x, y);
            pa[y] = x;
            size[x] += size[y];
            sum[x] += sum[y];
        }
        inline void move(size_t x, size_t y) {
            auto fx = find(x), fy = find(y);
            if(fx == fy) return;
            pa[x] = fy;
            --size[fx], ++size[fy];
            sum[fx] -= x, sum[fy] += x;
        }
        inline bool ask(size_t x, size_t y) {
        	x = find(x), y = find(y);
        	return x == y;
        }
        inline size_t find(size_t x) {
            return pa[x] == x ? pa[x] : pa[x] = find(pa[x]);
        }
    };
};
using namespace DSU;

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
namespace SegmentTree {
    template<class Info>
    struct SegmentTree{
        int n;
        std::vector<Info> info;
        SegmentTree() : n(0) {}
        SegmentTree(int n_, Info v_ = Info()) {
            init(n_, v_);
        }
        template<class T>
        SegmentTree(std::vector<T> init_) {
            init(init_);
        }
        void init(int n_, Info v_ = Info()) {
            init(std::vector(n_, v_));
        }
        template<class T>
        void init(std::vector<T> init_) {
            n = init_.size();
            info.assign(4 << std::__lg(n), Info());
            std::function<void(int, int, int)> build = [&](int p, int l, int r) {
                if (r - l == 1) {
                    info[p] = init_[l];
                    return;
                }
                int m = (l + r) / 2;
                build(2 * p, l, m);
                build(2 * p + 1, m, r);
                pull(p);
            };
            build(1, 0, n);
        }
        void pull(int p) {
            info[p] = info[2 * p] + info[2 * p + 1];
        }
        void modify(int p, int l, int r, int x, const Info &v) {
            if (r - l == 1) {
                info[p] = v;
                return;
            }
            int m = (l + r) / 2;
            if (x < m) {
                modify(2 * p, l, m, x, v);
            } else {
                modify(2 * p + 1, m, r, x, v);
            }
            pull(p);
        }
        void modify(int p, const Info &v) {
            modify(1, 0, n, p, v);
        }
        Info rangeQuery(int p, int l, int r, int x, int y) {
            if (l >= y || r <= x) {
                return Info();
            }
            if (l >= x && r <= y) {
                return info[p];
            }
            int m = (l + r) / 2;
            return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
        }
        Info rangeQuery(int l, int r) {
            return rangeQuery(1, 0, n, l, r);
        }
        template<class F>
        int findFirst(int p, int l, int r, int x, int y, F pred) {
            if (l >= y || r <= x || !pred(info[p])) {
                return -1;
            }
            if (r - l == 1) {
                return l;
            }
            int m = (l + r) / 2;
            int res = findFirst(2 * p, l, m, x, y, pred);
            if (res == -1) {
                res = findFirst(2 * p + 1, m, r, x, y, pred);
            }
            return res;
        }
        template<class F>
        int findFirst(int l, int r, F pred) {
            return findFirst(1, 0, n, l, r, pred);
        }
        template<class F>
        int findLast(int p, int l, int r, int x, int y, F pred) {
            if (l >= y || r <= x || !pred(info[p])) {
                return -1;
            }
            if (r - l == 1) {
                return l;
            }
            int m = (l + r) / 2;
            int res = findLast(2 * p + 1, m, r, x, y, pred);
            if (res == -1) {
                res = findLast(2 * p, l, m, x, y, pred);
            }
            return res;
        }
        template<class F>
        int findLast(int l, int r, F pred) {
            return findLast(1, 0, n, l, r, pred);
        }
    };
};
using namespace SegmentTree;

树状数组

一维树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline int lowbit(int x) {
    return x & -x;
}
 
inline void add(int tr[], int x, int y) {
    for(int i = x; i <= n; i += lowbit(i)) {
        tr[i] += y;
    }
}
 
inline int sum(int tr[], int x) {
    int ans = 0;
    for(int i = x; i; i -= lowbit(i)) {
        ans += tr[i];
    } return ans;
}
 
inline int ask(int x) {
    return sum(tr, x) * (x + 1) - sum(pretr, x);
}

二维树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
inline int lowbit(int x) {
    return x & -x;
}
 
inline void add(int x, int y, int d) {
    for(int i = x; i <= n; i += lowbit(i)) {
        for(int j = y; j <= m; j += lowbit(j)) {
            tr1[i][j] += d;
            tr2[i][j] += x * d;
            tr3[i][j] += y * d;
            tr4[i][j] += x * y * d;
        }
    }
}
 
inline int sum(int x, int y) {
    int ans = 0;
    for(int i = x; i; i -= lowbit(i)) {
        for(int j = y; j; j -= lowbit(j)) {
            ans += (x + 1) * (y + 1) * tr1[i][j] - (x + 1) * tr3[i][j] - (y + 1) * tr2[i][j] + tr4[i][j];
        }
    } return ans;
}
 
inline int query(int x1, int y1, int x2, int y2) {
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}
 
inline void get(int x1, int y1, int x2, int y2, int x) {
    add(x1, y1, x);
    add(x1, y2 + 1, -x);
    add(x2 + 1, y1, -x);
    add(x2 + 1, y2 + 1, x);
}

扫描线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
struct Segment {
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t)const {
        return x < t.x;
    }
} seg[N * 2];
struct Node {
    int l, r;
    int cnt;
    double len;
} tr[N * 8];

vector<double> ys;

inline int find(double y) {
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

inline void pushup(int u) {
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r) {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    } else tr[u].len = 0;
}

inline void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l != r) {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

inline void modify(int u, int l, int r, int k) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].cnt += k;
        pushup(u);
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

inline int get_cd() {
    for (int i = 0, j = 0; i < n; i ++ ) {
        double x1, y1, x2, y2;
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        seg[j ++ ] = {x1, y1, y2, 1};
        seg[j ++ ] = {x2, y1, y2, -1};
        ys.push_back(y1), ys.push_back(y2);
    } sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    build(1, 0, ys.size() - 2);
    sort(seg, seg + n * 2);
    double res = 0;
    for (int i = 0; i < n * 2; i ++ ) {
        if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
        modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
    } return res;
}

计算几何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
namespace CG {
    int sgn(double x) {
        if(fabs(x) < eps) {
            return 0;
        } if(x < 0) {
            return -1;
        } return 1;
    }
     
    struct point {
        double x, y;
        point() {}
        point (double a, double b) {
            x = a, y = b;
        }
        bool operator==(point b) {
            return !sgn(x - b.x)&&!sgn(y - b.y);
        }
        point operator-(point b) {
            return point(x - b.x,y - b.y);
        }
        point operator+(point b) {
            return point(x + b.x, y + b.y);
        }
        double operator^(point b) {
            return x * b.y - y * b.x;
        }
        double operator*(point b) {
            return x * b.x + y * b.y;
        }
        point operator*(double b) {
            return point(x * b, y * b);
        }
        point operator/(double b) {
            return point(x / b, y / b);
        }
        static double cross(point a, point b) {
            return a.x * b.y - a.y * b.x;
        }
        static double dot(point a, point b) {
            return a.x * b.x + a.y * b.y;
        }
        point rotleft() {            //逆时针转90 
            return point(-y, x);
        }
        point rotright() {           //顺时针转90 
            return point(y, -x);
        }
        point rotate(point p, double angle) {
            point v = (*this)-p;
            double c = cos(angle);
            double s = sin(angle);
            return point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
        }
        static double dis2(point a, point b) {
            return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
        }
        double dis(point b) {
            return sqrt((x - b.x) * (x - b.x) * 1.0 + (y - b.y) * (y - b.y) * 1.0);
        }
        double culk(point b) {
            return (y - b.y) / (x - b.x);
        }
    };
     
    struct line {
        point a, b;
        line() {}
        line(point q,point w) {                  //两点式 
            a = q, b = w;
        }
        line(point p, double angle) {             //斜率式 
            a = p;
            if(sgn(angle - pi / 2) == 0) {
                b=(a+point(0,1));
            } else{
                b = (a + point(1, tan(angle)));
            }
        }
        line(double A, double B, double C) {       //Ax+By+C=0 
            if(sgn(A) == 0){
                a = point(0.0, -C / B);
                b = point(1.0, -C / B);
            } else if(sgn(B) == 0) {
                a = point(-C / A, 0);
                b = point(-C / A, 1);
            } else {
                a = point(0, -C / B);
                b = point(1, (-A - C) / B);
            }
        }
        point crosspoint(line l) {               //找交点 
            double a1 = point::cross(l.b - a, b - a);
            double a2 = point::cross(l.a - a, b - a);
            return point((a1 * l.a.x - a2 * l.b.x) / (a1 - a2), (a1 * l.a.y - a2 * l.b.y) / (a1 - a2));
        }
        double pointtoLine(point p) {                //点到直线距离 
            return fabs((p - a) ^ (b - a)) / sqrt(point::dis2(a, b));
        }
        double pointtoSeg(point p) {                 //点到线段距离 
            if(sgn((p - a) * (b - a)) < 0||sgn((p - b) * (a - b)) < 0) {
                return min(point::dis2(p, a), point::dis2(p, b));
            } return pointtoLine(p);
        }
        point lineprog(point p) {                    //点在直线上投影 
            return a + (((b - a) * ((b - a) * (p - a))) / (point::dis2(b, a)));
        }
        point mirrorpoint(point p) {                 //点关于直线对称点 
            point q = lineprog(p);
            return point(2 * q.x - p.x, 2 * q.y - p.y);
        }
    };
     
    struct triangle {
        point a, b, c;
        triangle() {}
        triangle(vector<point> in) {
            a = in[0], b = in[1], c = in[2];
        }
        point Circumcenter() {        //三角形外接圆圆心
            double x1 = a.x, y1 = a.y;
            double x2 = b.x, y2 = b.y;
            double x3 = c.x, y3 = c.y;
             
            double a1 = 2 * (x2 - x1);
            double b1 = 2 * (y2 - y1);
            double c1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
             
            double a2 = 2 * (x3 - x2);
            double b2 = 2 * (y3 - y2);
            double c2 = x3 * x3 + y3 * y3 - x2 * x2 - y2 * y2;
             
            double x = (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);
            double y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
             
            return point(x, y);
        }
        point Incenter() {            //三角形内切圆圆心
            double A = b.dis(c);
            double B = a.dis(c);
            double C = a.dis(b);
            double S = A + B + C; 
            double x = (A * a.x + B * b.x + C * c.x) / S;
            double y = (A * a.y + B * b.y + C * c.y) / S;
            return point(x, y);
        }
        point Orthocenter() {        //三角形垂线交点
            return point((a.x + b.x + c.x) / 3.0, (a.y + b.y + c.y) / 3.0);
        }
        point Centroid() {            //三角形中线交点
            double a1, b1, a2, b2, c1, c2;
            a1 = c.x - b.x, b1 = c.y - b.y, c1 = 0;
            a2 = c.x - a.x, b2 = c.y - a.y, c2 = (b.x - a.x) * a2 + (b.y - a.y) * b2;
            double d = a1 * b2 - a2 * b1;
            return point(a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) / d);
        }
    };
     
    struct circle {
        point p;
        double r;
        circle() {}
        circle(point a, double b) {
            p = a, r = b;
        }
        circle(double x, double y, double a) {
            p = point(x, y);
            r = a;
        }
        circle(point a, point b, point c) {                //三角形外接圆 
            line u = line((a + b) / 2, ((a + b) / 2) + ((b - a).rotleft()));
            line v = line((b + c) / 2, ((b + c) / 2) + ((c - b).rotleft()));
            p = u.crosspoint(v);
            r = sqrt(point::dis2(p, a));
        }
        circle(point a, point b, point c, bool inside) {            //三角形内切圆,inside没有用,只是用来区分两个构造函数  
            double m = atan2((b - a).y, (b - a).x);
            double n = atan2((c - a).y, (c - a).x);
            if(inside) {r = 0;}
            line u, v;
            u.a = a;
            u.b = u.a + point(cos((n + m) / 2), sin((n + m) / 2));
            v.a = b;
            m = atan2((a - b).y, (a - b).x);
            n = atan2((c - b).y, (c - b).x);
            v.b = v.a + point(cos((n + m) / 2), sin((n + m) / 2));
            p = u.crosspoint(v);
            r = line(a, b).pointtoSeg(p);
        } 
    };
     
    struct MRCLP {                               //最小矩形覆盖信息 
        line lne;
        point upp;
        point lep;
        point rip;
        MRCLP() {}
        MRCLP(line a, point u, point l, point r) {
            lne = a;
            upp = u;
            lep = l;
            rip = r;
        }
        point findcp(point b, point inline1, point inline2, point sf) {
            return b - inline1 * (point::cross(inline2, sf) / point::cross(inline1, inline2));
        }
        point equer(point a) {
            return point(a.y, -a.x);
        }
        void getcrosspoint() {
            vector<point> ans(10);
            point le = lne.b - lne.a;
            point anot = equer(le);
            ans[0] = MRCLP::findcp(lne.b, le, anot, rip - lne.b);
            ans[1] = MRCLP::findcp(rip, anot, le, upp - rip);
            ans[2] = MRCLP::findcp(upp, le, anot, lep - upp);
            ans[3] = MRCLP::findcp(lep, anot, le, lne.b - lep);
            int ori = 0;
            for(int i = 0; i <= 3; i ++) {
                if(sgn(ans[i].x) == 0) ans[i].x = 0.000;
                if(sgn(ans[i].y) == 0) ans[i].y = 0.000;
            }
            for(int i = 1; i <= 3; i ++) {
                if(ans[i].y < ans[ori].y||(ans[i].y == ans[ori].y&&ans[i].x < ans[ori].x)) {
                    ori=i;
                }
            }
            swap(ans[0], ans[ori]);
            for(int i = 1; i <= 3; i ++) {
                for(int j = 1; j <= 3; j ++) {
                    if(point::cross(ans[i] - ans[0], ans[j] - ans[i]) > 0) {
                        swap(ans[i],ans[j]);
                    }
                }
            }
            for(int i = 0; i <= 3; i ++) {
                printf("%.5lf %.5lf\n", ans[i].x, ans[i].y);
            }
        }
    };
     
    struct polygon {                             //多边形 
        vector<point> in;                     //输入的点集，求凸包操作后成为凸包上的点集(逆时针方向) 
        int cnt;
        MRCLP tmp;
        polygon() {}
        polygon(vector<point> a) {
            in = a;
        }
        bool isPolygon() {
            return in.size() >= 3;
        }
        void quicksort(int l, int r) {               //快排 
            if(l < r) {
                swap(in[l], in[(l + r) / 2]);
                int i = l, j = r;
                point x = in[l];
                while(i < j) {
                    while(i < j&&(point::cross(in[j] - in[0], x - in[j]) < 0||
                        (point::cross(in[j] - in[0], x - in[j]) == 0&&point::dis2(in[j], in[0]) > point::dis2(x, in[0])))) {j --;}
                    if(i < j) {in[i ++] = in[j];}
                    while(i < j&&(point::cross(in[i] - in[0], x - in[i]) > 0||
                        (point::cross(in[i] - in[0], x - in[i]) == 0&&point::dis2(in[i], in[0]) < point::dis2(x, in[0])))) {i ++;}
                    if(i < j) {in[j --] = in[i];}
                }
                in[i] = x;
                quicksort(l, i - 1);
                quicksort(i + 1, r);
            }
        }
        void convexHell() {                          //查找凸包上的点 
            int ori = 0;
            for(int i = 0; i < in.size(); i ++) {
                if(in[i].y < in[ori].y||(in[i].y == in[ori].y&&in[i].x < in[ori].x)) {
                    ori = i;
                }
            }
            swap(in[0], in[ori]);
            quicksort(1, in.size() - 1);
            vector<point> tmp(in.size() + 10);
            int nw = -1;
            for(int i = 0; i < in.size(); i ++) {
                while(nw >= 1) {
                    if(point::cross(tmp[nw] - tmp[nw - 1], in[i] - tmp[nw]) > 0) {break;}
                    else if(point::cross(tmp[nw] - tmp[nw - 1], in[i] - tmp[nw]) == 0) {
                        nw --;
                        break;
                    } else {nw--;}
                }
                tmp[++ nw] = in[i];
            }
            in.clear();
            for(int i = 0; i <= nw; i ++) {
                in.push_back(tmp[i]);
            }
        }
        double diameter() {                      //旋转卡壳(返回直径的平方) 
            double ans = 0;
            int nw = 1;
            for(int i = 1; i <= in.size(); i ++) {
                while(point::cross(in[i % in.size()] - in[i - 1], in[nw % in.size()] - in[i % in.size()]) <
                    point::cross(in[i % in.size()] - in[i - 1], in[(nw + 1) % in.size()] - in[i % in.size()])) {nw ++;}
                ans = max({ans, point::dis2(in[nw % in.size()], in[i % in.size()]), point::dis2(in[nw % in.size()], in[i - 1])});
            } return ans;
        }
        double MRC() {                           //最小矩形覆盖  
            double ans = 1e18;
            int upp = 1, lep = in.size() - 1, rip = 1;
            while(lep >= 1&&point::dot(in[0] - in[1], in[lep] - in[1]) <= point::dot(in[0] - in[1], in[lep - 1] - in[1])) {lep --;}         //左侧顶点先反向遍历，不然会WA 
            for(int i = 1; i <= in.size(); i ++) {
                while(point::cross(in[i % in.size()] - in[i - 1], in[upp % in.size()] - in[i % in.size()]) <=
                    point::cross(in[i % in.size()] - in[i - 1], in[(upp + 1) % in.size()] - in[i % in.size()])) {upp ++;}
                while(point::dot(in[i % in.size()] - in[i - 1], in[rip % in.size()] - in[i - 1]) <= point::dot(in[i % in.size()] - in[i - 1], in[(rip + 1) % in.size()] - in[i - 1])) {rip++;}
                while( point::dot(in[i - 1] - in[i % in.size()], in[lep % in.size()] - in[i % in.size()]) <=
                    point::dot(in[i - 1] - in[i % in.size()], in[(lep + 1) % in.size()] - in[i % in.size()])) {lep ++;}
                double area = fabs(point::cross(in[i % in.size()] - in[i - 1], in[upp % in.size()] - in[i % in.size()]));
                double lefleg = fabs(point::dot(in[i - 1] - in[i % in.size()], in[lep % in.size()] - in[i % in.size()]));
                double rigleg = fabs(point::dot(in[i % in.size()] - in[i - 1], in[rip % in.size()] - in[i - 1]));
                double dezleg = fabs(point::dot(in[i % in.size()] - in[i - 1], in[i - 1] - in[i % in.size()]));
                double S = area * (lefleg + rigleg - dezleg) / dezleg;
                if(sgn(S - ans) == -1) {
                    tmp = MRCLP(line(in[i % in.size()], in[i - 1]), in[upp % in.size()], in[lep % in.size()], in[rip % in.size()]);
                    ans = S;
                }
            } return ans;
        }
        double cularea() {                       //计算面积 
            if(!isPolygon()) return -1.0;
            double ans = 0;
            for(int i = 0; i < in.size(); i ++) {
                ans += point::cross(in[i], in[(i + 1) % in.size()]);
            } return ans / 2;
        }
        double culcel() {                        //计算周长 
            if(!isPolygon()) return -1.0;          //洛谷模板题上删去这句，答案有非多边形情况 
            double ans = 0;
            for(int i = 0; i < in.size(); i ++) {
                ans += sqrt(point::dis2(in[i], in[(i + 1) % in.size()]));
            } return ans;
        }
    };
     
    struct HPIL : public line {            //半平面交直线特性 
        double angle;
        HPIL() {}
        HPIL(point q, point w) {
            a = q;
            b = w;
            angle = atan2((b - a).y, (b - a).x);
        }
        HPIL(line z) {
            a = z.a;
            b = z.b;
            angle = atan2((b - a).y, (b - a).x);
        }
        bool operator<(HPIL t) {
            if(sgn(angle - t.angle) == 0) {
                return sgn(point::cross(t.a - a, t.b - a)) == 1;
            } return sgn(angle - t.angle) == -1;
        }
    };
     
    struct HPI {                             //半平面交 向量方向右侧平面 
        vector<HPIL> in;
        HPIL e[maxn];
        HPIL dq[maxn];
        int cnt = 1, top, back;
        HPI() {}
        HPI(vector<HPIL> a) {
            in=a;
        }
        void unique() {                      //去重 
            cnt = 0;
            for(int i = 1; i < (int)in.size(); i ++) {
                if(sgn(in[i].angle - in[i - 1].angle) != 0) in[++ cnt] = in[i];
            }
            for(int i = 0; i <= cnt; i ++) e[i + 1] = in[i];
            cnt ++;
        }
        bool cp(HPIL a, HPIL b, HPIL c) {
            point o = b.crosspoint(c);
            return sgn(point::cross(a.a - o, a.b - o)) == -1;
        }
        void toans() {                       //求解 
            sort(&in[0], &in[in.size()]);
            unique();
            top = 2, back = 1;
            dq[1] = e[1];
            dq[2] = e[2];
            for(int i = 3; i <= cnt; i ++) {
                while(back < top&&cp(e[i], dq[top], dq[top - 1])) top --;
                while(back < top&&cp(e[i], dq[back], dq[back + 1])) back ++;
                dq[++ top] = e[i];
            }
            while(back < top&&cp(dq[back], dq[top], dq[top - 1])) top --
            while(back < top&&cp(dq[top], dq[back], dq[back + 1])) back ++;
        }
        vector<point> getpolygon() {
            toans();
            vector<point> ans;
            for(int i = back; i < top; i ++) {
            	ans.push_back(dq[i].crosspoint(dq[i + 1]));
            }
            if(top - back > 1) ans.push_back(dq[top].crosspoint(dq[back]));
            return ans;
        }
    };
}
using namespace CG;