Graph Theory Disjoint Set 【模板】并查集
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#define MAX_N 10000
using namespace std;
int n, m, f, x, y, father[MAX_N+5];
int getfather(int v) {if (father[v] == v) {return v;}father[v] = getfather(father[v]);return father[v];
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {father[i] = i;}for (int i = 0; i < m; i++) {cin >> f >> x >> y;if (f == 1) {int f1 = getfather(x);int f2 = getfather(y);if (f1 != f2) {father[f1] = f2;}} else {int f1 = getfather(x);int f2 = getfather(y);if (f1 != f2) {cout << "N" << endl; } else {cout << "Y" << endl;}}}return 0;
}
Minimum Spanning Tree (Kruskal) 【模板】最小生成樹
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 5000
#define MAX_M 200000
using namespace std;
struct node {int u, v, l;
} edge[MAX_M+5];
int n, m, tot = 0;
int father[MAX_N+5];
bool comp(const node &a, const node &b) {return a.l < b.l;
}
int getfather(int v) {if (father[v] == v) {return v;}father[v] = getfather(father[v]);return father[v];
}
int main() {cin >> n >> m;for (int i = 0; i < m; i++) {cin >> edge[i].u >> edge[i].v >> edge[i].l;}sort(edge, edge+m, comp);for (int i = 1; i <= n; i++) father[i] = i;int flag = n-1;for (int i = 0; i < m; i++) {int f1 = getfather(edge[i].u);int f2 = getfather(edge[i].v);if (f1 != f2) {father[f1] = f2;tot += edge[i].l;flag--;}if (flag == 0) break;}if (flag == 0) {cout << tot;} else {cout << "orz";}return 0;
}
Shortest Path Fastest Algorithm 【模板】單源最短路徑
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_M 500000
#define MAX_N 10000
#define INF 2147483647
using namespace std;
struct node {int v, len, next;node() {v = len = next = 0;}
} edge[MAX_M+5];
int n, m, s;
int first[MAX_N+5], cnt = 0;
int dis[MAX_N+5];
void insert(int u, int v, int l) {cnt++;edge[cnt].v = v;edge[cnt].len = l;edge[cnt].next = first[u];first[u] = cnt;
}
void SPFA() {for (int i = 1; i <= n; i++) {dis[i] = INF;}int que[MAX_N*20+5], mark[MAX_N+5];int head = 0, tail = 1;memset(mark, 0, sizeof(mark));que[1] = s;mark[s] = 1;dis[s] = 0;while (head <= tail) {head++;for (int tmp = first[que[head]]; tmp; tmp = edge[tmp].next) {if (dis[que[head]]+edge[tmp].len < dis[edge[tmp].v]) {dis[edge[tmp].v] = dis[que[head]]+edge[tmp].len;if (mark[edge[tmp].v] == 0) {mark[edge[tmp].v] = 1;tail++;que[tail] = edge[tmp].v;}}}mark[que[head]] = 0;}
}
int main() {cin >> n >> m >> s;memset(first, 0, sizeof(first));int u, v, l;for (int i = 0; i < m; i++) {cin >> u >> v >> l;insert(u, v, l);}SPFA();for (int i = 1; i <= n; i++) {cout << dis[i] << " ";}return 0;
}
Tarjan 【模板】縮點
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 100000
using namespace std;
int n, m, c[MAX_N+5], f[MAX_N+5];
int dfn[MAX_N+5], low[MAX_N+5], col[MAX_N+5], val[MAX_N+5], ind, cnt;
vector <int> G[MAX_N+5], E[MAX_N+5];
stack <int> sta;
bool insta[MAX_N+5];
void tarjan(int u) {dfn[u] = low[u] = ++ind, sta.push(u), insta[u] = true;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);else if (insta[v]) low[u] = min(low[u], dfn[v]);}if (dfn[u] == low[u]) {cnt++;for (int i = sta.top(); ; i = sta.top()) {col[i] = cnt, val[cnt] += c[i], insta[i] = false;sta.pop(); if (u == i) break;}}
}
int DFS(int u) {if (f[u]) return f[u];int mx = 0;for (int i = 0; i < E[u].size(); i++) mx = max(mx, DFS(E[u][i]));return f[u] = val[u]+mx;
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &c[i]);while (m--) {int u, v; scanf("%d%d", &u, &v);G[u].push_back(v);}for (int i = 1; i <= n; i++)if (!dfn[i]) tarjan(i);for (int u = 1; u <= n; u++) {for (int i = 0; i < G[u].size(); i++) {int v = G[u][i]; if (col[u] == col[v]) continue;E[col[u]].push_back(col[v]);}}int ans = 0;for (int i = 1; i <= cnt; i++)if (!f[i]) ans = max(ans, DFS(i));printf("%d", ans);return 0;
}
Cur Vertex 【模板】割點
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
struct Edge {int v, next;
} edge[MAX_M+5];
int first[MAX_N+5], flag[MAX_N+5], num[MAX_N+5], low[MAX_N+5];
int n, m, cnt = 0;
void insert(int u, int v, int pos) {edge[pos].next = first[u];edge[pos].v = v;first[u] = pos;
}
void dfs(int cur, int father) {int child = 0;num[cur] = low[cur] = ++cnt;for (int tmp = first[cur]; tmp; tmp = edge[tmp].next) {if (!num[edge[tmp].v]) {child++;dfs(edge[tmp].v, cur);low[cur] = min(low[cur], low[edge[tmp].v]);if (low[edge[tmp].v] >= num[cur]) {flag[cur] = 1;}} else if (num[edge[tmp].v] < num[cur] && edge[tmp].v != father) {low[cur] = min(low[cur], num[edge[tmp].v]);}}if (father == -1 && child == 1) {flag[cur] = 0;}
}
int main() {cin >> n >> m;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;insert(u, v, i*2+1);insert(v, u, i*2+2);}int tot = 0;for (int i = 1; i <= n; i++) {if (!num[i]) {dfs(i, -1);}if (flag[i]) {tot++;}}cout << tot << endl;for (int i = 1; i <= n; i++) {if (flag[i]) {cout << i << " ";}}return 0;
}
Lowest Common Ancestor 【模板】最近公共祖先 LCA
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 500000
using namespace std;
struct Edge {int next, to;
} edge[(MAX_N<<1)+5];
int n, m, s, x, y, cnt;
int d[MAX_N+5], p[MAX_N+5][25], first[MAX_N+5];
bool vis[MAX_N+5];
inline int read() {int ret = 0; char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') ret = ret*10+ch-'0', ch = getchar();return ret;
}
void INSERT(int a, int b) {edge[++cnt].next = first[a];edge[cnt].to = b;first[a] = cnt;
}
void DFS(int u) {vis[u] = true;for (int i = 1; (1<<i) <= n; i++) {if ((1<<i) <= d[u]) {p[u][i] = p[p[u][i-1]][i-1];}}for (int i = first[u]; i; i = edge[i].next) {int v = edge[i].to;if (!vis[v]) {d[v] = d[u]+1;p[v][0] = u;DFS(v);}}
}
int LCA(int a, int b) {int i, j;if (d[a] < d[b]) swap(a, b);for (i = 0; (1<<i) <= d[a]; i++) {}i--;for (j = i; j >= 0; j--) {if (d[a]-(1<<j) >= d[b]) {a = p[a][j];}}if (a == b) {return a;}for (j = i; j >= 0; j--) {if (p[a][j] != p[b][j]) {a = p[a][j];b = p[b][j];}}return p[a][0];
}
int main() {n = read(), m = read(), s = read();for (int i = 1; i < n; i++) {x = read(), y = read();INSERT(x, y);INSERT(y, x);}DFS(s);for (int i = 0; i < m; i++) {x = read(), y = read();cout << LCA(x, y) << endl; }return 0;
}
Negative Loop 【模板】負環(huán)
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 200000
#define SIZE 25000000
using namespace std;
int f; char BUF[SIZE], *buf = BUF;
inline void read(int &x) {bool flag = 0; while (*buf < 48) if (*buf++ == 45) flag = 1;x = 0; while (*buf > 32) x = x*10+*buf++-48; x = flag ? -x : x;
}
vector <int> G[MAX_N+5], E[MAX_N+5];
int dis[MAX_N+5];
bool insta[MAX_N+5], flag;
void init(int n) {flag = false;for (int i = 1; i <= n; i++) G[i].clear(), E[i].clear();memset(dis, 0, sizeof(dis)), memset(insta, false, sizeof(insta));
}
void DFS(int u) {insta[u] = true;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i], c = E[u][i];if (dis[u]+c >= dis[v]) continue;if (insta[v] || flag) {flag = true; break;}dis[v] = dis[u]+c, DFS(v);}insta[u] = false;
}
int main() {f = fread(BUF, 1, SIZE, stdin);int T; read(T);while (T--) {int n, m; read(n), read(m); init(n);while (m--) {int u, v, c; read(u), read(v), read(c);G[u].push_back(v), E[u].push_back(c);if (c >= 0) G[v].push_back(u), E[v].push_back(c);}for (int i = 1; i <= n; i++) {DFS(i); if (flag) break;}if (flag) printf("YE5\n");else printf("N0\n");}return 0;
}
Network Flow (Dinic) 【模板】網(wǎng)絡(luò)最大流
題目描述
輸入輸出格式
輸出格式：
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 10000
#define MAX_M 100000
#define INF 2147483647
using namespace std;
struct node {int v, c, next;
} E[MAX_M*2+5];
int first[MAX_N+5], cnt;
int n, m, s, t;
int d[MAX_N+5];
void init() {cnt = 0;memset(first, -1, sizeof(first));
}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c;E[cnt].next = first[u];first[u] = cnt++;
}
bool BFS() {memset(d, -1, sizeof(d));queue <int> que;que.push(s);d[s] = 0;while (!que.empty()) {int u = que.front();for (int i = first[u]; i != -1; i = E[i].next) {int v = E[i].v;if (E[i].c && d[v] == -1) {que.push(v);d[v] = d[u]+1;}}que.pop();}return d[t] != -1;
}
int DFS(int u, int flow) {if (u == t) {return flow;}int ret = 0;for (int i = first[u]; i != -1; i = E[i].next) {int v = E[i].v;if (E[i].c && d[u]+1 == d[v]) {int tmp = DFS(v, min(flow, E[i].c));flow -= tmp, E[i].c -= tmp, ret += tmp;E[i^1].c += tmp;if (flow == 0) break;}}if (ret == 0) d[u] = -1;return ret;
}
int main() {init();cin >> n >> m >> s >> t;for (int i = 0; i < m; i++) {int u, v, c;cin >> u >> v >> c;insert(u, v, c);insert(v, u, 0);}int ans = 0;while (BFS()) {ans += DFS(s, INF);}cout << ans;return 0;
}
Minimum Cost Maximum Flow 【模板】最小費用最大流
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 5000
#define MAX_M 50000
#define INF 2147483647
using namespace std;
int n, m, s, t, tot, ans;
int pre[MAX_N+5], match[MAX_N+5], cnt;
struct node {int u, v, c, w, nxt;} E[MAX_M*2+MAX_N*2+5];
void init() {cnt = 0; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c, int w) {E[cnt].u = u, E[cnt].v = v, E[cnt].c = c, E[cnt].w = w, E[cnt].nxt = pre[u], pre[u] = cnt++;}
bool SPFA() {queue <int> que;bool inque[MAX_N+5];int dis[MAX_N+5], pree[MAX_N+5];memset(inque, false, sizeof(inque));for (int i = 1; i <= n; i++) dis[i] = INF;memset(pree, -1, sizeof(pree));dis[s] = 0, que.push(s), inque[s] = true;while (!que.empty()) {int u = que.front();for (int i = pre[u]; i != -1; i = E[i].nxt) {int v = E[i].v;if (E[i].c && dis[u]+E[i].w < dis[v]) {dis[v] = dis[u]+E[i].w, pree[v] = i;if (!inque[v]) que.push(v), inque[v] = true;}}que.pop(), inque[u] = false;}if (dis[t] == INF) return false;int flow = INF;for (int i = pree[t]; i != -1; i = pree[E[i].u]) flow = min(flow, E[i].c);for (int i = pree[t]; i != -1; i = pree[E[i].u]) E[i].c -= flow, E[i^1].c += flow;tot += flow, ans += dis[t]*flow;return true;
}
int main() {scanf("%d%d%d%d", &n, &m, &s, &t);init();for (int i = 0; i < m; i++) {int u, v, c, w;scanf("%d%d%d%d", &u, &v, &c, &w);insert(u, v, c, w), insert(v, u, 0, -w);}while (SPFA()) ;printf("%d %d", tot, ans);return 0;
}
Bipartite Matching 【模板】二分圖匹配
題目描述
輸入輸出格式
輸入輸出樣例
說明
Hungary #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 1000
using namespace std;
int n, m, e, match[MAX_N+5], cnt;
vector <int> G[MAX_N+5];
bool vis[MAX_N+5];
bool DFS(int u) {for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!vis[v]) {vis[v] = true;if (!match[v] || DFS(match[v])) {match[v] = u;return true;}}}return false;
}
int main() {cin >> n >> m >> e;int a, b;for (int i = 0; i < e; i++) {cin >> a >> b;if (a > n || b > m) continue;G[a].push_back(b);}for (int i = 1; i <= n; i++) {memset(vis, false, sizeof(vis));if (DFS(i)) {cnt++;}}cout << cnt;return 0;
}
Dinic #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 2000
#define MAX_M 1000000
#define INF 2147483647
using namespace std;
int n, m, s, t, n1, n2;
int pre[MAX_N+5], tmp[MAX_N+5], d[MAX_N+5], cnt;
struct node {int v, c, nxt;} E[MAX_M*2+MAX_N*2+5];
void init() {cnt = 0; s = 0, t = n; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;}
bool BFS() {memset(d, -1, sizeof(d));queue <int> que;que.push(s), d[s] = 0;while (!que.empty()) {int u = que.front();for (int i = pre[u]; i != -1; i = E[i].nxt) {int v = E[i].v;if (E[i].c && d[v] == -1) {d[v] = d[u]+1;que.push(v);}}que.pop();}return d[t] != -1;
}
int DFS(int u, int flow) {if (u == t) return flow;int ret = 0;for (int &i = pre[u]; i != -1; i = E[i].nxt) {int v = E[i].v;if (E[i].c && d[u]+1 == d[v]) {int tmp = DFS(v, min(flow, E[i].c));E[i].c -= tmp, E[i^1].c += tmp, flow -= tmp, ret += tmp;if (!flow) break;}}if (!ret) d[u] = -1;return ret;
}
int Dinic() {int ret = 0;for (int i = 0; i <= n; i++) tmp[i] = pre[i];while (BFS()) {ret += DFS(s, INF);for (int i = 0; i <= n; i++) pre[i] = tmp[i];}return ret;
}
int main() {scanf("%d%d%d", &n1, &n2, &m); n = n1+n2+1;init();for (int i = 1; i <= n1; i++) insert(s, i, 1), insert(i, s, 0);for (int i = n1+1; i <= n1+n2; i++) insert(i, t, 1), insert(t, i, 0);for (int i = 0; i < m; i++) {int u, v;scanf("%d%d", &u, &v);if (u > n1 || v > n2) continue;insert(u, n1+v, 1), insert(n1+v, u, 0);}printf("%d", Dinic());return 0;
}
Math Theory Gauss Elimination 【模板】高斯消元
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100
#define EXP 1e-7
using namespace std;
typedef double fnt;
int n; vector <fnt> f[MAX_N+5]; fnt ans[MAX_N+5];
bool gauss() {for (int i = 1, tmp; i <= n; i++) {for (tmp = i; tmp <= n; tmp++) if (f[tmp][i] <= -EXP || f[tmp][i] >= EXP) break;if (tmp > n) return false; swap(f[i], f[tmp]);for (int j = 1; j <= n; j++) {fnt div = f[j][i]/f[i][i]; if (j == i) continue;for (int k = i; k <= n+1; k++) f[j][k] -= f[i][k]*div;}}for (int i = 1; i <= n; i++) ans[i] = f[i][n+1]/f[i][i];return true;
}
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {f[i].push_back(0);for (int j = 1; j <= n+1; j++) {fnt x; scanf("%lf", &x);f[i].push_back(x);}}if (gauss()) for (int i = 1; i <= n; i++) printf("%.2lf\n", ans[i]);else printf("No Solution");return 0;
}
Inverse 【模板】乘法逆元
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#define MAX_N 3000000
using namespace std;
typedef long long lnt;
lnt inv[MAX_N+5];
void init(int n, lnt p) {inv[0] = inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (p-p/i*inv[p%i]%p)%p;}
int main() {int n; lnt p; scanf("%d%lld", &n, &p);init(n, p);for (int i = 1; i <= n; i++) printf("%lld\n", inv[i]);return 0;
}
Linear Basis 【模板】線性基
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#define MAX_N 50
using namespace std;
typedef long long lnt;
int n; lnt base[MAX_N+5], pow[MAX_N+5];
int main() {scanf("%d", &n); pow[0] = 1;for (int i = 1; i <= MAX_N; i++) pow[i] = pow[i-1]*2;for (int i = 1; i <= n; i++) {lnt x; scanf("%lld", &x);for (int j = MAX_N; j >= 0; j--) if (pow[j]&x) {if (base[j]) x ^= base[j];else {base[j] = x; break;}}}lnt ans = 0;for (int i = MAX_N; i >= 0; i--) if ((ans^pow[i]) > ans) ans ^= base[i];printf("%lld", ans);return 0;
}
Lucas 【模板】盧卡斯定理
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
#include <iostream>
#include <cstdio>
#define MAX_P 100000
using namespace std;
typedef long long lnt;
lnt f[MAX_P+5] = {1};
void init(lnt p) {for (int i = 1; i <= MAX_P; i++) f[i] = f[i-1]*i%p;}
lnt FLT(lnt x, lnt p) {lnt ret = 1; x %= p;for (int k = p-2; k; k >>= 1) ret = k%2 ? ret*x%p : ret, x = x*x%p;return ret;
}
lnt lucas(lnt n, lnt m, lnt p) {return m ? (n%p >= m%p ? f[n%p]*FLT(f[m%p]*f[n%p-m%p], p)*lucas(n/p, m/p, p)%p : 0) : 1;}
int main() {int T; scanf("%d", &T);while (T--) {lnt n, m, p; scanf("%lld%lld%lld", &n, &m, &p);init(p), printf("%lld\n", lucas(n+m, min(n, m), p)%p);}return 0;
}
Matrix Fast Power 【模板】矩陣快速冪
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100
#define MOD 1000000007
using namespace std;
int n;
struct Matrix {long long ele[MAX_N][MAX_N];inline Matrix operator * (const Matrix &x) const {Matrix ret;memset(ret.ele, 0, sizeof(ret.ele));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++)ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j])%MOD;return ret;}
};
Matrix Power(Matrix a, long long k) {if (k == 1) return a;Matrix ret = Power(a, k/2);if (k%2) return a*ret*ret;return ret*ret;
}
int main() {long long k;Matrix a;cin >> n >> k;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> a.ele[i][j];a = Power(a, k);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)cout << a.ele[i][j] << " ";cout << endl;}return 0;
}
Prime Sieve 【模板】線性篩素數(shù)
題目描述
輸入輸出格式
輸入輸出樣例
說明
樣例說明：
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 10000000
using namespace std;
int n, m;
bool IsPrime[MAX_N+5];
int pri[MAX_N+5], cnt = 0;
void FindPrime() {IsPrime[0] = IsPrime[1] = false;for (int i = 2; i <= n; i++) {if (IsPrime) {pri[cnt++] = i;}for (int j = 0; j < cnt; j++) {if (i*pri[j] > n) break;IsPrime[i*pri[j]] = false;if (i%pri[j] == 0) break;}}
}
int main() {memset(IsPrime, true, sizeof(IsPrime));cin >> n;FindPrime();cin >> m;for (int i = 0; i < m; i++) {int x;cin >> x;if (IsPrime[x]) {cout << "Yes" << endl;} else {cout << "No" << endl;}}return 0;
}
Trigeminal Search 【模板】三分法
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
double s, t;
double a[14];
double calc(double x) {double tot = 0, tmp = 1;for (int i = 0; i <= n; i++) {tot += tmp*a[i];tmp *= x;}return tot;
}
void f(double l, double r) {if (abs(r-l) <= 0.000001) {printf("%.5f", l);return;}double ml = (2*l+r)/3, mr = (l+2*r)/3;if (calc(ml) > calc(mr)) {f(l, mr);} else {f(ml, r);}
}
int main() {cin >> n >> s >> t;for (int i = n; i >= 0; i--) {cin >> a[i];}f(s, t);return 0;
}
Data Structure Heap 【模板】堆
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
using namespace std;
int n, heap[1000000+5], size = 0;
void insert(int x) {size++;heap[size] = x;int current = size;int father = current/2;while (father > 0 && heap[father] > heap[current]) {swap(heap[father], heap[current]);current = father;father = current/2;}
}
void pop() {heap[1] = heap[size];size--;int current = 1;int child = current*2;if (child < size && heap[child] > heap[child+1]) child++;while (child <= size && heap[current] > heap[child]) {swap(heap[current], heap[child]);current = child;child = 2*current;if (child < size && heap[child] > heap[child+1]) child++;}
}
int main() {cin >> n;for (int i = 0; i < n; i++) {int f;cin >> f;if (f == 1) {int x;cin >> x;insert(x);} else if (f == 2) {cout << heap[1] << endl;} else {pop();}}return 0;
}
Mergeable Heap 【模板】左偏樹（可并堆）
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct node {int val, dis, ls, rs;} heap[MAX_N+5];
int n, m, fa[MAX_N+5];
int getf(int x) {return fa[x] == x ? fa[x] : getf(fa[x]);}
int merge(int a, int b) {if (!a || !b) return a^b;if (heap[a].val > heap[b].val || (heap[a].val == heap[b].val && a > b)) swap(a, b);heap[a].rs = merge(heap[a].rs, b), fa[heap[a].rs] = a;if (heap[heap[a].rs].dis > heap[heap[a].ls].dis) swap(heap[a].ls, heap[a].rs);heap[a].dis = heap[a].rs == 0 ? 0 : heap[heap[a].rs].dis+1; return a;
}
int pop(int a) {int l = heap[a].ls, r = heap[a].rs;heap[a].ls = heap[a].rs = heap[a].val = 0, fa[l] = l, fa[r] = r;return merge(l, r);
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &heap[i].val), fa[i] = i;while (m--) {int opt; scanf("%d", &opt);if (opt == 1) {int x, y; scanf("%d%d", &x, &y), x = getf(x), y = getf(y);if (heap[x].val && heap[y].val && x != y) merge(x, y);}if (opt == 2) {int x; scanf("%d", &x), x = getf(x);if (!heap[x].val) printf("-1\n");else printf("%d\n", heap[x].val), pop(x);}}return 0;
}
Binary Indexed Tree 1 【模板】樹狀數(shù)組 1
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {return x&(-x);
}
void modify(int pos, int x) {while (pos <= n) {tree[pos] += x;pos += lowbit(pos);}
}
long long query(int t) {long long tot = 0;while (t > 0) {tot += tree[t];t -= lowbit(t);}return tot;
}
int main() {memset(tree, 0, sizeof(tree));cin >> n >> m;for (int i = 1; i <= n; i++) {int tmp;cin >> tmp;modify(i, tmp);}for (int i = 0; i < m; i++) {int f, a, b;cin >> f >> a >> b;if (f == 1) {modify(a, b);} else {cout << query(b)-query(a-1) << endl;}}return 0;
}
2 【模板】樹狀數(shù)組 2
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {return x&(-x);
}
void modify(int pos, int x) {while (pos <= n) {tree[pos] += x;pos += lowbit(pos);}
}
long long query(int pos) {long long tot = 0;while (pos > 0) {tot += tree[pos];pos -= lowbit(pos);}return tot;
}
int main() {memset(tree, 0, sizeof(tree));cin >> n >> m;for (int i = 1; i <= n; i++) {int x;cin >> x;modify(i, x);modify(i+1, -x);}for (int i = 0; i < m; i++) {int f;cin >> f;if (f == 1) {int l, r, x;cin >> l >> r >> x;modify(l, x);modify(r+1, -x);} else {int x;cin >> x;cout << query(x) << endl;}}return 0;
}
Segment Tree 1 【模板】線段樹 1
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
using namespace std;
int n, k;
long long tree[MAX_N*4+50], tag[MAX_N*4+50];
void updata(int v) {tree[v] = tree[v*2]+tree[v*2+1];
}
void downtag(int v, int s, int t) {tag[v*2] += tag[v];tag[v*2+1] += tag[v];int m = (s+t)/2;tree[v*2] += tag[v]*(m-s+1);tree[v*2+1] += tag[v]*(t-m);tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {if (s >= l && t <= r) {tree[v] += x*(t-s+1);tag[v] += x;return;}int m = (s+t)/2;downtag(v, s, t);if (l <= m) {modify(v*2, s, m, l, r, x);}if (r >= m+1) {modify(v*2+1, m+1, t, l, r, x);}updata(v);
}
void build(int v, int s, int t) {if (s == t) {cin >> tree[v];return;}int m = (s+t)/2;build(v*2, s, m);build(v*2+1, m+1, t);updata(v);
}
long long query(int v, int s, int t, int l, int r) {if (s >= l && t <= r) {return tree[v];}int m = (s+t)/2;downtag(v, s, t);long long ret = 0;if (l <= m) {ret += query(v*2, s, m, l, r);}if (r >= m+1) {ret += query(v*2+1, m+1, t, l, r);}updata(v);return ret;
}
int main() {cin >> n >> k;build(1, 1, n);for (int i = 0; i < k; i++) {int f, l, r, x;cin >> f;if (f == 1) {cin >> l >> r >> x;modify(1, 1, n, l, r, x);} else {cin >> l >> r;cout << query(1, 1, n, l, r) << endl;}}return 0;
}
2 【模板】線段樹 2
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
#define ll long long
using namespace std;
int n, m;
ll p;
ll tree[MAX_N*4+5], mul[MAX_N*4+5], add[MAX_N*4+5];
void updata(int v) {tree[v] = (tree[v*2]+tree[v*2+1])%p;
}
void downtag(int v, int s, int t, int mid) {if (mul[v] == 1 && add[v] == 0) return;mul[v*2] = mul[v*2]*mul[v]%p;add[v*2] = (add[v*2]*mul[v]%p+add[v])%p;tree[v*2] = (tree[v*2]*mul[v]%p+add[v]*(ll)(mid-s+1)%p)%p;mul[v*2+1] = mul[v*2+1]*mul[v]%p;add[v*2+1] = (add[v*2+1]*mul[v]%p+add[v])%p;tree[v*2+1] = (tree[v*2+1]*mul[v]%p+add[v]*(ll)(t-mid)%p)%p;mul[v] = 1;add[v] = 0;return;
}
void create(int v, int s, int t) {mul[v] = 1;add[v] = 0;if (s == t) {cin >> tree[v];tree[v] %= p;return;}int mid = (s+t)/2;create(v*2, s, mid);create(v*2+1, mid+1, t);updata(v);
}
void modify1(int v, int s, int t, int l, int r, int x) {if (s >= l && t <= r) {add[v] = (add[v]+(ll)x)%p;tree[v] = (tree[v]+(ll)x*(ll)(t-s+1)%p)%p;return;}int mid = (s+t)/2;downtag(v, s, t, mid);if (l <= mid) {modify1(v*2, s, mid, l, r, x);}if (r >= mid+1) {modify1(v*2+1, mid+1, t, l, r, x);}updata(v);
}
void modify2(int v, int s, int t, int l, int r, int x) {if (s >= l && t <= r) {mul[v] = mul[v]*(ll)x%p;add[v] = add[v]*(ll)x%p;tree[v] = tree[v]*(ll)x%p;return; }int mid = (s+t)/2;downtag(v, s, t, mid);if (l <= mid) {modify2(v*2, s, mid, l, r, x);}if (r >= mid+1) {modify2(v*2+1, mid+1, t, l, r, x);}updata(v);
}
ll query(int v, int s, int t, int l, int r) {if (s >= l && t <= r) {return tree[v];}int mid = (s+t)/2;ll ret = 0;downtag(v, s, t, mid);if (l <= mid) {ret = (ret+query(v*2, s, mid, l, r))%p;}if (r >= mid+1) {ret = (ret+query(v*2+1, mid+1, t, l, r))%p;}updata(v);return ret;
}
int main() {cin >> n >> m >> p;create(1, 1, n);for (int i = 0; i < m; i++) {int f;cin >> f;if (f == 1) {int l, r, x;cin >> l >> r >> x;modify2(1, 1, n, l, r, x%p);} else if (f == 2) {int l, r, x;cin >> l >> r >> x;modify1(1, 1, n, l, r, x%p);} else {int l, r;cin >> l >> r;cout << query(1, 1, n, l, r) << endl;}}return 0;
}
Sparse Table 【模板】ST表
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX_N 100000
using namespace std;
int n, m, num[MAX_N+5], mx[MAX_N+5][20];
void setTable() {for (int i = 1; i <= n; i++) mx[i][0] = num[i];for (int j = 1; (1<<j) <= n; j++)for (int i = 1; i+(1<<j)-1 <= n; i++)mx[i][j] = max(mx[i][j-1], mx[i+(1<<j-1)][j-1]);
}
int query(int l, int r) {int range = (int)(log(r-l+1)/log(2));return max(mx[l][range], mx[r-(1<<range)+1][range]);
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &num[i]);setTable();while (m--) {int l, r; scanf("%d%d", &l, &r);printf("%d\n", query(l, r));}return 0;
}
Chairman Tree 【模板】可持久化線段樹/主席樹
題目背景
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 200000
using namespace std;
int n, m, num[MAX_N+5], hash[MAX_N+5], tot, root[MAX_N+5], cnt;
struct pre {int id, val;} p[MAX_N+5];
bool cmp (const pre &a, const pre &b) {return a.val < b.val;}
struct node {int ls, rs, val;} tr[MAX_N*50];
void updata(int v) {tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;}
void build(int v, int s, int t) {if (s == t) return; int mid = s+t>>1;tr[v].ls = ++cnt, tr[v].rs = ++cnt;build(tr[v].ls, s, mid), build(tr[v].rs, mid+1, t);
}
void modify(int v, int o, int s, int t, int x) {tr[v] = tr[o]; if (s == t) {tr[v].val++; return;}int mid = s+t>>1;if (x <= mid) modify(tr[v].ls = ++cnt, tr[o].ls, s, mid, x);else modify(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, x);updata(v);
}
int query(int v1, int v2, int s, int t, int k) {if (s == t) return s;int mid = s+t>>1, tmp = tr[tr[v2].ls].val-tr[tr[v1].ls].val;if (k <= tmp) return query(tr[v1].ls, tr[v2].ls, s, mid, k);else return query(tr[v1].rs, tr[v2].rs, mid+1, t, k-tmp);
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) p[i].id = i, scanf("%d", &p[i].val);sort(p+1, p+n+1, cmp);for (int i = 1; i <= n; i++) {if (p[i].val != p[i-1].val || i == 1) hash[++tot] = p[i].val; num[p[i].id] = tot;}root[0] = ++cnt, build(root[0], 1, tot);for (int i = 1; i <= n; i++) root[i] = ++cnt, modify(root[i], root[i-1], 1, tot, num[i]);while (m--) {int l, r, k; scanf("%d%d%d", &l, &r, &k);printf("%d\n", hash[query(root[l-1], root[r], 1, tot, k)]);}return 0;
}
Treap 【模板】普通平衡樹
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX_N 100000
using namespace std;
struct TNode {TNode* s[2];int val, k, size;TNode() {}TNode(int _val, TNode* _s) {val = _val, s[0] = s[1] = _s, k = rand(), size = 1;}void updata() {size = s[0]->size+s[1]->size+1;}
} nil, tr[MAX_N+5], *null, *root, *cnt;
typedef TNode* P_TNode;
void init() {srand(19260817);nil = TNode(0, NULL), null = &nil;null->s[0] = null->s[1] = null, null->size = 0;cnt = tr, root = null;
}
P_TNode newnode(int val) {*cnt = TNode(val, null);return cnt++;
}
P_TNode merge(P_TNode a, P_TNode b) {if (a == null) return b;if (b == null) return a;if (a->k > b->k) {a->s[1] = merge(a->s[1], b), a->updata(); return a;}if (a->k <= b->k) {b->s[0] = merge(a, b->s[0]), b->updata(); return b;}
}
void split(P_TNode v, int val, P_TNode &ls, P_TNode &rs) {if (v == null) {ls = rs = null; return;}if (val < v->val) {rs = v; split(rs->s[0], val, ls, rs->s[0]);}if (val >= v->val) {ls = v; split(ls->s[1], val, ls->s[1], rs);}v->updata();
}
void insert(int val) {P_TNode ls, rs;split(root, val, ls, rs);root = merge(merge(ls, newnode(val)), rs);
}
void remove(int val) {P_TNode ls, mids, rs;split(root, val-1, ls, rs);split(rs, val, mids, rs);root = merge(ls, merge(merge(mids->s[0], mids->s[1]), rs));
}
int get_rank(int val) {P_TNode ls, rs;split(root, val-1, ls, rs);int ret = ls->size+1;root = merge(ls, rs);return ret;
}
int get_kth(P_TNode v, int k) {if (k <= v->s[0]->size) return get_kth(v->s[0], k);if (k > v->s[0]->size+1) return get_kth(v->s[1], k-v->s[0]->size-1);return v->val;
}
int get_nearest(P_TNode v, int sn) {while (v->s[sn] != null) v = v->s[sn];return v->val;
}
int predecessor(int val) {P_TNode ls, rs;split(root, val-1, ls, rs);int ret = get_nearest(ls, 1);root = merge(ls, rs);return ret;
}
int successor(int val) {P_TNode ls, rs;split(root, val, ls, rs);int ret = get_nearest(rs, 0);root = merge(ls, rs);return ret;
}
int main() {init();int n, opt, x;scanf("%d", &n);while (n--) {scanf("%d%d", &opt, &x);if (opt == 1) insert(x);if (opt == 2) remove(x);if (opt == 3) printf("%d\n", get_rank(x));if (opt == 4) printf("%d\n", get_kth(root, x));if (opt == 5) printf("%d\n", predecessor(x));if (opt == 6) printf("%d\n", successor(x));}return 0;
}
Splay Normal 【模板】普通平衡樹
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#define MAX_N 100000
#define INF 2147483647
using namespace std;
struct SplayNode {SplayNode *s[2], *fa;int val, w, size;void updata();
} nil;
SplayNode* null = &nil;
struct Splay {SplayNode tr[MAX_N+5];SplayNode* root;int cnt;Splay();SplayNode* newnode(int _val);void rotate(SplayNode* v, bool sn);void rotate(SplayNode* &v);void splay(SplayNode* now, SplayNode* &to);SplayNode* predecessor(int _val);SplayNode* successor(int _val);void insert(int _val);void remove(int _val);int get_rank(int _val);int get_kth(int rank);
} BBST;
void SplayNode::updata() {if (!s[1]) return;size = s[0]->size+s[1]->size+w;
}
Splay::Splay() {cnt = 0;root = newnode(-INF);root->s[1] = newnode(INF);root->s[1]->fa = root;
}
SplayNode* Splay::newnode(int _val) {cnt++;tr[cnt].s[0] = null, tr[cnt].s[1] = null, tr[cnt].fa = null;tr[cnt].val = _val, tr[cnt].w = tr[cnt].size = 1;return &tr[cnt];
}
void Splay::rotate(SplayNode* v, bool sn) {SplayNode* tmp = v->s[sn^1];v->s[sn^1] = tmp->s[sn];tmp->s[sn] = v;v->s[sn^1]->fa = v;tmp->fa = v->fa;if (tmp->fa != null) tmp->fa->s[tmp->fa->s[1] == v] = tmp;else root = tmp;v->fa = tmp;v->updata();tmp->updata();
}
void Splay::rotate(SplayNode* &v) {bool sn = (v->fa->s[0] == v) ? 1 : 0;rotate(v->fa, sn);
}
void Splay::splay(SplayNode* now, SplayNode* &to) {while (now != to) {if (now->fa == to) {rotate(now);} else {if ((now->fa->s[0] == now) == (now->fa->fa->s[0] == now->fa)) rotate(now->fa);else rotate(now);rotate(now);}}
}
SplayNode* Splay::predecessor(int _val) {SplayNode* now = root;SplayNode* save = root;int maxv = -INF;for (;;) {if (now->val < _val && maxv < _val) maxv = now->val, save = now;SplayNode* nxt = now->s[(_val <= now->val) ? 0 : 1];if (nxt == null) return save;now = nxt;}
}
SplayNode* Splay::successor(int _val) {SplayNode* now = root;SplayNode* save = root;int minv = INF;for (;;) {if (now->val > _val && minv > _val) minv = now->val, save = now;SplayNode* nxt = now->s[(_val < now->val) ? 0 : 1];if (nxt == null) return save;now = nxt;}
}
void Splay::insert(int _val) {SplayNode* pre = predecessor(_val);SplayNode* suc = successor(_val);splay(pre, root), splay(suc, root->s[1]);if (root->s[1]->s[0] == null) {root->s[1]->s[0] = newnode(_val);root->s[1]->s[0]->fa = root->s[1];} else {root->s[1]->s[0]->w++;root->s[1]->s[0]->size++;}root->s[1]->updata();root->updata();
}
void Splay::remove(int _val) {SplayNode* pre = predecessor(_val);SplayNode* suc = successor(_val);splay(pre, root), splay(suc, root->s[1]);root->s[1]->s[0]->w--, root->s[1]->s[0]->size--;if (!root->s[1]->s[0]->w) root->s[1]->s[0] = null;root->s[1]->updata();root->updata();
}
int Splay::get_rank(int _val) {SplayNode* pre = predecessor(_val);SplayNode* suc = successor(_val);splay(pre, root), splay(suc, root->s[1]);return root->size-root->s[1]->size;
}
int Splay::get_kth(int rank) {rank++;SplayNode* now = root;for (;;) {if (rank <= now->s[0]->size) {now = now->s[0];} else {rank -= now->s[0]->size;if (rank <= now->w) return now->val;rank -= now->w;now = now->s[1];}}
}
int main() {int n, opt, x;scanf("%d", &n);while (n--) {scanf("%d%d", &opt, &x);if (opt == 1) BBST.insert(x);if (opt == 2) BBST.remove(x);if (opt == 3) printf("%d\n", BBST.get_rank(x));if (opt == 4) printf("%d\n", BBST.get_kth(x));if (opt == 5) printf("%d\n", BBST.predecessor(x)->val);if (opt == 6) printf("%d\n", BBST.successor(x)->val);}return 0;
}
Reverse 【模板】文藝平衡樹
題目背景
題目描述
輸入輸出格式
輸出格式：
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct SplayNode {SplayNode *s[2], *fa; int val, size; bool rev; void updata(); void downtag();};
struct SplayTree {SplayNode* root; SplayNode* newnode(int _val); SplayNode* build(SplayNode* v, int l, int r);void rotate(SplayNode* v, bool sn); void splay(SplayNode* now, SplayNode* to);SplayNode* find_kth(SplayNode* v, int k); void reverse(int l, int r); void output(SplayNode* v, int n);
} BBST;
void SplayNode::updata() {size = (s[0] == NULL ? 0 : s[0]->size)+(s[1] == NULL ? 0 : s[1]->size)+1;}
void SplayNode::downtag() {if (!rev) return; rev = false, swap(s[0], s[1]);if (s[0]) s[0]->rev ^= 1; if (s[1]) s[1]->rev ^= 1;
}
SplayNode* SplayTree::newnode(int _val) {SplayNode* v = new SplayNode;v->s[0] = v->s[1] = v->fa = NULL;v->val = _val, v->size = 1, v->rev = false;return v;
}
SplayNode* SplayTree::build(SplayNode* fa, int l, int r) {if (l > r) return NULL; int mid = l+r>>1, val = mid-1;SplayNode* v = newnode(val); v->fa = fa;v->s[0] = build(v, l, mid-1), v->s[1] = build(v, mid+1, r);v->updata(); return v;
}
void SplayTree::rotate(SplayNode* v, bool sn) {SplayNode* tmp = v->fa;tmp->s[sn^1] = v->s[sn], v->fa = tmp->fa;if (v->s[sn]) v->s[sn]->fa = tmp;if (tmp->fa != NULL) tmp->fa->s[tmp == tmp->fa->s[1]] = v;v->s[sn] = tmp, tmp->fa = v, tmp->updata(), v->updata();
}
void SplayTree::splay(SplayNode* now, SplayNode* to) {while (now->fa != to)if (now->fa->s[0] == now) {if (now->fa->fa != to && now->fa == now->fa->fa->s[0]) rotate(now->fa, 1);rotate(now, 1);} else {if (now->fa->fa != to && now->fa == now->fa->fa->s[1]) rotate(now->fa, 0);rotate(now, 0);}if (to == NULL) root = now;
}
SplayNode* SplayTree::find_kth(SplayNode* v, int k) {v->downtag(); int size = v->s[0] == NULL ? 0 : v->s[0]->size;if (size+1 == k) return v;if (size >= k) return find_kth(v->s[0], k);return find_kth(v->s[1], k-size-1);
}
void SplayTree::reverse(int l, int r) {SplayNode *nl = find_kth(root, l), *nr = find_kth(root, r+2);splay(nl, NULL), splay(nr, root); nr->s[0]->rev ^= 1;
}
void SplayTree::output(SplayNode* v, int n) {if (v == NULL) return;v->downtag(), output(v->s[0], n);if (v->val >= 1 && v->val <= n) printf("%d ", v->val);output(v->s[1], n);
}
int main() {int n, m; scanf("%d%d", &n, &m); BBST.root = BBST.build(NULL, 1, n+2);for (int i = 1, l, r; i <= m; i++) scanf("%d%d", &l, &r), BBST.reverse(l, r);BBST.output(BBST.root, n);return 0;
}
Tree Chain Division 【模板】樹鏈剖分
題目描述
輸入輸出格式
輸入輸出樣例
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, r, p, ind;
vector <int> G[MAX_N+5];
int c[MAX_N+5];
int dep[MAX_N+5], fa[MAX_N+5], size[MAX_N+5], son[MAX_N+5];
int top[MAX_N+5], dfn[MAX_N+5], last[MAX_N+5];
int seg[(MAX_N<<2)+5], tag[(MAX_N<<2)+5];
void DFS1(int u) {size[u] = 1;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (v == fa[u]) continue;dep[v] = dep[u]+1;fa[v] = u;DFS1(v);size[u] += size[v];if (!son[u] || size[son[u]] < size[v]) son[u] = v;}
}
void DFS2(int u, int tp) {top[u] = tp, dfn[u] = ++ind;if (son[u]) DFS2(son[u], tp);for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (v == fa[u] || v == son[u]) continue;DFS2(v, v);}last[u] = ind;
}
void updata(int v) {seg[v] = (seg[v<<1]+seg[v<<1|1])%p;}
void downtag(int v, int s, int t) {if (!tag[v]) return;int mid = s+t>>1;seg[v<<1] = (seg[v<<1]+tag[v]*(mid-s+1))%p;seg[v<<1|1] = (seg[v<<1|1]+tag[v]*(t-mid))%p;tag[v<<1] = (tag[v<<1]+tag[v])%p;tag[v<<1|1] = (tag[v<<1|1]+tag[v])%p;tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {if (s >= l && t <= r) {seg[v] = (seg[v]+x*(t-s+1))%p, tag[v] = (tag[v]+x)%p; return;}downtag(v, s, t);int mid = s+t>>1;if (l <= mid) modify(v<<1, s, mid, l, r, x);if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);updata(v);
}
int query(int v, int s, int t, int l, int r) {if (s >= l && t <= r) return seg[v];downtag(v, s, t);int mid = s+t>>1, ret = 0;if (l <= mid) ret = (ret+query(v<<1, s, mid, l, r))%p;if (r >= mid+1) ret = (ret+query(v<<1|1, mid+1, t, l, r))%p;updata(v);return ret;
}
void solve1(int x, int y, int z) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);modify(1, 1, n, dfn[top[x]], dfn[x], z);x = fa[top[x]];}modify(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z);
}
int solve2(int x, int y) {int ret = 0;while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);ret = (ret+query(1, 1, n, dfn[top[x]], dfn[x]))%p;x = fa[top[x]];}ret = (ret+query(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%p;return ret;
}
void solve3(int x, int z) {modify(1, 1, n, dfn[x], last[x], z);}
int solve4(int x) {return query(1, 1, n, dfn[x], last[x]);}
int main() {scanf("%d%d%d%d", &n, &m, &r, &p);for (int i = 1; i <= n; i++) scanf("%d", &c[i]);for (int i = 1; i < n; i++) {int u, v;scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}DFS1(r);DFS2(r, r);for (int i = 1; i <= n; i++) modify(1, 1, n, dfn[i], dfn[i], c[i]);while (m--) {int opt;scanf("%d", &opt);if (opt == 1) {int x, y, z;scanf("%d%d%d", &x, &y, &z);solve1(x, y, z);}if (opt == 2) {int x, y;scanf("%d%d", &x, &y);printf("%d\n", solve2(x, y));}if (opt == 3) {int x, z;scanf("%d%d", &x, &z);solve3(x, z);}if (opt == 4) {int x;scanf("%d", &x);printf("%d\n", solve4(x));}}return 0;
}
String KMP 【模板】KMP字符串匹配
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <string>
#define MAX_M 1000
using namespace std;
int next[MAX_M];
void CalcNext(string& s) {int m = s.length();int begin = 1, matched = 0;while (begin+matched < m) {if (s[begin+matched] == s[matched]) {matched++;next[begin+matched-1] = matched;} else {if (matched == 0) {begin++;} else {begin += matched-next[matched-1];matched = next[matched-1];}}}
}
void KMP(string& T, string& P) {int n = T.length(), m = P.length();int begin = 0, matched = 0;while (begin <= n-m) {if (matched < m && T[begin+matched] == P[matched]) {matched++;if (matched == m) {cout << begin+1 << endl;}} else {if (matched == 0) {begin++;} else {begin += matched-next[matched-1];matched = next[matched-1];}}}
}
int main() {string s1, s2;cin >> s1 >> s2;CalcNext(s2);KMP(s1, s2);for (int i = 0; i < s2.length(); i++) {cout << next[i] << " ";}return 0;
}
Manacher 【模板】manacher算法
題目描述
輸入輸出格式
輸出格式：
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_L 11000000
using namespace std;
char s[MAX_L*2+5];
int f[MAX_L*2+5];
int manacher (char* s0) {int len = strlen(s0);for (int i = 0; i < len; i++) s[i*2+1] = '#', s[i*2+2] = s0[i];s[len = len*2+1] = '#';int pos = 0, r = 0, ret = 0;for (int i = 1; i <= len; i++) {f[i] = (i < r) ? min(f[2*pos-i], r-i) : 1;while (i-f[i] >= 1 && i+f[i] <= len && s[i-f[i]] == s[i+f[i]]) f[i]++;if (i+f[i] > r) pos = i, r = i+f[i];ret = max(ret, f[i]-1);}return ret;
}
int main() {char s0[MAX_L+5]; scanf("%s", s0);printf("%d\n", manacher(s0));return 0;
}
Aho-Corasick Automation 【模板】AC自動機
題目描述
輸入輸出格式
輸入輸出樣例
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define DICNUM 26
#define MAX_LETTER 10500
#define MAX_LENGTH 1000000
using namespace std;
char P[155][75], T[MAX_LENGTH+5];
int root = 1, cnt, trie[MAX_LETTER+5][DICNUM], fail[MAX_LETTER+5], end[MAX_LETTER+5], tot[155];
void init() {memset(P, 0, sizeof(P)), memset(T, 0, sizeof(T)), memset(tot, 0, sizeof(tot));for (int i = 1; i <= cnt; i++) memset(trie[i], 0, sizeof(trie[i])), fail[i] = end[i] = 0; cnt = 1;
}
void insert(int id, char s[]) {int cur = 1, len = strlen(s);for (int i = 0; i < len; cur = trie[cur][s[i++]-'a'])if (!trie[cur][s[i]-'a']) trie[cur][s[i]-'a'] = ++cnt;end[cur] = id;
}
void SetFail() {queue <int> que; que.push(root);while (!que.empty()) {int u = que.front(); que.pop();for (int i = 0; i < DICNUM; i++)if (trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], que.push(trie[u][i]);else trie[u][i] = trie[fail[u]][i];}
}
void query() {int cur = root, index, len = strlen(T);for (int i = 0; i < len; i++) {index = T[i]-'a';while (!trie[cur][index]) cur = fail[cur];cur = trie[cur][index];for (int j = cur; j; j = fail[j]) tot[end[j]]++;}
}
int main() {int n;for (int i = 0; i < DICNUM; i++) trie[0][i] = root;while (scanf("%d", &n) && n) {init();for (int i = 1; i <= n; i++) scanf("%s", P[i]), insert(i, P[i]);SetFail(), scanf("%s", T), query();int ans = 0;for (int i = 1; i <= n; i++) ans = max(ans, tot[i]);printf("%d\n", ans);for (int i = 1; i <= n; i++) if (tot[i] == ans) printf("%s\n", P[i]);}return 0;
}
Hash Table 【模板】字符串哈希
題目描述
輸入輸出格式
輸入輸出樣例
說明
樣例說明：
#include <iostream>
#include <cstdio>
#include <string>
#define size 15000
using namespace std;
int n, cnt = 0;
string tmp;
string hash[size];
int calc(string& index) {int ret = 0;for (int i = 0; i < index.length(); i++) {ret = (ret*256+index[i]+128)%size;}return ret;
}
bool search(string& index, int& pos) {pos = calc(index);while (hash[pos] != "" && hash[pos] != index) {pos = (pos+1)%size;}if (hash[pos] == index) {return true;} else {return false;}
}
int insert(string& index) {int pos;if (search(index, pos)) {return 0;} else {hash[pos] = index;return 1;}
}
int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> tmp;cnt += insert(tmp);}cout << cnt << endl;return 0;
}
Suffix Array 【模板】后綴排序
題目背景
題目描述
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
int n; char ch[MAX_N+5];
int s[MAX_N+5], sa[MAX_N+5], tx[MAX_N+5], ty[MAX_N+5], cnt[MAX_N+5], rank[MAX_N+5];
int trans(char c) {if (c >= '0' && c <= '9') return c-'0'+1;if (c >= 'A' && c <= 'Z') return c-'A'+11;if (c >= 'a' && c <= 'z') return c-'a'+37;
}
void getSA() {int *x = tx, *y = ty; int DICNUM = 63;for (int i = 1; i <= n; i++) cnt[x[i] = s[i]]++;for (int i = 2; i <= DICNUM; i++) cnt[i] += cnt[i-1];for (int i = n; i; i--) sa[cnt[x[i]]--] = i;for (int h = 1; h <= n; h <<= 1) {int c = 0;for (int i = n-h+1; i <= n; i++) y[++c] = i;for (int i = 1; i <= n; i++) if (sa[i] > h) y[++c] = sa[i]-h;memset(cnt, 0, sizeof(cnt));for (int i = 1; i <= n; i++) cnt[x[i]]++;for (int i = 2; i <= DICNUM; i++) cnt[i] += cnt[i-1];for (int i = n; i; i--) sa[cnt[x[y[i]]]--] = y[i];swap(x, y), c = 0, x[sa[1]] = ++c;for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+h] == y[sa[i-1]+h]) ? c : ++c;DICNUM = c; if (c == n) break;}
}
int main() {scanf("%s", ch); n = strlen(ch);for (int i = 0; i < n; i++) s[i+1] = trans(ch[i]);getSA();printf("%d", sa[1]); for (int i = 2; i <= n; i++) printf(" %d", sa[i]);return 0;
}
Suffix Automation 【模板】后綴自動機
題目描述
輸入輸出格式
輸入輸出樣例
說明
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
typedef long long lnt;
struct node {int ch[26], par, len;} SAM[MAX_N*2+500];
int sz, root, last, cnt[MAX_N*2+500], dfn[MAX_N*2+500], f[MAX_N*2+500];
int newnode(int _len) {SAM[++sz].len = _len; return sz;}
void init() {sz = 0, root = last = newnode(0);}
void extend(int c) {int p = last, np = newnode(SAM[p].len+1); last = np, f[np] = 1;for (; p && !SAM[p].ch[c]; p = SAM[p].par) SAM[p].ch[c] = np;if (!p) SAM[np].par = root;else {int q = SAM[p].ch[c];if (SAM[q].len == SAM[p].len+1) SAM[np].par = q;else {int nq = newnode(SAM[p].len+1);memcpy(SAM[nq].ch, SAM[q].ch, sizeof(SAM[q].ch));SAM[nq].par = SAM[q].par, SAM[q].par = SAM[np].par = nq;for (; p && SAM[p].ch[c] == q; p = SAM[p].par) SAM[p].ch[c] = nq;}}
}
int main() {char s[MAX_N+5]; init(), scanf("%s", s); int l = strlen(s);for (int i = 0; i < l; i++) extend(s[i]-'a');for (int i = 1; i <= sz; i++) cnt[SAM[i].len]++;for (int i = 1; i <= l; i++) cnt[i] += cnt[i-1];for (int i = 1; i <= sz; i++) dfn[cnt[SAM[i].len]--] = i;for (int i = 1; i <= sz; i++) cout << dfn[i] << " "; cout << endl;lnt ans = 0;for (int i = sz; i >= 1; i--) {int p = dfn[i]; f[SAM[p].par] += f[p];if (f[p] > 1) ans = max(ans, (lnt)f[p]*SAM[p].len);}printf("%lld", ans);return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/AzraelDeath/p/7602748.html
總結(jié)
以上是生活随笔 為你收集整理的洛谷模板汇总 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
