模板
树状数组 1：
支持单点加和，单点修改，区间求和，区间求最大值，时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // 根据数据范围调整，假设n <= 1e5
const ll INF = 1LL << 60; // 用于最大值的初始负无穷，防止溢出
ll tree_sum[MAXN * 4]; // 线段树数组，维护范围和
ll tree_max[MAXN * 4]; // 线段树数组，维护范围最大值
int n; // 数组大小
// 构建线段树，初始值从数组a[1..n]中读取
// 参考文档中的build函数，用于初始化sum和maxx[[6]][doc_6]
void build(int o, int l, int r, ll a[]) {
if (l == r) {
tree_sum[o] = a[l]; // 叶节点：和等于值本身
tree_max[o] = a[l]; // 叶节点：最大值等于值本身
return;
}
int mid = (l + r) >> 1; // 取中点
build(o * 2, l, mid, a); // 递归左子树
build(o * 2 + 1, mid + 1, r, a); // 递归右子树
tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1]; // 上推：和为子树和之和
tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]); // 上推：最大值为子树最大值之max
}
// op3: 单点加k - 在位置pos加上val（支持负数，相当于减）
void update_add(int o, int l, int r, int pos, ll val) {
if (l == r) {
tree_sum[o] += val; // 叶节点：和增加val
tree_max[o] += val; // 叶节点：最大值增加val
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update_add(o * 2, l, mid, pos, val); // 向左子树递归
else update_add(o * 2 + 1, mid + 1, r, pos, val); // 向右子树递归
tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1]; // 上推和
tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]); // 上推最大值
}
// op4: 单点修改为k - 将位置pos的值设为val
// 参考文档中的update函数，用于单点设置值[[2]][doc_2][[6]][doc_6]
void update_set(int o, int l, int r, int pos, ll val) {
if (l == r) {
tree_sum[o] = val; // 叶节点：和设为val
tree_max[o] = val; // 叶节点：最大值设为val
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update_set(o * 2, l, mid, pos, val);
else update_set(o * 2 + 1, mid + 1, r, pos, val);
tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1]; // 上推和
tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]); // 上推最大值
}
// op1: 范围求和 - 查询[lq, rq]的和
// 参考文档中的query2函数，用于范围sum查询[[2]][doc_2]
ll query_sum(int o, int l, int r, int lq, int rq) {
if (lq > r || rq < l) return 0; // 无交集，返回0
if (lq <= l && r <= rq) return tree_sum[o]; // 完全覆盖，返回节点和
int mid = (l + r) >> 1;
return query_sum(o * 2, l, mid, lq, rq) + query_sum(o * 2 + 1, mid + 1, r, lq, rq); // 递归求子树和并相加
}
// op2: 范围求最大值 - 查询[lq, rq]的最大值
// 参考文档中的query1函数，用于范围max查询[[2]][doc_2]
ll query_max(int o, int l, int r, int lq, int rq) {
if (lq > r || rq < l) return -INF; // 无交集，返回负无穷
if (lq <= l && r <= rq) return tree_max[o]; // 完全覆盖，返回节点最大值
int mid = (l + r) >> 1;
return max(query_max(o * 2, l, mid, lq, rq), query_max(o * 2 + 1, mid + 1, r, lq, rq)); // 递归求子树最大值并取max
}
int main() {
// 示例使用（详见下方说明）
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
ll a[MAXN];
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n, a); // 构建树
int q;
cin >> q;// 查询数量
while (q--) {
int op;
cin >> op;
if (op == 1) { // 区间求和
int l, r;
cin >> l >> r;
cout << query_sum(1, 1, n, l, r) << endl;
} else if (op == 2) { // 区间求最大值
int l, r;
cin >> l >> r;
cout << query_max(1, 1, n, l, r) << endl;
} else if (op == 3) { // 单点加值
int pos;
cin >> pos;
ll val;
cin >> val;
update_add(1, 1, n, pos, val);
} else if (op == 4) { // 单点修改值
int pos;
cin >> pos;
ll val;
cin >> val;
update_set(1, 1, n, pos, val);
}
}
return 0;
}树状数组 2：
支持区间求和及区间加值，时间复杂度
#include <bits/stdc++.h>
using namespace std;
/*
说明：
- 本程序用两个树状数组（BIT1、BIT2）实现：
1) 区间加法：对 [l, r] 加 k
2) 区间求和：求 [l, r] 之和
- 公式（经典做法）：
对 [l, r] 加 k 等价于：
BIT1 加： add(BIT1, l, k), add(BIT1, r+1, -k)
BIT2 加： add(BIT2, l, k*(l-1)), add(BIT2, r+1, -k*r)
前缀和 prefix_sum(x) = sum(BIT1, x) * x - sum(BIT2, x)
区间和 range_sum(l, r) = prefix_sum(r) - prefix_sum(l-1)
- 下标统一为 1..n（1-based）
- 值域使用 long long
*/
// 全局变量：n 为数组大小，q 为操作数
int n, q;
vector<long long> BIT1, BIT2; // 两棵树状数组，大小开到 n+2
// 低位操作
inline int lowbit(int x) { return x & -x; }
// 在 BIT 上做单点增加：BIT[idx] += delta（延伸到后继节点）
void add(vector<long long>& BIT, int idx, long long delta) {
for (; idx <= n; idx += lowbit(idx)) {
BIT[idx] += delta;
}
}
// 求 BIT 的前缀和：sum(BIT, idx) = BIT[1] + ... + BIT[idx]
long long sum(const vector<long long>& BIT, int idx) {
long long res = 0;
for (; idx > 0; idx -= lowbit(idx)) {
res += BIT[idx];
}
return res;
}
// 对区间 [l, r] 每个元素都加上 k
void range_add(int l, int r, long long k) {
if (l > r) return;
// BIT1
add(BIT1, l, k);
if (r + 1 <= n) add(BIT1, r + 1, -k);
// BIT2
add(BIT2, l, k * (l - 1));
if (r + 1 <= n) add(BIT2, r + 1, -k * r);
}
// 求前缀和：a[1] + ... + a[x]
long long prefix_sum(int x) {
if (x <= 0) return 0;
long long s1 = sum(BIT1, x);
long long s2 = sum(BIT2, x);
return s1 * x - s2;
}
// 求区间和：a[l] + ... + a[r]
long long range_sum(int l, int r) {
if (l > r) return 0;
return prefix_sum(r) - prefix_sum(l - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 输入格式：
// n q
// a1 a2 ... an
// 之后 q 行操作：
// 1 l r 查询区间和
// 2 l r k 区间加 k
if (!(cin >> n >> q)) return 0;
BIT1.assign(n + 2, 0);
BIT2.assign(n + 2, 0);
// 读取初始数组，并用区间加的形式构建
for (int i = 1; i <= n; ++i) {
long long x; cin >> x;
// 等价于对 [i, i] 加 x
range_add(i, i, x);
}
// 处理操作
for (int i = 0; i < q; ++i) {
int op; cin >> op;
if (op == 1) {
int l, r; cin >> l >> r;
cout << range_sum(l, r) << '\n';
} else if (op == 2) {
int l, r; long long k; cin >> l >> r >> k;
range_add(l, r, k);
}
// 其他 op 值忽略（或可加入校验）
}
return 0;
}线段树 1：
支持区间求和，区间求最大值，区间加值，区间修改，时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100010; // n的最大值+10
const ll INF = 1LL << 60; // 用于最大值查询的负无穷（比-1e18小）
ll a[MAXN]; // 初始数组
ll tree_sum[MAXN * 4]; // 线段树存储区间和
ll tree_max[MAXN * 4]; // 线段树存储区间最大值
ll lazy_add[MAXN * 4]; // 懒惰加法标记
ll lazy_set[MAXN * 4]; // 懒惰赋值标记（-1表示无赋值）
// 构建线段树
void build(int o, int l, int r) {
if (l == r) { // 叶子节点
tree_sum[o] = a[l];
tree_max[o] = a[l];
return;
}
int mid = (l + r) >> 1; // 等同于/2
build(o * 2, l, mid);
build(o * 2 + 1, mid + 1, r);
tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1]; // 上推和
tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]); // 上推最大值
}
// 下推懒惰标记（先处理赋值，再处理加法）
void pushdown(int o, int l, int r) {
int mid = (l + r) >> 1;
if (lazy_set[o] != -1) { // 有赋值标记，优先应用（重置加法）
// 应用到左子树
tree_sum[o * 2] = lazy_set[o] * (mid - l + 1);
tree_max[o * 2] = lazy_set[o];
lazy_set[o * 2] = lazy_set[o];
lazy_add[o * 2] = 0; // 重置子树加法
// 应用到右子树
tree_sum[o * 2 + 1] = lazy_set[o] * (r - mid);
tree_max[o * 2 + 1] = lazy_set[o];
lazy_set[o * 2 + 1] = lazy_set[o];
lazy_add[o * 2 + 1] = 0;
// 清空当前标记
lazy_set[o] = -1;
lazy_add[o] = 0;
}
if (lazy_add[o] != 0) { // 有加法标记
// 应用到左子树
tree_sum[o * 2] += lazy_add[o] * (mid - l + 1);
tree_max[o * 2] += lazy_add[o];
lazy_add[o * 2] += lazy_add[o];
// 应用到右子树
tree_sum[o * 2 + 1] += lazy_add[o] * (r - mid);
tree_max[o * 2 + 1] += lazy_add[o];
lazy_add[o * 2 + 1] += lazy_add[o];
// 清空当前标记
lazy_add[o] = 0;
}
}
// 区间加k（op=3）
void update_add(int o, int l, int r, int ql, int qr, ll val) {
if (ql <= l && r <= qr) { // 完全覆盖
tree_sum[o] += val * (r - l + 1);
tree_max[o] += val;
lazy_add[o] += val;
return;
}
pushdown(o, l, r); // 下推标记
int mid = (l + r) >> 1;
if (ql <= mid) update_add(o * 2, l, mid, ql, qr, val);
if (qr > mid) update_add(o * 2 + 1, mid + 1, r, ql, qr, val);
tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1]; // 上推
tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]);
}
// 区间赋值为k（op=4）
void update_set(int o, int l, int r, int ql, int qr, ll val) {
if (ql <= l && r <= qr) { // 完全覆盖
tree_sum[o] = val * (r - l + 1);
tree_max[o] = val;
lazy_set[o] = val;
lazy_add[o] = 0; // 重置加法
return;
}
pushdown(o, l, r); // 下推标记
int mid = (l + r) >> 1;
if (ql <= mid) update_set(o * 2, l, mid, ql, qr, val);
if (qr > mid) update_set(o * 2 + 1, mid + 1, r, ql, qr, val);
tree_sum[o] = tree_sum[o * 2] + tree_sum[o * 2 + 1]; // 上推
tree_max[o] = max(tree_max[o * 2], tree_max[o * 2 + 1]);
}
// 查询区间和（op=1）
ll query_sum(int o, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0; // 无交集
if (ql <= l && r <= qr) return tree_sum[o]; // 完全覆盖
pushdown(o, l, r); // 下推标记
int mid = (l + r) >> 1;
ll res = 0;
if (ql <= mid) res += query_sum(o * 2, l, mid, ql, qr);
if (qr > mid) res += query_sum(o * 2 + 1, mid + 1, r, ql, qr);
return res;
}
// 查询区间最大值（op=2）
ll query_max(int o, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return -INF; // 无交集，返回负无穷
if (ql <= l && r <= qr) return tree_max[o]; // 完全覆盖
pushdown(o, l, r); // 下推标记
int mid = (l + r) >> 1;
ll res = -INF;
if (ql <= mid) res = max(res, query_max(o * 2, l, mid, ql, qr));
if (qr > mid) res = max(res, query_max(o * 2 + 1, mid + 1, r, ql, qr));
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
memset(lazy_add, 0, sizeof(lazy_add)); // 初始化加法为0
memset(lazy_set, -1, sizeof(lazy_set)); // 初始化赋值为-1（无）
build(1, 1, n); // 构建树
while (q--) {
int op;
cin >> op;
if (op == 1) { // 范围求和
int l, r;
cin >> l >> r;
cout << query_sum(1, 1, n, l, r) << '\n';
} else if (op == 2) { // 范围求最大值
int l, r;
cin >> l >> r;
cout << query_max(1, 1, n, l, r) << '\n';
} else if (op == 3) { // 区间加k
int l, r;
ll k;
cin >> l >> r >> k;
update_add(1, 1, n, l, r, k);
} else if (op == 4) { // 区间赋值为k
int l, r;
ll k;
cin >> l >> r >> k;
update_set(1, 1, n, l, r, k);
}
}
return 0;
}ST 表 1
支持末尾添加数字，区间求最大值和区间求最小值
#include <bits/stdc++.h>
using namespace std;
// 全局变量
static vector<vector<long long>> stMax; // stMax[k][i] 表示区间 [i, i+2^k-1] 的最大值
static vector<vector<long long>> stMin; // stMin[k][i] 表示区间 [i, i+2^k-1] 的最小值
static vector<int> lg = {0, 0}; // lg[n] = floor(log2(n))，至少有下标到 1
static int n = 0; // 当前数组长度（1-based 查询用）
// 确保 lg 数组有到 to 的取值
void ensureLogSize(int to) {
if ((int)lg.size() > to) return;
int old = (int)lg.size() - 1;
lg.resize(to + 1);
for (int i = old + 1; i <= to; ++i) {
lg[i] = lg[i / 2] + 1;
}
}
// 追加一个元素 x 到末尾（新位置为 n+1）
void add(long long x) {
int newN = n + 1;
ensureLogSize(newN);
int needLevels = lg[newN] + 1; // 需要的层数：[0 .. floor(log2(newN))]
if ((int)stMax.size() < needLevels) {
stMax.resize(needLevels);
stMin.resize(needLevels);
}
// 第 0 层：区间长度 1
stMax[0].push_back(x);
stMin[0].push_back(x);
// 更高层：每次只需在每层末尾补一个新块（长度 2^k 且以 newN-2^k 为起点）
for (int k = 1; k < needLevels; ++k) {
int i = newN - (1 << k); // 新块起点（0-based）
long long aMax = stMax[k - 1][i];
long long bMax = stMax[k - 1][i + (1 << (k - 1))];
stMax[k].push_back(max(aMax, bMax));
long long aMin = stMin[k - 1][i];
long long bMin = stMin[k - 1][i + (1 << (k - 1))];
stMin[k].push_back(min(aMin, bMin));
}
n = newN;
}
// 查询区间 [l, r]（1-based，且保证 1 <= l <= r <= n）最大值
long long queryMax(int l, int r) {
int len = r - l + 1;
int k = lg[len];
int i1 = l - 1; // 左块起点（0-based）
int i2 = r - (1 << k); // 右块起点（0-based）
return max(stMax[k][i1], stMax[k][i2]);
}
// 查询区间 [l, r]（1-based）最小值
long long queryMin(int l, int r) {
int len = r - l + 1;
int k = lg[len];
int i1 = l - 1;
int i2 = r - (1 << k);
return min(stMin[k][i1], stMin[k][i2]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long a[n+1];
for (int i = 1;i <= n; ++i) {
cin >> a[i];
add(a[i]);
}
int q;
cin >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
long long k;
cin >> k;
add(k);
} else if (op == 2) {
int l, r;
cin >> l >> r;
if (l > r) swap(l, r);
cout << queryMax(l, r) << '\n';
} else if (op == 3) {
int l, r;
cin >> l >> r;
if (l > r) swap(l, r);
cout << queryMin(l, r) << '\n';
}
}
return 0;
}字典树 1：
#include <bits/stdc++.h>
using namespace std;
/*
字典树（Trie）说明：
- 每个节点维护：
- passCnt[u]: 有多少个插入的模式串经过该节点（即以该节点对应的前缀开头）。
- nxt[u]: 该节点经由某个字符可到达的子节点编号（使用 unordered_map<char,int> 存）。
- 根节点编号为 0，对应空前缀。
- 插入一个模式串 s 时：从根出发，每到达一个节点（包含根和沿途新老节点），passCnt++。
- 查询一个文本串 t 时：从根沿 t 的字符走；若途中断边则答案为 0；否则到达节点 u，答案为 passCnt[u]。
复杂度：
- 设所有模式串总长度为 L，总查询串长度为 T。
- 时间复杂度约为 O(L + T)，常数取决于哈希表。
- 空间复杂度 O(节点数 + 边数) ≈ O(L)。
*/
// 全局容器：不使用 struct/class
static vector<unordered_map<char, int>> nxt; // nxt[u][c] = v
static vector<long long> passCnt; // 节点 u 的前缀通过计数
// 新建一个空节点并返回其编号
int new_node() {
nxt.emplace_back(); // 空的子边哈希表
passCnt.emplace_back(0); // 初始计数为 0
return (int)nxt.size() - 1;
}
// 初始化整棵 Trie（清空并创建根）
void init_trie(size_t reserve_nodes = 1) {
nxt.clear();
passCnt.clear();
nxt.reserve(reserve_nodes); // 预留节点容量（可选）
passCnt.reserve(reserve_nodes); // 预留节点容量（可选）
new_node(); // 建立根节点，编号 0
}
// 插入一个模式串 s（区分大小写，支持任意可读字符）
void trie_insert(const string& s) {
int u = 0;
// 根节点代表空前缀，也要计一次（空串是所有字符串的前缀）
passCnt[u]++;
for (char c : s) {
auto it = nxt[u].find(c);
if (it == nxt[u].end()) {
int v = new_node();
nxt[u][c] = v;
u = v;
} else {
u = it->second;
}
passCnt[u]++; // 该节点对应的前缀又多了一个模式串
}
}
// 查询：有多少模式串以 t 为前缀
long long trie_query_prefix_count(const string& t) {
int u = 0;
for (char c : t) {
auto it = nxt[u].find(c);
if (it == nxt[u].end()) {
return 0; // 路断了，说明没有任何模式串以 t 为前缀
}
u = it->second;
}
return passCnt[u];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
if (!(cin >> n >> q)) return 0;
vector<string> patterns(n);
size_t total_len = 0;
for (int i = 0; i < n; ++i) {
cin >> patterns[i];
total_len += patterns[i].size();
}
// 预估节点数上界：1（根） + 所有模式串总长度
init_trie(total_len + 1);
// 建树
for (const auto& s : patterns) {
trie_insert(s);
}
// 逐个查询
while (q--) {
string t;
cin >> t;
cout << trie_query_prefix_count(t) << '\n';
}
return 0;
}字典树 2：
支持查询求数组中两两元素异或的最大值。
#include <bits/stdc++.h>
using namespace std;
struct BinaryTrie {
// 每个节点有两个孩子（0/1），存子节点下标，-1 表示不存在
vector<array<int, 2>> nxt;
int maxBit; // 从 maxBit 到 0 遍历位
BinaryTrie(int maxBit_) : maxBit(maxBit_) {
nxt.clear();
nxt.push_back({-1, -1}); // 根节点
}
void insert(uint64_t x) {
int node = 0;
for (int b = maxBit; b >= 0; --b) {
int bit = (x >> b) & 1ULL;
if (nxt[node][bit] == -1) {
nxt[node][bit] = (int)nxt.size();
nxt.push_back({-1, -1});
}
node = nxt[node][bit];
}
}
// 在当前 Trie 中，找到与 x 异或结果最大的值，并返回该最大异或值
uint64_t queryMaxXor(uint64_t x) const {
int node = 0;
uint64_t res = 0;
for (int b = maxBit; b >= 0; --b) {
int bit = (x >> b) & 1ULL;
int want = bit ^ 1; // 希望走相反位以增大异或
if (nxt[node][want] != -1) {
res |= (1ULL << b);
node = nxt[node][want];
} else {
node = nxt[node][bit];
}
if (node == -1) break; // 空 Trie 安全防护
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
vector<uint64_t> a(N);
uint64_t mx = 0;
for (int i = 0; i < N; ++i) {
cin >> a[i];
mx = max(mx, a[i]);
}
if (N < 2) {
cout << 0 << '\n';
return 0;
}
// 计算需要的最高位（根据数组最大值自适应）
int maxBit = (mx == 0 ? 0 : 63 - __builtin_clzll(mx));
BinaryTrie trie(maxBit);
uint64_t ans = 0;
// 先插入第一个，再从第二个开始：保证 l < r（不会与自身配对）
trie.insert(a[0]);
for (int i = 1; i < N; ++i) {
ans = max(ans, trie.queryMaxXor(a[i]));
trie.insert(a[i]);
}
cout << ans << '\n';
return 0;
}dfs bfs模板
#include <bits/stdc++.h>
using namespace std;
/*
深度优先搜索（DFS）
参数说明：
- u: 当前访问的节点
- g: 图的邻接表（1..n）
- vis: 访问标记数组（1..n），1 表示已访问
- order: 记录 DFS 的访问顺序
设计要点：
- 预先保证 g[u] 已经按升序排序，这样遇到多个可访问的点时，会优先访问编号更小的点。
*/
void dfs(int u, const vector<vector<int>>& g, vector<int>& vis, vector<int>& order) {
vis[u] = 1; // 标记当前节点已访问
order.push_back(u); // 记录访问顺序
for (int v : g[u]) { // 按升序遍历邻居
if (!vis[v]) {
dfs(v, g, vis, order);
}
}
}
/*
广度优先搜索（BFS）
参数说明：
- start: 起点（本题默认从 1 开始，因为图保证联通）
- g: 图的邻接表（1..n）
返回值：
- 按访问顺序记录的节点序列
设计要点：
- 为确保同一层内先访问编号更小的节点，要求 g[u] 已升序；
将未访问的邻居按升序入队即可实现“同一时间访问，先输出较小点”的要求。
*/
vector<int> bfs(int start, const vector<vector<int>>& g) {
int n = (int)g.size() - 1; // g 按 1..n 存储，因此 size() - 1 是节点数
vector<int> vis(n + 1, 0);
queue<int> q;
vector<int> order;
vis[start] = 1;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
// g[u] 已经升序，因此入队顺序保证了同层由小到大
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = 1; // 入队前标记，避免同一层被重复入队
q.push(v);
}
}
}
return order;
}
/*
辅助函数：按空格分隔输出序列（末尾不多输出空格）
*/
void print_sequence(const vector<int>& seq) {
for (size_t i = 0; i < seq.size(); ++i) {
if (i) cout << ' ';
cout << seq[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// 建图（无向图），使用 1..n 的邻接表
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 为满足“多个点同时可访问时先访问编号更小的点”，对邻接表升序排序。
// 同时去重可避免多重边造成的重复判断（不影响正确性，只是更高效）。
for (int u = 1; u <= n; ++u) {
auto& adj = g[u];
sort(adj.begin(), adj.end());
adj.erase(unique(adj.begin(), adj.end()), adj.end());
}
// 由于题目说明图是联通的，默认从 1 号点开始遍历
int start = 1;
// DFS
vector<int> vis(n + 1, 0);
vector<int> dfs_order;
dfs(start, g, vis, dfs_order);
// BFS
vector<int> bfs_order = bfs(start, g);
// 输出：第一行 DFS 顺序，第二行 BFS 顺序
print_sequence(dfs_order);
print_sequence(bfs_order);
return 0;
}
/*
使用示例：
输入：
5 5
1 2
1 3
2 4
3 4
4 5
输出可能为：
1 2 4 3 5
1 2 3 4 5
说明：
- DFS：1 -> 2 -> 4 -> 3 -> 5（因邻接表排序，优先访问编号更小的邻居）
- BFS：层序从 1 开始，每层内按照节点编号从小到大入队访问
*/快速幂模板
int qp(int a,int b,int mod){
int ans=1;
while(b>0){
if(b&1)ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans%mod;
}DSU
class DSU {
private:
std::vector<int> parent;
std::vector<int> sz;
public:
DSU(int n) {
parent.resize(n);
std::iota(parent.begin(), parent.end(), 0);
sz.assign(n, 1);
}
int find(int i) {
if (parent[i] == i) {
return i;
}
return parent[i] = find(parent[i]);
}
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
if (sz[root_i] < sz[root_j]) {
std::swap(root_i, root_j);
}
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
}
}
};Bellman Ford
/*
Bellman-Ford（SPFA 队列优化）模板 —— 邻接表版（1..n）
参数说明：
- s: 源点（默认 1，可按需修改或从输入读取）
- g: 图的邻接表（1..n），g[u] = vector<pair<int,int>>，元素 (v, w) 表示边 u->v、权重 w
返回值：
- pair<bool, vector<long long>>
first = true 表示不存在从 s 可达的负环
first = false 表示存在从 s 可达的负环（此时 second 中的 d 可能无意义）
second = 最短路数组 d，若不可达则为 INF
设计要点：
- 仅当 d[v] 被成功松弛才将 v 入队，减少无效入队。
- inq[v] 标记 v 是否在队中，避免重复入队。
- cnt[v] 统计“v 被成功松弛”的次数；若 cnt[v] >= n，判定存在从 s 可达的负环。
- 时间复杂度：最坏 O(nm)，实际常优于朴素 Bellman-Ford。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
pair<bool, vector<ll>> spfa(int s, const vector<vector<pair<int,int>>>& g) {
int n = (int)g.size() - 1; // g 按 1..n 存储
vector<ll> d(n + 1, INF); // 最短路
vector<int> inq(n + 1, 0); // 是否在队列中
vector<int> cnt(n + 1, 0); // 成功松弛次数
queue<int> q;
d[s] = 0;
q.push(s);
inq[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = 0;
// 扫描 u 的所有出边
for (auto [v, w] : g[u]) {
if (d[u] != INF && d[v] > d[u] + (ll)w) {
d[v] = d[u] + (ll)w;
// v 被成功松弛一次
cnt[v] += 1;
if (cnt[v] >= n) {
// 存在从 s 可达的负环
return {false, d};
}
if (!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
return {true, d};
}
/*
辅助函数：按空格分隔输出最短路（INF 表示不可达）
*/
void print_d(const vector<ll>& d) {
int n = (int)d.size() - 1;
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
if (d[i] > INF / 2) cout << "INF";
else cout << d[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// 建图（有向图），使用 1..n 的邻接表
vector<vector<pair<int,int>>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
// 若为无向图，请同时加入：g[v].push_back({u, w});
}
int s = 1; // 源点（可按需修改或从输入读取）
auto [ok, d] = spfa(s, g);
if (!ok) {
cout << "NEGATIVE CYCLE\n";
} else {
print_d(d);
}
return 0;
}
/*
使用示例：
输入：
5 7
1 2 2
1 3 5
2 3 -3
2 4 4
3 5 1
4 5 2
5 4 -1
输出可能为：
0 2 -1 6 0
或若存在从 1 可达的负环：
NEGATIVE CYCLE
说明：
- d[i] = 从源点 1 到 i 的最短路；不可达输出 INF。
- 将 s 修改为需要的源点，或自行从输入读入。
*/Dijkstra
/*
Dijkstra 最短路（优先队列版）模板 —— 邻接表（1..n）
参数说明：
- s: 源点（默认 1，可按需修改或从输入读取）
- g: 图的邻接表（1..n），g[u] = vector<pair<int,int>>，元素 (v, w) 表示边 u->v、权重 w
返回值：
- vector<long long> d：最短路数组，d[i] = 从 s 到 i 的最短距离；不可达为 INF
设计要点：
- 使用最小堆（优先队列）按当前已知最短距离弹出节点，避免 O(nm) 的枚举，复杂度约 O((n+m) log n)
- 权重需满足非负（w >= 0）；若存在负边，请改用 Bellman-Ford/SPFA
- vis[u]（或称 st[u]）用于标记最短路已确定的点，避免重复扩展
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
/*
函数：dij
作用：从源点 s 计算到各点的最短路
*/
vector<ll> dij(int s, const vector<vector<pair<int,int>>>& g) {
int n = (int)g.size() - 1; // g 使用 1..n 存储
vector<ll> d(n + 1, INF); // 最短路
vector<int> vis(n + 1, 0); // 是否已确定最短路
// 小根堆：按 (距离, 节点) 最小优先
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
d[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (vis[u]) continue; // 已处理过的点跳过
vis[u] = 1;
// 用 u 的出边尝试松弛邻居
for (auto [v, w] : g[u]) {
if (d[v] > du + (ll)w) {
d[v] = du + (ll)w;
pq.push({d[v], v});
}
}
}
return d;
}
/*
辅助函数：按空格分隔输出最短路（INF 表示不可达）
*/
void print_d(const vector<ll>& d) {
int n = (int)d.size() - 1;
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
if (d[i] > INF / 2) cout << "INF";
else cout << d[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// 建图（有向图），使用 1..n 的邻接表
vector<vector<pair<int,int>>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
// 若为无向图，额外加入：g[v].push_back({u, w});
}
int s = 1; // 源点（可按需修改或从输入读取）
auto d = dij(s, g);
print_d(d);
return 0;
}
/*
使用示例：
输入：
5 7
1 2 2
1 3 5
2 3 1
2 4 4
3 5 1
4 5 2
2 5 7
输出可能为（从源点 1 出发）：
0 2 3 6 4
说明：
- d[i] = 从源点 1 到 i 的最短路；不可达输出 INF。
- 若图是无向的，请在读入时对称加入两条边。
- Dijkstra 要求所有边权非负。
*/Johnson
/*
Johnson 全源最短路模板 —— 邻接表（1..n）
参数说明：
- g: 图的邻接表（1..n），g[u] = vector<pair<int,long long>>，元素 (v, w) 表示边 u->v、权重 w
返回值：
- 若存在可达负环：输出 "NEGATIVE CYCLE"
- 否则：输出 n 行，每行 n 个数，第 i 行第 j 列为从 i 到 j 的最短距离；不可达为 INF
设计要点：
- 允许负权边，但不得存在可达负环。
- 使用 SPFA 计算势函数 h（相当于从超级源 0 到各点的最短路），以将边权重标定为非负：
w'(u,v) = w(u,v) + h[u] - h[v] >= 0
- 对每个源点运行 Dijkstra 于重标后的图，时间复杂度约 O(n (m log n))。
- 原距离恢复：d(u,v) = d'(u,v) - h[u] + h[v]，其中 d' 为重标图上的最短路。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
/*
SPFA 求势函数 h（从超级源 0 出发）
做法等价于：给每个点加一条 0->v 权值 0 的边，然后跑一次 Bellman-Ford。
实现细节：
- 将所有节点初始化入队，h[v] 初值为 0。
- cnt[v] 统计 v 被成功松弛的次数；若 >= n 则存在负环。
返回：
- true 无负环，h 填好
- false 存在可达负环
*/
bool spfa0(const vector<vector<pair<int,ll>>>& g, vector<ll>& h) {
int n = (int)g.size() - 1;
h.assign(n + 1, 0);
vector<int> inq(n + 1, 1), cnt(n + 1, 0);
queue<int> q;
for (int i = 1; i <= n; ++i) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = 0;
for (auto [v, w] : g[u]) {
if (h[v] > h[u] + w) {
h[v] = h[u] + w;
cnt[v] += 1;
if (cnt[v] >= n) return false; // 可达负环
if (!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
return true;
}
/*
Dijkstra（在重标后的图上进行，边权非负）
输入：
- s: 源点
- g: 原图邻接表
- h: 势函数（由 spfa0 计算）
返回：
- d': 从 s 到各点的重标最短路（若不可达为 INF）
转移：
- w'(u,v) = w(u,v) + h[u] - h[v]
*/
vector<ll> dij_rw(int s, const vector<vector<pair<int,ll>>>& g, const vector<ll>& h) {
int n = (int)g.size() - 1;
vector<ll> d(n + 1, INF);
using P = pair<ll,int>;
priority_queue<P, vector<P>, greater<P>> pq;
d[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != d[u]) continue; // 过期状态
for (auto [v, w] : g[u]) {
ll w2 = w + h[u] - h[v]; // 重标后的非负边权
if (w2 < 0) w2 = 0; // 数值稳健（理论上应 >= 0）
ll nd = du + w2;
if (nd < d[v]) {
d[v] = nd;
pq.push({nd, v});
}
}
}
return d;
}
/*
Johnson 主流程：
1) 用 spfa0 求势函数 h，检测负环；
2) 对每个源点 s，跑一次 Dijkstra（用重标权），得到 d'；
3) 还原原图距离：ans[s][v] = d'[v] - h[s] + h[v]
返回：
- pair<bool, vector<vector<ll>>>：
first = true 无负环；second 为 n+1 x n+1 的距离矩阵（1..n 有效）
first = false 存在负环；second 为空
*/
pair<bool, vector<vector<ll>>> johnson(const vector<vector<pair<int,ll>>>& g) {
int n = (int)g.size() - 1;
vector<ll> h;
if (!spfa0(g, h)) return {false, {}};
vector<vector<ll>> ans(n + 1, vector<ll>(n + 1, INF));
for (int s = 1; s <= n; ++s) {
auto d2 = dij_rw(s, g, h); // d' on reweighted graph
for (int v = 1; v <= n; ++v) {
if (d2[v] >= INF / 2) ans[s][v] = INF;
else ans[s][v] = d2[v] - h[s] + h[v]; // 还原原图距离
}
}
return {true, ans};
}
/*
辅助输出：打印 n 行 n 列的距离矩阵
*/
void print_mat(const vector<vector<ll>>& a) {
int n = (int)a.size() - 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (j > 1) cout << ' ';
if (a[i][j] >= INF / 2) cout << "INF";
else cout << a[i][j];
}
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// 建图（有向图），使用 1..n 的邻接表
vector<vector<pair<int,ll>>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
// 若为无向图，额外加入：g[v].push_back({u, w});
}
auto [ok, dist] = johnson(g);
if (!ok) {
cout << "NEGATIVE CYCLE\n";
return 0;
}
print_mat(dist);
return 0;
}
/*
使用示例：
输入：
5 7
1 2 2
1 3 5
2 3 -3
2 4 4
3 5 1
4 5 2
2 5 7
可能输出（某一合法结果）：
0 2 -1 6 0
INF 0 -3 4 -2
INF INF 0 INF 1
INF INF INF 0 2
INF INF INF INF 0
说明：
- 允许负边，但若存在可达负环会输出 NEGATIVE CYCLE。
- 对无向图请对称加入边。
- 若只需某些源点的最短路，可只对这些源点运行 Dijkstra。
*/拓扑排序
/*
拓扑排序（Topological Sort）模板 —— 邻接表（1..n）
参数说明：
- g: 有向图的邻接表（1..n），g[u] 存储所有从 u 指向的邻居 v（边 u->v）
返回值：
- 若存在有向环：输出 "CYCLE"
- 否则：输出一个拓扑序列（若有多个，默认输出“字典序最小”的序列）
设计要点：
- 使用 Kahn 算法（基于入度）：
1) 计算每个点的入度 deg[v]；
2) 将所有入度为 0 的点入队（这里用小根堆以得到字典序最小的拓扑序）；
3) 反复弹出一个入度为 0 的点 u，将其加入答案，并“删除”它的出边
（对应地将邻居 v 的入度减 1，若变为 0 则入队）。
- 若最终弹出的点不足 n 个，说明存在有向环（无法拓扑排序）。
- 复杂度：O(n + m)，使用小根堆为 O((n + m) log n)。
*/
#include <bits/stdc++.h>
using namespace std;
/*
函数：topo
作用：对有向图 g 进行拓扑排序；若有环返回空序列
细节：
- 使用小根堆（优先队列）保证多解时输出字典序最小的拓扑序
*/
vector<int> topo(const vector<vector<int>>& g) {
int n = (int)g.size() - 1; // g 按 1..n 存储
vector<int> deg(n + 1, 0); // 入度数组
for (int u = 1; u <= n; ++u) {
for (int v : g[u]) deg[v] += 1;
}
// 小根堆：保证每次取编号最小的入度为 0 的点
priority_queue<int, vector<int>, greater<int>> pq;
for (int u = 1; u <= n; ++u) if (deg[u] == 0) pq.push(u);
vector<int> ord;
ord.reserve(n);
while (!pq.empty()) {
int u = pq.top(); pq.pop();
ord.push_back(u);
for (int v : g[u]) {
if (--deg[v] == 0) pq.push(v);
}
}
if ((int)ord.size() != n) {
// 存在有向环，无法拓扑排序
return {};
}
return ord;
}
/*
辅助函数：按空格分隔输出序列（末尾不多输出空格）
*/
void print_seq(const vector<int>& a) {
for (size_t i = 0; i < a.size(); ++i) {
if (i) cout << ' ';
cout << a[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
// 建图（有向图），使用 1..n 的邻接表
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v; // 边 u -> v
g[u].push_back(v);
}
auto ord = topo(g);
if (ord.empty()) {
cout << "CYCLE\n";
} else {
print_seq(ord);
}
return 0;
}
/*
使用示例：
输入：
6 6
1 2
1 3
3 4
2 4
4 5
2 6
可能输出（字典序最小的一个拓扑序）：
1 2 3 4 6 5
说明：
- 若图中存在有向环，将输出：CYCLE
- 若不要求字典序最小，可将小根堆改为普通队列 queue<int>，其余逻辑不变。
*/树的直径
/*
树的直径（Tree Diameter）模板 —— 邻接表（1..n）
参数说明：
- g: 无向树的邻接表（1..n），g[u] 存储所有 (v, w) 表示边 u—v，权重为 w
返回值：
- 直径的两个端点 (a, b) 以及直径长度 len
设计要点：
- “两次最远点”法：
1) 从任意点 s（常取 1）出发，找到最远点 a；
2) 从 a 出发，找到最远点 b，同时得到距离 len = dist(a, b)；
则 (a, b) 为树的直径端点。
- 若是无权树，可将所有 w 设为 1；本模板统一支持带权/无权两种情况。
- 为避免深递归导致栈溢出，使用迭代 DFS。
- 复杂度 O(n)。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
函数：far
作用：从起点 s 出发，沿树进行一次迭代 DFS，返回距离最远的节点及其距离
说明：
- 树上任意走法的路径唯一，因此首次访问即得到其唯一的路径距离
- par 数组用于记录父节点，避免走回头路
*/
pair<int, ll> far(int s, const vector<vector<pair<int, ll>>>& g) {
int n = (int)g.size() - 1;
vector<int> par(n + 1, -1);
vector<ll> dist(n + 1, -1);
stack<int> st;
par[s] = 0;
dist[s] = 0;
st.push(s);
while (!st.empty()) {
int u = st.top(); st.pop();
for (auto [v, w] : g[u]) {
if (par[v] == -1) { // 未访问
par[v] = u;
dist[v] = dist[u] + w;
st.push(v);
}
}
}
int best = s;
for (int i = 1; i <= n; ++i) {
if (dist[i] > dist[best]) best = i;
}
return {best, dist[best]};
}
/*
函数：diam
作用：计算树的直径端点与长度
返回：
- tuple<int,int,ll> = (a, b, len)
*/
tuple<int,int,ll> diam(const vector<vector<pair<int, ll>>>& g) {
int s = 1; // 任取起点（树保证连通）
int a = far(s, g).first; // 第一次：找到最远点 a
auto [b, len] = far(a, g); // 第二次：从 a 出发得到最远点 b 及距离 len
return {a, b, len};
}
/*
可选：输出 (a, b, len)，其中 len 为直径长度
*/
void print_diam(int a, int b, ll len) {
// 统一以空格分隔；如需自定义格式可在此修改
cout << a << ' ' << b << ' ' << len << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
// 构建邻接表（无向树），使用 1..n
vector<vector<pair<int, ll>>> g(n + 1);
// 输入格式一（默认无权树）：接下来的 n-1 行，每行 u v，边权视为 1
// 若为带权树，请将下面的读入替换为“输入格式二”
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
ll w = 1; // 无权树：边权为 1
g[u].push_back({v, w});
g[v].push_back({u, w});
}
// 输入格式二（带权树）：若你的数据有权重，请改用下面注释块（并注释掉上面的无权读入）
/*
for (int i = 0; i < n - 1; ++i) {
int u, v; ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
*/
auto [a, b, len] = diam(g);
print_diam(a, b, len);
return 0;
}
/*
使用示例（无权）：
输入：
5
1 2
2 3
2 4
4 5
输出（端点与直径长度，可能存在多个合法端点对）：
3 5 3
说明：
- 直径长度为 3（边数），一个最远点对是 3 与 5。
- 若为带权树，将输入改为三元组 (u, v, w)，并启用“输入格式二”。
*/树的中心
/*
树的中心（Tree Center）模板 —— 邻接表（1..n）
参数说明：
- g: 无向树的邻接表（1..n），g[u] 存储所有与 u 相邻的点 v
返回值：
- 树的中心（可能 1 个或 2 个）：若为 1 个中心返回 {c}，若为 2 个中心返回 {c1, c2}
设计要点：
- 采用“剥叶法”（Kahn 思想）：
1) 计算每个点的度数 deg[u]，将所有度为 1 的点入队（即叶子）；
2) 分层地剥去当前所有叶子，并将其相邻点的度数减 1；
3) 当剩余节点数 rem <= 2 时，队列中的点即为树的中心（1 或 2 个）。
- 复杂度 O(n)；仅依赖度数与邻接表，不需要递归与长路径恢复。
*/
#include <bits/stdc++.h>
using namespace std;
/*
函数：center
作用：求树的中心（可能 1 或 2 个）
输入：
- g: 邻接表（1..n）
返回：
- vector<int>：按升序返回中心点编号（1 或 2 个）
*/
vector<int> center(const vector<vector<int>>& g) {
int n = (int)g.size() - 1; // g 按 1..n 存储
if (n <= 0) return {};
if (n == 1) return {1};
vector<int> deg(n + 1, 0);
queue<int> q;
for (int u = 1; u <= n; ++u) {
deg[u] = (int)g[u].size();
if (deg[u] <= 1) q.push(u); // 叶子或孤点（树中仅可能为叶子）
}
int rem = n; // 剩余未剥除的节点数量
while (rem > 2) {
int sz = (int)q.size(); // 当前层叶子数量
rem -= sz; // 剥去这一层所有叶子
while (sz--) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (--deg[v] == 1) q.push(v); // 新形成的叶子入队
}
}
}
// 此时队列中为 1 或 2 个中心
vector<int> cent;
while (!q.empty()) { cent.push_back(q.front()); q.pop(); }
sort(cent.begin(), cent.end());
cent.erase(unique(cent.begin(), cent.end()), cent.end());
return cent;
}
/*
辅助函数：按空格分隔输出序列（末尾不多输出空格）
*/
void print_seq(const vector<int>& a) {
for (size_t i = 0; i < a.size(); ++i) {
if (i) cout << ' ';
cout << a[i];
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
// 建树（无向），使用 1..n 的邻接表
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
auto c = center(g);
print_seq(c);
return 0;
}
/*
使用示例：
输入：
5
1 2
2 3
2 4
4 5
可能输出（一个合法中心集合）：
2 4
说明：
- 本例中直径长度为 3，中心为直径中点（若直径长度为奇数，则有 1 个中心；为偶数，则有 2 个中心）。
- 本模板针对无向连通无环图（树）。若输入不是树，行为未定义。
*/LCA
/*
最近公共祖先（LCA, Lowest Common Ancestor）模板 —— 邻接表（1..n）
参数说明：
- g: 无向树的邻接表（1..n），g[u] 存储与 u 相邻的所有点 v
- rt: 根节点（默认 1，可根据需要指定或从输入读取）
返回值：
- 函数 lca(u, v) 返回节点 u 和 v 的最近公共祖先
设计要点：
- 二进制提升（倍增）：
1) BFS/DFS 预处理 dep[u]（深度）与 up[k][u]（u 的第 2^k 个祖先）；
2) 先把较深的点提到同一深度，再同时向上跳，O(log n) 求解 LCA。
- 复杂度：预处理 O(n log n)，单次查询 O(log n)。
*/
#include <bits/stdc++.h>
using namespace std;
/*
函数：init
作用：用 BFS 预处理深度和倍增祖先表
输入：
- rt: 根节点
- g: 邻接表（1..n）
输出：
- dep: dep[u] 为从根到 u 的深度（根为 0）
- up: up[k][u] 为 u 的第 2^k 个祖先（根的祖先定义为根自己）
*/
void init(int rt, const vector<vector<int>>& g, vector<int>& dep, vector<vector<int>>& up) {
int n = (int)g.size() - 1;
int LG = 32 - __builtin_clz(n); // ceil(log2(n))
up.assign(LG, vector<int>(n + 1, rt));
dep.assign(n + 1, -1);
queue<int> q;
dep[rt] = 0;
up[0][rt] = rt;
q.push(rt);
// BFS 建树：确定每个点的父亲 up[0][u] 与深度 dep[u]
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (dep[v] != -1) continue; // 已访问（已确定父亲）
dep[v] = dep[u] + 1;
up[0][v] = u;
q.push(v);
}
}
// 倍增：up[k][u] = up[k-1][ up[k-1][u] ]
for (int k = 1; k < LG; ++k) {
for (int u = 1; u <= n; ++u) {
up[k][u] = up[k-1][ up[k-1][u] ];
}
}
}
/*
函数：lift
作用：将节点 u 向上提升 dist 层（返回提升后的节点）
说明：
- 使用 up 表按二进制分解进行跳跃
*/
int lift(int u, int dist, const vector<vector<int>>& up) {
for (int k = 0; dist; ++k, dist >>= 1) {
if (dist & 1) u = up[k][u];
}
return u;
}
/*
函数：lca
作用：返回 u 与 v 的最近公共祖先
做法：
- 先把较深的点提升到相同深度；
- 若相等则为 LCA；
- 否则自高位到低位同时向上跳，最终返回其父亲。
*/
int lca(int u, int v, const vector<int>& dep, const vector<vector<int>>& up) {
if (dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
u = lift(u, diff, up);
if (u == v) return u;
for (int k = (int)up.size() - 1; k >= 0; --k) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
}
/*
可选：若需要两点间距离（无权树按边数计），可用：
dist(u, v) = dep[u] + dep[v] - 2 * dep[lca(u, v)]
若为带权树，可在 BFS/DFS 时同步维护从根到每点的前缀权和 sum[u]，
则加权距离 = sum[u] + sum[v] - 2 * sum[lca(u, v)]。
*/
/*
辅助函数：按行输出查询结果
*/
void print_ans(int x) {
cout << x << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
if (!(cin >> n >> q)) return 0;
// 建树（无向），使用 1..n 的邻接表
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int rt = 1; // 根（可根据题意修改或从输入读取）
vector<int> dep;
vector<vector<int>> up;
init(rt, g, dep, up);
// 处理 q 次查询：每次给出 u, v 输出 LCA(u, v)
while (q--) {
int u, v;
cin >> u >> v;
int a = lca(u, v, dep, up);
print_ans(a);
}
return 0;
}
/*
使用示例：
输入：
7 4
1 2
1 3
2 4
2 5
3 6
6 7
4 5
4 6
5 7
2 7
输出：
2
1
1
1
说明：
- 树为 1 为根的无向树（输入的是边，程序会以 1 为根进行预处理）。
- 每行对应一次 LCA 查询的答案。
*/拓展欧拉定理
/*
扩展欧拉定理模板：计算 a^b mod m
参数说明：
- a, b, m（m >= 1）
返回值：
- a^b mod m
设计要点（扩展欧拉定理）：
- 令 φ = phi(m)
- 若 gcd(a, m) == 1，则 a^b ≡ a^{b mod φ} (mod m)
- 若 gcd(a, m) != 1，则
当 b < φ 时：a^b ≡ a^b (mod m)（不做降幂）
当 b ≥ φ 时：a^b ≡ a^{(b mod φ) + φ} (mod m)
- 注意：m == 1 时，任何数 mod 1 为 0
实现细节：
- phi(m) 通过质因数分解 O(sqrt m)
- 幂运算使用二进制快速幂；乘法用 __int128 防溢出
- 额外提供大指数版本（b 为字符串），仅用于比较 b 与 φ 的大小和取 b mod φ
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
// 乘法（避免溢出）：(x * y) % mod
static inline i64 mul_mod(i64 x, i64 y, i64 mod) {
return (i64)((i128)x * y % mod);
}
// 快速幂：计算 (a^e) % mod，要求 mod >= 1
i64 fpow(i64 a, u64 e, i64 mod) {
if (mod == 1) return 0;
a %= mod;
if (a < 0) a += mod;
i64 r = 1 % mod;
while (e) {
if (e & 1) r = mul_mod(r, a, mod);
a = mul_mod(a, a, mod);
e >>= 1;
}
return r;
}
// 欧拉函数 phi(n)：统计 1..n 中与 n 互质的数
i64 phi(i64 n) {
if (n == 1) return 1; // 习惯上 phi(1) = 1（不会用于取模降幂）
i64 r = n;
for (i64 p = 2; p * p <= n; ++p) {
if (n % p == 0) {
r = r / p * (p - 1);
while (n % p == 0) n /= p;
}
}
if (n > 1) r = r / n * (n - 1);
return r;
}
// 扩展欧拉定理（b 为 64 位）：返回 a^b mod m
i64 pw_ext(i64 a, u64 b, i64 m) {
if (m == 1) return 0;
i64 ph = phi(m);
i64 g = std::gcd((i64)((a % m + m) % m), m);
u64 e; // 实际用于幂运算的指数
if (g == 1) {
// 互质：直接 b % phi(m)
e = (ph == 0 ? 0 : (b % (u64)ph));
} else {
// 不互质：b < phi ? 用 b : 用 (b % phi + phi)
if (b < (u64)ph) e = b;
else e = (ph == 0 ? b : (b % (u64)ph + (u64)ph));
}
return fpow(a, e, m);
}
/* ========== 进阶：大指数版本（b 以十进制字符串给出） ========== */
// 计算 s（十进制大整数） % mod（mod fits in 64-bit）
u64 mod_str(const string& s, u64 mod) {
if (mod == 0) return 0;
u64 r = 0;
for (char c : s) {
r = (r * 10 + (c - '0')) % mod;
}
return r;
}
// 判断大整数字符串 s 是否 >= x（x fits in 64-bit）
bool ge_str(const string& s, u64 x) {
string t = to_string(x);
if (s.size() != t.size()) return s.size() > t.size();
return s >= t;
}
// 扩展欧拉定理（b 为字符串）：返回 a^b mod m
i64 pw_ext_big(i64 a, const string& bs, i64 m) {
if (m == 1) return 0;
i64 ph = phi(m);
i64 g = std::gcd((i64)((a % m + m) % m), m);
u64 e;
if (g == 1) {
if (ph == 0) e = 0;
else e = mod_str(bs, (u64)ph);
} else {
if (ph == 0) {
// 罕见：m==1 时已提前返回；这里保底
// 直接不降幂（可能很大，无法计算），但该情形不会触发
e = 0;
} else {
if (ge_str(bs, (u64)ph)) e = mod_str(bs, (u64)ph) + (u64)ph;
else {
// 将 bs 转为 u64（bs < phi，且 phi fits u64）
u64 v = 0;
for (char c : bs) v = v * 10 + (c - '0');
e = v;
}
}
}
return fpow(a, e, m);
}
/*
示例 main：
- 读取 a b m，其中 b 可为 64 位或大整数字符串（二选一）
- 输出 a^b mod m
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 a, m;
// 版本一：b 为 64 位整数
/*
u64 b;
if (!(cin >> a >> b >> m)) return 0;
cout << pw_ext(a, b, m) << '\n';
*/
// 版本二：b 为大整数（字符串）
string b;
if (!(cin >> a >> b >> m)) return 0;
cout << pw_ext_big(a, b, m) << '\n';
return 0;
}
/*
使用示例 1（b 为 64 位）：
输入：
2 1000000000000000000 1000000007
输出：
140625001
使用示例 2（b 为大整数）：
输入：
2 123456789123456789123456789 1000000007
输出：
320484785
说明：
- 当 gcd(a, m) == 1 时，指数可直接对 phi(m) 取模；
- 当 gcd(a, m) != 1 时，若 b >= phi(m)，需加一段 phi(m) 再取模，以保证等价性；
- m == 1 时结果恒为 0。
*/exgcd
/*
扩展欧几里得算法（exgcd）模板
功能概述：
- exgcd(a, b, x, y)：返回 gcd(a, b)，并给出一组系数 (x, y)，使得 a*x + b*y = gcd(a, b)
- inv(a, m)：在 m > 1 且 gcd(a, m) = 1 的前提下，返回 a 在模 m 下的乘法逆元；不存在则返回 -1
- sol(a, b, c, x, y, g)：求解线性丢番图方程 a*x + b*y = c 的一个整数解（若存在）
- cong(a, b, m, x, mod)：求解同余方程 a*x ≡ b (mod m) 的最小非负解（若存在）
设计要点：
- exgcd 同时得到贝祖系数，可直接用于线性方程、逆元与同余方程求解。
- 处理 a 或 b 为负数时，返回的 gcd 为非负（|gcd|），系数会自动匹配使等式成立。
- 乘法可能溢出时，计算中使用 __int128。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
/*
函数：exgcd
作用：求 gcd(a, b) 及其对应的贝祖系数 (x, y)，满足 a*x + b*y = gcd(a, b)
说明：
- 返回的 gcd 恒为非负值
- 支持 a 或 b 为负
*/
ll exgcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = (a >= 0 ? 1 : -1); // 使 a*x = |a|
y = 0;
return llabs(a);
}
ll x1, y1;
ll g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
/*
函数：norm
作用：将 x 归一化到 [0, m-1]
*/
ll norm(ll x, ll m) {
x %= m;
if (x < 0) x += m;
return x;
}
/*
函数：inv
作用：求 a 在模 m 下的乘法逆元（最小非负）
返回：
- 若存在，返回 inv ∈ [0, m-1]
- 若不存在（m <= 1 或 gcd(a, m) != 1），返回 -1
*/
ll inv(ll a, ll m) {
if (m <= 1) return -1;
ll x, y;
ll g = exgcd(a, m, x, y);
if (g != 1) return -1;
return norm(x, m);
}
/*
函数：sol
作用：求解线性丢番图方程 a*x + b*y = c 的一个整数解
输入/输出：
- 返回 true 表示有解，并给出一组 (x, y) 与 gcd g（使得 a*x + b*y = c）
- 返回 false 表示无解（当 c % g != 0）
备注：
- 通解形式：x = x0 + t*(b/g)，y = y0 - t*(a/g)，t ∈ Z
*/
bool sol(ll a, ll b, ll c, ll& x, ll& y, ll& g) {
ll x0, y0;
g = exgcd(a, b, x0, y0);
if (c % g != 0) return false;
i128 k = (i128)c / g;
x = (ll)((i128)x0 * k);
y = (ll)((i128)y0 * k);
return true;
}
/*
函数：cong
作用：求解同余方程 a*x ≡ b (mod m) 的最小非负解
返回：
- 若有解，返回 true，并给出：
x 为最小非负解；
mod 为解的模周期（所有解为 x + t*mod）
- 若无解（b % gcd(a, m) != 0），返回 false
*/
bool cong(ll a, ll b, ll m, ll& x, ll& mod) {
ll x0, y0;
ll g = exgcd(a, m, x0, y0);
if (b % g != 0) return false;
mod = m / g;
// x ≡ (x0 * (b/g)) mod (m/g)
i128 t = (i128)x0 * (b / g);
x = norm((ll)(t % mod), mod);
return true;
}
/*
示例 main：
- 读取 a b m
- 第一行输出一组贝祖系数 x y 与 gcd g（格式：x y g）
- 第二行输出 a 在模 m 下的逆元（不存在则输出 -1）
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b, m;
if (!(cin >> a >> b >> m)) return 0;
ll x, y;
ll g = exgcd(a, b, x, y);
cout << x << ' ' << y << ' ' << g << '\n';
cout << inv(a, m) << '\n';
return 0;
}
/*
使用示例：
输入：
30 18 7
输出：
-1 2 6
1
说明：
- exgcd：30*(-1) + 18*2 = 6
- inv：30 在模 7 下等价于 2，2 的逆元为 4；但 inv(30,7) = inv(2,7) = 4。
由于实现输出的是 inv(a, m)，对上述输入会输出 1？不对，重新说明：
a = 30, m = 7 ⇒ a ≡ 2 (mod 7)，2 的逆元为 4，因此程序输出 4。
*/CRT AND EXCRT
/*
CRT 与 EXCRT 模板（同余方程组求解）
功能概述：
- crt(r, m, M): 适用于模数两两互质的情形，求解 x ≡ r[i] (mod m[i])
- excrt(r, m, x, M): 通用情况（模数不必互质），若有解给出最小非负解 x 及周期 M
设计要点：
- 使用扩展欧几里得算法求逆元与合并方程
- 计算中使用 __int128 防溢出；最终结果假定在 64 位有符号范围内
- 约定：
· 所有模 m[i] > 0
· 输入的余数 r[i] 可不在 [0, m[i])，内部会自动归一化
· 对 EXCRT，若无解（余数不一致），返回 false
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
/* 扩展欧几里得：返回 gcd(a,b)，并求出 x,y 使得 a*x + b*y = gcd(a,b) */
ll exgcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = (a >= 0 ? 1 : -1);
y = 0;
return llabs(a);
}
ll x1, y1;
ll g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
/* 将 x 归一化到 [0, m-1]（m > 0） */
inline ll norm(ll x, ll m) {
x %= m;
if (x < 0) x += m;
return x;
}
/* 计算 a 在模 m 下的逆元（要求 gcd(a,m)=1），不存在返回 -1 */
ll inv_mod(ll a, ll m) {
ll x, y;
ll g = exgcd(a, m, x, y);
if (g != 1) return -1;
return norm(x, m);
}
/*
CRT（两两互质版）
输入：
- r: 余数数组 r[i]
- m: 模数数组 m[i]（需两两互质）
输出：
- 返回 pair<bool, pair<ll,ll>>：
· first = true 时，second = {x, M}，其中 x 为最小非负解，M = ∏ m[i]
· first = false 时，表示输入不合法（如 m[i] <= 0 或乘积溢出风险等）
实现：
- x = Σ r[i] * (M/m[i]) * inv(M/m[i] mod m[i]) (mod M)
*/
pair<bool, pair<ll,ll>> crt(const vector<ll>& r, const vector<ll>& m) {
int n = (int)r.size();
if ((int)m.size() != n || n == 0) return {false, {0,0}};
for (ll mi : m) if (mi <= 0) return {false, {0,0}};
// 计算 M = prod m[i]（用 128 位中间变量，最终假设 fit in int64）
i128 M128 = 1;
for (ll mi : m) M128 *= (i128)mi;
ll M = (ll)M128; // 若可能超 64 位，请改为返回 __int128，并实现打印
i128 x128 = 0;
for (int i = 0; i < n; ++i) {
ll mi = m[i];
ll ri = norm(r[i], mi);
ll Mi = (ll)(M128 / mi); // M / mi，仍可能超 64 位，但此处已转回 ll，假设安全
ll inv = inv_mod(Mi % mi, mi); // 互质保证逆元存在
if (inv == -1) return {false, {0,0}}; // 理论不应发生（若 m 互质）
x128 += (i128)ri * (i128)Mi % (i128)M * (i128)inv % (i128)M;
x128 %= (i128)M;
}
ll x = (ll)x128;
x = norm(x, M);
return {true, {x, M}};
}
/*
EXCRT（扩展中国剩余定理）
输入：
- r: 余数数组 r[i]
- m: 模数数组 m[i]（不要求互质）
输出：
- 返回 bool：是否有解
- 若有解：x 为最小非负解，M 为解的周期（所有解为 x + t*M）
做法（逐个合并）：
- 当前解：x ≡ a (mod M)
- 合并下一个方程：x ≡ b (mod m2)
等价于：M * t ≡ (b - a) (mod m2)
设 g = gcd(M, m2)，若 (b - a) % g != 0 则无解
令 M' = M/g, m2' = m2/g, d = (b - a)/g
求 t0 ≡ d * inv(M' mod m2') (mod m2')
新解：a = a + M * t0，M = M * m2'
*/
bool excrt(const vector<ll>& r, const vector<ll>& m, ll& x, ll& M) {
int n = (int)r.size();
if ((int)m.size() != n || n == 0) return false;
for (ll mi : m) if (mi <= 0) return false;
x = norm(r[0], m[0]);
M = m[0];
for (int i = 1; i < n; ++i) {
ll a = x, m1 = M;
ll b = norm(r[i], m[i]), m2 = m[i];
ll c = b - a;
ll s, t;
ll g = exgcd(m1, m2, s, t); // s*m1 + t*m2 = g
if (c % g != 0) return false;
// 归约
ll m1_ = m1 / g;
ll m2_ = m2 / g;
// t0 ≡ (c/g) * inv(m1_ mod m2_) (mod m2_)
ll inv = norm(s, m2_); // s 即为 m1 在模 m2 上的逆的缩放，取模 m2_
i128 t0 = (i128)(c / g) * inv % m2_;
// 合并
i128 nx = (i128)a + (i128)m1 * t0; // 新的代表解
i128 nM = (i128)m1 * m2_; // 新的模（lcm）
// 规范化到 [0, nM)
x = (ll)( (nx % nM + nM) % nM );
M = (ll)nM; // 若可能超 64 位，可改为 __int128
}
return true;
}
/*
示例 main：
- 输入：
k
r1 m1
r2 m2
...
rk mk
- 输出（EXCRT）：
若有解：x M
无解：NO SOLUTION
- 如保证模两两互质，可改为调用 crt，并输出其结果
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
if (!(cin >> k)) return 0;
vector<ll> r(k), m(k);
for (int i = 0; i < k; ++i) cin >> r[i] >> m[i];
ll x, M;
if (excrt(r, m, x, M)) {
cout << x << ' ' << M << '\n';
} else {
cout << "NO SOLUTION\n";
}
// 若已知 m 两两互质，可使用以下代码（示例）：
/*
auto res = crt(r, m);
if (!res.first) cout << "INVALID\n";
else {
auto [x, M] = res.second;
cout << x << ' ' << M << '\n';
}
*/
return 0;
}
/*
使用示例 1（EXCRT 可解）：
输入：
3
2 6
3 9
2 15
输出：
47 90
校验：47 ≡ 2 (mod 6), 47 ≡ 3 (mod 9), 47 ≡ 2 (mod 15)
使用示例 2（EXCRT 无解）：
输入：
2
1 4
2 6
输出：
NO SOLUTION
原因：x ≡ 1 (mod 4) 与 x ≡ 2 (mod 6) 在 mod 2 上矛盾
*/Miller-Rabin
/*
Miller–Rabin 素性测试模板（64 位无符号整数）
功能：
- isprime(n): 判断 0 <= n < 2^64 是否为素数（确定性）
设计要点：
- 将 n-1 表示为 d * 2^s（d 为奇数），对若干“基” a 进行见证测试：
· 计算 x = a^d mod n
· 若 x == 1 或 x == n-1，则本轮通过
· 否则反复平方 x，共 s-1 次，若出现 x == n-1 则通过
· 若所有平方后仍未通过，则 n 为合数
- 为保证对 64 位整数的“确定性”，采用已知覆盖 64 位的基集合：
bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}
- 乘法使用 128 位中间变量（__uint128_t）避免溢出
- 先筛掉若干小素数可加速，并处理边界情况
复杂度：
- 单次测试约 O(k log^3 n)，k 为基的数量（此处固定为 7）
*/
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using u128 = __uint128_t;
/* 乘法取模：返回 (a * b) % mod，使用 128 位中间变量防溢出 */
static inline u64 mul(u64 a, u64 b, u64 mod) {
return (u64)((u128)a * b % mod);
}
/* 快速幂取模：返回 (a^e) % mod */
static inline u64 pw(u64 a, u64 e, u64 mod) {
u64 r = 1 % mod;
a %= mod;
while (e) {
if (e & 1) r = mul(r, a, mod);
a = mul(a, a, mod);
e >>= 1;
}
return r;
}
/*
单基 Miller–Rabin 见证测试
输入：
- n: 待测奇数且 n >= 3
- a: 测试基（a % n != 0 时才有意义）
- d, s: n-1 = d * 2^s，且 d 为奇数
返回：
- true 若 a 不能证明 n 为合数（本轮通过）
- false 若 a 证明 n 为合数
*/
static inline bool mr_once(u64 n, u64 a, u64 d, int s) {
u64 x = pw(a, d, n);
if (x == 1 || x == n - 1) return true;
for (int i = 1; i < s; ++i) {
x = mul(x, x, n);
if (x == n - 1) return true;
}
return false;
}
/*
主函数：isprime
返回：
- true 素数
- false 合数
处理流程：
- 处理小数与偶数
- 与一组小素数比对，加速筛除
- 写成 n-1 = d * 2^s，使用固定基集合进行 MR 测试
*/
bool isprime(u64 n) {
if (n < 2) return false;
// 小数与偶数快速处理
static const u64 small[] = {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL};
for (u64 p : small) {
if (n == p) return true;
if (n % p == 0) return n == p;
}
// 将 n-1 写成 d * 2^s
u64 d = n - 1;
int s = 0;
while ((d & 1) == 0) { d >>= 1; ++s; }
// 64 位确定性基集合（文献与实践中常用的一组）
static const u64 bases[] = {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL};
for (u64 a : bases) {
if (a % n == 0) continue; // 基与 n 取模为 0，无需测试
if (!mr_once(n, a, d, s)) return false;
}
return true;
}
/*
示例 main：
- 输入：
t
n1
n2
...
nt
- 输出：
对每个 ni 输出一行：YES 表示素数，NO 表示合数
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
if (!(cin >> t)) return 0;
while (t--) {
unsigned long long n;
cin >> n;
cout << (isprime(n) ? "YES" : "NO") << '\n';
}
return 0;
}
/*
使用示例：
输入：
5
1
2
17
221
2305843009213693951
输出：
NO
YES
YES
NO
YES
说明：
- 221 = 13 * 17，为合数
- 2305843009213693951 = 2^61 - 1，为素数
*/KMP
/*
KMP（Knuth–Morris–Pratt）字符串匹配模板
功能：
- 构造前缀函数（pi）：pi[i] = 模式串 p[0..i] 的最长相等“真前缀=后缀”的长度
- kmp(t, p)：在主串 t 中查找模式串 p 的所有出现位置（返回起始下标，0 基）
设计要点：
- 利用失败指针（前缀函数）在匹配失败时不回退主串指针，保证 O(n + m)
- 匹配结束后，为了支持重叠匹配，发生一次完整匹配后将 j 回退到 pi[j-1]
复杂度：
- 预处理 O(m)，匹配 O(n)
备注：
- 本模板返回 0 基坐标；示例输出时转换为 1 基更符合常见题面
- 若 p 为空串，按常见竞赛习惯返回空结果（不进行匹配）
*/
#include <bits/stdc++.h>
using namespace std;
/*
函数：get_pi
作用：构造模式串 p 的前缀函数 pi
含义：
- pi[i] = p[0..i] 的最长真前缀与后缀的相等长度
*/
vector<int> get_pi(const string& p) {
int m = (int)p.size();
vector<int> pi(m, 0);
for (int i = 1, j = 0; i < m; ++i) {
// 失配时回退 j 到上一个可匹配的位置
while (j > 0 && p[i] != p[j]) j = pi[j - 1];
if (p[i] == p[j]) ++j;
pi[i] = j;
}
return pi;
}
/*
函数：kmp
作用：在主串 t 中查找模式串 p 的所有出现位置（返回起始下标，0 基）
流程：
- 预处理 pi
- 线性扫描 t，配合失败指针推进/回退 j
*/
vector<int> kmp(const string& t, const string& p) {
int n = (int)t.size(), m = (int)p.size();
vector<int> pos;
if (m == 0) return pos; // 按约定：空模式不匹配任何位置
auto pi = get_pi(p);
for (int i = 0, j = 0; i < n; ++i) {
while (j > 0 && t[i] != p[j]) j = pi[j - 1];
if (t[i] == p[j]) ++j;
if (j == m) {
pos.push_back(i - m + 1); // 记录一次匹配（起始为 0 基）
j = pi[j - 1]; // 支持重叠匹配
}
}
return pos;
}
/*
辅助输出：将 0 基下标转换为 1 基输出（空格分隔）
*/
void print_pos_1based(const vector<int>& pos) {
for (size_t i = 0; i < pos.size(); ++i) {
if (i) cout << ' ';
cout << (pos[i] + 1);
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读取主串 t 与模式串 p（默认不含空格；如需支持空格，可改用 getline）
string t, p;
if (!(cin >> t >> p)) return 0;
auto pos = kmp(t, p);
print_pos_1based(pos); // 输出所有匹配起点（1 基）
// 若需要同时输出前缀函数，可取消下方注释：
/*
auto pi = get_pi(p);
for (int i = 0; i < (int)pi.size(); ++i) {
if (i) cout << ' ';
cout << pi[i];
}
cout << '\n';
*/
return 0;
}
/*
使用示例：
输入：
abaabaaba aba
输出：
1 4 7
说明：
- 在主串 "abaabaaba" 中，模式 "aba" 出现在 1、4、7（1 基）
*/Manacher
/*
Manacher 算法模板 —— 最长回文子串（O(n)）
功能：
- pal_odd(s): 计算所有“奇数长度”回文的半径数组 d1
d1[i] = 以 i 为中心的最长奇回文半径（包含中心），对应长度 = 2*d1[i] - 1
- pal_even(s): 计算所有“偶数长度”回文的半径数组 d2
d2[i] = 以 i-1 与 i 之间为中心的最长偶回文半径，对应长度 = 2*d2[i]
- best_pal(s, d1, d2, st, len): 给出 s 的最长回文子串的起点 st 与长度 len
设计要点：
- 维护当前回文最右端区间 [l, r]，利用对称位置的半径加速扩展
- 奇、偶两种中心分别计算，覆盖所有回文
复杂度：
- 线性 O(n)
*/
#include <bits/stdc++.h>
using namespace std;
/*
函数：pal_odd
作用：计算奇回文半径数组 d1
参数：
- s: 原串
返回：
- d1: 向量，d1[i] 为以 i 为中心的最大奇回文半径（长度 = 2*d1[i]-1）
*/
vector<int> pal_odd(const string& s) {
int n = (int)s.size();
vector<int> d1(n, 0);
int l = 0, r = -1;
for (int i = 0; i < n; ++i) {
int k = 1;
if (i <= r) k = min(d1[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) ++k;
d1[i] = k;
--k;
if (i + k > r) { l = i - k; r = i + k; }
}
return d1;
}
/*
函数：pal_even
作用：计算偶回文半径数组 d2
参数：
- s: 原串
返回：
- d2: 向量，d2[i] 为以 (i-1, i) 为中心的最大偶回文半径（长度 = 2*d2[i]）
*/
vector<int> pal_even(const string& s) {
int n = (int)s.size();
vector<int> d2(n, 0);
int l = 0, r = -1;
for (int i = 0; i < n; ++i) {
int k = 0;
if (i <= r) k = min(d2[l + r - i + 1], r - i + 1);
while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
d2[i] = k;
--k;
if (i + k > r) { l = i - k - 1; r = i + k; }
}
return d2;
}
/*
函数：best_pal
作用：给出 s 的最长回文子串的位置与长度
参数/输出：
- s, d1, d2：预处理得到的回文半径
- st, len：输出最长回文子串的起始下标与长度（0 基）
*/
void best_pal(const string& s, const vector<int>& d1, const vector<int>& d2, int& st, int& len) {
int n = (int)s.size();
st = 0; len = 0;
// 奇回文
for (int i = 0; i < n; ++i) {
int cur = 2 * d1[i] - 1;
if (cur > len) {
len = cur;
st = i - d1[i] + 1;
}
}
// 偶回文
for (int i = 0; i < n; ++i) {
int cur = 2 * d2[i];
if (cur > len) {
len = cur;
st = i - d2[i];
}
}
}
/*
示例 main：
- 输入：一行字符串 s（不含空格；若需含空格，可改用 getline）
- 输出：
第一行：最长回文子串的长度
第二行：最长回文子串本身
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
if (!(cin >> s)) return 0;
auto d1 = pal_odd(s);
auto d2 = pal_even(s);
int st, len;
best_pal(s, d1, d2, st, len);
cout << len << '\n';
cout << s.substr(st, len) << '\n';
return 0;
}
/*
使用示例：
输入：
babad
输出（可能之一）：
3
bab
说明：
- 最长回文为 "bab" 或 "aba"，长度均为 3，程序输出其中之一。
*/单调栈
/*
基于 STL 的单调栈模板（Monotonic Stack）
功能：
- nsl(a): 每个位置 i 的“左侧最近更小元素”的下标（严格小于），若不存在为 -1
- nsr(a): 每个位置 i 的“右侧最近更小元素”的下标（严格小于），若不存在为 n
- ngl(a): 每个位置 i 的“左侧最近更大元素”的下标（严格大于），若不存在为 -1
- ngr(a): 每个位置 i 的“右侧最近更大元素”的下标（严格大于），若不存在为 n
- hist_max(h): 直方图最大矩形面积（常见单调栈应用示例）
设计要点：
- 使用 std::stack<int> 存储“候选下标”，保持栈内对应值单调（增或减）
- 为了得到“严格更小/更大”，在维护单调性时使用 >= 或 <= 进行弹栈
· 更小：用 >= 保证栈内严格递增
· 更大：用 <= 保证栈内严格递减
复杂度：
- 所有函数均为 O(n)
约定：
- 返回的下标为 0 基；无解时左侧返回 -1，右侧返回 n（n 为数组长度）
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
函数：nsl（nearest smaller to left）
作用：左侧最近更小元素下标（严格小于）
实现：维护值“严格递增”的栈（值相等需要弹出）
*/
vector<int> nsl(const vector<ll>& a) {
int n = (int)a.size();
vector<int> L(n, -1);
stack<int> st; // 存储下标，a[st] 严格递增
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
L[i] = st.empty() ? -1 : st.top();
st.push(i);
}
return L;
}
/*
函数：nsr（nearest smaller to right）
作用：右侧最近更小元素下标（严格小于）
实现：从右到左，维护值“严格递增”的栈（值相等需要弹出）
*/
vector<int> nsr(const vector<ll>& a) {
int n = (int)a.size();
vector<int> R(n, n);
stack<int> st; // 存储下标，a[st] 严格递增
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
R[i] = st.empty() ? n : st.top();
st.push(i);
}
return R;
}
/*
函数：ngl（nearest greater to left）
作用：左侧最近更大元素下标（严格大于）
实现：维护值“严格递减”的栈（值相等需要弹出）
*/
vector<int> ngl(const vector<ll>& a) {
int n = (int)a.size();
vector<int> L(n, -1);
stack<int> st; // 存储下标，a[st] 严格递减
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
L[i] = st.empty() ? -1 : st.top();
st.push(i);
}
return L;
}
/*
函数：ngr（nearest greater to right）
作用：右侧最近更大元素下标（严格大于）
实现：从右到左，维护值“严格递减”的栈（值相等需要弹出）
*/
vector<int> ngr(const vector<ll>& a) {
int n = (int)a.size();
vector<int> R(n, n);
stack<int> st; // 存储下标，a[st] 严格递减
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
R[i] = st.empty() ? n : st.top();
st.push(i);
}
return R;
}
/*
示例应用：直方图最大矩形面积
思路：
- 对每个柱 i，左右边界由“最近更小元素”决定：
left = nsl[i] + 1, right = nsr[i] - 1
宽度 = right - left + 1 = nsr[i] - nsl[i] - 1
面积 = h[i] * 宽度
*/
long long hist_max(const vector<ll>& h) {
int n = (int)h.size();
auto L = nsl(h);
auto R = nsr(h);
long long ans = 0;
for (int i = 0; i < n; ++i) {
long long w = (long long)R[i] - L[i] - 1;
ans = max(ans, h[i] * w);
}
return ans;
}
/*
辅助输出：空格分隔输出整型数组（0 基下标；-1 或 n 表示不存在）
*/
template <class T>
void print_arr(const vector<T>& a) {
for (size_t i = 0; i < a.size(); ++i) {
if (i) cout << ' ';
cout << a[i];
}
cout << '\n';
}
/*
示例 main：
- 输入：
n
a1 a2 ... an
- 输出：
四行：NSL、NSR、NGL、NGR 的下标数组（0 基；无解位置为 -1 或 n）
第五行：直方图最大矩形面积
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<ll> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
auto Ls = nsl(a);
auto Rs = nsr(a);
auto Lg = ngl(a);
auto Rg = ngr(a);
print_arr(Ls);
print_arr(Rs);
print_arr(Lg);
print_arr(Rg);
cout << hist_max(a) << '\n';
return 0;
}
/*
使用示例：
输入：
7
2 1 5 6 2 3 1
输出（可能之一）：
-1 -1 1 2 1 5 -1
1 7 4 4 6 6 7
-1 0 -1 -1 3 4 5
2 2 3 5 5 7 7
10
说明：
- 前四行分别为：左更小、右更小、左更大、右更大（无解为 -1 或 n）
- 最后一行是直方图最大矩形面积：对于样例，最大面积为 10（柱 5 和 6 的组合）
*/单调队列
/*
基于 STL 的单调队列模板（Sliding Window + deque）
功能：
- win_min(a, k): 返回数组 a 所有长度为 k 的滑动窗口的最小值
- win_max(a, k): 返回数组 a 所有长度为 k 的滑动窗口的最大值
设计要点：
- 使用 std::deque<int> 存下标，队列内对应的值保持单调
· 最小值：保持队尾到队首严格递增（入队时弹出 >= 的元素）
· 最大值：保持队尾到队首严格递减（入队时弹出 <= 的元素）
- 维护窗口有效性：当队首下标 < 当前窗口左端时弹出
- 每个元素最多入队、出队一次，总复杂度 O(n)
约定：
- 若 k <= 0 或 k > n，则返回空结果
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
函数：win_min
作用：计算长度为 k 的每个滑动窗口的最小值
实现细节：
- dq 存储下标，保证 a[dq[0]] <= a[dq[1]] <= ...（递增）
- 入队时，弹出队尾所有 >= a[i] 的下标，再将 i 入队
- 维护窗口左边界 L = i - k + 1，弹出 dq.front() < L 的下标
- 当 i >= k - 1 时，窗口形成，最小值为 a[dq.front()]
*/
vector<ll> win_min(const vector<ll>& a, int k) {
int n = (int)a.size();
vector<ll> res;
if (k <= 0 || k > n) return res;
deque<int> dq;
for (int i = 0; i < n; ++i) {
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
int L = i - k + 1;
while (!dq.empty() && dq.front() < L) dq.pop_front();
if (i >= k - 1) res.push_back(a[dq.front()]);
}
return res;
}
/*
函数：win_max
作用：计算长度为 k 的每个滑动窗口的最大值
实现细节：
- dq 存储下标，保证 a[dq[0]] >= a[dq[1]] >= ...（递减）
- 入队时，弹出队尾所有 <= a[i] 的下标，再将 i 入队
- 维护窗口左边界 L = i - k + 1，弹出 dq.front() < L 的下标
- 当 i >= k - 1 时，窗口形成，最大值为 a[dq.front()]
*/
vector<ll> win_max(const vector<ll>& a, int k) {
int n = (int)a.size();
vector<ll> res;
if (k <= 0 || k > n) return res;
deque<int> dq;
for (int i = 0; i < n; ++i) {
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
int L = i - k + 1;
while (!dq.empty() && dq.front() < L) dq.pop_front();
if (i >= k - 1) res.push_back(a[dq.front()]);
}
return res;
}
/*
辅助输出：空格分隔
*/
template <class T>
void print_vec(const vector<T>& v) {
for (size_t i = 0; i < v.size(); ++i) {
if (i) cout << ' ';
cout << v[i];
}
cout << '\n';
}
/*
示例 main：
- 输入：
n k
a1 a2 ... an
- 输出：
第一行：每个窗口的最小值
第二行：每个窗口的最大值
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
if (!(cin >> n >> k)) return 0;
vector<ll> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
auto mn = win_min(a, k);
auto mx = win_max(a, k);
print_vec(mn);
print_vec(mx);
return 0;
}
/*
使用示例：
输入：
8 3
1 3 -1 -3 5 3 6 7
输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明：
- 长度为 3 的滑动窗口最小值与最大值分别如上。
*/几何模板！！！
/*
二维计算几何模板（点 / 直线 / 线段 / 圆 / 多边形）
目标：
- 封装常用几何原语与运算，变量与函数名简洁，注释详细
- 涵盖：点与向量、直线/线段、圆、相交/距离/投影/切线、多边形（面积/周长/重心/点内判定/凸包/直径）等
精度：
- 使用 double 浮点；EPS = 1e-9
- 用 sgn(x) 将实数比较离散化为 {-1,0,1}，避免直接用 == 比较
约定：
- “相交/在上”类判断均默认“含等号”（即接触=相交，在边界=在上）
- 所有坐标单位、角度（弧度）的度量需与题目一致
复杂度：
- 除凸包 O(n log n)、直径（旋转卡壳）O(n)、裁剪 O(n) 外，多数基本操作 O(1)
*/
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
const double PI = acos(-1.0);
int sgn(double x) { return (x > EPS) - (x < -EPS); }
double clamp1(double x) { return x < -1 ? -1 : (x > 1 ? 1 : x); }
/* ====================== 点与向量 ======================
定义：
- P 既表示平面点，也作为从原点或某点出发的向量
说明：
- operator< 用于排序（严格弱序）；不引入 EPS，避免破坏传递性
- operator== 使用 EPS 判断“几何相等”
*/
struct P {
double x, y;
P() : x(0), y(0) {}
P(double _x, double _y) : x(_x), y(_y) {}
// 向量加减、数乘/除
P operator + (const P& o) const { return P(x + o.x, y + o.y); }
P operator - (const P& o) const { return P(x - o.x, y - o.y); }
P operator * (double k) const { return P(x * k, y * k); }
P operator / (double k) const { return P(x / k, y / k); }
// 排序与几何相等
bool operator < (const P& o) const { return x < o.x || (x == o.x && y < o.y); }
bool operator == (const P& o) const { return sgn(x - o.x) == 0 && sgn(y - o.y) == 0; }
};
/* 基础运算：
- dot(a,b) 点积：|a||b|cosθ，平行投影量
- crs(a,b) 叉积：|a||b|sinθ，带符号面积（a 在 b 左侧为正）
- len(a) 长度
- len2(a) 长度平方（免开根更高效）
- unit(a) 单位向量（零向量返回 {0,0}）
- rot(a,θ) 逆时针旋转
- perp(a) 逆时针旋转 90°（与 a 垂直）
- ccw(a,b,c) 方向：>0 左转，<0 右转，=0 共线
*/
double dot(P a, P b) { return a.x * b.x + a.y * b.y; }
double crs(P a, P b) { return a.x * b.y - a.y * b.x; }
double len(P a) { return hypot(a.x, a.y); }
double len2(P a){ return dot(a, a); }
P unit(P a) { double L = len(a); return L == 0 ? P(0,0) : a / L; }
P rot(P a, double th) { return P(a.x * cos(th) - a.y * sin(th), a.x * sin(th) + a.y * cos(th)); }
P perp(P a) { return P(-a.y, a.x); }
int ccw(P a, P b, P c) { return sgn(crs(b - a, c - a)); }
/* ====================== 直线与线段 ======================
约定：
- 用 L 表示有向线（或线段）ab；当作为“直线”用时表示过 a,b 的无限延长线
*/
struct L {
P a, b; // 有向端点 a->b
L() {}
L(P _a, P _b) : a(_a), b(_b) {}
P v() const { return b - a; } // 方向向量
};
/* 投影与反射：
- proj(p,l): p 在直线 l 上的正交投影
- refl(p,l): p 关于直线 l 的镜像点（先投影，再关于投影对称）
注意：
- l 需为“直线”（无限延长），不区分是否在“线段”范围内
*/
P proj(P p, L l) {
P v = l.v();
return l.a + v * (dot(p - l.a, v) / dot(v, v));
}
P refl(P p, L l) { return proj(p, l) * 2 - p; }
/* 距离：
- dist_pl: 点到直线距离
- dist_ps: 点到线段距离（若投影不在线段内取端点最近）
- dist_ll: 直线到直线距离（相交=0，平行且异线=到其中一条直线的距离）
- dist_ss: 线段到线段距离（相交=0，否则端点到对段最小距离）
*/
double dist_pl(P p, L l) {
return fabs(crs(l.v(), p - l.a)) / len(l.v());
}
double dist_ps(P p, L s) {
P v = s.v();
double t = dot(p - s.a, v) / dot(v, v);
if (t < 0) return len(p - s.a);
if (t > 1) return len(p - s.b);
P q = s.a + v * t;
return len(p - q);
}
double dist_ll(L l1, L l2) {
if (sgn(crs(l1.v(), l2.v())) != 0) return 0.0; // 相交（不平行）距离为 0
return dist_pl(l2.a, l1); // 平行：任取一点到另一条线的距离
}
double dist_ss(L s1, L s2) {
if (sgn(crs(s1.v(), s2.v())) != 0 && // 先快速判相交（Proper 或端点接触）
(ccw(s1.a, s1.b, s2.a) * ccw(s1.a, s1.b, s2.b) <= 0) &&
(ccw(s2.a, s2.b, s1.a) * ccw(s2.a, s2.b, s1.b) <= 0))
return 0.0;
double d = 1e300;
d = min(d, dist_ps(s1.a, s2));
d = min(d, dist_ps(s1.b, s2));
d = min(d, dist_ps(s2.a, s1));
d = min(d, dist_ps(s2.b, s1));
return d;
}
/* 点与线段位置关系：
- on_seg(p,s): p 是否在线段 s 上（含端点）
- parallel/collinear：两直线是否平行/共线
*/
bool on_seg(P p, L s) {
return sgn(crs(s.b - s.a, p - s.a)) == 0 && sgn(dot(p - s.a, p - s.b)) <= 0;
}
bool parallel(L l1, L l2) { return sgn(crs(l1.v(), l2.v())) == 0; }
bool collinear(L l1, L l2) { return parallel(l1, l2) && sgn(crs(l2.a - l1.a, l1.v())) == 0; }
/* 交点与相交性：
- inter_ll(l1,l2,out): 直线唯一交点（不平行），返回 bool
- inter_ss_proper(s1,s2): 线段严格相交（交点不含端点）
- inter_ss(s1,s2): 线段一般相交（含端点接触/重合边界视为相交）
- inter_ss_point(s1,s2,out): 线段唯一交点（不含重合/多解），返回 bool
注意：
- 对“重合线段”没有单一交点，inter_ss_point 返回 false
*/
bool inter_ll(L l1, L l2, P& out) {
double d = crs(l1.v(), l2.v());
if (sgn(d) == 0) return false;
double t = crs(l2.a - l1.a, l2.v()) / d;
out = l1.a + l1.v() * t;
return true;
}
bool inter_ss_proper(L s1, L s2) {
int c1 = ccw(s1.a, s1.b, s2.a), c2 = ccw(s1.a, s1.b, s2.b);
int c3 = ccw(s2.a, s2.b, s1.a), c4 = ccw(s2.a, s2.b, s1.b);
return c1 * c2 < 0 && c3 * c4 < 0;
}
bool inter_ss(L s1, L s2) {
if (inter_ss_proper(s1, s2)) return true;
if (on_seg(s2.a, s1) || on_seg(s2.b, s1) || on_seg(s1.a, s2) || on_seg(s1.b, s2)) return true;
return false;
}
bool inter_ss_point(L s1, L s2, P& out) {
if (!inter_ss(s1, s2)) return false;
if (parallel(s1, s2)) return false; // 重合/平行：无唯一交点
return inter_ll(s1, s2, out);
}
/* ====================== 圆 ======================
C：
- o：圆心
- r：半径（≥ 0）
contains(p, strict):
- 判断点在圆内；strict=true 表示“严格在内”（不含边界）
*/
struct C {
P o; double r;
C() : o(), r(0) {}
C(P _o, double _r) : o(_o), r(_r) {}
bool contains(P p, bool strict=false) const {
return sgn(len2(p - o) - r*r) < (strict ? 0 : 1);
}
};
/* 圆与直线/线段交点：
- inter_cl(c,l): 与直线交点（0/1/2 个）
· 思路：圆心到直线作垂线，若距离 d>r 无交；=r 一切；<r 两交
- inter_cs(c,s): 与线段交点（从 inter_cl 结果中过滤在段上的点）
*/
vector<P> inter_cl(C c, L l) {
P h = proj(c.o, l); // 垂足
double d = len(h - c.o); // 圆心到直线距离
int s = sgn(c.r - d);
if (s < 0) return {}; // 相离
if (s == 0) return {h}; // 相切
double t = sqrt(max(0.0, c.r * c.r - d * d));
P dir = unit(l.v());
return { h - dir * t, h + dir * t };
}
vector<P> inter_cs(C c, L s) {
vector<P> pts = inter_cl(c, s);
vector<P> res;
for (auto& p : pts) if (on_seg(p, s)) res.push_back(p);
return res;
}
/* 圆与圆交点：
- inter_cc(c1,c2): 0/1/2 个交点
· 同心：无唯一解（返回空）
· 相离/内含（距离过大/过小）：无交
· 否则：计算两圆心连线上的脚点 m 以及左右偏移 off
*/
vector<P> inter_cc(C c1, C c2) {
P d = c2.o - c1.o;
double D = len(d);
if (sgn(D) == 0) return {}; // 同心（无唯一交点）
if (sgn(D - (c1.r + c2.r)) > 0) return {}; // 相离
if (sgn(fabs(c1.r - c2.r) - D) > 0) return {}; // 内含
double a = (c1.r * c1.r - c2.r * c2.r + D * D) / (2 * D);
double h2 = c1.r * c1.r - a * a;
P m = c1.o + unit(d) * a; // 中垂线脚点
if (sgn(h2) == 0) return {m}; // 相切
double h = sqrt(max(0.0, h2));
P off = perp(unit(d)) * h;
return { m - off, m + off };
}
/* 点到圆的切线：
- tan_pc(p,c): 返回切点（0/1/2 个）
· p 圆内：无切线；圆上：1 个切点（自身）；圆外：2 个切点
*/
vector<P> tan_pc(P p, C c) {
P v = p - c.o;
double d2 = len2(v), r2 = c.r * c.r;
int s = sgn(d2 - r2);
if (s < 0) return {};
if (s == 0) return {p};
// 切点公式（向量推导）
P u = v * (r2 / d2);
P w = perp(v) * (c.r * sqrt(max(0.0, d2 - r2)) / d2);
return { c.o + u - w, c.o + u + w };
}
/* 两圆的公切线（外/内）：
- tan_cc(a,b): 返回每条切线在两圆上的“切点对”（p1 on a, p2 on b）
· 若同心：无穷多/无（此模板返回空）
· 总计最多 4 条切线（外公切线 2，内公切线 2）
*/
vector<pair<P,P>> tan_cc(C a, C b) {
vector<pair<P,P>> res;
P d = b.o - a.o;
double sq = len2(d);
if (sgn(sq) == 0) return res; // 同心
double D = sqrt(sq);
for (int sgn_rb : {-1, 1}) { // -1: 内，+1: 外
double r = (b.r * sgn_rb - a.r) / D;
double h2 = 1 - r * r;
if (h2 < -EPS) continue;
h2 = max(0.0, h2);
P u = d * r;
P v = perp(d) * sqrt(h2);
for (int sgn_v : {-1, 1}) {
P dir = (u + v * sgn_v) / D; // 方向单位向量
P p1 = a.o + dir * a.r;
P p2 = b.o + dir * (b.r * sgn_rb);
res.push_back({p1, p2});
}
}
return res;
}
/* 两圆相交面积：
- inter_area_cc(c1,c2): 返回两圆的交集面积
· 相离：0；内含：小圆面积；一般：扇形-三角形之和
*/
double inter_area_cc(C c1, C c2) {
double d = len(c1.o - c2.o);
double r1 = c1.r, r2 = c2.r;
if (sgn(d - (r1 + r2)) >= 0) return 0.0; // 相离/外切
if (sgn(d - fabs(r1 - r2)) <= 0) { // 内含/内切
double r = min(r1, r2);
return PI * r * r;
}
double a1 = acos(clamp1((r1*r1 + d*d - r2*r2) / (2*r1*d)));
double a2 = acos(clamp1((r2*r2 + d*d - r1*r1) / (2*r2*d)));
double s1 = r1*r1 * (a1 - sin(2*a1)/2);
double s2 = r2*r2 * (a2 - sin(2*a2)/2);
return s1 + s2;
}
/* ====================== 多边形（简单/凸） ======================
Poly：
- 用 vector<P> 表示多边形顶点序列（可顺/逆时针）
- 若显式要求“凸多边形”，应先用凸包或其它方式保证
*/
using Poly = vector<P>;
/* 面积与周长：
- area2(pg): 有向面积的两倍（>0 CCW, <0 CW）
- area(pg): 绝对面积
- perim(pg): 周长（首尾相连）
注意：
- 面积公式使用“叉积求和”（Shoelace），允许点列重复，结果仍正确
*/
double area2(const Poly& pg) {
long double s = 0;
int n = (int)pg.size();
for (int i = 0; i < n; ++i)
s += (long double)crs(pg[i], pg[(i + 1) % n]);
return (double)s;
}
double area(const Poly& pg) { return fabs(area2(pg)) / 2.0; }
double perim(const Poly& pg) {
double p = 0;
int n = (int)pg.size();
for (int i = 0; i < n; ++i) p += len(pg[(i + 1) % n] - pg[i]);
return p;
}
/* 重心（质心）：
- centroid(pg): 对简单多边形的“几何中心”（均匀密度）
退化：
- 当面积为 0（退化为线段/点），返回顶点平均值作为退化重心
*/
P centroid(const Poly& pg) {
double A2 = area2(pg);
if (sgn(A2) == 0) {
P c{0,0};
for (auto& p : pg) c = c + p;
return pg.empty() ? P(0,0) : c / (double)pg.size();
}
long double cx = 0, cy = 0;
int n = (int)pg.size();
for (int i = 0; i < n; ++i) {
long double c = crs(pg[i], pg[(i + 1) % n]);
cx += (pg[i].x + pg[(i + 1) % n].x) * c;
cy += (pg[i].y + pg[(i + 1) % n].y) * c;
}
cx /= (3.0L * A2);
cy /= (3.0L * A2);
return P((double)cx, (double)cy);
}
/* 点在多边形内（射线法）：
- in_poly(pg,p): 2=严格内部，1=在边上，0=外部
细节：
- 特判边上：on_seg
- 射线与边相交计数时需避免“顶点双计”，采用半开区间策略
*/
int in_poly(const Poly& pg, P p) {
bool in = false;
int n = (int)pg.size();
for (int i = 0, j = n - 1; i < n; j = i++) {
P a = pg[j], b = pg[i];
if (on_seg(p, L(a, b))) return 1;
bool up = (b.y > p.y) != (a.y > p.y);
if (up) {
double x = (b.x - a.x) * (p.y - a.y) / (b.y - a.y + 0.0) + a.x;
if (x > p.x) in = !in;
}
}
return in ? 2 : 0;
}
/* 凸包（Andrew 单调链）：
- hull(pts): 输入可含重复点；输出 CCW 顺序且首尾不重复
细节：
- 当需要“严格凸包”（去除共线边上的点），在判定中使用 <0；本模板使用 <=0 以去除共线中间点
*/
Poly hull(vector<P> p) {
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int n = (int)p.size();
if (n <= 1) return p;
Poly lo, up;
for (int i = 0; i < n; ++i) {
while (lo.size() >= 2 && ccw(lo[lo.size()-2], lo.back(), p[i]) <= 0) lo.pop_back();
lo.push_back(p[i]);
}
for (int i = n - 1; i >= 0; --i) {
while (up.size() >= 2 && ccw(up[up.size()-2], up.back(), p[i]) <= 0) up.pop_back();
up.push_back(p[i]);
}
lo.pop_back(); up.pop_back();
lo.insert(lo.end(), up.begin(), up.end());
return lo;
}
/* 凸多边形直径（最远点对距离平方）：
- dia_convex(ch): 输入为凸包（CCW）；旋转卡壳 O(n)
返回：
- (i, j, dist2)：最远点对的两个下标及其距离平方
细节：
- 对 n=1/2 分别特判
*/
tuple<int,int,double> dia_convex(const Poly& ch) {
int n = (int)ch.size();
if (n == 1) return {0, 0, 0.0};
if (n == 2) return {0, 1, len2(ch[1] - ch[0])};
double best = 0; int bi = 0, bj = 0;
int j = 1;
for (int i = 0; i < n; ++i) {
int ni = (i + 1) % n;
while (true) {
int nj = (j + 1) % n;
double cur = fabs(crs(ch[ni] - ch[i], ch[nj] - ch[i]));
double prv = fabs(crs(ch[ni] - ch[i], ch[j] - ch[i]));
if (cur > prv + EPS) j = nj;
else break;
}
double d2 = len2(ch[i] - ch[j]);
if (d2 > best) best = d2, bi = i, bj = j;
}
return {bi, bj, best};
}
/* 多边形按半平面裁剪：
- cut_poly(pg, a, b): 保留直线 a->b 的左侧（含边界），返回新多边形
用途：
- 单条直线裁剪（凸/非凸皆可）；多半平面交可多次调用
细节：
- 边跨越裁剪线时，加入交点（线段与直线的唯一交点）
*/
Poly cut_poly(const Poly& pg, P a, P b) {
Poly res;
int n = (int)pg.size();
for (int i = 0; i < n; ++i) {
P c = pg[i], d = pg[(i + 1) % n];
double c1 = crs(b - a, c - a);
double c2 = crs(b - a, d - a);
if (sgn(c1) >= 0) res.push_back(c); // 当前点在左侧（或边上）
if (sgn(c1) * sgn(c2) < 0) { // 跨越裁剪线，加入交点
L s(c, d), l(a, b);
double t = crs(a - c, l.v()) / crs(s.v(), l.v()); // c + t*(d-c)
P inter = c + (d - c) * t;
res.push_back(inter);
}
}
// 去除相邻重复点与首尾重复
if (!res.empty()) {
Poly t;
t.reserve(res.size());
for (int i = 0; i < (int)res.size(); ++i) {
if (i == 0 || !(res[i] == res[i - 1])) t.push_back(res[i]);
}
if (t.size() >= 2 && t.front() == t.back()) t.pop_back();
return t;
}
return res;
}
/* ====================== 示例 main（演示常用 API） ======================
输入：
n
x1 y1
...
xn yn
q
q 行点坐标，查询“点在多边形内”结果
输出：
- 多边形面积、周长、重心
- 凸包点数与直径长度
- 每个查询点的 IN/ON/OUT
提示：
- 根据题目需要可替换/扩展 main；上方库函数可直接复用
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
Poly pg(n);
for (int i = 0; i < n; ++i) cin >> pg[i].x >> pg[i].y;
cout.setf(ios::fixed); cout << setprecision(10);
// 多边形基础量
cout << "area " << area(pg) << '\n';
cout << "perim " << perim(pg) << '\n';
P cen = centroid(pg);
cout << "centroid " << cen.x << ' ' << cen.y << '\n';
// 凸包与直径
Poly ch = hull(pg);
auto [i, j, d2] = dia_convex(ch);
cout << "hull_sz " << (int)ch.size() << '\n';
cout << "diameter " << sqrt(max(0.0, d2)) << '\n';
// 点内判定演示
int q; cin >> q;
while (q--) {
P p; cin >> p.x >> p.y;
int res = in_poly(pg, p);
cout << (res == 2 ? "IN" : res == 1 ? "ON" : "OUT") << '\n';
}
return 0;
}
/*
使用示例：
输入：
5
0 0
4 0
5 2
2 4
-1 2
3
2 2
5 5
0 0
输出（可能之一）：
area 16.0000000000
perim 16.9442719100
centroid 2.0000000000 1.8000000000
hull_sz 5
diameter 5.0000000000
IN
OUT
ON
更多用法提示：
- 线段最短距离：dist_ss({A,B},{C,D})
- 点到线/线段距离：dist_pl(P,L)、dist_ps(P,Seg)
- 线/段交点：inter_ll、inter_ss_point
- 圆与线/段/圆交：inter_cl、inter_cs、inter_cc
- 点到圆切线：tan_pc；两圆公切线：tan_cc
- 圆交面积：inter_area_cc
- 半平面裁剪（单条直线）：cut_poly
*/