$C++$模板

很多$C++$的模板

1. 快读

inline int read() {int w = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-') {f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + (ch - '0');ch = getchar();}return w * f;
}

2. 线段树(区间求和)

#include <bits/stdc++.h>#define N 100001
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)using namespace std;int n, m;
int a[N];
ll tree[N << 2];
int siz[N << 2];
int lazy[N << 2];void upd(int p) {tree[p] = tree[ls] + tree[rs];
}void upds(int p) {siz[p] = siz[ls] + siz[rs];
}void pushd(int p) {tree[ls] += lazy[p] * siz[ls];tree[rs] += lazy[p] * siz[rs];lazy[ls] += lazy[p];lazy[rs] += lazy[p];lazy[p] = 0;
}void build(int p, int l, int r) {lazy[p] = 0;if(l == r)  {siz[p] = 1;tree[p] = a[l];return ;}build(ls, l, mid);build(rs, mid + 1, r);upd(p);upds(p);
}void mdf(int p, int l, int r, int ql, int qr, int k) {if(ql <= l && r <= qr) {tree[p] += 1ll * siz[p] * k;lazy[p] += k;return;}pushd(p);if(ql <= mid) {mdf(ls, l, mid, ql, qr, k);}if(qr > mid) {mdf(rs, mid + 1, r, ql, qr, k);}upd(p);
}ll qry(int p, int l, int r, int ql, int qr) {if(ql <= l && r <= qr) {return tree[p];}pushd(p);ll sum = 0;if(ql <= mid) {sum += qry(ls, l, mid, ql, qr);}if(qr > mid) {sum += qry(rs, mid + 1, r, ql, qr);}return sum;
}int main() {cin >> n >> m;for(int i = 1; i <= n; ++i) {cin >> a[i];}build(1, 1, n);while(m--) {int op, x, y, k;cin >> op >> x >> y;if(op == 1) {cin >> k;mdf(1, 1, n, x, y, k);}else {cout << qry(1, 1, n, x, y) << endl;}}return 0;
}

3. 网络流(最大流)

#include <bits/stdc++.h>#define N 500010using namespace std;long long nxt[N], to[N], head[N], w[N];
long long now[N];
int d[N];
long long n, m, s, t;
long long cnt = 1;inline void add(int u, int v, long long c) {nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;w[cnt] = c;nxt[++cnt] = head[v];head[v] = cnt;to[cnt] = u;w[cnt] = 0;
}inline bool bfs() {queue<int> q;q.push(s);memset(d, 0x3f, sizeof(d));d[s] = 0;now[s] = head[s];while(!q.empty()) {int x = q.front();q.pop();for(int i = head[x]; i; i = nxt[i]) {int v = to[i];if(d[v] == 0x3f3f3f3f && w[i] > 0) {d[v] = d[x] + 1;now[v] = head[v];q.push(v);if(v == t) {return 1;}}}}return 0;
}inline long long dfs(int x, long long flow) {if(x == t) {return flow;}long long k;for(int i = now[x]; i; i = nxt[i]) {now[x] = i;int v = to[i];if(d[v] != d[x] + 1 || w[i] <= 0) {continue;}k = dfs(v, min(flow, w[i]));if(k) {w[i] -= k;w[i ^ 1] += k;return k;}else {d[v] = 0x3f3f3f3f;}}return 0;
}inline long long dinic() {long long sum = 0;while(bfs()) {sum += dfs(s, 0x7fffffff);}return sum;
}int main() {cin >> n >> m >> s >> t;while(m--) {long long u, v, c;cin >> u >> v >> c;add(u, v, c);}cout << dinic() << endl;return 0;
}