本文最后更新于 144 天前，其中的信息可能已经有所发展或是发生改变。
三维前缀和
s[x2][y2][z2]-s[x1-1][y2][z2]-s[x2][y1-1][z2]-s[x2][y2][z1-1]+s[x1-1][y1-1][z2]+s[x1-1][y2][z1-1]+s[x2][y1-1][z1-1]-s[x1-1][y1-1][z1-1]
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
b[i][j][k] += b[i][j][k - 1];
for (int i = 1; i <= n; i++)
for (int k = 1; k <= n; k++)
for (int j = 1; j <= n; j++)
b[i][j][k] += b[i][j - 1][k];
for (int k = 1; k <= n; k++)
for (int j = 1; j <= n; j++)
for (int i = 1; i <= n; i++)
b[i][j][k] += b[i - 1][j][k];
int i, j, k, x, y, z;
std::cin >> i >> x >> j >> y >> k >> z;
std::cout << b[x][y][z] + b[i - 1][j - 1][z] + b[i - 1][y][k - 1] + b[x][j - 1][k - 1]
- b[x][y][k - 1] - b[x][j - 1][z] - b[i - 1][y][z] - b[i - 1][j - 1][k - 1] << '\n';
凸包直径 旋转卡壳
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const double pi = acos(-1.0);
const double eps = 1e-9;
// 判断 x 的大小，<0 返回 -1，>0 返回 1，==0 返回 0
int sgn(double x) {
if (fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
// 比较两个浮点数
int dcmp(double x, double y) {
if (fabs(x - y) < eps) return 0;
else return x < y ? -1 : 1;
}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator + (const Point& B) const { return Point(x + B.x, y + B.y); }
Point operator - (const Point& B) const { return Point(x - B.x, y - B.y); }
Point operator * (double k) const { return Point(x * k, y * k); }
Point operator / (double k) const { return Point(x / k, y / k); }
bool operator == (const Point& B) const {
return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
}
bool operator<(Point B) { return sgn(x - B.x) < 0 || sgn(x - B.x) == 0 && sgn(y - B.y) < 0; }
// 先按x再按y排序
};
typedef Point Vector;
class Geometry {
public:
static double Distance(const Point& A, const Point& B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
static double Dot(const Vector& A, const Vector& B) {
return A.x * B.x + A.y * B.y;
}
static int AngleJudge(const Vector& A, const Vector& B) {
return sgn(Dot(A, B));
}
static double Len(const Vector& A) {
return sqrt(Dot(A, A));
}
static double Len2(const Vector& A) {
return Dot(A, A);
}
static double Angle(const Vector& A, const Vector& B) {
return acos(Dot(A, B) / Len(A) / Len(B));
}
static double Cross(const Vector& A, const Vector& B) {
return A.x * B.y - A.y * B.x;
}
static double Area2(const Point& A, const Point& B, const Point& C) {
return Cross(B - A, C - A);
}
static double AreaTriangle(const Point& A, const Point& B, const Point& C) {
return Area2(A, B, C) / 2;
}
static Vector Rotate(const Vector& A, double rad) {
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
static Vector Normal(const Vector& A) {
double len = Len(A);
return Vector(-A.y / len, A.x / len);
}
static bool Parallel(const Vector& A, const Vector& B) {
return sgn(Cross(A, B)) == 0;
}
};
int n, m;
int sta[N], top; // 将凸包上的节点编号存在栈里，第一个和最后一个节点编号相同
Point a[N], ch[N];
ll pf(ll x) { return x * x; }
ll dis(int p, int q) { return pf(ch[p].x - ch[q].x) + pf(ch[p].y - ch[q].y); }
ll sqr(int p, int q, int y) {
return abs(Geometry::Cross((ch[q] - ch[p]), (ch[y] - ch[q])));
}
int Convex_hull(Point* p, int n, Point* ch) { // ch放凸包顶点，返回值是顶点个数
n = unique(p, p + n) - p; // 去重
sort(p, p + n);
int v = 0;
for (int i = 0; i < n; i++) {
while (v > 1 && sgn(Geometry::Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
v--;
ch[v++] = p[i];
}
int j = v;
// 求上凸包
for (int i = n - 2; i >= 0; i--) {
while (v > j && sgn(Geometry::Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
v--;
ch[v++] = p[i];
}
if (n > 1) v--;
return v;
}
ll mx;
void get_longest() { // 求凸包直径
mx = 0;
int j = 3;
if (top < 3) {
mx = dis(sta[1], sta[2]);
return;
}
for (int i = 1; i <= top; ++i) {
while (sqr(sta[i], sta[i + 1], sta[j]) <=
sqr(sta[i], sta[i + 1], sta[j % top + 1]))
j = j % top + 1;
mx = max(mx, max(dis(sta[i + 1], sta[j]), dis(sta[i], sta[j])));
}
}
void solve() {
top = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
int v = Convex_hull(a, n, ch); // 先求凸包
for (int i = 1; i <= v; i++) sta[++top] = i - 1; // sta存储点的下标
sta[v + 1] = 0; // 封闭图形，多放的是第一个点的下标
get_longest(); // 求凸包直径，该题输出直径的平方
cout << mx << '\n';
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _T = 1;
// cin >> _T;
while (_T--)
solve();
return 0;
}
替罪羊树
写一种能够满足以下操作的数据结构：
- 插入一个数 $x$。
- 删除一个数 $x$（若有多个相同的数，应只删除一个）。
- 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
- 查询数据结构中排名为 $x$ 的数。
- 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
- 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。
对于操作 3,5,6，不保证当前数据结构中存在数 $x$。
对于操作 $3,4,5,6$ 每行输出一个数，表示对应答案。
对于 $100%$ 的数据，$1\le n \le 10^5$，$|x| \le 10^7$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const double alpha = 0.75; // 不平衡率
struct Node {
int ls, rs;
int val;
int tot; // 当前子树占用的空间数量，包括实际存储的节点和被标记删除的节点
int size; // 子树上实际存储数字的数量
bool del; // del=1 表示这个节点存有数字，=0 表示被删除
}t[N];
int order[N], cnt; // order[] 记录拍平后的结果，即那些存有数字的节点
int tree_stack[N], top = 0; // 用栈来回收和分配可用的节点
int root = 0; // 重建过程中根节点会变化
void inorder(int u) { // 中序遍历，“拍平”摧毁这棵子树
if (!u) return;
inorder(t[u].ls);
if (t[u].del) order[++cnt] = u;
else tree_stack[++top] = u;
inorder(t[u].rs);
}
void initnode(int u) {
t[u].ls = t[u].rs = 0;
t[u].size = t[u].tot = t[u].del = 1;
}
void update(int u) {
t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}
void build(int l, int r, int& u) {
int mid = (l + r) >> 1;
u = order[mid];
if (l == r) { initnode(u); return; }
if (l < mid) build(l, mid - 1, t[u].ls);
if (l == mid) t[u].ls = 0;
build(mid + 1, r, t[u].rs);
update(u);
}
void rebuild(int& u) {
cnt = 0;
inorder(u);
if (cnt) build(1, cnt, u);
else u = 0;
}
bool notbalance(int u) {
if ((double)t[u].size * alpha <= (double)max(t[t[u].ls].size, t[t[u].rs].size))
return true;
return false;
}
void Insert(int& u, int x) {
if (!u) {
u = tree_stack[top--];
t[u].val = x;
initnode(u);
return;
}
t[u].size++;
t[u].tot++;
if (t[u].val >= x) Insert(t[u].ls, x);
else Insert(t[u].rs, x);
if (notbalance(u)) rebuild(u);
}
int Rank(int u, int x) {
if (u == 0) return 0;
if (x > t[u].val) return t[t[u].ls].size + t[u].del + Rank(t[u].rs, x);
return Rank(t[u].ls, x);
}
int kth(int k) {
int u = root;
while (u) {
if (t[u].del && t[t[u].ls].size + 1 == k) return t[u].val;
else if (t[t[u].ls].size >= k) u = t[u].ls;
else {
k -= t[t[u].ls].size + t[u].del;
u = t[u].rs;
}
}
return t[u].val;
}
void del_k(int& u, int k) {
t[u].size--;
if (t[u].del && t[t[u].ls].size + 1 == k) {
t[u].del = 0;
return;
}
if (t[t[u].ls].size + t[u].del >= k) del_k(t[u].ls, k);
else del_k(t[u].rs, k - t[t[u].ls].size - t[u].del);
}
void del(int x) {
del_k(root, Rank(root, x) + 1);
if (t[root].tot * alpha >= t[root].size)
rebuild(root);
}
/*
// 测试：打印二叉树
void print_tree(int u) {
if(u) {
cout << "v = " << t[u].val << ", l = " << t[u].ls << ", r = " << t[u].rs << '\n';
print_tree(t[u].ls);
print_tree(t[u].rs);
}
}
*/
int main()
{
for (int i = N - 1; i >= 1; i--) tree_stack[++top] = i;
int q; cin >> q;
while (q--) {
int op, x; cin >> op >> x;
switch (op) {
case 1: Insert(root, x); break;
case 2: del(x); break;
case 3: cout << Rank(root, x) + 1 << '\n'; break;
case 4: cout << kth(x) << '\n'; break;
case 5: cout << kth(Rank(root, x)) << '\n'; break;
case 6: cout << kth(Rank(root, x + 1) + 1) << '\n'; break;
}
// cout << ">>" << '\n'; print_tree(root); << cout << '<<\n'; // 打印二叉树测试
}
}
STL 代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
int q; cin >> q;
while (q--) {
int op, x; cin >> op >> x;
if(op == 1) v.insert(lower_bound(v.begin(), v.end(), x), x);
if(op == 2) v.erase(lower_bound(v.begin(), v.end(), x));
if(op == 3) cout << lower_bound(v.begin(), v.end(), x) - v.begin() + 1 << '\n';
if(op == 4) cout << v[x - 1] << '\n';
if(op == 5) cout << v[lower_bound(v.begin(), v.end(), x) - v.begin() - 1] << '\n';
if(op == 6) cout << v[upper_bound(v.begin(), v.end(), x) - v.begin()] << '\n';
}
}
莫队
普通莫队
现有数列 $A_1,A_2,\ldots,A_N$，$Q$ 个询问 $(L_i,R_i)$，询问 $A_{L_i} ,A_{L_i+1},\ldots,A_{R_i}$ 是否互不相同。
第一行，两个整数$N,Q$。
第二行，$N$ 个整数$A_1, A_2, \ldots , A_N$。
接下来 $Q$ 行，每行两个整数 $L_i,R_i$。
对每个询问输出一行，Yes 或 No。
数据范围 $1 \le N,Q \le 10^5$，$1 \le A_i \le N$，$1 \le L_i \le R_i \le N$。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[N], cnt[N], ans[N], tot;
struct Q {
int l, r, id;
};
int pos[N];
void add(int x) {
if (!cnt[a[x]]) tot++;
cnt[a[x]]++;
}
void del(int x) {
cnt[a[x]]--;
if (!cnt[a[x]]) tot--;
}
void solve() {
cin >> n >> m;
int len = sqrt(n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[i] = (i - 1) / len + 1;
}
vector<Q> v(m);
for (int i = 0; i < m; i++) {
cin >> v[i].l >> v[i].r;
v[i].id = i;
}
sort(v.begin(), v.end(), [&](Q a, Q b) {
if (pos[a.l] == pos[b.l]) {
if (pos[a.l] & 1) return a.r > b.r;
return a.r < b.r;
}
return pos[a.l] < pos[b.l];
});
int l = 1, r = 0;
for (int i = 0; i < m; i++) {
while (l > v[i].l) add(--l);
while (r < v[i].r) add(++r);
while (l < v[i].l) del(l++);
while (r > v[i].r) del(r--);
ans[v[i].id] = (tot == v[i].r - v[i].l + 1);
}
for (int i = 0; i < m; i++) {
if (ans[i]) cout << "Yes\n";
else cout << "No\n";
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _T = 1;
// cin >> _T;
while (_T--)
solve();
return 0;
}
带修改莫队
增加一个时间维度，分块长度 $len=n^{2/3}$
题目大意：给你一个序列，M 个操作，有两种操作：
- 修改序列上某一位的数字
- 询问区间 $[l,r]$ 中数字的种类数（多个相同的数字只算一个）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n, m;
struct Q { // 记录查询操作，t为这次查询之前经过的修改次数
int id, t, l, r;
} q[N];
struct RE { // 记录修改操作
int p, c;
} r[N];
int cnt[N];
int a[N], pos[N], ans[N], tot;
int qcnt, rcnt;
inline void add(int x) {
if (cnt[x] == 0) tot++;
cnt[x]++;
}
inline void del(int x) {
if (cnt[x] == 1) tot--;
cnt[x]--;
}
inline void solve() {
cin >> n >> m;
int len = pow(n, 2.0 / 3);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[i] = (i - 1) / len + 1;
}
for (int i = 0; i < m; i++) {
char ch;
int x, y;
cin >> ch >> x >> y;
if (ch == 'Q') {
q[++qcnt] = { qcnt, rcnt, x, y };
}
else {
r[++rcnt] = { x, y };
}
}
sort(q + 1, q + 1 + qcnt, [&](Q a, Q b) {
if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
if (pos[a.r] != pos[b.r]) return pos[a.r] < pos[b.r];
return a.t < b.t;
});
int L = 1, R = 0, last = 0; // last记录最后一次修改的时间点
for (int i = 1; i <= qcnt; i++) {
while (R < q[i].r) add(a[++R]);
while (R > q[i].r) del(a[R--]);
while (L > q[i].l) add(a[--L]);
while (L < q[i].l) del(a[L++]);
// 时间维度的变化
while (last < q[i].t) { // 进行修改
last++;
if (L <= r[last].p && r[last].p <= R) {
add(r[last].c);
del(a[r[last].p]);
}
swap(a[r[last].p], r[last].c); // 更新，回退时会用到
}
while (last > q[i].t) { // 回退修改
if (L <= r[last].p && r[last].p <= R) {
add(r[last].c);
del(a[r[last].p]);
}
swap(a[r[last].p], r[last].c);
last--; // 先修改再last--
}
ans[q[i].id] = tot;
}
for (int i = 1; i <= qcnt; i++) {
cout << ans[i] << '\n';
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _T = 1;
// cin >> _T;
while (_T--)
solve();
return 0;
}
树上莫队
- 给定 $n$ 个结点的树，每个结点有一种颜色。
- $m$ 次询问，每次询问给出 $u,v$，回答 之$u,v$间的路径上的结点的不同颜色数。
- $1 \leq n \leq 4*10^4,1 \leq m \leq 10^5$，颜色是不超过 $2×10^9$ 的非负整数。
#include <bits/stdc++.h>
const int N = 1e5 + 5;
int n, m;
int a[N], col[N], ans[N];
int tot, pos1[N], pos2[N], pos[N]; // pos1为某点第一次出现的位置（进入dfs序），pos2为第二次的位置（离开dfs序）
int cnt[N];
std::vector<int> ed[N];
bool vis[N];
int idx[N];
struct Q {
int l, r, id, lca;
};
int fa[N][20], deep[N];
inline void DFS(int x, int f) {
deep[x] = deep[f] + 1;
fa[x][0] = f;
for (int i = 1; (1 << i) <= deep[x]; i++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i : ed[x])
if (i != f)
DFS(i, x);
}
inline int lca(int x, int y) {
if (deep[x] < deep[y]) std::swap(x, y);
for (int i = 16; i >= 0; i--)
if (deep[x] - (1 << i) >= deep[y])
x = fa[x][i];
if (x == y) return x;
for (int i = 16; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
inline void update(int u, bool op) {
if (op)
u = idx[u];
if (!vis[u]) {
cnt[a[u]]++;
if (cnt[a[u]] == 1) tot++;
}
else {
if (cnt[a[u]] == 1) tot--;
cnt[a[u]]--;
}
vis[u] ^= 1;
}
signed main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
col[i] = a[i]; // 用来排序
}
std::sort(col + 1, col + 1 + n);
auto getid = [](int c) -> int {
return std::lower_bound(col + 1, col + 1 + n, c) - (col + 1); // 对颜色进行离散化
};
for (int i = 1; i <= n; i++) {
a[i] = getid(a[i]);
}
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
ed[u].push_back(v);
ed[v].push_back(u);
}
std::vector<int> d;
std::vector<bool> vis(n + 1, 0);
auto dfs = [&](auto&& self, int u, int f) -> void {
d.push_back(u);
for (int v : ed[u]) {
if (v == f || vis[v]) continue;
vis[v] = 1;
self(self, v, u);
}
d.push_back(u);
};
dfs(dfs, 1, 0); // 获取dfs序
int len = sqrt(n << 1);
for (int i = 0; i < (n << 1); i++) {
if (!pos1[d[i]]) {
pos1[d[i]] = i + 1;
}
else {
pos2[d[i]] = i + 1;
}
pos[i + 1] = i / len + 1;
idx[i + 1] = d[i];
}
DFS(1, 0); // lca初始化
std::vector<Q> q(m);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
if (pos1[u] > pos1[v]) std::swap(u, v);
int F = lca(u, v);
if (F == u || F == v) {
q[i].l = pos1[u];
q[i].r = pos1[v];
q[i].lca = 0;
}
else {
q[i].l = pos2[u];
q[i].r = pos1[v];
q[i].lca = F; // dfs序中没有lca，要加上它带来的更新
}
q[i].id = i;
}
std::sort(q.begin(), q.end(), [&](Q a, Q b) {
if (pos[a.l] == pos[b.l]) return a.r < b.r;
return pos[a.l] < pos[b.l];
});
int l = 1, r = 0;
for (int i = 0; i < m; i++) {
while (l < q[i].l) update(l++, 1);
while (l > q[i].l) update(--l, 1);
while (r > q[i].r) update(r--, 1);
while (r < q[i].r) update(++r, 1);
if (q[i].lca) {
update(q[i].lca, 0);
}
ans[q[i].id] = tot;
if (q[i].lca) {
update(q[i].lca, 0);
}
}
for (int i = 0; i < m; i++) std::cout << ans[i] << std::endl;
}
扫描线
int lazy[N << 3]; // 标记了这条线段出现的次数
double s[N << 3];
struct node1 {
double l, r;
double sum;
} cl[N << 3]; // 线段树
struct node2 {
double x, y1, y2;
int flag;
} p[N << 3]; // 坐标
// 定义sort比较
bool cmp(node2 a, node2 b) { return a.x < b.x; }
// 上传
void pushup(int rt) {
if (lazy[rt] > 0)
cl[rt].sum = cl[rt].r - cl[rt].l;
else
cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;
}
// 建树
void build(int rt, int l, int r) {
if (r - l > 1) {
cl[rt].l = s[l];
cl[rt].r = s[r];
build(rt * 2, l, (l + r) / 2);
build(rt * 2 + 1, (l + r) / 2, r);
pushup(rt);
} else {
cl[rt].l = s[l];
cl[rt].r = s[r];
cl[rt].sum = 0;
}
return;
}
// 更新
void update(int rt, double y1, double y2, int flag) {
if (cl[rt].l == y1 && cl[rt].r == y2) {
lazy[rt] += flag;
pushup(rt);
return;
} else {
if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);
if (cl[rt * 2 + 1].l < y2)
update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);
pushup(rt);
}
}
void solve() {
int temp = 1, n;
double x1, y1, x2, y2, ans;
cin >> n;
ans = 0;
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
p[i].x = x1;
p[i].y1 = y1;
p[i].y2 = y2;
p[i].flag = 1;
p[i + n].x = x2;
p[i + n].y1 = y1;
p[i + n].y2 = y2;
p[i + n].flag = -1;
s[i + 1] = y1;
s[i + n + 1] = y2;
}
sort(s + 1, s + (2 * n + 1)); // 离散化
sort(p, p + 2 * n, cmp); // 把矩形的边的横坐标从小到大排序
build(1, 1, 2 * n); // 建树
memset(lazy, 0, sizeof(lazy));
update(1, p[0].y1, p[0].y2, p[0].flag);
for (int i = 1; i < 2 * n; i++) {
ans += (p[i].x - p[i - 1].x) * cl[1].sum;
update(1, p[i].y1, p[i].y2, p[i].flag);
}
cout << ans << '\n';
}
分层图
给定一个带权无向图，求 $s$ 到 $t$ 的最短路，其中可以令路径上最多 $k \leq 10$ 条道路花费为 $0$。
#include <bits/stdc++.h>
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int n, m, k, s, t;
std::cin >> n >> m >> k >> s >> t;
std::vector<std::vector<std::pair<int, int>>> ed(n * (k + 1));
for (int i = 0; i < m; i++) {
int a, b, c;
std::cin >> a >> b >> c;
for (int j = 0; j <= k; j++) {
int u = a + n * j, v = b + n * j;
ed[u].push_back({v, c});
ed[v].push_back({u, c});
if (j < k) {
ed[u].push_back({v + n, 0});
ed[v].push_back({u + n, 0});
}
}
}
std::vector<bool> vis(n * (k + 1), false);
std::vector<int> dis(n * (k + 1), 1e9);
auto dijkstra = [&](int s) -> void {
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
q.push({0, s});
dis[s] = 0;
while (q.size()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto e : ed[u]) {
int v = e.first, w = e.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
};
dijkstra(s);
int ans = 1e9;
for (int i = 0; i <= k; i++) {
ans = std::min(ans, dis[t + n * i]);
}
std::cout << ans << '\n';
}
线性判定排列逆序数的奇偶性
bool parity = n & 1;
for (int i : p) if (~i) {
for (int j = i; ~j; ) {
std::tie(j, p[j]) = std::tuple{p[j], -1};
}
parity ^= 1;
}
tuple
#include <tuple>
auto t = std::make_tuple(1, 2.5, "Hello");
// get 获取元素
auto t = std::make_tuple(1, 2.5, "Hello");
int i = std::get<0>(t); // 1
double d = std::get<1>(t); // 2.5
const char* s = std::get<2>(t); // "Hello"
// tie 解包获取元素
int i;
double d;
const char* s;
auto t = std::make_tuple(1, 2.5, "Hello");
std::tie(i, d, s) = t;
// size 获取size
auto t = std::make_tuple(1, 2.5, "Hello");
constexpr size_t size = std::tuple_size<decltype(t)>::value; // 3
// tuple_element 获取某个元素的类型
auto t = std::make_tuple(1, 2.5, "Hello");
using FirstType = std::tuple_element<0, decltype(t)>::type; // int
using SecondType = std::tuple_element<1, decltype(t)>::type; // double
// tuple_cat 连接多个tuple
auto t1 = std::make_tuple(1, 2.5);
auto t2 = std::make_tuple("Hello", 'a');
auto t3 = std::tuple_cat(t1, t2); // t3 is std::tuple<int, double, const char*, char>
// apply 将tuple中的元素作为参数传递给一个函数
void print(int i, double d, const char* s) {
std::cout << i << ", " << d << ", " << s << std::endl;
}
auto t = std::make_tuple(1, 2.5, "Hello");
std::apply(print, t); // 1, 2.5, Hello
// for_each + index_sequence 遍历并使用元素
template<typename Tuple, std::size_t... I>
void print_tuple(const Tuple& t, std::index_sequence<I...>) {
((std::cout << (I == 0 ? "" : ", ") << std::get<I>(t)), ...);
std::cout << std::endl;
}
template<typename... Args>
void print_tuple(const std::tuple<Args...>& t) {
print_tuple(t, std::index_sequence_for<Args...>{});
}
int main() {
auto t = std::make_tuple(1, 2.5, "Hello");
print_tuple(t); // 1, 2.5, Hello
return 0;
}
预处理组合数
for (int i = 0; i <= 5000; i++) {
for (int j = 0; j <= i; j++) {
if (!j) C[i][j] = 1;
else C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
C[i][j] %= mod;
}
}
防爆模乘
以 $O(1)$ 计算 $a \cdot b % p$ ，由于不取模，常数比 int128 更小。其中 $1 \leq a,b,p \leq 10^{18}$。
int mul(int a, int b, int m) {
int r = a * b - m * (int)(1.L / m * a * b);
return r - m * (r >= m) + m * (r < 0);
}
jiangly 取模运算+组合数板子
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res {1};
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MInt {
i64 x;
constexpr MInt() : x {0} {}
constexpr MInt(i64 x) : x {norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
if (getMod() < (1ULL << 31)) {
x = x * rhs.x % int(getMod());
} else {
x = mul(x, rhs.x, getMod());
}
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
friend constexpr bool operator<(MInt lhs, MInt rhs) {
return lhs.val() < rhs.val();
}
};
template<>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;
struct Comb {
int n;
std::vector<Z> _fac;
std::vector<Z> _invfac;
std::vector<Z> _inv;
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
m = std::min<i64>(m, Z::getMod() - 1);
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Z fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Z invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Z inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Z binom(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
} comb;