算法模板
v1.1.1.20240115：之前的历史版本已经不可寻，创建了第一份算法模板。
v1.2.1.20240116：删除“编译”-“手动开栈”与“编译”-“手动开O优化”；将“编译”-“CF模板”中的第20行代码cin>>T;注释；删除“读写”及其目录下的内容；删除“图论”-“欧拉图”-“混合图”；删除“图论”-“可达性统计”；删除“数据类型”-“高精类”。
编译
CF模板
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
图论
存储
namespace _Graph
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
struct Edge
{
int u, v, w;
Edge(int _u = 0, int _v = 0, int _w = 0)
{
u = _u, v = _v, w = _w;
}
int node(int x)const
{
return x == u ? v : u;
}
};
/*====================*/
int n, m;
Edge edge[M];
vector<int>G[N];
/*====================*/
void Init(void)
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
G[i].clear();
}
for (int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
edge[i] = Edge(u, v, w);
G[u].push_back(i); G[v].push_back(i);
}
}
}
2-SAT
namespace _TwoSAT
{
using namespace _SCC;
void Init(void)
{
for (int i = 1; i <= n; ++i)
{
int u = idx[i][1], v = idx[i][0];
if (belong[u] == belong[v])
{
cout << "IMPOSSIBLE" << endl; return;
}
}
cout << "POSSIBLE" << endl;
for (int i = 1; i <= n; ++i)
{
int u = idx[i][1], v = idx[i][0];
cout << ((belong[u] < belong[v]) ? 1 : 0) << " ";
}
cout << endl;
}
}
欧拉图
无向图
namespace _Euler
{
/*
默认连通图，-1不存在，0存在欧拉路径，1存在欧拉回路
*/
const int N = 1e5 + 10;
/*====================*/
int degree[N];
/*====================*/
bool Init(void)
{
for (int i = 1; i <= n; ++i)
{
degree[i] = G[i].size();
}
int cnt = 0;
for (int i = 1; i <= n; ++i)
{
if (degree[i] % 2 == 1)cnt++;
}
return cnt == 0 ? 1 : (cnt == 2 ? 0 : -1);
}
}
有向图
namespace _Euler
{
/*
默认连通图，-1不存在，0存在欧拉路径，1存在欧拉回路
*/
const int N = 1e5 + 10;
/*====================*/
int degree[N];
/*====================*/
bool Init(void)
{
for (int i = 1; i <= n; ++i)
{
degree[i] = 0;
}
for (int i = 1; i <= m; ++i)
{
int u = edge[i].u;
int v = edge[i].v;
degree[u]++, degree[v]--;
}
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 1; i <= n; ++i)
{
if (degree[i] == -1)cnt1++;
if (degree[i] == +0)cnt2++;
if (degree[i] == +1)cnt3++;
}
if (cnt1 == 1 && cnt3 == 1 && cnt2 + 2 == n)
{
return +0;
}
else if (cnt2 == n)
{
return +1;
}
else
{
return -1;
}
}
}
最大团
namespace _MaxClique
{
const int N = 5e1 + 10;
/*====================*/
int n; int G[N][N];
int dp[N], stk[N][N], res;
/*====================*/
bool DFS(int ns, int dep)
{
if (ns == 0)
{
if (dep > res)
{
res = dep; return true;
}
return false;
}
for (int i = 0; i < ns; ++i)
{
int u = stk[dep][i], cnt = 0;
if (dep + dp[u] <= res)return false;
if (dep + ns - i <= res)return false;
for (int j = i + 1; j < ns; ++j)
{
int v = stk[dep][j];
if (G[u][v])stk[dep + 1][cnt++] = v;
}
if (DFS(cnt, dep + 1))return true;
}
return false;
}
/*====================*/
int Init(void)
{
cin >> n; res = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
cin >> G[i][j];
}
}
for (int i = n; i >= 1; --i)
{
int ns = 0;
for (int j = i + 1; j <= n; ++j)
{
if (G[i][j])stk[1][ns++] = j;
}
DFS(ns, 1); dp[i] = res;
}
return res;
}
}
最短路
SPFA
namespace _SPFA
{
const int N = 1e5 + 10;
/*====================*/
int dis[N]; bool vis[N];
/*====================*/
void Init(int s)
{
memset(dis, 0X3F, sizeof(dis));
memset(vis, false, sizeof(vis));
queue<int>q; dis[s] = 0; q.push(s);
while (!q.empty())
{
int cur = q.front(); q.pop(); vis[cur] = false;
for (int i = 0; i < G[cur].size(); ++i)
{
int val = edge[G[cur][i]].w;
int nxt = edge[G[cur][i]].node(cur);
if (dis[nxt] > dis[cur] + val)
{
dis[nxt] = dis[cur] + val;
if (!vis[nxt])
{
q.push(nxt); vis[nxt] = true;
}
}
}
}
}
}
Floyd
namespace _Floyd
{
const int N = 2e2 + 10;
/*====================*/
int dp[N][N];
/*====================*/
void Init(void)
{
for (int k = 1; k <= n; ++k)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
}
Dijkstra
namespace _Dijkstra
{
const int N = 1e5 + 10;
/*====================*/
struct Unit
{
int v, w;
Unit(int _v = 0, int _w = 0)
{
v = _v, w = _w;
}
friend bool operator<(const Unit& a, const Unit& b)
{
return a.w > b.w;
}
};
/*====================*/
int dis[N]; bool vis[N];
/*====================*/
void Init(int s)
{
memset(dis, 0X3F, sizeof(dis));
memset(vis, false, sizeof(vis));
priority_queue<Unit>q;
q.push(Unit(s, dis[s] = 0));
while (!q.empty())
{
int cur = q.top().v; q.pop();
if (vis[cur])continue; vis[cur] = true;
for (int i = 0; i < G[cur].size(); ++i)
{
int val = edge[G[cur][i]].w;
int nxt = edge[G[cur][i]].node(cur);
if (dis[nxt] > dis[cur] + val)
{
dis[nxt] = dis[cur] + val;
q.push(Unit(nxt, dis[nxt]));
}
}
}
}
}
SPFA-SLF
namespace _SPFA
{
const int N = 1e5 + 10;
/*====================*/
int dis[N]; bool vis[N];
/*====================*/
void Init(int s)
{
memset(dis, 0X3F, sizeof(dis));
memset(vis, false, sizeof(vis));
deque<int>q; dis[s] = 0; q.push_back(s);
while (!q.empty())
{
int cur = q.front();
q.pop_front(); vis[cur] = false;
if (!q.empty() && dis[q.front()] > dis[q.back()])
{
swap(q.front(), q.back());
}
for (int i = 0; i < G[cur].size(); ++i)
{
int val = edge[G[cur][i]].w;
int nxt = edge[G[cur][i]].node(cur);
if (dis[nxt] > dis[cur] + val)
{
dis[nxt] = dis[cur] + val;
if (!vis[nxt])
{
vis[nxt] = true;
if (!q.empty() && dis[nxt] < dis[q.front()])
{
q.push_front(nxt);
}
else
{
q.push_back(nxt);
}
}
}
}
}
}
}
环相关
判环
namespace _Loop
{
const int N = 1e5 + 10;
/*====================*/
int indegree[N];
/*====================*/
bool Init(void)
{
queue<int>q; int cnt = 0;
memset(indegree, 0, sizeof(indegree));
for (int i = 1; i <= m; ++i)
{
indegree[edge[i].v]++;
}
for (int i = 1; i <= n; ++i)
{
if (indegree[i] == 0)q.push(i);
}
while (!q.empty())
{
int cur = q.front(); q.pop(); cnt++;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (--indegree[nxt] == 0)q.push(nxt);
}
}
return cnt == n;
}
}
判负环
namespace _Loop
{
const int N = 1e5 + 10;
/*====================*/
int dis[N], cnt[N]; bool vis[N];
/*====================*/
bool Init(void)
{
queue<int>q;
memset(cnt, 0, sizeof(cnt));
memset(dis, 0, sizeof(dis));
for (int i = 1; i <= n; ++i)
{
q.push(i); vis[i] = true;
}
while (!q.empty())
{
int cur = q.front();
q.pop(); vis[cur] = false;
for (int i = 0; i < G[cur].size(); ++i)
{
int val = edge[G[cur][i]].w;
int nxt = edge[G[cur][i]].node(cur);
if (dis[nxt] > dis[cur] + val)
{
cnt[nxt] = cnt[cur] + 1;
dis[nxt] = dis[cur] + val;
if (cnt[nxt] > n)
{
return true;
}
if (!vis[nxt])
{
q.push(nxt); vis[nxt] = true;
}
}
}
}
return false;
}
}
求最小环
namespace _Loop
{
int Init(void)
{
int res = 0X3F3F3F3F;
for (int i = 1; i <= m; ++i)
{
_Dijkstra::Init(edge[i].v, i);
res = min(res, dis[edge[i].u] + edge[i].w);
}
return res;
}
}
网络流
最大流
ISAP
namespace _ISAP
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X7FFFFFFF;
/*====================*/
struct Edge
{
int u, v, c, f;
Edge(int _u = 0, int _v = 0, int _c = 0, int _f = 0)
{
u = _u, v = _v, c = _c, f = _f;
}
};
/*====================*/
int pre[N];//路径前驱
int cur[N];//当前弧优化
int n, m, s, t;//点，边，源，汇
vector<int>G[N];//邻接表
int d[N], vis[N], num[N];//图分层
Edge edge[2 * M]; int cnt;//边
/*====================*/
void AddEdge(int u, int v, int c)
{
edge[cnt++] = Edge(u, v, c, 0);
edge[cnt++] = Edge(v, u, 0, 0);
G[u].push_back(cnt - 2);
G[v].push_back(cnt - 1);
}
/*====================*/
void BFS(void)
{
for (int i = 0; i <= n; ++i)
{
d[i] = vis[i] = num[i] = 0;
}
queue<int>q; q.push(t);
d[t] = 0; vis[t] = 1;
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = 0; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (!vis[e.u] && e.c > e.f)
{
vis[e.u] = 1; d[e.u] = d[x] + 1; q.push(e.u);
}
}
}
for (int i = 0; i < n; ++i)num[d[i]]++;
}
int Augumemt(void)
{
int x, k = INF;
x = t; while (x != s)
{
Edge& e = edge[pre[x]];
k = min(k, e.c - e.f);
x = edge[pre[x]].u;
}
x = t; while (x != s)
{
edge[pre[x]].f += k;
edge[pre[x] ^ 1].f -= k;
x = edge[pre[x]].u;
}
return k;
}
int MaxFlow(void)
{
for (int i = 1; i <= n; ++i)
{
pre[i] = cur[i] = 0;
}
BFS(); int x = s, flow = 0;
while (d[s] < n)
{
if (x == t)
{
flow += Augumemt(); x = s;
}
int flag = 0;
for (int& i = cur[x]; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (e.c > e.f && d[x] == d[e.v] + 1)
{
flag = 1; pre[e.v] = G[x][i]; x = e.v; break;
}
}
if (!flag)
{
int l = n - 1;
for (int i = 0; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (e.c > e.f)l = min(l, d[e.v]);
}
if (--num[d[x]] == 0)break;
num[d[x] = l + 1]++; cur[x] = 0;
if (x != s)x = edge[pre[x]].u;
}
}
return flow;
}
/*====================*/
int Init(void)
{
cnt = 0;
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; ++i)
{
G[i].clear();
}
for (int i = 1; i <= m; ++i)
{
int u, v, c;
cin >> u >> v >> c;
AddEdge(u, v, c);
}
return MaxFlow();
}
};
HLPP
namespace _HLPP
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X7FFFFFFF;
/*====================*/
struct Edge
{
int next, v, c;
Edge(int _next = 0, int _v = 0, int _c = 0)
{
next = _next, v = _v, c = _c;
}
};
/*====================*/
int n, m, s, t;
int d[N], num[N];
stack<int> lib[N];
int ex[N], level = 0;
Edge edge[2 * M]; int head[N], cnt;
/*====================*/
void AddEdge(int u, int v, int c)
{
edge[cnt] = Edge(head[u], v, c), head[u] = cnt++;
edge[cnt] = Edge(head[v], u, 0), head[v] = cnt++;
}
/*====================*/
int Push(int u)
{
bool init = u == s;
for (int i = head[u]; i != -1; i = edge[i].next)
{
const int& v = edge[i].v, & c = edge[i].c;
if (!c || init == false && d[u] != d[v] + 1)continue;
int k = init ? c : min(c, ex[u]);
if (v != s && v != t && !ex[v]) lib[d[v]].push(v), level = max(level, d[v]);
ex[u] -= k, ex[v] += k, edge[i].c -= k, edge[i ^ 1].c += k;
if (!ex[u]) return 0;
}
return 1;
}
void Relabel(int x)
{
d[x] = INF;
for (int i = head[x]; i != -1; i = edge[i].next)
{
if (edge[i].c) d[x] = min(d[x], d[edge[i].v]);
}
if (++d[x] < n)
{
lib[d[x]].push(x); level = max(level, d[x]); ++num[d[x]];
}
}
bool BFS(void)
{
for (int i = 1; i <= n; ++i)
{
d[i] = INF; num[i] = 0;
}
queue<int>q; q.push(t), d[t] = 0;
while (!q.empty())
{
int u = q.front(); q.pop(); num[d[u]]++;
for (int i = head[u]; i!=-1; i = edge[i].next)
{
const int& v = edge[i].v;
if (edge[i ^ 1].c && d[v] > d[u] + 1) d[v] = d[u] + 1, q.push(v);
}
}
return d[s] != INF;
}
int Select(void)
{
while (lib[level].size() == 0 && level > -1) level--;
return level == -1 ? 0 : lib[level].top();
}
int MaxFlow(void)
{
if (!BFS()) return 0;
d[s] = n; Push(s); int x;
while (x = Select())
{
lib[level].pop();
if (Push(x))
{
if (!--num[d[x]])
{
for (int i = 1; i <= n; ++i)
{
if (i != s && i != t && d[i] > d[x] && d[i] < n + 1)
{
d[i] = n + 1;
}
}
}
Relabel(x);
}
}
return ex[t];
}
/*====================*/
int Init(void)
{
cnt = 0;
cin >> n >> m >> s >> t;
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; ++i)
{
int u, v, c;
cin >> u >> v >> c;
AddEdge(u, v, c);
}
return MaxFlow();
}
}
Dinic
namespace Dinic
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X7FFFFFFF;
/*====================*/
struct Edge
{
int u, v, c, f;
Edge(int _u = 0, int _v = 0, int _c = 0, int _f = 0)
{
u = _u, v = _v, c = _c, f = _f;
}
};
/*====================*/
int cur[N];//当前弧优化
int n, m, s, t;//点，边，源，汇
vector<int>G[N];//邻接表
int d[N], vis[N];//图分层
Edge edge[2 * M]; int cnt;//边
/*====================*/
int AddEdge(int u, int v, int c)
{
edge[m++] = Edge(u, v, c, 0);
edge[m++] = Edge(v, u, 0, 0);
G[u].push_back(m - 2);
G[v].push_back(m - 1);
return m - 2;
}
/*====================*/
bool BFS(void)
{
for (int i = 0; i <= n; ++i)
{
d[i] = vis[i] = 0;
}
queue<int>q; q.push(s);
d[s] = 0; vis[s] = 1;
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = 0; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (!vis[e.v] && e.c > e.f)
{
vis[e.v] = 1; d[e.v] = d[x] + 1; q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x, int k)
{
int flow = 0, f;
if (x == t || k == 0) return k;
for (int& i = cur[x]; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (d[x] + 1 == d[e.v] && (f = DFS(e.v, min(k, e.c - e.f))) > 0)
{
e.f += f; edge[G[x][i] ^ 1].f -= f;
flow += f; k -= f; if (k == 0) break;
}
}
return flow;
}
int MaxFlow(void)
{
int flow = 0;
while (BFS())
{
flow += DFS(s, INF);
for (int i = 1; i <= n; ++i)
{
cur[i] = 0;
}
}
return flow;
}
/*====================*/
void Init(void)
{
for (int i = 1; i <= n; ++i)
{
G[i].clear();
}
m = 0; n = 0; s = ++n, t = ++n;
}
}
Dinic-Scaling
namespace _Dinic
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X7FFFFFFF;
/*====================*/
struct Edge
{
int u, v, c, f;
Edge(int _u = 0, int _v = 0, int _c = 0, int _f = 0)
{
u = _u, v = _v, c = _c, f = _f;
}
friend bool operator<(const Edge& a, const Edge& b)
{
return a.c > b.c;
}
};
/*====================*/
int d[N];//图分层
int cur[N];//当前弧优化
Edge _edge[M];//即将加入流网络的边
int n, m, s, t;//点，边，源，汇
vector<int>G[N];//邻接表
Edge edge[2 * M]; int cnt;//边
/*====================*/
void AddEdge(int u, int v, int c)
{
edge[cnt++] = Edge(u, v, c, 0);
edge[cnt++] = Edge(v, u, 0, 0);
G[u].push_back(cnt - 2);
}
/*====================*/
bool BFS(void)
{
for (int i = 0; i <= n; ++i)
{
d[i] = INF;
}
queue<int>q; q.push(s); d[s] = 0;
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = 0; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (d[e.v] >= INF && e.c > e.f)
{
d[e.v] = d[x] + 1; q.push(e.v);
}
}
}
return d[t] < INF;
}
int DFS(int x, int k)
{
int flow = 0, f;
if (x == t || k == 0) return k;
for (int& i = cur[x]; i < G[x].size(); ++i)
{
Edge& e = edge[G[x][i]];
if (d[x] + 1 == d[e.v] && (f = DFS(e.v, min(k, e.c - e.f))) > 0)
{
e.f += f; edge[G[x][i] ^ 1].f -= f;
flow += f; k -= f; if (k == 0) break;
}
}
return flow;
}
int Dinic(void)
{
int flow = 0;
while (BFS())
{
flow += DFS(s, INF);
for (int i = 1; i <= n; ++i)
{
cur[i] = 0;
}
}
return flow;
}
int MaxFlow(void)
{
int flow = 0;
sort(_edge, _edge + m);
for (int type : {0, 1})
{
for (int p = 1 << 30, i = 0; p; p /= 2)
{
while (i < m && _edge[i].c >= p)
{
if (type == 0)AddEdge(_edge[i].u, _edge[i].v, _edge[i].c);
if (type == 1)G[_edge[i].v].push_back(i * 2 + 1); i++;
}
flow += Dinic();
}
}
return flow;
}
/*====================*/
int Init(void)
{
cnt = 0;
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; ++i)
{
G[i].clear();
}
for (int i = 0; i < m; ++i)
{
int u, v, c;
cin >> u >> v >> c;
_edge[i] = Edge(u, v, c);
}
return MaxFlow();
}
}
费用流
EK
namespace _EK
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
struct Edge
{
int next, v, c, w;
Edge(int _next = 0, int _v = 0, int _c = 0, int _w = 0)
{
next = _next, v = _v, c = _c, w = _w;
}
};
/*====================*/
int n, m, s, t;
int maxflow, mincost;
Edge edge[2 * M]; int head[N], cnt;
int dis[N], pre[N], incf[N]; bool vis[N];
/*====================*/
void AddEdge(int u, int v, int c, int w)
{
edge[cnt] = Edge(head[u], v, c, +w); head[u] = cnt++;
edge[cnt] = Edge(head[v], u, 0, -w); head[v] = cnt++;
}
/*====================*/
bool SPFA(void)
{
memset(dis, 0X3F, sizeof(dis));
queue<int> q; q.push(s);
dis[s] = 0, incf[s] = INF, incf[t] = 0;
while (!q.empty())
{
int u = q.front(); q.pop(); vis[u] = false;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v, c = edge[i].c, w = edge[i].w;
if (!c || dis[v] <= dis[u] + w) continue;
dis[v] = dis[u] + w, incf[v] = min(c, incf[u]), pre[v] = i;
if (!vis[v])q.push(v), vis[v] = true;
}
}
return incf[t];
}
int MinCost(void)
{
while (SPFA())
{
maxflow += incf[t];
for (int u = t; u != s; u = edge[pre[u] ^ 1].v)
{
edge[pre[u]].c -= incf[t];
edge[pre[u] ^ 1].c += incf[t];
mincost += incf[t] * edge[pre[u]].w;
}
}
return mincost;
}
/*====================*/
int Init(void)
{
cin >> n >> m >> s >> t;
mincost = maxflow = cnt = 0;
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; ++i)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
AddEdge(u, v, c, w);
}
return MinCost();
}
}
ZKW费用流
namespace _ZKW
{
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X7FFFFFFF;
/*====================*/
struct Edge
{
int u, v, c, w;
Edge(int _u = 0, int _v = 0, int _c = 0, int _w = 0)
{
u = _u, v = _v, c = _c, w = _w;
}
};
/*====================*/
int n, m, s, t;
vector<int>G[N];
int mincost, maxflow;
int dep[N]; bool vis[N];
Edge edge[2 * M]; int cnt;
/*====================*/
void AddEdge(int u, int v, int c, int w)
{
edge[cnt++] = Edge(u, v, c, +w);
edge[cnt++] = Edge(v, u, 0, -w);
G[u].push_back(cnt - 2);
G[v].push_back(cnt - 1);
}
/*====================*/
bool SPFA(void)
{
for (int i = 1; i <= n; ++i)
{
vis[i] = false, dep[i] = INF;
}
vis[t] = true, dep[t] = 0;
deque<int> q; q.push_back(t);
while (!q.empty())
{
int x = q.front(); q.pop_front(), vis[x] = false;
if (!q.empty() && dep[q.front()] > dep[q.back()])
{
swap(q.front(), q.back());
}
for (int i = 0; i < G[x].size(); ++i)
{
Edge& e1 = edge[G[x][i] ^ 0];
Edge& e2 = edge[G[x][i] ^ 1];
if (e2.c != 0 && dep[e1.v] > dep[x] - e1.w)
{
dep[e1.v] = dep[x] - e1.w;
if (!vis[e1.v])
{
vis[e1.v] = true;
if (!q.empty() && dep[e1.v] < dep[q.front()])
{
q.push_front(e1.v);
}
else
{
q.push_back(e1.v);
}
}
}
}
}
return dep[s] < INF;
}
int DFS(int x, int k)
{
vis[x] = true; int flow = 0, f;
if (x == t || k == 0) return k;
for (int i = 0; i < G[x].size(); ++i)
{
Edge& e1 = edge[G[x][i] ^ 0];
Edge& e2 = edge[G[x][i] ^ 1];
if (vis[e1.v] || e1.c == 0)continue;
if (dep[x] - e1.w == dep[e1.v] && (f = DFS(e1.v, min(k, e1.c))) > 0)
{
e1.c -= f, e2.c += f; flow += f, k -= f;
mincost += f * e1.w; if (k == 0) break;
}
}
return flow;
}
int MinCost(void)
{
while (SPFA())
{
vis[t] = true;
while (vis[t])
{
for (int i = 1; i <= n; ++i)
{
vis[i] = false;
}
maxflow += DFS(s, INF);
}
}
return mincost;
}
/*====================*/
int Init(void)
{
cin >> n >> m >> s >> t;
mincost = maxflow = cnt = 0;
for (int i = 1; i <= n; ++i)
{
G[i].clear();
}
for (int i = 1; i <= m; ++i)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
AddEdge(u, v, c, w);
}
return MinCost();
}
}
支配树
namespace Lengauer_Tarjan
{
struct Edge
{
int v, x;
Edge(int _v = 0, int _x = 0)
{
v = _v, x = _x;
}
};
/*====================*/
int n, m;
Edge edge[M * 3]; int head[3][N], tot;
int idx[N], dfn[N], dfc;
int fa[N], fth[N], mn[N], idm[N], sdm[N];
/*====================*/
void Add(int x, int u, int v)
{
edge[head[x][u] = ++tot] = Edge(v, head[x][u]);
}
void Add(int u, int v)
{
Add(0, u, v); Add(1, v, u);
}
void DFS(int u)
{
idx[dfn[u] = ++dfc] = u;
for (int i = head[0][u]; i; i = edge[i].x)
{
int v = edge[i].v;
if (!dfn[v])
{
DFS(v), fth[v] = u;
}
}
}
int Find(int x)
{
if (fa[x] == x)
{
return x;
}
int tmp = fa[x];
fa[x] = Find(fa[x]);
if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]])
{
mn[x] = mn[tmp];
}
return fa[x];
}
void Tarjan(int st)
{
DFS(st);
for (int i = 1; i <= n; ++i)
{
fa[i] = sdm[i] = mn[i] = i;
}
for (int i = dfc; i >= 2; --i)
{
int u = idx[i], res = INF;
for (int j = head[1][u]; j; j = edge[j].x)
{
int v = edge[j].v; Find(v);
if (dfn[v] < dfn[u])
{
res = min(res, dfn[v]);
}
else
{
res = min(res, dfn[sdm[mn[v]]]);
}
}
sdm[u] = idx[res];
fa[u] = fth[u];
Add(2, sdm[u], u);
u = fth[u];
for (int j = head[2][u]; j; j = edge[j].x)
{
int v = edge[j].v; Find(v);
if (sdm[mn[v]] == u)
{
idm[v] = u;
}
else
{
idm[v] = mn[v];
}
}
head[2][u] = 0;
}
for (int i = 2; i <= dfc; ++i)
{
int u = idx[i];
if (idm[u] != sdm[u])
{
idm[u] = idm[idm[u]];
}
}
}
/*====================*/
void Init(int s)
{
Tarjan(s);
tot = dfc = 0;
for (int i = 1; i <= n; ++i)
{
dfn[i] = head[0][i] = head[1][i] = head[2][i] = 0;
}
}
//树上连边idm[i] -> i;
}
拓扑排序
namespace _TopSort
{
const int N = 1e5 + 10;
/*====================*/
int indegree[N];
/*====================*/
void Init(void)
{
queue<int>q;
memset(indegree, 0, sizeof(indegree));
for (int i = 1; i <= m; ++i)
{
indegree[edge[i].v]++;
}
for (int i = 1; i <= n; ++i)
{
if (indegree[i] == 0)q.push(i);
}
while (!q.empty())
{
int cur = q.front(); q.pop(); cout << cur << " ";
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (--indegree[nxt] == 0)q.push(nxt);
}
}
}
}
差分约束
namespace _SDC
{
/*
存在负环时无解
记得建立一个超级源点
A-B<=W的不等式，由B->A，边权为W
跑最短路时为最大差值，跑最长路时为最小差值
*/
const int N = 1e5 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
int dis[N]; int cnt[N]; bool vis[N];
/*====================*/
bool Init(void)
{
G[0].clear(); cnt[0] = 0;
for (int i = 1; i <= n; ++i)
{
G[0].push_back(++m);
edge[m] = Edge(0, i, 0);
dis[i] = INF, vis[i] = false, cnt[i] = 0;
}
queue<int>q; dis[0] = 0; q.push(0);
while (!q.empty())
{
int cur = q.front(); q.pop(); vis[cur] = false;
for (int i = 0; i < G[cur].size(); ++i)
{
int val = edge[G[cur][i]].w;
int nxt = edge[G[cur][i]].node(cur);
if (dis[nxt] > dis[cur] + val)
{
cnt[nxt] = cnt[cur] + 1;
dis[nxt] = dis[cur] + val;
if (cnt[nxt] > n)return false;
if (!vis[nxt])
{
q.push(nxt); vis[nxt] = true;
}
}
}
}
return true;
}
}
图的连通性
双连通分量
边双连通分量
namespace _E_DCC
{
const int N = 1e5 + 10;
/*====================*/
int belong[N], cnt;
int dfn[N], low[N], num;
/*====================*/
void Tarjan(int cur, int in_edge)
{
dfn[cur] = low[cur] = ++num;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (!dfn[nxt])
{
Tarjan(nxt, G[cur][i]);
low[cur] = min(low[cur], low[nxt]);
if (low[nxt] > dfn[cur])
{
edge[G[cur][i]].bridge = true;
}
}
else if (i != in_edge)
{
low[cur] = min(low[cur], dfn[nxt]);
}
}
}
void DFS(int cur)
{
belong[cur] = cnt;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (edge[G[cur][i]].bridge)continue;
if (belong[nxt])continue; DFS(nxt);
}
}
/*====================*/
void Init(void)
{
for (int i = 1; i <= n; ++i)
{
if (!dfn[i])Tarjan(i, 0);
}
for (int i = 1; i <= n; ++i)
{
if (!belong[i])cnt++, DFS(i);
}
}
}
点双连通分量
namespace _V_DCC
{
const int N = 1e5 + 10;
/*====================*/
vector<int>dcc[N];
bool cut[N]; int cnt;
stack<int>lib; int root;
int dfn[N], low[N], num;
/*====================*/
void Tarjan(int cur)
{
int flag = 0; lib.push(cur);
dfn[cur] = low[cur] = ++num;
if (cur == root && G[cur].size() == 0)
{
dcc[++cnt].push_back(cur); return;
}
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (!dfn[nxt])
{
Tarjan(nxt);
low[cur] = min(low[cur], low[nxt]);
if (low[nxt] >= dfn[cur])
{
flag++; cnt++; int top;
if (cur != root || flag > 1)
{
cut[cur] = true;
}
do
{
top = lib.top(); lib.pop();
dcc[cnt].push_back(top);
} while (top != nxt);
dcc[cnt].push_back(cur);
}
}
else
{
low[cur] = min(low[cur], dfn[nxt]);
}
}
}
/*====================*/
void Init(void)
{
for (int i = 1; i <= n; ++i)
{
if (!dfn[i])Tarjan(root = i);
}
}
}
获取点双内部的边
void Tarjan(int cur, int e)
{
dfn[cur] = low[cur] = ++num;
if (cur != root || G[cur].size() != 0)
{
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (!dfn[nxt])
{
lib.push(G[cur][i]); Tarjan(nxt, G[cur][i]);
low[cur] = min(low[cur], low[nxt]);
if (low[nxt] >= dfn[cur])
{
cnt++; int top;
do
{
top = lib.top(); lib.pop();
dcc[cnt].push_back(edge[top].w);
} while (top != G[cur][i]);
}
}
else
{
if (dfn[nxt] < dfn[cur] && G[cur][i] != e)
{
lib.push(G[cur][i]);
}
low[cur] = min(low[cur], dfn[nxt]);
}
}
}
}
强连通分量
namespace _SCC
{
const int N = 1e5 + 10;
/*====================*/
int belong[N];
int dfn[N], low[N], num;
stack<int>lib; int ins[N];
vector<int>scc[N]; int cnt;
/*====================*/
void Tarjan(int cur)
{
lib.push(cur); ins[cur] = 1;
dfn[cur] = low[cur] = ++num;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (!dfn[nxt])
{
Tarjan(nxt);
low[cur] = min(low[cur], low[nxt]);
}
else if (ins[nxt])
{
low[cur] = min(low[cur], dfn[nxt]);
}
}
if (dfn[cur] == low[cur])
{
cnt++; int top;
do
{
top = lib.top(); lib.pop(); ins[top] = 0;
belong[top] = cnt; scc[cnt].push_back(top);
} while (top != cur);
}
}
/*====================*/
void Init(void)
{
num = cnt = 0;
for (int i = 1; i <= n; ++i)
{
dfn[i] = low[i] = 0;
}
for (int i = 1; i <= n; ++i)
{
if (!dfn[i])Tarjan(i);
}
}
}
最小树形图
有向有环图
挖坑：朱刘算法
有向无环图
namespace _DMST
{
const int N = 1e5 + 10;
/*====================*/
const int INF = 0X7FFFFFFF;
/*====================*/
int val[N], sum;
/*====================*/
void Init(void)
{
sum = 0;
for (int i = 1; i <= n; ++i)
{
val[i] = INF;
}
for (int i = 1; i <= m; ++i)
{
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
val[v] = min(val[v], w);
}
for (int i = 1; i <= n; ++i)
{
if (val[i] != INF)
{
sum += val[i];
}
}
}
}
树论
LCT
class Link_Cut_Tree
{
public:
void Init(void)
{
}
private:
int rev[N], fa[N], ch[N][2];
/*====================*/
bool Which(int x)
{
return ch[fa[x]][1] == x;
}
bool IsRoot(int x)
{
return ch[fa[x]][Which(x)] != x;
}
/*====================*/
void PushUp(int x)
{
/*PushUp*/
}
void PushAll(int x)
{
if (!IsRoot(x))
{
PushAll(fa[x]);
}
PushDown(x);
}
void PushDown(int x)
{
if (rev[x])
{
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
/*PushDown*/
}
/*====================*/
void Rotate(int x)
{
int y = fa[x], z = fa[y], w = Which(x);
if (!IsRoot(y)) ch[z][Which(y)] = x; fa[x] = z;
ch[y][w] = ch[x][w ^ 1];
if (ch[y][w]) fa[ch[y][w]] = y;
ch[x][w ^ 1] = y; fa[y] = x;
PushUp(y); PushUp(x);
}
void Splay(int x)
{
PushAll(x);
for (; !IsRoot(x); Rotate(x))
{
if (!IsRoot(fa[x]))
{
Rotate(Which(x) == Which(fa[x]) ? fa[x] : x);
}
}
}
/*====================*/
void Access(int x)
{
for (int p = 0; x; p = x, x = fa[x])
{
Splay(x), ch[x][1] = p, PushUp(x);
}
}
/*====================*/
int FindRoot(int x)
{
Access(x); Splay(x);
while (ch[x][0]) x = ch[x][0];
Splay(x); return x;
}
void MakeRoot(int x)
{
Access(x); Splay(x); rev[x] ^= 1;
}
/*====================*/
void Cut(int u, int v)
{
Split(u, v);
if (fa[u] == v && !ch[u][1])
{
ch[v][0] = fa[u] = 0;
}
}
void Link(int u, int v)
{
MakeRoot(u); fa[u] = v;
}
/*====================*/
void Split(int u, int v)
{
MakeRoot(u); Access(v); Splay(v);
}
/*====================*/
int LCA(int u, int v)
{
Access(u); int ans = 0;
for (int child = 0; v; child = v, v = fa[v])
{
Splay(v); ch[v][1] = child; ans = v;
}
return ans;
}
}LCT;
LCA
树剖法
class _LCA
{
public:
~_LCA(void)
{
delete[] node;
}
int operator()(int u, int v)
{
while (node[u].top != node[v].top)
{
int topu = node[u].top;
int topv = node[v].top;
if (node[topu].dep > node[topv].dep)
{
u = node[topu].pre;
}
else
{
v = node[topv].pre;
}
}
return node[u].dep > node[v].dep ? v : u;
}
void init(int n, vector<int>G[], int root = 1)
{
this->G = G;
this->root = root;
node = new Node[n + 1];
DFS1(root, root); DFS2(root, root);
}
private:
struct Node
{
int pre = -1;
int dep = +0;
int siz = +1;
int son = -1;
int top = -1;
};
/*====================*/
int root = -1;
Node* node = NULL;
vector<int>* G = NULL;
/*====================*/
void DFS1(int pre, int cur)
{
node[cur].pre = pre;
node[cur].dep = node[pre].dep + 1;
for (auto nxt : G[cur])
{
if (nxt != pre)
{
DFS1(cur, nxt);
node[cur].siz += node[nxt].siz;
if (node[cur].son == -1)
{
node[cur].son = nxt;
}
else if (node[nxt].siz > node[node[cur].son].siz)
{
node[cur].son = nxt;
}
}
}
}
void DFS2(int cur, int top)
{
node[cur].top = top;
if (node[cur].son != -1)
{
DFS2(node[cur].son, top);
for (auto nxt : G[cur])
{
if (nxt == node[cur].pre)continue;
if (nxt == node[cur].son)continue;
DFS2(nxt, nxt);
}
}
}
};
ST表法
class _LCA
{
public:
int operator()(int u, int v)
{
if (u == v)return u;
if ((u = dfn[u]) > (v = dfn[v]))swap(u, v);
int d = log2[v - u++];
return Get(st[d][u], st[d][v - (1 << d) + 1]);
}
void init(int n, vector<int>G[], int root = 1)
{
this->G = G; dfn[0] = 0;
/*====================*/
log2[0] = -1;
for (int i = 1; i <= n; ++i)
{
log2[i] = log2[i >> 1] + 1;
}
/*====================*/
DFS(0, root);
for (int i = 1; i <= log2[n]; i++)
{
for (int j = 1; j + (1 << i) - 1 <= n; j++)
{
st[i][j] = Get(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
}
}
private:
int dfn[N];
int log2[N];
int st[19][N];
vector<int>* G;
/*====================*/
void DFS(int pre, int cur)
{
st[0][dfn[cur] = ++dfn[0]] = pre;
for (auto nxt : G[cur])
{
if (nxt != pre)
{
DFS(cur, nxt);
}
}
}
int Get(int x, int y)
{
return dfn[x] < dfn[y] ? x : y;
}
}lca;
树哈希
class Tree_Hash
{
public:
int operator()(vector<int>G[], int root)
{
this->G = G;
return DFS(root, root);
}
private:
vector<int>* G = NULL;
map<vector<int>, int>mp;
int DFS(int pre, int cur)
{
vector<int>vec;
for (auto nxt : G[cur])
{
if (nxt != pre)
{
vec.push_back(DFS(cur, nxt));
}
}
sort(vec.begin(), vec.end());
if (mp.find(vec) == mp.end())
{
mp[vec] = mp.size();
}
return mp[vec];
}
};
树分治
点分治
class _TCD
{
public:
~_TCD(void)
{
delete[] siz;
delete[] rooted;
}
void init(int n, vector<int>G[])
{
this->G = G;
siz = new int[n + 10];
rooted = new bool[n + 10];
for (int i = 0; i < n + 10; ++i)
{
siz[i] = 0, rooted[i] = false;
}
DividTree(Centroid(1, n));
}
private:
vector<int>* G = NULL;
/*====================*/
int* siz = NULL;
bool* rooted = NULL;
/*====================*/
int centroid, all_part;
/*====================*/
int Centroid(int cur, int all)
{
centroid = -1; all_part = all;
DFS(cur, cur, all); return centroid;
}
void DFS(int pre, int cur, int all)
{
siz[cur] = 1; int cur_part = 0;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = G[cur][i];
if (nxt == pre)continue;
if (rooted[nxt])continue;
DFS(cur, nxt, all);
siz[cur] += siz[nxt];
cur_part = max(cur_part, siz[nxt]);
}
cur_part = max(cur_part, all - siz[cur]);
if (cur_part < all_part)
{
all_part = cur_part, centroid = cur;
}
}
/*====================*/
void CalcSon(int pre, int cur)
{
/*
添加cur到右树tree中
*/
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = G[cur][i];
if (nxt == pre)continue;
if (rooted[nxt])continue;
/*=====================*/
CalcSon(cur, nxt);
}
}
void CalcRoot(int root)
{
/*
初始化左库lib
*/
for (int i = 0; i < G[root].size(); ++i)
{
int son = G[root][i];
if (!rooted[son])
{
/*
初始化右树tree
*/
CalcSon(son, son);
/*
遍历右树tree匹配左库lib
*/
/*
添加右树tree到左库lib
*/
}
}
}
/*====================*/
void DividTree(int root)
{
rooted[root] = true; CalcRoot(root);
for (int i = 0; i < G[root].size(); ++i)
{
int son = G[root][i];
if (!rooted[son])
{
DividTree(Centroid(son, siz[son]));
}
}
}
};
树链剖分
重链剖分
struct Node
{
int pre, dep, siz, son;
int top, dfn, idx;
int val;
Node(void)
{
pre = -1; dep = +0;
siz = +1; son = -1;
top = -1; dfn = +0;
idx = +0; val = +0;
}
};
/*====================*/
Node node[N];
/*====================*/
class HLD
{
public:
void operator()(vector<int>G[], int root = 1)
{
cnt = 0;
this->G = G; this->root = root;
DFS1(root, root); DFS2(root, root);
}
private:
int cnt = 0;
int root = -1;
vector<int>* G = NULL;
/*====================*/
void DFS1(int pre, int cur)
{
node[cur].pre = pre;
node[cur].dep = node[pre].dep + 1;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = G[cur][i];
if (nxt != pre)
{
DFS1(cur, nxt); node[cur].siz += node[nxt].siz;
if (node[cur].son == -1)
{
node[cur].son = nxt;
}
else if (node[nxt].siz > node[node[cur].son].siz)
{
node[cur].son = nxt;
}
}
}
}
void DFS2(int cur, int top)
{
node[cur].top = top;
node[cur].dfn = ++cnt;
node[cnt].idx = cur;
if (node[cur].son != -1)
{
DFS2(node[cur].son, top);
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = G[cur][i];
if (nxt == node[cur].pre)continue;
if (nxt == node[cur].son)continue;
DFS2(nxt, nxt);
}
}
}
};
树的重心
class Centroid
{
public:
int operator()(int n, vector<int>G[])
{
this->G = G;
siz = new int[n + 1];
centroid = -1;
all_part = n;
DFS(1, 1, n);
delete[] siz;
return centroid;
}
private:
int* siz = NULL;
int all_part = 0;
int centroid = -1;
vector<int>* G = NULL;
/*====================*/
void DFS(int pre, int cur, int all)
{
siz[cur] = 1;
int cur_part = 0;
for (auto nxt : G[cur])
{
if (nxt != pre)
{
DFS(cur, nxt, all);
siz[cur] += siz[nxt];
cur_part = max(cur_part, siz[nxt]);
}
}
cur_part = max(cur_part, all - siz[cur]);
if (cur_part < all_part)
{
all_part = cur_part, centroid = cur;
}
}
};
树上路径求交
假设当前要求路径 \((a,b)\) 和 \((c,d)\) 的交。
设 \(d_x\) 表示 \(x\) 的深度。
先求出 \(p[4]={lca(a,c),lca(a,d),lca(b,c),lca(b,d)}\)。
将 \(p\) 数组按深度排序，取出深度较大的两个，记为 \(p0,p1\)。
若存在交，则 \((p0,p1)\) 即所求。
现在只需要判断路径是否有交。
若 \(p0\neq p1\)，则一定有交。
否则若 \(d_{p0}=\max(d_{lca(a,b)},d_{lca(c,d)})\)，也有交。
否则路径不相交。
树上启发式合并
对于以 u 为根的子树
①. 先统计它轻子树(轻儿子为根的子树)的答案，统计完后删除信息
②. 再统计它重子树(重儿子为根的子树)的答案，统计完后保留信息
③. 然后再将重子树的信息合并到 u上
④. 再去遍历 u 的轻子树，然后把轻子树的信息合并到 u 上
⑤. 判断 u 的信息是否需要传递给它的父节点（u 是否是它父节点的重儿子）
void DFS(int root, int cur)
{
cnt[node[cur].val]++;
if (cnt[node[cur].val] > maxcnt)
{
ans[root] = node[cur].val;
maxcnt = cnt[node[cur].val];
}
else if (cnt[node[cur].val] == maxcnt)
{
ans[root] += node[cur].val;
}
for (auto nxt : G[cur])
{
if (nxt == node[cur].pre)continue;
if (nxt == node[root].son)continue;
DFS(root, nxt);
}
}
void DSU(int cur, bool keep)
{
for (auto nxt : G[cur])
{
if (nxt == node[cur].pre)continue;
if (nxt == node[cur].son)continue;
DSU(nxt, false);
}
if (node[cur].son != -1)DSU(node[cur].son, true);
if (node[cur].son != -1)
{
ans[cur] = ans[node[cur].son];
}
DFS(cur, cur);
if (keep == false)
{
maxcnt = 0;
for (int i = node[cur].dfn; i < node[cur].dfn + node[cur].siz; ++i)
{
cnt[node[node[i].idx].val]--;
}
}
}
数学
逆元
快速幂法
class INV
{
public:
void init(int P)
{
this->P = P;
}
int operator[](int x)
{
return Pow(x % P, P - 2);
}
private:
int P = 0;
/*====================*/
int Pow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
{
res = (res * a) % P;
}
b >>= 1, a = (a * a) % P;
}
return res;
}
};
线性递推法
class INV
{
public:
~INV(void)
{
delete[] inv;
}
int operator[](int x)
{
return inv[x];
}
void init(int n, int P)
{
inv = new int[n + 1];
inv[0] = 0, inv[1] = 1;
for (int i = 2; i <= n; ++i)
{
inv[i] = (P - P / i) * inv[P % i] % P;
}
}
private:
int* inv = NULL;
};
扩展欧几里得法
class INV
{
public:
void init(int P)
{
this->P = P;
}
int operator[](int x)
{
int a, b;
exgcd(x, P, a, b);
return (a % P + P) % P;
}
private:
int P = 0;
/*====================*/
void exgcd(int a, int b, int& x, int& y)
{
if (b == 0)
{
x = 1, y = 0;
}
else
{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}
};
质数
欧拉筛法
class Prime
{
public:
~Prime(void)
{
delete[] vis;
delete[] table;
}
int size(void)
{
return cnt;
}
void init(int n)
{
Euler(n);
}
bool operator()(int x)
{
return vis[x];
}
int operator[](int x)
{
return table[x];
}
private:
int cnt = 0;
bool* vis = NULL;
int* table = NULL;
/*====================*/
void Euler(int n)
{
vis = new bool[n + 1];
table = new int[n + 1];
for (int i = 0; i <= n; ++i)
{
vis[i] = true;
}
vis[0] = vis[1] = false;
for (int i = 2; i <= n; ++i)
{
if (vis[i])table[++cnt] = i;
for (int j = 1; j <= cnt; ++j)
{
if (i * table[j] > n)break;
vis[i * table[j]] = false;
if (i % table[j] == 0)break;
}
}
}
};
六倍试除法
class Prime
{
public:
bool operator()(int x)
{
if (x <= 1)return false;
if (x == 2 || x == 3 || x == 5)return true;
if (x % 2 == 0 || x % 3 == 0)return false;
for (int i = 5; i * i <= x; i += 6)
{
if (x % i == 0 || x % (i + 2) == 0)
{
return false;
}
}
return true;
}
};
Miller-Rabin
class Prime
{
public:
bool operator()(lnt x)
{
if (x < 3 || x % 2 == 0) return x == 2;
lnt a = x - 1, b = 0;
while (a % 2 == 0) a /= 2, ++b;
//lnt lib[] = { 2,7,61 };
lnt lib[] = { 2,325,9375,28178,450775,9780504,1795265022 };
for (lnt r : lib)
{
lnt v = Pow(r, a, x);
if (v == 1 || v == x - 1 || v == 0) continue;
for (lnt j = 1; j <= b; j++)
{
v = Mul(v, v, x);
if (v == x - 1 && j != b) { v = 1; break; }
if (v == 1) return false;
}
if (v != 1) return false;
}
return true;
}
private:
lnt Mul(lnt a, lnt b, lnt p)
{
lnt res = 0;
while (b != 0)
{
if (b % 2 == 1)
{
res = (res + a) % p;
}
b /= 2, a = (a * 2) % p;
}
return res;
}
lnt Pow(lnt a, lnt b, lnt p)
{
lnt res = 1;
while (b != 0)
{
if (b % 2 == 1)
{
res = Mul(res, a, p);
}
b /= 2, a = Mul(a, a, p);
}
return res;
}
};
快速幂
int Pow(int a, int b, int p)
{
int res = 1;
while (b)
{
if (b & 1)
{
res = (res * a) % p;
}
b >>= 1, a = (a * a) % p;
}
return res;
}
龟速乘
int Mul(int a, int b, int p)
{
int res = 0;
while (b)
{
if (b & 1)
{
res = (res + a) % p;
}
b >>= 1, a = (a * 2) % p;
}
return res;
}
lnt Mul(lnt a, lnt b, lnt p)
{
return (a * b - (lnt)(a / (long double)p * b + 1e-3) * p + p) % p;
}
逆序对
template<class Type>
class _CountInversions
{
public:
lnt operator()(int n, Type arr[])
{
res = 0;
a = new Type[n + 1];
temp = new Type[n + 1];
for (int i = 1; i <= n; ++i)
{
a[i] = arr[i];
}
MergeSort(1, n);
delete[] a; delete[] temp;
return res;
}
private:
Type* a = NULL;
lnt res = 0;
Type* temp = NULL;
/*====================*/
void MergeSort(int l, int r)
{
if (l < r)
{
int i = l;
int mid = (l + r) >> 1;
int p = l, q = mid + 1;
MergeSort(l, mid + 0);
MergeSort(mid + 1, r);
while (p <= mid && q <= r)
{
if (a[p] <= a[q])
{
temp[i++] = a[p++];
}
else
{
temp[i++] = a[q++];
res += (lnt)(mid - p + 1);
}
}
while (p <= mid)temp[i++] = a[p++];
while (q <= r) temp[i++] = a[q++];
for (i = l; i <= r; i++)a[i] = temp[i];
}
}
};
多项式
快速傅里叶变换
typedef complex<double> Comp;
const ll SIZE = 4000000 + 10;
const double PI = acos(-1.0);
Comp temp[SIZE];
void FFT(Comp* p, ll len, ll inv)//inv=+1 FFT;inv=-1 IFFT
{
if (len == 1) return;
const int E = 0, O = len / 2;
for (ll i = 0; i < len; ++i) temp[i] = p[i];
for (ll i = 0; i < len; ++i)
{
if ((i & 1) == 1)p[i / 2 + O] = temp[i];
if ((i & 1) == 0)p[i / 2 + E] = temp[i];
}
Comp* pe = p + E; FFT(pe, len / 2, inv);
Comp* po = p + O; FFT(po, len / 2, inv);
Comp omega(1, 0);
const double Angle = 2 * PI / len;
const Comp step(cos(Angle), sin(inv * Angle));
for (ll k = 0; k < len / 2; ++k, omega *= step)
{
temp[k + E] = pe[k] + omega * po[k];
temp[k + O] = pe[k] - omega * po[k];
}
for (ll i = 0; i < len; ++i) p[i] = temp[i];
}
离散对数
ll BSGS(ll a, ll b, ll m)
{
static unordered_map<ll, ll> hs;
hs.clear();
ll cur = 1, t = sqrt(m) + 1;
for (int B = 1; B <= t; ++B)
{
(cur *= a) %= m;
hs[b * cur % m] = B; // 哈希表中存B的值
}
ll now = cur; // 此时cur = a^t
for (int A = 1; A <= t; ++A)
{
auto it = hs.find(now);
if (it != hs.end())
return A * t - it->second;
(now *= cur) %= m;
}
return -1; // 没有找到，无解
}
欧拉函数
试除法
class PHI
{
public:
int operator[](int x)
{
return GetPhi(x);
}
private:
int GetPhi(int x)
{
int res = x;
for (int i = 2; i * i <= x; ++i)
{
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
};
欧拉筛法
class PHI
{
public:
~PHI(void)
{
delete[] phi;
}
void init(int n)
{
GetPhi(n);
}
int operator[](int x)
{
return phi[x];
}
private:
int* phi = NULL;
void GetPhi(int n)
{
phi = new int[n + 1];
bool* vis = new bool[n + 1];
int* table = new int[n + 1];
for (int i = 0; i <= n; ++i)
{
vis[i] = true;
}
int cnt = 0; phi[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (vis[i])
{
phi[i] = i - 1;
table[++cnt] = i;
}
for (int j = 1; j <= cnt; ++j)
{
if (i * table[j] > n)break;
vis[i * table[j]] = false;
if (i % table[j] == 0)
{
phi[i * table[j]] = phi[i] * table[j]; break;
}
else
{
phi[i * table[j]] = phi[i] * (table[j] - 1);
}
}
}
delete[] vis; delete[] table;
}
};
欧拉降幂
class EX_Euler
{
public:
int operator()(int a, string s, int p)
{
int b = 0;
bool flag = false;
int phi = GetPhi(p);
for (auto c : s)
{
b = (b * 10 + c - '0');
if (b >= phi)flag = true, b %= phi;
}
if (flag)b += phi; return Pow(a % p, b, p);
}
private:
int GetPhi(int x)
{
int res = x;
for (int i = 2; i * i <= x; ++i)
{
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int Pow(int a, int b, int p)
{
int res = 1;
while (b != 0)
{
if (b % 2 == 1)
{
res = (res * a) % p;
}
b /= 2, a = (a * a) % p;
}
return res;
}
};
欧几里得
最大公因数
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
最小公倍数
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
扩展欧几里得
void exgcd(int a, int b, int& x, int& y)
{
if (b == 0)
{
x = 1, y = 0;
}
else
{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}
分解质因数
欧拉筛优化
void PFF(int x, vector<int>& num, vector<int>& cnt)
{
for (int i = 1; i <= prime.size(); ++i)
{
if (prime[i] * prime[i] > x)break;
if (x % prime[i] == 0)
{
num.push_back(prime[i]);
cnt.push_back(0);
while (x % prime[i] == 0)
{
cnt.back()++;
x /= prime[i];
}
}
}
if (x != 1)
{
num.push_back(x);
cnt.push_back(1);
}
}
Pollard_Rho
class Pollard_Rho
{
public:
void operator()(lnt X, vector<lnt>& num, vector<lnt>& cnt)
{
GetAllFactor(X, num);
unordered_map<lnt, lnt>cntp; for (auto p : num)cntp[p]++;
sort(num.begin(), num.end()); num.erase(unique(num.begin(), num.end()), num.end());
for (auto p : num)cnt.push_back(cntp[p]);
}
private:
lnt gcd(lnt a, lnt b)
{
return b == 0 ? a : gcd(b, a % b);
}
lnt Mul(lnt a, lnt b, lnt p)
{
return (__int128)a * b % p;
}
lnt Pow(lnt a, lnt b, lnt p)
{
lnt res = 1;
while (b != 0)
{
if (b % 2 == 1)
{
res = Mul(res, a, p);
}
b /= 2, a = Mul(a, a, p);
}
return res;
}
bool Check(lnt x)
{
if (x < 3 || x % 2 == 0) return x == 2;
lnt a = x - 1, b = 0;
while (a % 2 == 0) a /= 2, ++b;
//lnt lib[] = { 2,7,61 };
lnt lib[] = { 2,325,9375,28178,450775,9780504,1795265022 };
for (lnt r : lib)
{
lnt v = Pow(r, a, x);
if (v == 1 || v == x - 1 || v == 0) continue;
for (lnt j = 1; j <= b; j++)
{
v = Mul(v, v, x);
if (v == x - 1 && j != b) { v = 1; break; }
if (v == 1) return false;
}
if (v != 1) return false;
}
return true;
}
lnt GetFactor(lnt X)
{
if (X == 4)return 2;
if (Check(X))return X;
mt19937 rng(time(NULL));
while (1)
{
lnt c = rng() % (X - 1) + 1;
auto f = [=](lnt x) { return ((__int128)x * x + c) % X; };
lnt t = 0, r = 0, p = 1, q;
do
{
for (int i = 0; i < 128; ++i)
{
t = f(t), r = f(f(r));
if (t == r || (q = (__int128)p * abs(t - r) % X) == 0)break;
p = q;
}
lnt d = gcd(p, X); if (d > 1)return d;
} while (t != r);
}
}
void GetAllFactor(lnt X, vector<lnt>& lib)
{
lnt fac = GetFactor(X);
if (fac == X)lib.push_back(fac);
else GetAllFactor(fac, lib), GetAllFactor(X / fac, lib);
}
}PFF;
获得全部因数
void GetDivisor(int x, vector<int>& divisor)
{
vector<int>num, cnt;
PFF(x, num, cnt);
divisor.push_back(1);
for (int i = 0; i < num.size(); ++i)
{
int val = 1;
int lim = divisor.size();
for (int j = 1; j <= cnt[i]; ++j)
{
val *= num[i];
for (int k = 0; k < lim; ++k)
{
divisor.push_back(divisor[k] * val);
}
}
}
}
字符串
Hash
class Hash
{
public:
void Init(const string& str, lnt base)
{
powbase = new lnt[str.size()];
invbase = new lnt[str.size()];
sumhash = new lnt[str.size()];
/*====================*/
for (int i = 0; i < str.size(); ++i)
{
if (i == 0)powbase[i] = 1;
else powbase[i] = powbase[i - 1] * base % MOD;
}
base = inv[base];
for (int i = 0; i < str.size(); ++i)
{
if (i == 0)invbase[i] = 1;
else invbase[i] = invbase[i - 1] * base % MOD;
}
for (int i = 0; i < str.size(); ++i)
{
if (i == 0)sumhash[i] = str[i] * powbase[i] % MOD;
else sumhash[i] = (sumhash[i - 1] + str[i] * powbase[i]) % MOD;
}
}
lnt operator()(int l, int r)
{
return (sumhash[r] - (l > 0 ? sumhash[l - 1] : 0) + MOD) * invbase[l] % MOD;
}
private:
lnt* powbase = NULL;
lnt* invbase = NULL;
lnt* sumhash = NULL;
};
数据结构
莫队
int n, m;
/*====================*/
int S;
struct Query
{
int l, r, idx;
Query(int _l = 0, int _r = 0, int _idx = 0)
{
l = _l, r = _r, idx = _idx;
}
friend bool operator<(const Query& a, const Query& b)
{
return (a.l / S == b.l / S) ? (((a.l / S) & 1) ? (a.r > b.r) : (a.r < b.r)) : (a.l < b.l);
}
}query[M];
/*====================*/
int ans[M];
/*====================*/
void Add(int pos)
{
}
void Del(int pos)
{
}
/*====================*/
void Solve(void)
{
cin >> n >> m;
S = n / sqrt(m) + 1;
for (int i = 1; i <= m; ++i)
{
int l, r; cin >> l >> r;
query[i] = Query(l, r, i);
}
sort(query + 1, query + 1 + m);
int l = 1, r = 0;
for (int i = 1; i <= m; ++i)
{
while (query[i].l < l)Add(--l);
while (r < query[i].r)Add(++r);
while (l < query[i].l)Del(l++);
while (query[i].r < r)Del(r--);
//获得ans[query[i].idx];
}
}
猫树
#include<iostream>
using namespace std;
const int N = 1 << 20;
const int LEVEL = 20;
int a[N];
int lg[N];
int pos[N];
int MaoA[LEVEL][N];//最大子段和
int MaoB[LEVEL][N];//最大连续和
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return (p << 1) | 1; }
void Build(int p, int l, int r, int level)
{
if (l == r) { pos[l] = p; return; }
int mid = (l + r) >> 1;
int tempA, tempB;
//the left
MaoA[level][mid] = MaoB[level][mid] = a[mid];
tempA = max(a[mid], 0), tempB = a[mid];
for (int i = mid - 1; i >= l; --i)
{
tempA += a[i]; MaoA[level][i] = max(MaoA[level][i + 1], tempA); tempA = max(tempA, 0);
tempB += a[i]; MaoB[level][i] = max(MaoB[level][i + 1], tempB);
}
//the right
MaoA[level][mid + 1] = MaoB[level][mid + 1] = a[mid + 1];
tempA = max(a[mid + 1], 0), tempB = a[mid + 1];
for (int i = mid + 2; i <= r; ++i)
{
tempA += a[i]; MaoA[level][i] = max(MaoA[level][i - 1], tempA); tempA = max(tempA, 0);
tempB += a[i]; MaoB[level][i] = max(MaoB[level][i - 1], tempB);
}
//
Build(ls(p), l, mid, level + 1); Build(rs(p), mid + 1, r, level + 1);
}
int Ask(int l, int r)
{
if (l == r)return a[l];
int level = (lg[pos[l]] - lg[pos[l] ^ pos[r]]);
return max(max(MaoA[level][l], MaoA[level][r]), MaoB[level][l] + MaoB[level][r]);
}
int main()
{
int n; cin >> n;
int len = 1; while (len < n)len <<= 1;
for (int i = 2; i < N; ++i)lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; ++i)cin >> a[i];
Build(1, 1, len, 1);
int m; cin >> m;
for (int i = 1; i <= m; ++i)
{
int l, r; cin >> l >> r;
cout << Ask(l, r) << endl;
}
return 0;
}
ST表
template<class Type>
class _ST
{
public:
~_ST(void)
{
delete[] log2;
for (int i = 0; i < logn; ++i)
{
delete[] table[i];
}
delete[] table;
}
Type operator()(int l, int r)
{
int d = log2[r - l + 1];
if (flag)
{
return max(table[d][l], table[d][r - (1 << d) + 1]);
}
else
{
return min(table[d][l], table[d][r - (1 << d) + 1]);
}
}
void init(int n, Type arr[], bool flag)
{
this->n = n;
this->flag = flag;
while ((1 << logn) <= n)
{
logn++;
}
table = new Type * [logn];
for (int i = 0; i < logn; ++i)
{
table[i] = new Type[n+1];
}
log2 = new int[n + 1]; log2[0] = -1;
for (int i = 1; i <= n; ++i)
{
log2[i] = log2[i >> 1] + 1;
}
for (int i = 1; i <= n; ++i)
{
table[0][i] = arr[i];
}
for (int j = 1; (1 << j) <= n; ++j)
{
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
{
if (flag)
{
table[j][i] = max(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
}
else
{
table[j][i] = min(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
}
}
}
}
private:
int n = 0;
int logn = 1;
int* log2 = NULL;
Type** table = NULL;
/*====================*/
#define MAX true
#define MIN false
bool flag = MIN;
};
扫描线
矩形面积并
namespace ScanLine
{
const int N = 1e5 + 10;
/*====================*/
struct Rectangle
{
double x1, y1;
double x2, y2;
};
Rectangle rectangle[N];
/*====================*/
vector<double>pos;
/*====================*/
struct Line
{
int val;
int l, r;
double h;
Line(int _l = 0, int _r = 0, double _h = 0, int _val = 0)
{
l = _l, r = _r, h = _h, val = _val;
}
friend bool operator<(const Line& a, const Line& b)
{
if (a.h != b.h)
{
return a.h < b.h;
}
else
{
return a.val > b.val;
}
}
};
vector<Line>line;
/*====================*/
struct Tree
{
int l, r;
int cnt; double len;
};
Tree tree[N << 3];
int ls(int p)
{
return p << 1;
}
int rs(int p)
{
return p << 1 | 1;
}
void PushUp(int p)
{
if (tree[p].cnt >= 1)
{
tree[p].len = pos[tree[p].r] - pos[tree[p].l - 1];
}
else
{
if (tree[p].l != tree[p].r)
{
tree[p].len = tree[ls(p)].len + tree[rs(p)].len;
}
else
{
tree[p].len = 0;
}
}
}
void Build(int p, int l, int r)
{
tree[p].l = l, tree[p].r = r;
tree[p].cnt = 0; tree[p].len = 0;
if (tree[p].l != tree[p].r)
{
int mid = (tree[p].l + tree[p].r) >> 1;
Build(ls(p), l, mid + 0);
Build(rs(p), mid + 1, r);
}
}
void Change(int p, int l, int r, int d)
{
if (l <= tree[p].l && tree[p].r <= r)
{
tree[p].cnt += d; PushUp(p);
}
else
{
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid)Change(ls(p), l, r, d);
if (mid < r) Change(rs(p), l, r, d);
PushUp(p);
}
}
/*====================*/
double Init(void)
{
int n; cin >> n;
pos.clear(); line.clear();
for (int i = 1; i <= n; ++i)
{
double x1, y1; cin >> x1 >> y1;//左上
double x2, y2; cin >> x2 >> y2;//右下
pos.push_back(x1); pos.push_back(x2);
rectangle[i].x1 = x1; rectangle[i].y1 = y1;
rectangle[i].x2 = x2; rectangle[i].y2 = y2;
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 1; i <= n; ++i)
{
int l = lower_bound(pos.begin(), pos.end(), rectangle[i].x1) - pos.begin();
int r = lower_bound(pos.begin(), pos.end(), rectangle[i].x2) - pos.begin();
line.push_back(Line(l, r, rectangle[i].y1, +1));
line.push_back(Line(l, r, rectangle[i].y2, -1));
}
sort(line.begin(), line.end());
Build(1, 1, pos.size() - 1);
bool flag = true;
double ans = 0.0;
double last = 0.0;
auto it = line.begin();
while (it != line.end())
{
double high = it->h;
if (flag)last = high, flag = false;
ans += (high - last) * tree[1].len;
while (it != line.end() && it->h == high)
{
Change(1, it->l + 1, it->r, it->val); it++;
}
last = high;
}
return ans;
}
}
矩形面积交
namespace ScanLine
{
const int N = 1e5 + 10;
/*====================*/
struct Rectangle
{
double x1, y1;
double x2, y2;
};
Rectangle rectangle[N];
/*====================*/
vector<double>pos;
/*====================*/
struct Line
{
int val;
int l, r;
double h;
Line(int _l = 0, int _r = 0, double _h = 0, int _val = 0)
{
l = _l, r = _r, h = _h, val = _val;
}
friend bool operator<(const Line& a, const Line& b)
{
if (a.h != b.h)
{
return a.h < b.h;
}
else
{
return a.val > b.val;
}
}
};
vector<Line>line;
/*====================*/
struct Tree
{
int cnt;
int l, r;
double len1;
double len2;
};
Tree tree[N << 3];
int ls(int p)
{
return p << 1;
}
int rs(int p)
{
return p << 1 | 1;
}
void PushUp(int p)
{
if (tree[p].cnt >= 1)
{
tree[p].len1 = pos[tree[p].r] - pos[tree[p].l - 1];
}
else
{
if (tree[p].l != tree[p].r)
{
tree[p].len1 = tree[ls(p)].len1 + tree[rs(p)].len1;
}
else
{
tree[p].len1 = 0;
}
}
if (tree[p].cnt >= 2)
{
tree[p].len2 = pos[tree[p].r] - pos[tree[p].l - 1];
}
else
{
if (tree[p].l != tree[p].r)
{
if (tree[p].cnt == 1)
{
tree[p].len2 = tree[ls(p)].len1 + tree[rs(p)].len1;
}
else
{
tree[p].len2 = tree[ls(p)].len2 + tree[rs(p)].len2;
}
}
else
{
tree[p].len2 = 0;
}
}
}
void Build(int p, int l, int r)
{
tree[p].cnt = 0;
tree[p].l = l, tree[p].r = r;
tree[p].len1 = 0; tree[p].len2 = 0;
if (tree[p].l != tree[p].r)
{
int mid = (tree[p].l + tree[p].r) >> 1;
Build(ls(p), l, mid + 0);
Build(rs(p), mid + 1, r);
}
}
void Change(int p, int l, int r, int d)
{
if (l <= tree[p].l && tree[p].r <= r)
{
tree[p].cnt += d; PushUp(p);
}
else
{
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid)Change(ls(p), l, r, d);
if (mid < r) Change(rs(p), l, r, d);
PushUp(p);
}
}
/*====================*/
double Init(void)
{
int n; cin >> n;
pos.clear(); line.clear();
for (int i = 1; i <= n; ++i)
{
double x1, y1; cin >> x1 >> y1;//左上
double x2, y2; cin >> x2 >> y2;//右下
pos.push_back(x1); pos.push_back(x2);
rectangle[i].x1 = x1; rectangle[i].y1 = y1;
rectangle[i].x2 = x2; rectangle[i].y2 = y2;
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 1; i <= n; ++i)
{
int l = lower_bound(pos.begin(), pos.end(), rectangle[i].x1) - pos.begin();
int r = lower_bound(pos.begin(), pos.end(), rectangle[i].x2) - pos.begin();
line.push_back(Line(l, r, rectangle[i].y1, +1));
line.push_back(Line(l, r, rectangle[i].y2, -1));
}
sort(line.begin(), line.end());
Build(1, 1, pos.size() - 1);
bool flag = true;
double ans = 0.0;
double last = 0.0;
auto it = line.begin();
while (it != line.end())
{
double high = it->h;
if (flag)last = high, flag = false;
ans += (high - last) * tree[1].len2;
while (it != line.end() && it->h == high)
{
Change(1, it->l + 1, it->r, it->val); it++;
}
last = high;
}
return ans;
}
}
矩形周长并
namespace ScanLine
{
const int N = 1e5 + 10;
/*====================*/
struct Rectangle
{
double x1, y1;
double x2, y2;
};
Rectangle rectangle[N];
/*====================*/
vector<double>pos;
/*====================*/
struct Line
{
int val;
int l, r;
double h;
Line(int _l = 0, int _r = 0, double _h = 0, int _val = 0)
{
l = _l, r = _r, h = _h, val = _val;
}
friend bool operator<(const Line& a, const Line& b)
{
if (a.h != b.h)
{
return a.h < b.h;
}
else
{
return a.val > b.val;
}
}
};
vector<Line>line;
typedef vector<Line>::iterator iter;
/*====================*/
struct Tree
{
int l, r;
int cnt; double len;
};
Tree tree[N << 3];
int ls(int p)
{
return p << 1;
}
int rs(int p)
{
return p << 1 | 1;
}
void PushUp(int p)
{
if (tree[p].cnt >= 1)
{
tree[p].len = pos[tree[p].r] - pos[tree[p].l - 1];
}
else
{
if (tree[p].l != tree[p].r)
{
tree[p].len = tree[ls(p)].len + tree[rs(p)].len;
}
else
{
tree[p].len = 0;
}
}
}
void Build(int p, int l, int r)
{
tree[p].l = l, tree[p].r = r;
tree[p].cnt = 0; tree[p].len = 0;
if (tree[p].l != tree[p].r)
{
int mid = (tree[p].l + tree[p].r) >> 1;
Build(ls(p), l, mid + 0);
Build(rs(p), mid + 1, r);
}
}
void Change(int p, int l, int r, int d)
{
if (l <= tree[p].l && tree[p].r <= r)
{
tree[p].cnt += d; PushUp(p);
}
else
{
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid)Change(ls(p), l, r, d);
if (mid < r) Change(rs(p), l, r, d);
PushUp(p);
}
}
/*====================*/
double Init(void)
{
int n; cin >> n; double ans = 0;
for (int i = 1; i <= n; ++i)
{
double x1, y1; cin >> x1 >> y1;//左上
double x2, y2; cin >> x2 >> y2;//右下
rectangle[i].x1 = x1; rectangle[i].y1 = y1;
rectangle[i].x2 = x2; rectangle[i].y2 = y2;
}
/*====================*/
pos.clear(); line.clear();
for (int i = 1; i <= n; ++i)
{
pos.push_back(rectangle[i].x1);
pos.push_back(rectangle[i].x2);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 1; i <= n; ++i)
{
int l = lower_bound(pos.begin(), pos.end(), rectangle[i].x1) - pos.begin();
int r = lower_bound(pos.begin(), pos.end(), rectangle[i].x2) - pos.begin();
line.push_back(Line(l, r, rectangle[i].y1, +1));
line.push_back(Line(l, r, rectangle[i].y2, -1));
}
sort(line.begin(), line.end());
Build(1, 1, pos.size() - 1);
double last1 = 0;
for (iter it = line.begin(); it != line.end(); ++it)
{
Change(1, it->l + 1, it->r, it->val);
ans += abs(tree[1].len - last1); last1 = tree[1].len;
}
/*====================*/
pos.clear(); line.clear();
for (int i = 1; i <= n; ++i)
{
pos.push_back(rectangle[i].y1);
pos.push_back(rectangle[i].y2);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 1; i <= n; ++i)
{
int l = lower_bound(pos.begin(), pos.end(), rectangle[i].y1) - pos.begin();
int r = lower_bound(pos.begin(), pos.end(), rectangle[i].y2) - pos.begin();
line.push_back(Line(l, r, rectangle[i].x1, +1));
line.push_back(Line(l, r, rectangle[i].x2, -1));
}
sort(line.begin(), line.end());
Build(1, 1, pos.size() - 1);
double last2 = 0;
for (iter it = line.begin(); it != line.end(); ++it)
{
Change(1, it->l + 1, it->r, it->val);
ans += abs(tree[1].len - last2); last2 = tree[1].len;
}
/*====================*/
return ans;
}
}
可删堆
template<class Type>
class Heap
{
public:
Type top(void)
{
while (!heap2.empty() && heap1.top() == heap2.top())
{
heap1.pop(); heap2.pop();
}
return heap1.top();
}
void pop(void)
{
while (!heap2.empty() && heap1.top() == heap2.top())
{
heap1.pop(); heap2.pop();
}
heap1.pop();
}
int size(void)
{
return heap1.size() - heap2.size();
}
void clear(void)
{
while (!heap1.empty())heap1.pop();
while (!heap2.empty())heap2.pop();
}
bool empty(void)
{
return heap1.size() == heap2.size();
}
void erase(Type val)
{
heap2.push(val);
}
void insert(Type val)
{
heap1.push(val);
}
private:
priority_queue<Type>heap1;
priority_queue<Type>heap2;
};
并查集
class _DSU
{
public:
~_DSU(void)
{
if (pre != NULL)
{
delete[] pre; pre = NULL;
}
if (siz != NULL)
{
delete[] siz; siz = NULL;
}
}
int find(int cur)
{
return cur == pre[cur] ? cur : pre[cur] = find(pre[cur]);
}
void clear(void)
{
delete[] pre; pre = NULL;
delete[] siz; siz = NULL;
}
void init(int n)
{
pre = new int[n + 1];
siz = new int[n + 1];
for (int i = 0; i <= n; ++i)
{
pre[i] = i, siz[i] = 1;
}
}
int operator[](int cur)
{
return find(cur);
}
void merge(int u, int v)
{
u = find(u), v = find(v);
if (siz[u] < siz[v])
{
pre[u] = v, siz[v] += siz[u];
}
else
{
pre[v] = u, siz[u] += siz[v];
}
}
void operator()(int u, int v)
{
merge(u, v);
}
private:
int* pre = NULL;
int* siz = NULL;
};
主席树
template<class Type>
class ChairmanTree
{
public:
~ChairmanTree(void)
{
delete[] root;
delete[] node;
}
Type ask(int l, int r, int k)
{
return val_key[Ask(root[l - 1], root[r], 1, len, k)];
}
void init(int n, Type arr[])
{
vector<Type>line;
for (int i = 1; i <= n; ++i)
{
line.push_back(arr[i]);
}
sort(line.begin(), line.end());
line.erase(unique(line.begin(), line.end()), line.end());
len = line.size();
for (int i = 0; i < line.size(); ++i)
{
key_val[line[i]] = i + 1;
val_key[i + 1] = line[i];
}
this->n = n;
root = new int[n + 10];
node = new Node[(n + 10) << 5];
root[0] = Zero(1, len);
for (int i = 1; i <= n; ++i)
{
root[i] = UpData(key_val[arr[i]], 1, len, root[i - 1]);
}
}
private:
struct Node
{
int val = 0;
int ls = 0, rs = 0;
};
/*====================*/
int pos = 0;
int* root = NULL;
Node* node = NULL;
int n = 0, len = 0;
map<Type, int>key_val;
map<int, Type>val_key;
/*====================*/
int Zero(int l, int r)
{
int root = ++pos;
if (l == r)return root;
int mid = (l + r) >> 1;
node[root].ls = Zero(l, mid + 0);
node[root].rs = Zero(mid + 1, r);
return root;
}
int UpData(int k, int l, int r, int oldroot)
{
int newroot = ++pos; node[newroot] = node[oldroot]; node[newroot].val += 1;
if (l == r)return newroot; int mid = (l + r) >> 1;
if (k <= mid)node[newroot].ls = UpData(k, l, mid + 0, node[oldroot].ls);
if (mid < k) node[newroot].rs = UpData(k, mid + 1, r, node[oldroot].rs);
return newroot;
}
int Ask(int u, int v, int l, int r, int k)
{
if (l == r)return l; int mid = (l + r) >> 1;
int x = node[node[v].ls].val - node[node[u].ls].val;
if (k <= x)return Ask(node[u].ls, node[v].ls, l, mid, k);
else return Ask(node[u].rs, node[v].rs, mid + 1, r, k - x);
}
};
平衡树
Treap·权值树
template<class Type>
class Treap
{
public:
~Treap(void)
{
Clear(root);
delete null;
}
int size(void)
{
return count;
}
void clear(void)
{
count = 0;
Clear(root);
root = null;
}
bool empty(void)
{
return count == 0;
}
void erase(Type val)
{
count--; Delete(root, val);
}
void insert(Type val)
{
count++; Insert(root, val);
}
int operator()(Type valu)
{
return GetRankByValu(valu);
}
Type operator[](int rank)
{
return GetValuByRank(rank);
}
private:
struct Node
{
int siz = 0;
Type val = Type();
int priority = rand();
Node* lch = NULL, * rch = NULL;
};
/*====================*/
int count = 0;
Node* null = new Node;
Node* root = null;
/*====================*/
Node* Creat(Type val)
{
Node* node = new Node;
node->lch = null;
node->rch = null;
node->val = val;
node->siz = 1;
return node;
}
void PushUp(Node* cur)
{
cur->siz = cur->lch->siz + cur->rch->siz + 1;
}
void LRotate(Node*& cur)
{
Node* son = cur->rch;
cur->rch = son->lch; son->lch = cur; cur = son;
PushUp(cur->lch); PushUp(cur);
}
void RRotate(Node*& cur)
{
Node* son = cur->lch;
cur->lch = son->rch; son->rch = cur; cur = son;
PushUp(cur->rch); PushUp(cur);
}
void Insert(Node*& cur, Type val)
{
if (cur == null)
{
cur = Creat(val);
}
else
{
if (val < cur->val)
{
Insert(cur->lch, val);
if (cur->priority < cur->lch->priority)
{
RRotate(cur);
}
}
else
{
Insert(cur->rch, val);
if (cur->priority < cur->rch->priority)
{
LRotate(cur);
}
}
PushUp(cur);
}
}
void Delete(Node*& cur, Type val)
{
if (cur == null)return;
if (val == cur->val)
{
if (cur->lch != null && cur->rch != null)
{
if (cur->lch->priority < cur->rch->priority)
{
LRotate(cur); Delete(cur->lch, val); PushUp(cur);
}
else
{
RRotate(cur); Delete(cur->rch, val); PushUp(cur);
}
}
else if (cur->lch != null)
{
RRotate(cur); Delete(cur->rch, val); PushUp(cur);
}
else if (cur->rch != null)
{
LRotate(cur); Delete(cur->lch, val); PushUp(cur);
}
else
{
Node* temp = cur; cur = null; delete temp;
}
}
else
{
if (val < cur->val)
{
Delete(cur->lch, val);
}
else
{
Delete(cur->rch, val);
}
PushUp(cur);
}
}
Type GetValuByRank(int rank)
{
Node* cur = root;
while (cur != null)
{
if (cur->lch->siz + 1 == rank)
{
return cur->val;
}
else
{
if (cur->lch->siz < rank)
{
rank -= cur->lch->siz + 1;
cur = cur->rch;
}
else
{
cur = cur->lch;
}
}
}
return Type();
}
int GetRankByValu(Type valu)
{
int res = 1;
Node* cur = root;
while (cur != null)
{
if (cur->val < valu)
{
res += cur->lch->siz + 1;
cur = cur->rch;
}
else
{
cur = cur->lch;
}
}
return res;
}
void Clear(Node* cur)
{
if (cur != null)
{
Clear(cur->lch);
Clear(cur->rch);
delete cur;
}
}
};
Treap·序列树
namespace Treap
{
struct Node
{
int siz = 0;
int val = 0;
int priority = rand();
Node* lch = NULL, * rch = NULL;
};
/*====================*/
Node* null = new Node;
Node* root = null;
/*====================*/
Node* Creat(int val)
{
Node* node = new Node;
node->lch = null;
node->rch = null;
node->val = val;
node->siz = 1;
return node;
}
/*====================*/
void PushUp(Node* cur)
{
cur->siz = cur->lch->siz + cur->rch->siz + 1;
}
void PushDown(Node* cur)
{
/*预留*/
}
/*====================*/
Node* Build(int l, int r)
{
if (l > r)return null;
int mid = (l + r) >> 1;
Node* cur = Creat(arr[mid]);
cur->lch = Build(l, mid - 1);
cur->rch = Build(mid + 1, r);
/*=*/PushUp(cur); return cur;
}
/*====================*/
Node* Merge(Node* ltree, Node* rtree)
{
if (ltree == null)return rtree;
if (rtree == null)return ltree;
PushDown(ltree); PushDown(rtree);
if (ltree->priority < rtree->priority)
{
rtree->lch = Merge(ltree, rtree->lch);
/*======*/PushUp(rtree); return rtree;
}
else
{
ltree->rch = Merge(ltree->rch, rtree);
/*======*/PushUp(ltree); return ltree;
}
}
/*====================*/
void Lower_Split(Node* cur, int index, Node*& ltree, Node*& rtree)//index留在rtree
{
if (cur == null)
{
ltree = rtree = null; return;
}
PushDown(cur);
if (cur->lch->siz + 1 < index)
{
Lower_Split(cur->rch, index - cur->lch->siz - 1, ltree, rtree);
/*================*/cur->rch = ltree; PushUp(cur); ltree = cur;
}
else
{
Lower_Split(cur->lch, index, ltree, rtree);
cur->lch = rtree; PushUp(cur); rtree = cur;
}
}
void Upper_Split(Node* cur, int index, Node*& ltree, Node*& rtree)//index留在ltree
{
if (cur == null)
{
ltree = rtree = null; return;
}
PushDown(cur);
if (cur->lch->siz < index)
{
Upper_Split(cur->rch, index - cur->lch->siz - 1, ltree, rtree);
/*================*/cur->rch = ltree; PushUp(cur); ltree = cur;
}
else
{
Upper_Split(cur->lch, index, ltree, rtree);
cur->lch = rtree; PushUp(cur); rtree = cur;
}
}
/*====================*/
void Clear(Node* cur)
{
if (cur != null)
{
Clear(cur->lch);
Clear(cur->rch);
delete cur;
}
}
/*====================*/
void Init(void)
{
root = Build(1, n);
/*操作*/
Clear(root); root = null;
}
}
Splay·权值树
template<class Type>
class Splay
{
public:
~Splay(void)
{
Clear(root);
delete null;
}
int size(void)
{
return count;
}
void clear(void)
{
Clear(root);
root = null;
}
bool empty(void)
{
return count == 0;
}
Type pre(Type val)
{
root = splay(FindPre(root, val));
return root->val;
}
Type nxt(Type val)
{
root = splay(FindNxt(root, val));
return root->val;
}
void erase(Type val)
{
count--; root = Delete(FindByValu(root, val));
}
void insert(Type val)
{
count++; root = splay(Insert(root, val));
}
int operator()(Type val)
{
root = splay(FindByValu(root, val));
return root->lch->siz + 1;
}
Type operator[](int rank)
{
root = splay(FindByRank(root, rank));
return root->val;
}
Type lower_bound(Type val)
{
root = splay(FindLower(root, val));
return root->val;
}
Type upper_bound(Type val)
{
root = splay(FindUpper(root, val));
return root->val;
}
private:
struct Node
{
int siz = 0;
Type val = Type();
Node* fa = NULL;
Node* lch = NULL;
Node* rch = NULL;
};
/*====================*/
typedef bool CHILD;
const CHILD LCH = true;
const CHILD RCH = false;
/*====================*/
int count = 0;
Node* null = new Node;
Node* root = null;
/*====================*/
CHILD Child(Node* cur)
{
Node* pre = cur->fa;
if (pre->lch == cur)
{
return LCH;
}
else
{
return RCH;
}
}
void PushUp(Node* cur)
{
cur->siz = cur->lch->siz + cur->rch->siz + 1;
}
void Del(Node* cur, Node* pre, CHILD WCH)
{
cur->fa = null;
if (WCH == LCH)pre->lch = null;
if (WCH == RCH)pre->rch = null;
}
void Add(Node* cur, Node* pre, CHILD WCH)
{
cur->fa = pre;
if (WCH == LCH)pre->lch = cur;
if (WCH == RCH)pre->rch = cur;
}
void LRotate(Node* cur)
{
Node* pre = cur->fa, * nxt = cur->lch, * anc = pre->fa;
CHILD WCH = Child(pre);
Del(nxt, cur, LCH); Del(cur, pre, RCH); Del(pre, anc, WCH);
Add(nxt, pre, RCH); Add(pre, cur, LCH); Add(cur, anc, WCH);
PushUp(pre); PushUp(cur);
}
void RRotate(Node* cur)
{
Node* pre = cur->fa, * nxt = cur->rch, * anc = pre->fa;
CHILD WCH = Child(pre);
Del(nxt, cur, RCH); Del(cur, pre, LCH); Del(pre, anc, WCH);
Add(nxt, pre, LCH); Add(pre, cur, RCH); Add(cur, anc, WCH);
PushUp(pre); PushUp(cur);
}
void Rotate(Node* cur)
{
if (Child(cur) == LCH)
{
RRotate(cur);
}
else
{
LRotate(cur);
}
}
void Clear(Node* cur)
{
if (cur != null)
{
Clear(cur->lch);
Clear(cur->rch);
delete cur;
}
}
Node* Creat(Type val)
{
Node* cur = new Node;
cur->lch = null;
cur->rch = null;
cur->fa = null;
cur->val = val;
cur->siz = 1;
return cur;
}
Node* splay(Node* cur)
{
while (true)
{
Node* pre = cur->fa;
if (cur->fa == null)break;
if (pre->fa == null)break;
CHILD CHpre = Child(pre);
CHILD CHcur = Child(cur);
if (CHpre == CHcur)
{
Rotate(pre); Rotate(cur); continue;
}
if (CHpre != CHcur)
{
Rotate(cur); Rotate(cur); continue;
}
}
if (cur->fa != null)Rotate(cur); return cur;
}
Node* Insert(Node* cur, Type val)
{
CHILD WCH = LCH; Node* pre = null;
while (cur != null)
{
if (val < cur->val)
{
pre = cur; cur = cur->lch; WCH = LCH;
}
else
{
pre = cur; cur = cur->rch; WCH = RCH;
}
}
cur = Creat(val); Add(cur, pre, WCH); return cur;
}
Node* Delete(Node* cur)
{
splay(cur);
Node* lch = cur->lch;
Node* rch = cur->rch;
delete cur; return Merge(lch, rch);
}
Node* Merge(Node* ltree, Node* rtree)
{
if (ltree == null)
{
rtree->fa = null; return rtree;
}
if (rtree == null)
{
ltree->fa = null; return ltree;
}
ltree->fa = null; rtree->fa = null;
if (ltree->siz < rtree->siz)
{
Node* cur = FindMax(ltree); splay(cur);
Add(rtree, cur, RCH); PushUp(cur); return cur;
}
else
{
Node* cur = FindMin(rtree); splay(cur);
Add(ltree, cur, LCH); PushUp(cur); return cur;
}
}
Node* FindByValu(Node* cur, Type val)
{
Node* res = null;
while (cur != null)
{
if (val == cur->val)
{
res = cur, cur = cur->lch;
}
else
{
if (val < cur->val)
{
cur = cur->lch;
}
else
{
cur = cur->rch;
}
}
}
return res;
}
Node* FindByRank(Node* cur, int rank)
{
while (cur != null)
{
if (cur->lch->siz + 1 == rank)
{
return cur;
}
else
{
if (cur->lch->siz < rank)
{
rank -= cur->lch->siz + 1;
cur = cur->rch;
}
else
{
cur = cur->lch;
}
}
}
return null;
}
Node* FindLower(Node* cur, Type val)
{
Node* res = null;
while (cur != null)
{
if (cur->val < val)
{
cur = cur->rch;
}
else
{
res = cur;
cur = cur->lch;
}
}
return res;
}
Node* FindUpper(Node* cur, Type val)
{
Node* res = null;
while (cur != null)
{
if (val < cur->val)
{
res = cur;
cur = cur->lch;
}
else
{
cur = cur->rch;
}
}
return res;
}
Node* FindMin(Node* cur)
{
while (cur->lch != null)
{
cur = cur->lch;
}
return cur;
}
Node* FindMax(Node* cur)
{
while (cur->rch != null)
{
cur = cur->rch;
}
return cur;
}
Node* FindPre(Node* cur, Type val)
{
Node* res = null;
while (cur != null)
{
if (cur->val < val)
{
res = cur;
cur = cur->rch;
}
else
{
cur = cur->lch;
}
}
return res;
}
Node* FindNxt(Node* cur, Type val)
{
Node* res = null;
while (cur != null)
{
if (val < cur->val)
{
res = cur;
cur = cur->lch;
}
else
{
cur = cur->rch;
}
}
return res;
}
};
珂朵莉树
template<class Type>
class Chtholly
{
public:
void init(int n, Type arr[])
{
for (int i = 1; i <= n; ++i)
{
tree.insert(Node(i, i, arr[i]));
}
}
void cover(int l, int r, Type val)
{
auto end = Split(r + 1), begin = Split(l);
for (auto it = begin; it != end; ++it)
{
/*
统计信息
*/
}
tree.erase(begin, end);
tree.insert(Node(l, r, val));
}
private:
struct Node
{
int l, r;
mutable Type val;
Node(int _l = 0, int _r = 0, Type _val = Type())
{
l = _l, r = _r, val = _val;
}
friend bool operator<(const Node& a, const Node& b)
{
return a.l < b.l;
}
};
/*====================*/
set<Node>tree;
/*====================*/
set<Node>::iterator Split(int pos)//lower
{
auto it = tree.lower_bound(Node(pos));
if (it != tree.end() && it->l == pos)return it;
--it; int l = it->l, r = it->r, val = it->val;
tree.erase(it); tree.insert(Node(l, pos - 1, val));
return tree.insert(Node(pos, r, val)).first;
}
};
树状数组
权值树状数组
class FenwickTree
{
public:
int size(void)
{
return tree[0];
}
void clear(void)
{
if (tree != NULL)
{
delete[] tree;
tree = NULL;
}
}
void init(int n)
{
this->n = n; m = 0;
tree = new int[n + 1];
for (int i = 0; i <= n; ++i)
{
tree[i] = 0;
}
while ((1 << (m + 1)) <= n)m++;
}
bool empty(void)
{
return tree[0] == 0;
}
void erase(int x)
{
tree[0]--;
while (x <= n)
{
tree[x] -= 1;
x += lowbit(x);
}
}
void insert(int x)
{
tree[0]++;
while (x <= n)
{
tree[x] += 1;
x += lowbit(x);
}
}
~FenwickTree(void)
{
clear();
}
int operator()(int valu)
{
valu--;
int rank = 0;
while (valu)
{
rank += tree[valu];
valu -= lowbit(valu);
}
return rank + 1;
}
int operator[](int rank)
{
int sum = 0, valu = 0;
for (int i = m; i >= 0; --i)
{
int temp = valu + (1 << i);
if (temp <= n && sum + tree[temp] < rank)
{
sum += tree[temp]; valu = temp;
}
}
return valu + 1;
}
private:
int n = 0, m = 0;
int* tree = NULL;
/*====================*/
int lowbit(int x) { return x & (-x); }
};
一维树状数组
template<class Type>
class FenwickTree
{
public:
Type ask(int pos)
{
Type res = Type();
while (pos)
{
res += tree[pos];
pos -= lowbit(pos);
}
return res;
}
void init(int n)
{
this->n = n;
tree = new Type[n + 1];
for (int i = 0; i <= n; ++i)
{
tree[i] = Type();
}
}
~FenwickTree(void)
{
delete[] tree;
}
void add(int pos, Type d)
{
while (pos <= n)
{
tree[pos] += d;
pos += lowbit(pos);
}
}
Type ask(int l, int r)
{
Type res = Type(); l--;
while (r > l)res += tree[r], r -= lowbit(r);
while (l > r)res -= tree[l], l -= lowbit(l);
return res;
}
private:
int n = 0;
Type* tree = NULL;
/*====================*/
int lowbit(int x) { return x & (-x); }
};
二维树状数组
template<class Type>
class FenwickTree
{
public:
~FenwickTree(void)
{
for (int i = 0; i <= n; ++i)
{
delete[] tree[i];
}
delete[] tree;
}
Type ask(int x, int y)
{
Type res = Type();
while (x)
{
int tempy = y;
while (tempy)
{
res += tree[x][tempy];
tempy -= lowbit(tempy);
}
x -= lowbit(x);
}
return res;
}
void init(int n, int m)
{
this->n = n;
this->m = m;
tree = new Type * [n + 1];
for (int i = 0; i <= n; ++i)
{
tree[i] = new Type[m + 1];
for (int j = 0; j <= m; ++j)
{
tree[i][j] = Type();
}
}
}
void add(int x, int y, Type d)
{
while (x <= n)
{
int tempy = y;
while (tempy <= m)
{
tree[x][tempy] += d;
tempy += lowbit(tempy);
}
x += lowbit(x);
}
}
Type ask(int x1, int y1, int x2, int y2)
{
return ask(x2, y2) - ask(x1 - 1, y2) - ask(x2, y1 - 1) + ask(x1 - 1, y1 - 1);
}
private:
int n = 0, m = 0;
Type** tree = NULL;
/*====================*/
int lowbit(int x) { return x & (-x); }
};
区间mex
class Range_MEX
{
public:
Range_MEX(int n, int arr[], int l, int r)
{
root = new int[n + 1];
tree = new Tree[4200000 + 10];
for (int i = 0; i <= n; ++i)root[i] = -1;
BuildZero(root[0], l, r);
for (int i = 1; i <= n; ++i)
{
BuildChain(root[i - 1], root[i], i, arr[i]);
}
}
int operator()(int l, int r)
{
return Ask(root[r], l);
}
~Range_MEX(void)
{
delete[] tree;
delete[] root;
}
private:
struct Tree
{
int idx;
int l, r;
int ls, rs;
Tree(void)
{
idx = 0;
l = 0, r = 0;
ls = -1, rs = -1;
}
};
/*====================*/
int * root;
Tree* tree; int cnt = -1;
/*====================*/
void PushUp(int cur)
{
tree[cur].idx = min(tree[tree[cur].ls].idx, tree[tree[cur].rs].idx);
}
/*====================*/
void BuildZero(int& cur, int l, int r)
{
if (cur == -1)cur = ++cnt;
/*====================*/
tree[cur].l = l, tree[cur].r = r;
if (l != r)
{
int mid = (l + r) >> 1;
BuildZero(tree[cur].ls, l, mid + 0);
BuildZero(tree[cur].rs, mid + 1, r);
}
}
void BuildChain(int& pre, int& cur, int idx, int val)
{
if (cur == -1)cur = ++cnt;
/*====================*/
tree[cur].l = tree[pre].l, tree[cur].r = tree[pre].r;
tree[cur].ls = tree[pre].ls, tree[cur].rs = tree[pre].rs;
if (tree[cur].l == tree[cur].r)
{
tree[cur].idx = idx;
}
else
{
int mid = (tree[cur].l + tree[cur].r) >> 1;
if (val <= mid)BuildChain(tree[pre].ls, tree[cur].ls = -1, idx, val);
if (mid < val) BuildChain(tree[pre].rs, tree[cur].rs = -1, idx, val);
PushUp(cur);
}
}
/*====================*/
int Ask(int& cur, int l)
{
if (tree[cur].l == tree[cur].r)return tree[cur].l;
if (tree[tree[cur].ls].idx < l)return Ask(tree[cur].ls, l);
if (tree[tree[cur].rs].idx < l)return Ask(tree[cur].rs, l);
return tree[cur].r + 1;
}
};
Hash_MAP
const int Base = 19260817;
class Hash_Map
{
public:
Hash_Map()
{
memset(head, -1, sizeof(head));
nxt.reserve(1e7);
key.reserve(1e7);
val.reserve(1e7);
}
lnt& operator[](lnt k)
{
int h = hash(k);
for (int i = head[h]; ~i; i = nxt[i])
{
if (key[i] == k)
{
return val[i];
}
}
nxt.push_back(head[h]);
key.push_back(k);
val.push_back(0);
head[h] = nxt.size() - 1;
return val.back();
}
lnt has_key(lnt k)
{
int h = hash(k);
for (int i = head[h]; ~i; i = nxt[i])
{
if (key[i] == k)
{
return true;
}
}
return false;
}
private:
int head[Base];
vector<int>nxt;
vector<lnt>key;
vector<lnt>val;
int hash(lnt k)
{
return k % Base;
}
};
线段树合并
Tree* Merge(Tree*& a, Tree*& b)
{
Tree* cur = NULL;
if (a == NULL)
{
cur = b; b = NULL; return cur;
}
if (b == NULL)
{
cur = a; a = NULL; return cur;
}
cur = new Tree(a->l, b->r);
if (a->l == b->r)
{
//do something
}
else
{
cur->ls = Merge(a->ls, b->ls);
cur->rs = Merge(a->rs, b->rs);
}
PushUp(cur); delete a; a = NULL; delete b; b = NULL; return cur;
}
李超线段树
const int N = 4e4 + 10;
const double INF = 1e9;
/*====================*/
typedef long long ll;
/*====================*/
struct Function
{
int id;
double k, b;
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
double operator()(double x)
{
return k * x + b;
}
Function(int _id = 0, int x1 = 1, int x2 = 2, int y1 = 1, int y2 = 2)
{
id = _id;
if (x1 == x2)
{
k = 0, b = max(y1, y2);
}
else
{
int d = gcd(abs(y1 - y2), abs(x1 - x2));
double dy = (y1 - y2) / d;
double dx = (x1 - x2) / d;
k = dy / dx; b = y1 - k * x1;
}
}
};
/*====================*/
struct Node
{
Function f;
int l = 0, r = 0;
};
/*====================*/
int idx[N];
Node node[N << 2];
/*====================*/
int ls(int p)
{
return p << 1;
}
int rs(int p)
{
return p << 1 | 1;
}
void Build(int p, int l, int r)
{
node[p].l = l, node[p].r = r;
if (node[p].l == node[p].r)
{
idx[l] = p; return;
}
else
{
int mid = (node[p].l + node[p].r) >> 1;
Build(ls(p), l, mid + 0);
Build(rs(p), mid + 1, r);
}
}
void PushDown(int p, Function f)
{
if (node[p].f.id == 0)
{
node[p].f = f;
}
else
{
int l = node[p].l, r = node[p].r;
int x = (node[p].l + node[p].r) >> 1;
if (l == r)
{
if (node[p].f(x) < f(x))
{
node[p].f = f;
}
else if (node[p].f(x) == f(x))
{
if (node[p].f.id > f.id)
{
node[p].f = f;
}
}
}
else
{
if (node[p].f.k < f.k)
{
if (node[p].f(x) < f(x))
{
PushDown(ls(p), node[p].f); node[p].f = f;
}
else if (node[p].f(x) == f(x))
{
PushDown(rs(p), f);
}
else if (node[p].f(x) > f(x))
{
PushDown(rs(p), f);
}
}
else if (node[p].f.k == f.k)
{
if (node[p].f.b < f.b)
{
node[p].f = f;
}
else if (node[p].f.b == f.b)
{
if (node[p].f.id > f.id)
{
node[p].f = f;
}
}
}
else if (node[p].f.k > f.k)
{
if (node[p].f(x) < f(x))
{
PushDown(rs(p), node[p].f); node[p].f = f;
}
else if (node[p].f(x) == f(x))
{
PushDown(ls(p), f);
}
else if (node[p].f(x) > f(x))
{
PushDown(ls(p), f);
}
}
}
}
}
void Add(int p, int l, int r, Function f)
{
if (l <= node[p].l && node[p].r <= r)
{
PushDown(p, f);
}
else
{
int mid = (node[p].l + node[p].r) >> 1;
if (l <= mid)Add(ls(p), l, r, f);
if (mid < r) Add(rs(p), l, r, f);
}
}
void Ask(int p, int x, double fx, int &id)
{
if (node[p].f.id != 0)
{
if (node[p].f(x) == fx)
{
if (node[p].f.id < id)
{
id = node[p].f.id;
}
}
else if (node[p].f(x) > fx)
{
fx = node[p].f(x);
id = node[p].f.id;
}
}
if (node[p].l != node[p].r)
{
int mid = (node[p].l + node[p].r) >> 1;
if (x <= mid)Ask(ls(p), x, fx, id);
if (mid < x) Ask(rs(p), x, fx, id);
}
}
/*====================*/
int main()
{
int n; cin >> n;
int lastans = 0;
Build(1, 1, MODX + 10);
for (int i = 1; i <= n; ++i)
{
int op; cin >> op;
if (op == 1)
{
static int id = 0;
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
x0 = (x0 + lastans - 1) % MODX + 1;
x1 = (x1 + lastans - 1) % MODX + 1;
y0 = (y0 + lastans - 1) % MODY + 1;
y1 = (y1 + lastans - 1) % MODY + 1;
Add(1, min(x0, x1), max(x0, x1), Function(++id, x0, x1, y0, y1));
}
else
{
int x; cin >> x; x = (x + lastans - 1) % MODX + 1;
lastans = 0; Ask(1, x, -INF, lastans);
cout << lastans << endl;
}
}
return 0;
}
Treap维护珂朵莉树
namespace Treap
{
struct Node
{
Range range;
int priority;
int lch, rch;
}node[N * 4];
/*====================*/
int null = -1;
int root = -1;
/*====================*/
int Creat(Range range)
{
static int cnt = 0; ++cnt;
node[cnt].lch = null;
node[cnt].rch = null;
node[cnt].priority = rand();
node[cnt].range = range;
return cnt;
}
/*====================*/
void PushUp(int cur)
{
node[cur].range.L = node[cur].range.l;
node[cur].range.R = node[cur].range.r;
node[cur].range.Sum = node[cur].range.sum();
if (node[cur].lch != null)
{
node[cur].range.L = node[node[cur].lch].range.L;
node[cur].range.Sum += node[node[cur].lch].range.Sum;
}
if (node[cur].rch != null)
{
node[cur].range.R = node[node[cur].rch].range.R;
node[cur].range.Sum += node[node[cur].rch].range.Sum;
}
}
void PushDown(int cur)
{
if (node[cur].range.lazy != 0)
{
if (node[cur].lch != null)
{
node[node[cur].lch].range.Maintain(node[cur].range.lazy);
}
if (node[cur].rch != null)
{
node[node[cur].rch].range.Maintain(node[cur].range.lazy);
}
node[cur].range.lazy = 0;
}
}
/*====================*/
int Merge(int ltree, int rtree)
{
if (ltree == null)return rtree;
if (rtree == null)return ltree;
PushDown(ltree); PushDown(rtree);
if (node[ltree].priority < node[rtree].priority)
{
node[rtree].lch = Merge(ltree, node[rtree].lch);
/*======*/PushUp(rtree); return rtree;
}
else
{
node[ltree].rch = Merge(node[ltree].rch, rtree);
/*======*/PushUp(ltree); return ltree;
}
}
/*====================*/
void Lower_Split(int cur, unt index, int& ltree, int& rtree)//index留在rtree
{
if (cur == null)
{
ltree = rtree = null; return;
}
PushDown(cur);
if (node[cur].range.r < index)
{
Lower_Split(node[cur].rch, index, ltree, rtree);
node[cur].rch = ltree; PushUp(cur); ltree = cur;
}
else
{
Lower_Split(node[cur].lch, index, ltree, rtree);
node[cur].lch = rtree; PushUp(cur); rtree = cur;
}
}
void Upper_Split(int cur, unt index, int& ltree, int& rtree)//index留在ltree
{
if (cur == null)
{
ltree = rtree = null; return;
}
PushDown(cur);
if (node[cur].range.l > index)
{
Upper_Split(node[cur].lch, index, ltree, rtree);
node[cur].lch = rtree; PushUp(cur); rtree = cur;
}
else
{
Upper_Split(node[cur].rch, index, ltree, rtree);
node[cur].rch = ltree; PushUp(cur); ltree = cur;
}
}
/*====================*/
void SplitL(int root, unt index, int& ltree, int& rtree)
{
int _temp, _ltree, _mtree, _rtree;
Upper_Split(root, index, _temp, _rtree);
Lower_Split(_temp, index, _ltree, _mtree);
unt l = node[_mtree].range.l;
unt r = node[_mtree].range.r;
unt val = node[_mtree].range.val;
if (l != index)
{
ltree = Merge(_ltree, Creat(Range(l, index - 1, val)));
rtree = Merge(Creat(Range(index + 0, r, val)), _rtree);
}
else
{
ltree = _ltree;
rtree = Merge(_mtree, _rtree);
}
}
void SplitR(int root, unt index, int& ltree, int& rtree)
{
int _temp, _ltree, _mtree, _rtree;
Upper_Split(root, index, _temp, _rtree);
Lower_Split(_temp, index, _ltree, _mtree);
unt l = node[_mtree].range.l;
unt r = node[_mtree].range.r;
unt val = node[_mtree].range.val;
if (r != index)
{
ltree = Merge(_ltree, Creat(Range(l, index + 0, val)));
rtree = Merge(Creat(Range(index + 1, r, val)), _rtree);
}
else
{
ltree = Merge(_ltree, _mtree);
rtree = _rtree;
}
}
}
数据类型
大数类
struct Bigint {
// representations and structures
string a; // to store the digits
int sign; // sign = -1 for negative numbers, sign = 1 otherwise
// constructors
Bigint() {} // default constructor
Bigint(string b) { (*this) = b; } // constructor for string
// some helpful methods
int size() { // returns number of digits
return a.size();
}
Bigint inverseSign() { // changes the sign
sign *= -1;
return (*this);
}
Bigint normalize(int newSign) { // removes leading 0, fixes sign
for (int i = a.size() - 1; i > 0 && a[i] == '0'; i--)
a.erase(a.begin() + i);
sign = (a.size() == 1 && a[0] == '0') ? 1 : newSign;
return (*this);
}
// assignment operator
void operator = (string b) { // assigns a string to Bigint
a = b[0] == '-' ? b.substr(1) : b;
reverse(a.begin(), a.end());
this->normalize(b[0] == '-' ? -1 : 1);
}
// conditional operators
bool operator < (const Bigint& b) const { // less than operator
if (sign != b.sign) return sign < b.sign;
if (a.size() != b.a.size())
return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
for (int i = a.size() - 1; i >= 0; i--) if (a[i] != b.a[i])
return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
return false;
}
bool operator == (const Bigint& b) const { // operator for equality
return a == b.a && sign == b.sign;
}
// mathematical operators
Bigint operator + (Bigint b) { // addition operator overloading
if (sign != b.sign) return (*this) - b.inverseSign();
Bigint c;
for (int i = 0, carry = 0; i < a.size() || i < b.size() || carry; i++) {
carry += (i < a.size() ? a[i] - 48 : 0) + (i < b.a.size() ? b.a[i] - 48 : 0);
c.a += (carry % 10 + 48);
carry /= 10;
}
return c.normalize(sign);
}
Bigint operator - (Bigint b) { // subtraction operator overloading
if (sign != b.sign) return (*this) + b.inverseSign();
int s = sign; sign = b.sign = 1;
if ((*this) < b) return ((b - (*this)).inverseSign()).normalize(-s);
Bigint c;
for (int i = 0, borrow = 0; i < a.size(); i++) {
borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
borrow = borrow >= 0 ? 0 : 1;
}
return c.normalize(s);
}
Bigint operator * (Bigint b) { // multiplication operator overloading
Bigint c("0");
for (int i = 0, k = a[i] - 48; i < a.size(); i++, k = a[i] - 48) {
while (k--) c = c + b; // ith digit is k, so, we add k times
b.a.insert(b.a.begin(), '0'); // multiplied by 10
}
return c.normalize(sign * b.sign);
}
Bigint operator / (Bigint b) { // division operator overloading
if (b.size() == 1 && b.a[0] == '0') b.a[0] /= (b.a[0] - 48);
Bigint c("0"), d;
for (int j = 0; j < a.size(); j++) d.a += "0";
int dSign = sign * b.sign; b.sign = 1;
for (int i = a.size() - 1; i >= 0; i--) {
c.a.insert(c.a.begin(), '0');
c = c + a.substr(i, 1);
while (!(c < b)) c = c - b, d.a[i]++;
}
return d.normalize(dSign);
}
Bigint operator % (Bigint b) { // modulo operator overloading
if (b.size() == 1 && b.a[0] == '0') b.a[0] /= (b.a[0] - 48);
Bigint c("0");
b.sign = 1;
for (int i = a.size() - 1; i >= 0; i--) {
c.a.insert(c.a.begin(), '0');
c = c + a.substr(i, 1);
while (!(c < b)) c = c - b;
}
return c.normalize(sign);
}
// output method
void print() {
if (sign == -1) putchar('-');
for (int i = a.size() - 1; i >= 0; i--) putchar(a[i]);
}
};
分数类
class Fraction
{
public:
Fraction(const Fraction& temp)
{
up = temp.up, dw = temp.dw;
}
Fraction(int _up = 0, int _dw = 1)
{
up = _up, dw = _dw; reduction();
}
int upval(void)
{
return up;
}
int dwval(void)
{
return dw;
}
double val(void)
{
return double(up) / double(dw);
}
friend Fraction operator+(const Fraction& a, const Fraction& b)
{
Fraction res;
res.dw = a.dw * b.dw;
res.up = a.up * b.dw + b.up * a.dw;
res.reduction(); return res;
}
friend Fraction operator-(const Fraction& a, const Fraction& b)
{
Fraction res;
res.dw = a.dw * b.dw;
res.up = a.up * b.dw - b.up * a.dw;
res.reduction(); return res;
}
friend Fraction operator*(const Fraction& a, const Fraction& b)
{
Fraction res;
res.dw = a.dw * b.dw;
res.up = a.up * b.up;
res.reduction(); return res;
}
friend Fraction operator/(const Fraction& a, const Fraction& b)
{
Fraction res;
res.dw = a.dw * b.up;
res.up = a.up * b.dw;
res.reduction(); return res;
}
friend bool operator<(const Fraction& a, const Fraction& b)
{
return (a.up * b.dw) < (b.up * a.dw);
}
friend bool operator==(const Fraction& a, const Fraction& b)
{
return (a.up == b.up) && (a.dw == b.dw);
}
friend bool operator>(const Fraction& a, const Fraction& b)
{
return (a.up * b.dw) > (b.up * a.dw);
}
friend bool operator<=(const Fraction& a, const Fraction& b)
{
return !(a > b);
}
friend bool operator!=(const Fraction& a, const Fraction& b)
{
return !(a == b);
}
friend bool operator>=(const Fraction& a, const Fraction& b)
{
return !(a < b);
}
void operator+=(const Fraction& x)
{
up = up * x.dw + x.up * dw;
dw = dw * x.dw;
reduction();
}
void operator-=(const Fraction& x)
{
up = up * x.dw - x.up * dw;
dw = dw * x.dw;
reduction();
}
void operator*=(const Fraction& x)
{
up = up * x.up;
dw = dw * x.dw;
reduction();
}
void operator/=(const Fraction& x)
{
up = up * x.dw;
dw = dw * x.up;
reduction();
}
private:
int up = 0, dw = 1;
/*====================*/
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
/*====================*/
void reduction(void)
{
int divisor = gcd(up, dw);
if (divisor != 0)
{
up /= divisor, dw /= divisor;
if (dw < 0)dw *= -1, up *= -1;
}
}
};
模数类
class Modulo
{
public:
int val(void)
{
return num;
}
Modulo(int x = 0)
{
num = x % MOD;
}
Modulo(const Modulo& temp)
{
num = temp.num;
}
friend Modulo operator+(const Modulo& a, const Modulo& b)
{
Modulo res;
res.num = (a.num + b.num) % res.MOD;
return res;
}
friend Modulo operator-(const Modulo& a, const Modulo& b)
{
Modulo res;
res.num = (a.num - b.num + res.MOD) % res.MOD;
return res;
}
friend Modulo operator*(const Modulo& a, const Modulo& b)
{
Modulo res;
res.num = (a.num * b.num) % res.MOD;
return res;
}
friend Modulo operator/(const Modulo& a, const Modulo& b)
{
Modulo res;
res.num = (a.num * res.inv(b.num)) % res.MOD;
return res;
}
friend bool operator< (const Modulo& a, const Modulo& b)
{
return a.num < b.num;
}
friend bool operator==(const Modulo& a, const Modulo& b)
{
return a.num == b.num;
}
friend bool operator> (const Modulo& a, const Modulo& b)
{
return a.num > b.num;
}
friend bool operator<=(const Modulo& a, const Modulo& b)
{
return a.num <= b.num;
}
friend bool operator!=(const Modulo& a, const Modulo& b)
{
return a.num != b.num;
}
friend bool operator>=(const Modulo& a, const Modulo& b)
{
return a.num >= b.num;
}
void operator+=(const Modulo& x)
{
num = (num + x.num) % MOD;
}
void operator-=(const Modulo& x)
{
num = (num - x.num + MOD) % MOD;
}
void operator*=(const Modulo& x)
{
num = (num * x.num) % MOD;
}
void operator/=(const Modulo& x)
{
num = (num * inv(x.num)) % MOD;
}
private:
int num = 0;
const int MOD = 998244353;
/*====================*/
int inv(int x)
{
return Pow(x, MOD - 2);
}
int Pow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
{
res = (res * a) % MOD;
}
b >>= 1, a = (a * a) % MOD;
}
return res;
}
};