暑假更新了一些数据结构和字符串。
[TOC]
1 数据结构
1.1 并查集
int p[N]; //存储每个点的祖宗节点
// int size[N]; 维护size
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
void init (int x) {
for (int i = 0; i <= x; i ++ ) {
p[i] = i;
// size[i] = 1; 维护size
}
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
// size[b] += size[a];维 护size1.2 单调栈
找出每个数左边离它最近的比它大/小的数
stack<int> s;
for (int i = 1; i <= n; i ++ )
{
while (sz(s) && check(s.top(), i)) s.pop();
s.push(i);
}1.3 单调队列
// 滑动窗口
int a[N], q[N]; // q为单调队列，需要注意，队列中存放的是数组下标。
int main()
{
int n, k;
//n个数，窗口长度为k
cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int hh = 0, tt = -1; // hh为队列头，tt为队列尾。tt < hh的原因是防止在刚进入循环时判断出错，所以要将tt小于hh，从而达到先入一个数的情况。
for (int i = 0; i < n; i ++ ){ // 模拟队尾碰到新数a[i]的过程
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ; // 单调队列长度大于k，队头出队，加上hh <= tt的原因主要是防止初始状态时tt < hh。
while (hh <= tt && a[q[tt]] >= a[i]) tt --; // 碰到新数a[i]后，若当前队尾大于a[i]，则放入后不满足单调递减
q[ ++ tt] = i; // 新元素入队
if (i >= k - 1) printf("%d ", a[q[hh]]); // 用单调队列维护一个单调递减的区间，故每次窗口内最大值一定是队头
}
printf("\n");
// 以下同上，改为维护单调递增即可。
hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ){
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
printf("\n");
return 0;
}1.4 树状数组
1.4.1 单点修改与区间查询
int t[maxn];
int lowbit (int x) {
return x & -x;
}
void add(int x, int k){ // 单点修改， 可用于添数或建树
for (; x <= n; x += x & -x) t[x] += k;
}
int query(int x){ // 区间查询 (1 ~ x)
int ans = 0;
for (; x; x -= x & -x) ans += t[x];
return ans;
}
int range (int l, int r) { // 区间查询 (l ~ r)
return query(r) - query(l - 1);
}
1.4.2 区间修改与单点查询
int t[maxn], q[maxn]; // 用t数组维护差分数组
int lowbit (int x) {
return x & -x;
}
void add(int x, int k){
for (; x <= n; x += x & -x) t[x] += k;
}
int query(int x){
int ans = 0;
for (; x; x -= x & -x) ans += t[x];
return ans;
}
int range (int l, int r) {
return query(r) - query(l - 1);
}
signed main()
{
cin >> n >> p;
for (int i = 1; i <= n; i ++ ){
cin >> q[i];
add(i, q[i] - q[i - 1]);
}
while (p -- ){
int op, l, r, x;
cin >> op;
if (op == 1){
cin >> l >> r >> x;
add(l, x), add(r + 1, -x);
}
if (op == 2){
cin >> x;
cout << q[x] + ask(x) << endl; // ask(x)即为q[x]的增量
}
}
return 0;
}
1.4.3 区间修改与区间查询
//区间修改与区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p;
int q[1123456], t[1123456], s[1123456], sum[1123456];
inline int lowbit(int x)
{
return x & -x;
}
void add1(int x, int k)
{
for (int i = x; i <= n; i += lowbit(i)) t[i] += k, s[i] += x * k;
}
int ask1(int x)
{
int ans = 0;
for (int i = x; i; i -= lowbit(i)) ans += (x + 1) * t[i] - s[i];
return ans;
}
signed main()
{
cin >> n >> p;
for (int i = 1; i <= n; i ++ ){
cin >> q[i];
sum[i] = q[i] + sum[i - 1];
add1(i, q[i] - q[i - 1]);
}
while (p -- ){
int op, l, r, x;
cin >> op;
if (op == 1){
cin >> l >> r >> x;
add1(l, x), add1(r + 1, -x);
}
if (op == 2){
cin >> l >> r;
cout << ask1(r) - ask1(l - 1) << endl;
}
}
return 0;
}1.5 线段树
// pushup
void pushup1(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
} // 父节点的区间和等于左右儿子的区间和。
void pushup2(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
} // 父节点的最大值等于左右儿子的最大值。
// pushdown
void pushdown(int u) // 例为维护区间加的lazytag
{
auto &r = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (r.add){
left.add += r.add, left.sum += (left.r - left.l + 1) * r.add;
right.add += r.add, right.sum += (right.r - right.l + 1) * r.add;
r.add = 0;
}
}
// build
void build (int u, int l, int r) {
if (l == r) tr[u] = {l, r, q[r]};
else {
tr[u] = {l, r, q[r], 0}; // 该节点的左端点，右端点，以及维护的值和lazytag（可以不为1）
int mid = l + r >> 1;
build(u << 1, l, mid); // 向左下递归建树
build(u << 1 | 1, mid + 1, r); // 向右下递归建树
pushup(u); // 最后自底向上更新节点所维护的值
}
}
//modify
// 1.单点修改
void modify1(int u, int x, int v) // x为待修改的数的下标，v为修改后的值
{
if (tr[u].l == x && tr[u].r == x) tr[u].v = v; // 修改
else{ // 未达到就继续递归
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u); // 修改后自底向上更新一下。
}
}
// 2.区间修改（需要lazytag）
void modify2(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
//query
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u); // 如果有则加
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum += query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}1.6 对顶堆
int q[i];
priority_queue<int> bg; // 大根堆
priority_queue<int, vector<int>, greater<int>> ss; // 小根堆
//bg.push(q[1]);
int mid = q[1];
cout << mid << endl;
for (int i = 2; i <= n; i ++ ) {
if (q[i] > mid) ss.push(q[i]);
else bg.push(q[i]);
if (i & 1) { // 当i为奇数输出中位数
while (bg.size() != ss.size()) {
if (bg.size() > ss.size()) {
ss.push(mid);v,
mid = bg.top();
bg.pop();
}
else {
bg.push(mid);
mid = ss.top();
ss.pop();
}
}
cout << mid << endl;
}
}1.7 主席树
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, len;
int q[maxn], a[maxn];
int root[maxn], now = 0;
struct node {
int l, r, v;
}tr[maxn * 20];
int build (int l, int r) {
int p = ++ now, mid = (l + r) >> 1;
if (l < r) {
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
}
tr[p].v = 0;
return p;
}
int update (int pre, int l, int r, int v) {
int p = ++ now, mid = (l + r) >> 1;
tr[p].l = tr[pre].l, tr[p].r = tr[pre].r, tr[p].v = tr[pre].v + 1;
if (l < r) {
if (v <= mid) tr[p].l = update(tr[pre].l, l, mid, v);
else tr[p].r = update(tr[pre].r, mid + 1, r, v);
}
return p;
}
int query (int x, int y, int l, int r, int k) {
if (l == r) return l;
int sum = tr[tr[y].l].v - tr[tr[x].l].v, mid = (l + r) >> 1;
if (k <= sum) return query(tr[x].l, tr[y].l, l, mid, k);
else return query(tr[x].r, tr[y].r, mid + 1, r, k - sum);
}
int main () {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &q[i]);
a[i] = q[i];
}
sort(q + 1, q + n + 1);
len = unique(q + 1, q + n + 1) - (q + 1);
for (int i = 1; i <= n; i ++ ) {
a[i] = lower_bound(q + 1, q + len + 1, a[i]) - q;
}
root[0] = build(1, len);
for (int i = 1; i <= n; i ++ ) {
root[i] = update(root[i - 1], 1, len, a[i]);
}
while (m -- ) {
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
int ans = query(root[l - 1], root[r], 1, len, k);
printf("%d\n", q[ans]);
}
}1.8 Treap
1.8.1 旋转Treap
int tt;
int n, m, k;
int now, root;
int sz[maxn], key[maxn], cnt[maxn], rd[maxn], son[maxn][2];
inline void push_up(int x) {
sz[x] = sz[son[x][0]] + sz[son[x][1]] + cnt[x];
}
inline void rotate (int &x, int y) {
int ii = son[x][y ^ 1];
son[x][y ^ 1] = son[ii][y];
son[ii][y] = x;
push_up(x), push_up(ii);
x = ii;
}
void insert (int &u, int x) {
if (!u) {
u = ++ now;
sz[u] = cnt[u] = 1;
key[u] = x;
rd[u] = rand();
return;
}
if (key[u] == x) {
cnt[u] ++ ;
sz[u] ++ ;
return;
}
int d = (x > key[u]);
insert(son[u][d], x);
if (rd[u] < rd[son[u][d]]) {
rotate(u, d ^ 1);
}
push_up(u);
}
void del (int &u, int x) {
if (!u) return;
if (x != key[u]) {
del (son[u][x > key[u]], x);
}
else {
if (!son[u][0] && !son[u][1]) {
cnt[u] -- ;
sz[u] -- ;
if (cnt[u] == 0) u = 0;
}
else if (son[u][0] && !son[u][1]) {
rotate(u, 1);
del (son[u][1], x);
}
else if (!son[u][0] && son[u][1]) {
rotate(u, 0);
del (son[u][0], x);
}
else {
int d = rd[son[u][0]] > rd[son[u][1]];
rotate(u, d);
del(son[u][d], x);
}
}
push_up(u);
}
int get_rank(int u, int x) { // 得到排名
if (!u) return 0;
if (key[u] == x) return sz[son[u][0]] + 1;
if (key[u] < x) return sz[son[u][0]] + cnt[u] + get_rank(son[u][1], x);
return get_rank(son[u][0], x);
}
int find (int u, int x) { // 查询排名
if (!u) return 0;
if(sz[son[u][0]] >= x) {
return find(son[u][0], x);
}
else if (sz[son[u][0]] + cnt[u] < x) {
return find(son[u][1], x - cnt[u] - sz[son[u][0]]);
}
else return key[u];
}
int pre (int u, int x) { // 查询前驱
if (!u) return -inf;
if (key[u] >= x) {
return pre(son[u][0], x);
}
else return max(key[u], pre(son[u][1], x));
}
int suf (int u, int x) { // 查询后继
if (!u) return inf;
if (key[u] <= x) {
return suf(son[u][1], x);
}
else return min(key[u], suf(son[u][0], x));
}
void solve() {
int query;
cin >> query;
while (query -- ) {
int op, x;
cin >> op >> x;
if (op == 1) insert(root, x);
if (op == 2) del(root, x);
if (op == 3) cout << get_rank(root, x) << endl;
if (op == 4) cout << find(root, x) << endl;
if (op == 5) cout << pre(root, x) << endl;
if (op == 6) cout << suf(root, x) << endl;
}
}1.8.2 Fhq Treap
mt19937 rnd(233);
int root, idx;
int x, y, z;
struct fhq {
int l, r;
int key, val; // key权值，val堆值
int size;
}tr[maxn];
inline int get_node (int key) {
tr[ ++ idx].key = key;
tr[idx].val = rnd();
tr[idx].size = 1;
return idx;
}
inline void pushup (int u) {
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}
inline void split (int u, int k, int &x, int &y) {
if (!u) x = y = 0;
else {
if (tr[u].key <= k) {
x = u;
split(tr[u].r, k, tr[u].r, y);
}
else {
y = u;
split(tr[u].l, k, x, tr[u].l);
}
pushup(u);
}
}
inline int merge (int x, int y) {
if (!x || !y) return x + y;
if (tr[x].val > tr[y].val) {
tr[x].r = merge(tr[x].r, y);
pushup(x); return x;
}
else {
tr[y].l = merge(x, tr[y].l);
pushup(y); return y;
}
}
inline void insert (int k) {
split (root, k, x, y);
root = merge(merge(x, get_node(k)), y);
}
inline void del (int k) {
split (root, k, x, z);
split (x, k - 1, x, y);
y = merge(tr[y].l, tr[y].r);
root = merge(merge(x, y), z);
}
inline int get_rank (int k) {
split (root, k - 1, x, y);
k = tr[x].size + 1;
root = merge(x, y);
return k;
}
inline int get_key (int k) {
int p = root;
while (p) {
if (tr[tr[p].l].size + 1 == k) {
break;
}
else if (tr[tr[p].l].size >= k) {
p = tr[p].l;
}
else {
k -= tr[tr[p].l].size + 1;
p = tr[p].r;
}
}
return tr[p].key;
}
inline int pre (int k) {
split (root, k - 1, x, y);
int p = x;
while (tr[p].r) p = tr[p].r;
k = tr[p].key;
root = merge(x, y);
return k;
}
inline int suf (int k) {
split (root, k, x, y);
int p = y;
while (tr[p].l) p = tr[p].l;
k = tr[p].key;
root = merge(x, y);
return k;
}
void solve() {
read(n);
for (int i = 1; i <= n; i ++ ) {
int op, x; read(op); read(x);
if (op == 1) insert(x);
else if (op == 2) del(x);
else if (op == 3) printf("%lld\n", get_rank(x));
else if (op == 4) printf("%lld\n", get_key(x));
else if (op == 5) printf("%lld\n", pre(x));
else printf("%lld\n", suf(x));
}
}
// 区间反转版本
mt19937 rnd(233);
int root, idx;
int x, y, z;
struct fhq {
int l, r;
int key, val; // key权值，val堆值
int size;
int tag;
}tr[maxn];
inline int get_node (int key) {
tr[ ++ idx].key = key;
tr[idx].val = rnd();
tr[idx].size = 1;
tr[idx].tag = 0;
return idx;
}
inline void pushup (int u) {
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}
inline void pushdown (int u) {
if (tr[u].tag) {
swap(tr[u].l, tr[u].r);
tr[tr[u].l].tag ^= 1, tr[tr[u].r].tag ^= 1;
tr[u].tag = 0;
}
}
inline void split (int u, int k, int &x, int &y) {
if (!u) x = y = 0;
else {
pushdown(u);
if (tr[tr[u].l].size + 1 <= k) {
x = u;
split(tr[u].r, k - tr[tr[u].l].size - 1, tr[u].r, y);
}
else {
y = u;
split(tr[u].l, k, x, tr[u].l);
}
pushup(u);
}
}
inline int merge (int x, int y) {
if (!x || !y) return x + y;
if (tr[x].val > tr[y].val) {
pushdown(x);
tr[x].r = merge(tr[x].r, y);
pushup(x); return x;
}
else {
pushdown(y);
tr[y].l = merge(x, tr[y].l);
pushup(y); return y;
}
}
inline void insert (int k) {
split (root, k, x, y);
root = merge(merge(x, get_node(k)), y);
}
inline void del (int k) {
split (root, k, x, z);
split (x, k - 1, x, y);
y = merge(tr[y].l, tr[y].r);
root = merge(merge(x, y), z);
}
inline int get_rank (int k) {
split (root, k - 1, x, y);
k = tr[x].size + 1;
root = merge(x, y);
return k;
}
inline int get_key (int k) {
int p = root;
while (p) {
if (tr[tr[p].l].size + 1 == k) {
break;
}
else if (tr[tr[p].l].size >= k) {
p = tr[p].l;
}
else {
k -= tr[tr[p].l].size + 1;
p = tr[p].r;
}
}
return tr[p].key;
}
inline int pre (int k) {
split (root, k - 1, x, y);
int p = x;
while (tr[p].r) p = tr[p].r;
k = tr[p].key;
root = merge(x, y);
return k;
}
inline int suf (int k) {
split (root, k, x, y);
int p = y;
while (tr[p].l) p = tr[p].l;
k = tr[p].key;
root = merge(x, y);
return k;
}
inline void print (int u) {
if (!u) return;
pushdown(u);
print(tr[u].l); printf("%lld ", tr[u].key); print(tr[u].r);
}
void solve() {
read(n), read(m);
// insert(-inf); insert(inf);
for (int i = 1; i <= n; i ++ ) insert(i);
while (m -- ) {
int l, r; read(l); read(r);
split (root, l - 1, x, y);
split (y, r - l + 1, y, z);
tr[y].tag ^= 1;
root = merge(x, merge(y, z));
}
print(root);
}1.9 轻重链剖分
int h[maxn], ne[maxn], e[maxn], idx;
int w[maxn], wt[maxn], id[maxn], top[maxn], fa[maxn], depth[maxn], sz[maxn], son[maxn];
int tt;
int n, m, k;
int root, mod, cnt;
struct node {
int l, r;
int sum, add;
}tr[maxn << 2];
inline void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs1 (int u, int f) {
depth[u] = depth[f] + 1;
fa[u] = f;
sz[u] = 1;
int mxson = -1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j != f) {
dfs1(j, u);
sz[u] += sz[j];
if (sz[j] > mxson) {
mxson = sz[j];
son[u] = j;
}
}
}
}
void dfs2 (int u, int topf) {
id[u] = ++ cnt;
wt[cnt] = w[u];
top[u] = topf;
if (!son[u]) return;
dfs2(son[u], topf);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!id[j]) dfs2(j, j);
}
}
inline void pushup (int u) {
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}
inline void pushdown (int u) {
auto &r = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (r.add) {
right.add = (right.add + r.add) % mod;
right.sum = (right.sum + (right.r - right.l + 1) * r.add) % mod;
left.add = (left.add + r.add) % mod;
left.sum = (left.sum + (left.r - left.l + 1) * r.add) % mod;
r.add = 0;
}
}
inline void build (int u, int l, int r) {
if (l == r) {
tr[u] = {l, r, wt[r], 0};
return;
}
tr[u] = {l, r, 0, 0};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
inline void modify (int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].sum = (tr[u].sum + (tr[u].r - tr[u].l + 1) * d) % mod;
tr[u].add += d;
}
else {
pushdown(u);
int mid = tr[u].r + tr[u].l >> 1;
if (l <= mid) modify (u << 1, l, r, d);
if (r > mid) modify (u << 1 | 1, l, r, d);
pushup(u);
}
}
inline int query (int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = (sum + query(u << 1, l, r)) % mod;
if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % mod;
return sum;
}
inline void Uprange (int x, int y, int d) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) swap(x, y);
modify(1, id[top[x]], id[x], d);
x = fa[top[x]];
}
if (depth[x] > depth[y]) swap(x, y);
modify(1, id[x], id[y], d);
}
inline int Qrange (int x, int y) {
int sum = 0;
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) swap(x, y);
sum = (sum + query(1, id[top[x]], id[x])) % mod;
x = fa[top[x]];
}
if (depth[x] > depth[y]) swap(x, y);
sum = (sum + query(1, id[x], id[y])) % mod;
return sum;
}
inline int lca (int x, int y) {
while (top[x] != top[y]) {
depth[top[x]] > depth[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
}
return depth[x] < depth[y] ? x : y;
}
void solve() {
scanf("%d%d%d%d", &n, &m, &root, &mod);
for (int i = 1; i <= n; i ++ ) scanf("%d", w + i);
ms(h, -1);
for (int i = 1; i < n; i ++ ) {
int u, v; scanf("%d%d", &u, &v);
add(u, v);add(v, u);
}
dfs1(root, 0);
dfs2(root, root);
build(1, 1, n);
for (int i = 1; i <= m; i ++ ) {
int op;
scanf("%d", &op);
if (op == 1) {
int l, r, d;
scanf("%d%d%d", &l, &r, &d);
Uprange(l, r, d);
}
if (op == 2) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", Qrange(l, r));
}
if (op == 3) {
int x, d;
scanf("%d%d", &x, &d);
modify(1, id[x], id[x] + sz[x] - 1, d % mod);
}
if (op == 4) {
int x;
scanf("%d", &x);
printf("%d\n", query(1, id[x], id[x] + sz[x] - 1));
}
}
}1.10 Dsu on Tree
// 处理重儿子
void dfs (int u, int fa) {
sz[u] = 1;
for (auto j : G[u]) {
if (j != fa) {
dfs(j, u);
sz[u] += sz[j];
if (sz[j] > sz[son[u]]) son[u] = j;
}
}
}
// 这一步需要结合题意
void count (int u, int fa, int v) {
cnt[val[u]] += v; // 增加或删除贡献
if (cnt[val[u]] > mx) {
mx = cnt[val[u]];
sum = val[u];
}
else if (cnt[val[u]] == mx) {
sum += val[u];
}
// 统计除标记外的重儿子的所有子树的贡献
for (auto j : G[u]) {
if (j == fa || j == flag) continue;
count(j, u, v);
}
}
void dfs (int u, int fa, bool op) {
for (auto j : G[u]) { // 先处理所有轻儿子及其子树并且计算答案，删除贡献。
if (j != fa && j != son[u]) {
dfs(j, u, false);
}
}
if (son[u]) { // 处理重儿子及其子树并计算答案，不删除贡献
dfs(son[u], u, true);
flag = son[u];
}
count(u, fa, 1); // 暴力统计u及其所有轻儿子的贡献合并到刚算出的重儿子信息里
flag = 0;
ans[u] = sum;
// 把需要删除贡献的删一删
if (!op) {
count(u, fa, -1);
sum = mx = 0; //这是因为count函数中会改变这两个变量值
}
}1.11 Splay
#define ls(x) tr[x].ch[0]
#define rs(x) tr[x].ch[1]
#define fa(x) tr[x].fa
#define root tr[0].ch[1]
struct node {
int fa , ch[2], val, rec, sum, tag;
}tr[maxn];
int tot, pointnum;
void update (int x) {tr[x].sum = tr[ls(x)].sum + tr[rs(x)].sum + tr[x].rec;}
int ident (int x) {return tr[fa(x)].ch[0] == x ? 0 : 1;}
void connect (int x, int fa, int how) {tr[fa].ch[how] = x; tr[x].fa = fa;}
inline void pushdown (int u) {
if (tr[u].tag) {
tr[tr[u].ch[0]].tag ^= 1;
tr[tr[u].ch[1]].tag ^= 1;
swap(tr[u].ch[0], tr[u].ch[1]);
tr[u].tag = 0;
}
}
void rotate (int x) {
int y = fa(x), r = fa(y);
int yson = ident(x), rson = ident(y);
connect(tr[x].ch[yson ^ 1], y, yson);
connect(y, x, yson ^ 1);
connect(x, r, rson);
update(y), update(x);
}
void splay (int x, int to) {
to = fa(to);
while (fa(x) != to) {
int y = fa(x);
if (tr[y].fa == to) rotate(x);
else if (ident(x) == ident(y)) rotate(y), rotate(x);
else rotate(x), rotate(x);
}
}
int newnode (int v, int f) {
tr[ ++ tot].fa = f;
tr[tot].rec = tr[tot].sum = 1;
tr[tot].val = v;
return tot;
}
void insert (int x) {
int now = root;
if (!root) {newnode(x, 0); root = tot;}
else {
while (1) {
tr[now].sum ++ ;
if (tr[now].val == x) {tr[now].rec ++ ; splay(now, root); return;}
int ne = x < tr[now].val ? 0 : 1;
if (!tr[now].ch[ne]) {
int p = newnode(x, now);
tr[now].ch[ne] = p;
splay(p, root); return;
}
now = tr[now].ch[ne];
}
}
}
int find (int x) { // 找到值为x的某一结点
int now = root;
while (1) {
if (!now) return 0;
if (tr[now].val == x) {splay(now, root); return now;}
int ne = x < tr[now].val ? 0 : 1;
now = tr[now].ch[ne];
}
}
void del (int x) {
int p = find(x);
if (!p) return;
if (tr[p].rec > 1) {tr[p].rec -- , tr[p].sum -- ; return;}
else {
if (!tr[p].ch[0] && !tr[p].ch[1]) {root = 0; return;}
else if (!tr[p].ch[0]) {
root = tr[p].ch[1]; tr[root].fa = 0; return;
}
else {
int left = tr[p].ch[0];
while (tr[left].ch[1]) left = tr[left].ch[1];
splay(left, tr[p].ch[0]);
connect (tr[p].ch[1], left, 1);
connect (left, 0, 1);
update(left);
}
}
}
int rk (int x) { // x的排名
int now = root, ans = 0;
while (1) {
if (tr[now].val == x) return ans + tr[tr[now].ch[0]].sum + 1;
int ne = x < tr[now].val ? 0 : 1;
if (ne == 1) ans = ans + tr[tr[now].ch[0]].sum + tr[now].rec;
now = tr[now].ch[ne];
}
}
int kth (int x) { // x排名的数
int now = root;
while (1) {
int used = tr[now].sum - tr[tr[now].ch[1]].sum;
if (tr[tr[now].ch[0]].sum < x && x <= used) {
splay(now, root); return tr[now].val;
// return now; 用于区间反转
}
if (x < used) now = tr[now].ch[0];
else now = tr[now].ch[1], x -= used;
}
}
int pre (int x) {
int now = root, ans = -inf;
while (now) {
if (tr[now].val <= x) ans = max(ans, tr[now].val);
int ne = x <= tr[now].val ? 0 : 1;
now = tr[now].ch[ne];
}
return ans;
}
int suf (int x) {
int now = root, ans = inf;
while (now) {
if (tr[now].val >= x) ans = min(ans, tr[now].val);
int ne = x < tr[now].val ? 0 : 1;
now = tr[now].ch[ne];
}
return ans;
}
inline void reverse (int x, int y) { // 区间反转
int l = kth(x), r = kth(y + 2);
splay(l, 0); splay(r, l);
tr[tr[tr[root].ch[1]].ch[0]].tag ^= 1;
}
inline void print (int u) { // 中序遍历
pushdown(u);
if (tr[u].ch[0]) print(tr[u].ch[0]);
if (tr[u].val > 1 && tr[u].val < n + 2) printf("%lld ", tr[u].val - 1);
if (tr[u].ch[1]) print(tr[u].ch[1]);
}
1.12 莫队
// 普通莫队，add和del可以修改
int sq;
struct query {
int l, r, id;
bool operator < (const query &it) const {
if (l / sq != it.l / sq) return l < it.l;
if (l / sq & 1) return r < it.r;
return r > it.r;
}
}Q[1000010];
int q[1000010], ans[1000010], cnt[2000010], cur, l = 1, r;
inline void add (int x) {
if (!cnt[q[x]]) cur ++ ;
cnt[q[x]] ++ ;
}
inline void del (int x) {
cnt[q[x]] -- ;
if (!cnt[q[x]]) cur -- ;
}
void solve() {
read(n);
sq = sqrt(n);
for (int i = 1; i <= n; i ++ ) read(q[i]);
int query; read(query);
for (int i = 0; i < query; i ++ ) read(Q[i].l), read(Q[i].r), Q[i].id = i;
sort(Q, Q + query);
for (int i = 0; i < query; i ++ ) {
while (l > Q[i].l) add( -- l);
while (r < Q[i].r) add( ++ r );
while (l < Q[i].l) del(l ++ );
while (r > Q[i].r) del(r -- );
ans[Q[i].id] = cur;
}
for (int i = 0; i < query; i ++ ) printf("%d\n", ans[i]);
}
//带修莫队，块长可以选择pow(n*t, 0.33333) 或者 pow(n, 0.66666)
const int maxn = 500010;
int sq;
struct query {
int l, r, t, id;
bool operator < (const query &it) const {
if (l / sq != it.l / sq) return l < it.l;
else if (r / sq != it.r / sq) return r < it.r;
else return t < it.t;
}
}Q[maxn];
struct change {
int p, col;
}c[maxn];
int q[maxn], ans[maxn], cnt[maxn * 2], cur;
int l = 1, r = 0, qcnt, ccnt;
inline void add (int x) {
if (!cnt[x]) cur ++ ;
cnt[x] ++ ;
}
inline void del (int x) {
cnt[x] -- ;
if (!cnt[x]) cur -- ;
}
inline void work (int x, int ti) {
if (c[ti].p >= Q[x].l && c[ti].p <= Q[x].r) {
del(q[c[ti].p]);
add(c[ti].col);
}
swap(q[c[ti].p], c[ti].col);
}
void solve() {
read(n); read(m);
sq = pow(n, 0.66666); // 块长
for (int i = 1; i <= n; i ++ ) {
read(q[i]);
}
char op[10];
for (int i = 1; i <= m; i ++ ) {
scanf("%s", op);
if (op[0] == 'Q') {
qcnt ++ ;
read(Q[qcnt].l); read(Q[qcnt].r);
Q[qcnt].t = ccnt;
Q[qcnt].id = qcnt;
}
else {
ccnt ++ ;
read(c[ccnt].p); read(c[ccnt].col);
}
}
sort(Q + 1, Q + qcnt + 1);
int now = 0;
for (int i = 1; i <= qcnt; i ++ ) {
while (l > Q[i].l) add(q[ -- l]);
while (r < Q[i].r) add(q[ ++ r]);
while (l < Q[i].l) del(q[l ++ ]);
while (r > Q[i].r) del(q[r -- ]);
while (now < Q[i].t) work(i, ++ now);
while (now > Q[i].t) work(i, now --);
ans[Q[i].id] = cur;
}
for (int i = 1; i <= qcnt; i ++ ) printf("%d\n", ans[i]);
}2. 图论
2.1 最短路
2.1.1 朴素Dijkstra O(n^2)
int g[N][N]; // 邻接矩阵存稠密图
int dist[N]; // 每个点距离点1的距离
bool st[N]; // 判断该点是否确定
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i ++ ){ // n个点循环n次
int t = -1;
for (int j = 1; j <= n; j ++ ){ // 找未确定的点中dist最小的点
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
if (t == n && dist[t] != 0x3f3f3f3f) return dist[t];
else if (t == n && dist[t] == 0x3f3f3f3f) return -1; // 提前结束循环的优化
st[t] = true;
for (int j = 1; j <= n; j ++ )// 用t更新其他未确定点的距离
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m -- ){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
printf("%d\n", dijkstra());
return 0;
}2.1.2 堆优化Dijkstra O(mlogn)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
int add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue; // 防止产生冗余
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > dist[ver] + w[i]){
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}2.1.3 Bellman-ford O(nm)
// 有边数限制的最短路
struct Edge
{
int a, b ,c;
}edges[M]; // 结构体存边
int n, m, k;
int dist[N];
int backup[N]; // 题目有特殊的边数限制，因此在更新时只能更新上次备份，否则会出现串联
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i ++ ){
memcpy(backup, dist, sizeof dist); // 每次都将上次的dist存到备份里
for (int j = 0; j < m; j ++ ){
auto e = edges[j];
dist[e.b] = min(dist[e.b], backup[e.a] + e.c);
}
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m ; i ++ ){
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
bellman_ford();
if (dist[n] > 0x3f3f3f3f / 2) printf("impossible\n");
else printf("%d\n", dist[n]);
return 0;
}
// 无边数限制的最短路
#include <bits/stdc++.h>
using namespace std;
const int M = 1000010;
struct Edge
{
int a, b ,c;
}edges[M]; // 结构体存边
int n, m, k;
int dist[M];
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ ){
for (int j = 0; j < m; j ++ ){
auto e = edges[j];
dist[e.b] = min(dist[e.b], dist[e.a] + e.c);
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m ; i ++ ){
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
if (bellman_ford() == -1) printf("impossible\n");
else printf("%d\n", dist[n]);
return 0;
}2.1.4 SPFA O(nm)
// 最短路
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size()){
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if (!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
printf("%d\n", dist[n]);
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa() == 0x3f3f3f3f) printf("impossible");
else printf("%d\n", spfa());
return 0;
}
// 判断负权环
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 优化：queue改stack，或入队总数大于2*n即有负环
bool spfa()
{
queue<int> q;
for (int i = 1; i <= n; i ++ ){
st[i] = true;
q.push(i);
}
while (q.size()){
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset (h, -1, sizeof h);
while (m -- ){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa()) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
// SLF优化
int dist[maxn];
int cnt[maxn];
bool st[maxn];
vector<PII> G[maxn];
bool spfa(int s)
{
deque<int> q;
dist[s] = 0;
q.push_back(s);
cnt[s] ++ ;
st[s] = 1;
while (q.size()) {
int t = q.front();
q.pop_front();
st[t] = 0;
for (auto it : G[t]) {
int j = it.first, w = it.second;
if (dist[j] > dist[t] + w) {
dist[j] = dist[t] + w;
if (!st[j]) {
if (!q.empty() && dist[j] > dist[q.front()]) {
q.push_back(j);
}
else q.push_front(j);
cnt[j] ++ ;
if (cnt[j] > n) return true;
st[j] = 1;
}
}
}
}
return false;
}2.1.5 Floyd O(n^3)
#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N]; // i到j距离
void floyd()
{
for (int k = 1; k <= n; k ++ ){
for (int j = 1; j <= n; j ++ ){
for (int i = 1; i <= n; i ++ ){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main()
{
cin >> n >> m >> Q;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= n; j ++ ){
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
}
}
while (m -- ){
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}
floyd();
while (Q -- ){
int a, b;
cin >> a >> b;
int t =d[a][b];
if (t > INF / 2) printf("impossible");
else printf("%d\n", t);
}
return 0;
}
// 传递闭包
for (int k = 0; k < n; k ++ ) {
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < n; j ++ ) {
d[i][j] |= d[i][k] && d[k][j];
}
}
}
// 求最小环
int n, m;
int d[maxn][maxn], g[maxn][maxn];
int pos[maxn][maxn];
int path[maxn], cnt;
void get_path (int i, int j) {
if (pos[i][j] == 0) return;
int k = pos[i][j];
get_path(i, k);
path[cnt ++ ] = k;
get_path(k, j);
}
int main () {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i ++ ) g[i][i] = 0;
while (m -- ) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int res = inf;
memcpy(d, g, sizeof d);
for (int k = 1; k <= n; k ++ ) {
for (int i = 1; i < k; i ++ ) {
for (int j = i + 1; j < k; j ++ ) {
if((long long)d[i][j] + g[j][k] + g[k][i] < res) {
res = d[i][j] + g[j][k] + g[k][i];
cnt = 0;
path[cnt ++] = k;
path[cnt ++] = i;
get_path(i, j);
path[cnt ++] = j;
}
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
pos[i][j] = k;
}
}
}
}
if (res == inf) puts("No solution.");
else {
for (int i = 0; i < cnt; i ++ ) cout << path[i] << ' ';
cout << endl;
}
}
2.1.6 路径还原
//以朴素dijkstra为例，记录一个path数组，当dist数组被更新时，就同步跟新path数组
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
const int inf = 0x3f3f3f3f;
int g[maxn][maxn];
int st[maxn];
int dist[500010];
int path[500010]; // 记录走来的路径
int n, m;
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(path, -1 ,sizeof path);
dist[1] = 0;
for (int i = 1; i <= n; i ++ ){
int t = -1;
for (int j = 1; j <= n; j ++ ){
if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
}
st[t] = 1;
for (int j = 1; j <= n; j ++ ){
if (dist[j] > dist[t] + g[t][j]){
dist[j] = dist[t] + g[t][j];
path[j] = t; // 记录
}
}
}
return dist[n];
}
vector<int> get_path(int x){
vector<int> p;
for (; x != -1; x = path[x]) p.push_back(x);
reverse(p.begin(), p.end()); //p中存下的是n到1的顺序，我们逆反一下顺序。
return p;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= n; j ++ ){
g[i][j] = (i == j) ? 0 : inf;
}
}
for (int i = 1; i <= m; i ++ ){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
printf("%d\n", dijkstra());
vector<int> p = get_path(n);
for (auto it : p){
printf("%d ", it);
}
return 0;
}2.1.7 最短路计数
int cnt[maxn]; // 长度为i的路径的数量。
while (q.size()) { // 以bfs为例
auto t = q.front();
q.pop();
for (auto it : G[t]) {
if (dist[it] > dist[t] + 1) {
dist[it] = dist[t] + 1;
cnt[it] = cnt[t];
q.push(it);
}
else if (dist[it] == dist[t] + 1) cnt[it] = (cnt[it] + cnt[t]) % mod;
}
}2.2 最小生成树
2.2.1 Prim
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N]; // 邻接矩阵存图
int dist[N]; // 1~i的距离
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ ){
int t = -1;
for (int j = 1; j <= n; j ++ ){
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m -- ){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图
}
int t = prim();
if (t == INF) printf("impossible");
else printf("%d\n", t);
return 0;
}2.2.2 Kruskal
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N]; // 并查集
struct Edge
{
int a, b, w;
}edges[M];
bool cmp(Edge a, Edge b)
{
return a.w < b.w;
}
int find (int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m, cmp);
for (int i = 0; i <= n; i ++ ) p[i] = i; // 并查集的初始操作
int res = 0, cnt = 0; // cnt表示连通的边数
for (int i = 0; i < m; i ++ ){
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b){
p[a] = b; // 将边加入集合
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
int main()
{
cin >> n>> m;
for (int i = 0; i < m; i ++ ){
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
int t = kruskal();
if (t == INF) printf("impossible"); // 不连通
else printf("%d", t);
return 0;
}
// 次小生成树
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 510, maxm = 10010;
typedef pair<int, int> PII;
int n, m;
struct node {
int a, b, w;
bool f;
bool operator < (const node &it) const {
return w < it.w;
}
}e[maxm];
int p[maxn];
int d1[maxn][maxn], d2[maxn][maxn];
vector<PII> G[maxn];
int find (int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void dfs (int u, int fa, int maxd1, int maxd2, int d1[], int d2[]) {
d1[u] = maxd1, d2[u] = maxd2;
for (auto it : G[u]) {
int j = it.first, w = it.second;
if (j != fa) {
int td1 = maxd1, td2 = maxd2;
if (w > td1) td2 = td1, td1 = w;
else if (w < td1 && w > td2) td2 = w;
dfs(j, u, td1, td2, d1, d2);
}
}
}
signed main () {
cin >> n >> m;
for (int i = 1; i <= m; i ++ ) {
int a, b, w;
cin >> a >> b >> w;
e[i] = {a, b, w};
}
sort(e + 1, e + m + 1);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int sum = 0;
for (int i = 1; i <= m; i ++ ) {
int a = e[i].a, b = e[i].b, w = e[i].w;
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pa] = pb;
sum += w;
G[a].push_back({b, w});
G[b].push_back({a, w});
e[i].f = 1;
}
}
for (int i = 1; i <= n; i ++ ) {
dfs(i, -1, -1e9, -1e9, d1[i], d2[i]);
}
int res = 1e18;
for (int i = 1; i <= m; i ++ ) {
if (!e[i].f) {
int a = e[i].a, b = e[i].b, w = e[i].w;
int t;
if (w > d1[a][b]) {
t = sum + w - d1[a][b];
}
else if (w > d2[a][b]) {
t = sum + w - d2[a][b];
}
res = min(res, t);
}
}
cout << res << endl;
}2.3 二分图匹配
2.3.1 染色法判断二分图
/*
染色法的实现思路（DFS）：
1.用1，2代表两个颜色，0代表未染色，任选一个点染成1或2
2.遍历所有点，每次将未染色的点进行dfs
3.若染色失败即break/return
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int u, int c)
{
color[u] = c; // 染色
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (!color[j]){
if (!dfs(j, 3 - c)) return false; // 如果在dfs递归的过程中出现染色失败，则整个图都不是二分图
}
else if (color[j] == c) return false; // 如果一条边的两端点同种颜色，则染色失败
}
return true; // 无染色错误则染色成功
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ){
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bool flag = true;
for (int i = 1; i <= n; i ++ ){ // 遍历所有点，因为二分图不一定是连通图
if (!color[i]){
if (!dfs(i, 1)){
flag = false;
break;
}
}
}
if (flag) printf("Yes\n");
else printf("No");
return 0;
}2.3.2 匈牙利算法判断最大匹配
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N]; // match[a] = b, 表示点a目前匹配了b
bool st[N]; // st[a] = true, 表示点a目前已经有预定
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool find(int x) // 注意与并查集的find函数区别，为x找一个匹配，或x的匹配点被别人预定，x要重新找一个匹配
{
// 匹配成功返回true
for (int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]){ // 该点目前没有被匹配
st[j] = true; // 预定该点
if (match[j] == 0 || find(match[j])){ // j点没有匹配，或与j匹配的点可以更换匹配
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof h);
while (m -- ){
int a, b;
cin >> a >> b;
add(a, b); // 从左集合找右集合，只存一条边也可以
}
int res = 0;
for (int i = 0; i <= n1; i ++ ){ // 二分图不一定连通，因此要为所有点尝试匹配
memset(st, false, sizeof st);
if (find(i)) res ++;
}
cout << res << endl;
return 0;
}
最小点覆盖 = 最大匹配
最大独立集 = n - 最大匹配
最小路径点覆盖= n - 最大匹配
2.4 拓扑排序
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx;
int d[N];// d 代表每个元素的入度
int top[N];// top是拓扑排序的序列
int cnt = 1; // cnt代表top中有多少个元素
int n, m;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool topsort(){
queue<int> q;
int t;
for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列
if(d[i] == 0) q.push(i);
while(q.size()){
t = q.front();//每次取出队列的首部
top[cnt] = t;//加入到 拓扑序列中
cnt ++; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i]){
// 遍历 t 点的出边
int j = e[i];
d[j] --;// j 的入度 --
if(d[j] == 0) q.push(j); //如果 j 入度为0，加入队列当中
}
}
if(cnt < n) return 0;
else return 1;
}
int main(){
int a,b;
cin >> n >> m;
memset(h,-1,sizeof h);
while(m--){
cin >> a >> b;
add(a,b);
d[b] ++;// a -> b , b的入度++
}
if(topsort() == 0) cout << "-1"; // 序列不合法
else {
for(int i = 1;i <= n; ++i){
cout << top[i] <<" ";
}
}
return 0;
}2.5 LCA
int n, m;
int h[maxn], e[maxm], ne[maxm], idx;
int depth[maxn], fa[maxn][20];
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs (int root) {
queue<int> q;
q.push(root);
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for (int k = 1; k <= 19; k ++ ) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca (int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 19; k >= 0; k -- ) {
if (depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if (a == b) return a;
for (int k = 19; k >= 0; k -- ) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}2.6 Tarjan 强连通分量
int n, m;
int h[maxn], e[maxm], ne[maxm], idx; // 存图
int dfn[maxn], low[maxn], timestamp; // dfn表示编号为i的点的时间戳，low表示以点i出发走到的最小时间戳，timestamp为当前时间戳
int stk[maxn], top; // 模拟栈
bool in_stk[maxn]; // 判断是否在栈内
int id[maxn], scc_cnt, sz[maxn]; // id为点i在哪个强连通分量，scc_cnt教师强连通分量的数量
int dout[maxn]; // 出度
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], low[j]);
}
if (dfn[u] == low[u]) {
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
} while (y != u);
}
}
int main () {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b;
cin >> a >> b;
add(a, b);
}
for (int i = 1; i <= n; i ++ ) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = h[i]; ~j; j = ne[j]) {
int k = e[j];
int a = id[i], b = id[k];
if (a != b) dout[a] ++ ;
}
}
//剩下由题
}2.7 差分约束
/* 求最小值，用最长路，求最大值，用最短路。
A = B <=> A≥B B≥A add(b, a, 0), add(a, b, 0);
A < B <=> B≥A+1 add(a, b, 1);
A≥B <=> A≥B add (b, a, 0);
A > B <=> A≥B+1 add(b, a, 1);
B≥A <=> B≥A add(a, b, 0);
x >= 1
建立虚拟源点x0 (dist[x0] = 0)
即x >= x0 + 1 add(x0, x, 1);
*/3 数学
3.1 线性筛
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}3.2 快速乘 & 快速幂
// 快速幂
int qmi (int a, int b) { // a ^ b
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod; // 或 ans = mul(ans, a);
a = a * a % mod; // 或 ans = mul(a, a);
b >>= 1;
}
return ans;
}
// 快速乘
int mul (int a, int b) { // a * b
int ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % mod;
b >>= 1;
a = (a * 2) % mod;
}
return ans;
}3.3 拓展欧几里得算法 exgcd
/ 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
if (!b) {
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}3.4 欧拉函数
// 求1~N中与N互质的个数
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; 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 primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}3.5 约数 个数/和 定理
// 约数个数
//n=p1^a1*p2^a2*p3^a3*…*pk^ak
//f(n) = (a1+1)(a2+1)(a3+1)…(ak+1)
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
for (auto p : primes) res = res * (p.second + 1) % mod;
cout << res << endl;
return 0;
}
// 约数之和
//n=p1^a1*p2^a2*p3^a3*…*pk^ak
//f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）
unordered_map<int, int> mp;
while(t -- )
{
int x; scanf("%d", &x); // 即n
for(int i = 2; i <= x / i; i ++)
{
while(x % i == 0)
{
x /= i;
mp[i]++;
}
}
if(x > 1) mp[x] ++;
}
long long res = 1;
for(auto p : mp)
{
long long a = p.first, b = p.second;
long long t = 1;
while(b -- )
{
t = (t * a + 1) % mod; // 秦九韶算法
}
res = res * t % mod;
}
cout << res << endl;3.6 组合数
// O(ab)
const int N = 2010;
int c[N][N];
void init () {
for (int i = 0; i < N ; 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]) % mod;
}
}
}
// lucas定理
// C(a, b) = C(a % p, b % p) * C(a / p, b / p); p为质数
int a, b, p; // 求C(a, b) % p;
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b, int p)
{
if (b > a) return 0;
int res = 1;
for (int i = 1, j = a; i <= b; i ++, j -- )
{
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2, p) % p;
}
return res;
}
int lucas(LL a, LL b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
inline void init () {
fac[0] = 1;
for (int i = 1; i <= n; i ++ ) fac[i] = fac[i - 1] * i % mod2;
ifac[n] = qmi(fac[n], mod2 - 2) % mod2;
for (int i = n; i >= 1; i -- ) ifac[i - 1] = ifac[i] * i % mod2;
}
inline int C (int n, int m) {
return fac[n] * ifac[m] % mod2 * ifac[n - m] % mod2;
}
// k次前缀和的组合数
C（k-1+i，k-1）3.7 整除分块
$$
\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor
$$
// 下取整
inline int getdown (int n) {
int ans = 0;
for(int l = 1, r, len; l <= n; l = r + 1) {
r = n / (n / l), len = r - l + 1;
ans += len * (n / l);
}
return ans;
}
// 上取整
inline int getup (int n) {
int ans = 0;
for(int l = 1, r, len; l <= n; l = r + 1) {
r = n / (n / l), len = r - l + 1;
ans += len * (n / l + 1);
if (n % r == 0) ans -= r;
}
return ans;
}3.8 卡特兰数
$$
f(n)=C_{2n}^{n}-C_{2n}^{n-1}
$$
1.n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列。
2.n 对括号，则有多少种 “括号匹配” 的括号序列
3.n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树
4.电影票一张 50 coin，且售票厅没有 coin，m 个人各自持有 50 coin，n 个人各自持有 100 coin。则有多少种排队方式，可以让每个人都买到电影票。
5.8 个高矮不同的人需要排成两队，每队 4 个人。其中，每排都是从低到高排列，且第二排的第 i 个人比第一排中第 i 个人高，则有多少种排队方式?
6.在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。
前几项：
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...3.9 线性求逆
ll inv[maxn] = {0,1};
for (int i = 2; i < maxn; i ++ )
inv[i] = (mod - mod / i) * inv[mod % i] % mod;3.10 博弈论
经典nim
n堆，每次拿任意个，不可不拿，先拿完赢
// 先手是否必胜？
cin >> n;
int res = 0;
for (int i = 0; i < n; i ++ ){
int a;
cin >> a;
res ^= a;
}
if (res) printf("Yes\n");
else printf("No\n");
anti-nim游戏
n堆，每次拿任意个，不可不拿，先拿完输
先手胜当且仅当 ①所有堆石子数都为1且游戏的SG值为0（即有偶数个孤单堆-每堆只有1个石子数）；②存在某堆石子数大于1且游戏的SG值不为0.
bool ok = 0;
int ans = 0;
for (int i = 0; i < sz(res); i ++ ) {
ans ^= res[i];
if (res[i] > 1) ok = 1;
}
if ((!ok && ans == 0) || (ok && ans != 0)) puts("Alice win");
else puts("Bob win");
对称博弈
3.11 快速傅里叶变换
struct Complex{
double x,y;
Complex (double x = 0, double y = 0) : x(x), y(y) {}
inline Complex operator + (const Complex b) const {
return Complex (x + b.x, y + b.y);
}
inline Complex operator - (const Complex b) const {
return Complex(x - b.x, y - b.y);
}
inline Complex operator * (const Complex b) const {
Complex res;
res.x = x * b.x - y * b.y;
res.y = x * b.y + y * b.x;
return res;
}
}a[maxn], b[maxn];
int n, m, k;
int rev[maxn], l;
int lim = 1;
void FFT (Complex *a, int type) {
for (int i = 0; i < lim; i ++ ) {
if (i < rev[i]) swap(a[i], a[rev[i]]);
}
for (int mid = 1; mid < lim; mid <<= 1) { // 区间的中点
Complex wn(cos(pi / mid), type * sin(pi / mid));
for (int r = mid << 1, j = 0; j < lim; j += r) { // 右端点
Complex w(1, 0);
for(int k = 0; k < mid; k ++ , w = w * wn) { // 枚举左半区间
Complex x = a[j + k], y = w * a[mid + j + k];
a[j + k] = x + y, a[mid + j + k] = x - y;
}
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i ++ ) scanf("%lf", &a[i].x);
for (int i = 0; i <= m; i ++ ) scanf("%lf", &b[i].x);
while (lim <= n + m) lim <<= 1, l ++ ;
for (int i = 0; i < lim; i ++ ) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
FFT(a, 1), FFT(b, 1);
for (int i = 0; i <= lim; i ++ ) a[i] = a[i] * b[i];
FFT(a, -1);
for (int i = 0; i <= n + m; i ++ ) printf("%d ", (int)(a[i].x / lim + 0.5));
}
//大整数相乘
cin >> A >> B;
for (int i = A.size() - 1; i >= 0; i -- ) {
a[A.size() - i - 1].x = A[i] - '0';
}
for (int i = B.size() - 1; i >= 0; i -- ) {
b[B.size() - i - 1].x = B[i] - '0';
}
while (lim <= A.size() + B.size()) lim <<= 1, l ++ ;
for (int i = 0; i < lim; i ++ ) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
FFT(a, 1), FFT(b, 1);
for (int i = 0; i <= lim; i ++ ) {
a[i] = a[i] * b[i];
}
FFT(a, -1);
for (int i = 0; i <= lim; i ++ ) {
ans[i] += (int)(a[i].x / lim + 0.5);
if (ans[i] >= 10) {
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;
if (i == lim) lim ++ ;
}
}
while (!ans[lim] && lim >= 1) lim -- ;
while (lim >= 0) {
printf("%d", ans[lim -- ]);
}3.12 最小二乘法求线性回归方程
$$
k = \frac{\sum_{i = 1}^{n} x_iy_i - n\bar{x}\bar{y}}{\sum_{i = 1}^{n} x_i^2 - n\bar{x}^2}
$$
$$
d = \bar{y} - k\bar{x}
$$
for (int i = 1; i <= n; i ++ ) q[i] = read();
double sumx = 0, sumy = 0, iq = 0, ii = 0;
for (int i = 1; i <= n; i ++ ) {
sumx += i, sumy += q[i];
iq += i * q[i];
ii += i * i;
}
double k = (iq - sumx * sumy / n) / (ii - sumx * sumx / n);
double d = sumy / n - k * sumx / n;
double ans = 0;
for (int i = 1; i <= n; i ++ ) {
ans += (k * i + d - q[i]) * (k * i + d - q[i]);
}
printf("%.6Lf\n", ans);3.13 线性基
const int MAXL = 60;
struct LinearBasis {
int a[MAXL + 1];
int cnt = 0;
LinearBasis () {
fill(a, a + MAXL + 1, 0);
}
LinearBasis (int *x, int n) { // 快速构造线性基
build (x, n);
}
inline bool insert (int t) { // 线性基动态插入数
for (int j = MAXL; j >= 0; j -- ) {
if (!t) return false;
if (!(t & (1ll << j))) continue;
if (a[j]) t ^= a[j];
else {
cnt ++ ;
// for (int k = 0; k < j; k ++ ) {
// if (t & (1ll << k)) t ^= a[k];
// }
// for (int k = j + 1; k <= MAXL; k ++ ) {
// if (a[k] & (1ll << j)) a[k] ^= t;
// }
a[j] = t;
return false;
}
}
return true;
}
void build (int *x, int n) {
fill(a, a + MAXL + 1, 0);
for (int i = 1; i <= n; i ++ ) insert(x[i]);
}
inline void rebuild () { // 重构成易于求kth的形式
for (int i = 0; i <= MAXL; i ++ ) {
for (int j = i - 1; j >= 0; j -- ) {
if (a[i] & (1ll << j)) a[i] ^= a[j];
}
}
}
inline void mergefrom (const LinearBasis &b) { // 合并两个线性基
for (int i = 0; i <= MAXL; i ++ ) insert(b.a[i]);
}
static LinearBasis merge (const LinearBasis &a, const LinearBasis &b) {
LinearBasis res = a;
for (int i = 0; i <= MAXL; i ++ ) res.insert(b.a[i]);
return res;
}
inline int querymax () { // 查询子集最大异或和
int res = 0;
for (int i = 0; i <= MAXL; i ++ ) res ^= a[i];
return res;
}
inline int querymin () { // 查询子集最小异或和
for (int i = 0; i <= MAXL; i ++ ) if (a[i]) return a[i];
}
inline int kth (int k) { // k大异或和
if (cnt < n) k -- ;
if (k >= (1ll << cnt)) return -1;
int ans = 0;
for (int i = 0, j = 0; i <= MAXL; i ++ ) {
if (a[i]) {
if (k & (1ll << j)) ans ^= a[i];
j ++ ;
}
}
return ans;
}
inline int rank (int x) { // 查询异或和排名，不去重需要 k % mod * qmi(2, n - a.cnt) % mod + 1) % mod;
int ans = 0;
for (int i = 0, j = 0; i <= MAXL; i ++ ) {
if (a[i]) {
if (x & (1ll << i)) ans |= (1ll << j);
j ++ ;
}
}
return ans;
}
};4 动态规划
4.1 线性DP
4.1.2 最长上升子序列 O(nlogn)
// O(n^2)
int f[N], q[N]; // q原数组,f[i]表示以结尾的最长上升序列
int mx = 1;
for (int i = 1; i <= n; i ++ ) {
f[i] = 1; // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
for (int j = 1; j < i; j ++ ) {
if (q[i] > q[j]) f[i] = max(f[i], f[j] + 1);
}
mx = max(mx, f[i]);
}
// O(nlogn)
vector<int> stk;
stk.push_back(q[1]);
for (int i = 2; i <= n; i ++ ) {
if (q[i] > stk.back()) stk.push_back(q[i]); // //如果该元素大于栈顶元素,将该元素入栈
else *lower_bound(stk.begin(), stk.end(), q[i]) = q[i]; // //替换掉第一个大于或者等于这个数字的那个数
}
cout << stk.size() << endl;4.1.3 最长公共子序列 O(n^2)
int a[N], b[N];
int f[N][N]; // f[i][j]表示a串前i个元素和b串前j个元素的最长公共子序列长度，注意下标从1开始
cin >> n >> m >> a + 1 >> b + 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if (a[i] == b[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
}
else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
// LCS + 输出字符串
cin >> n >> m >> a + 1 >> b + 1;
int A = strlen(a + 1), B = strlen(b + 1); // a串b串长度
for (int i = A; i >= 1; i -- ) {
for (int j = B; j >= 1; j -- ) {
if (a[i] == b[j]) f[i][j] = f[i + 1][j + 1] + 1;
else f[i][j] = max (f[i + 1][j], f[i][j + 1]);
}
}
int i = 1, j = 1;
while (i <= A && j <= B) {
if (a[i] == b[j]) {
cout << a[i]; // 输出最长公共子串
i ++ , j ++ ;
}
else if (f[i][j] == f[i + 1][j]) i ++ ;
else j ++ ;
}4.1.4 最长公共上升子序列 O(n^2)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010;
int a[maxn], b[maxn];
int f[maxn][maxn]; // f[i] [j] 代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的长度最大值；
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for (int i = 1; i <= n; i ++ ){
int maxv = 1;
for (int j = 1; j <= n; j ++ ){
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) ans = max(ans, f[n][i]);
cout << ans << endl;
}4.2 背包
4.2.1 01背包 O(nm)
// 求恰好装满的最优解,f[0] = 0, f[1~m] = -inf;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m; // n件物品，背包容量为m
for (int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w; // v质量，w价值
for (int j = m; j >= v; j -- ) f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}4.2.2 完全背包 O(nm)
// 每件物品有无限个
int f[N];
int main()
{
cin >> n >> m; // n件物品，背包容量为m
for (int i = 0; i <= n; i ++ ){
int v, w;
cin >> v >> w;// v质量，w价值
// 正序枚举
for (int j = v; j <= m; j ++ ) f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}4.2.3 多重背包
4.2.3.1 二进制优化 O (NVlogs)
// 每件物品最多有Si个，用二进制优化后再做01背包
int v[N], w[N];
int f[M];
int main()
{
cin >> n >> m;
int cnt = 0; // 表示下标
for (int i = 1; i <= n; i ++ ){
int a, b, s; // a质量，b价值，s最多个数
cin >> a >> b >> s;
int k = 1; // 幂次
while (k <= s){
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0){ // 表示有大于幂次的部分
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
//n = cnt;
for (int i = 1; i <= cnt; i ++ ){
for (int j = m; j >= v[i]; j -- ){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}4.2.3.2 单调队列优化 O (NV)
int f[N], g[N], q[N]; // fj为前i个物品，在体积j下的最大价值，g为前i-1个物品,在体积j下的最大价值, q为单调队列.
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j ++ )
{
int hh = 0, tt = -1;
for (int k = j; k <= m; k += v)
{
if (hh <= tt && q[hh] < k - s * v) hh ++ ;
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
q[ ++ tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}4.2.4 分组背包 O (nms)
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
cin >> s[i];
for (int j = 0; j < s[i]; j ++ ){
cin >> v[i][j] >> w[i][j];
}
}
for (int i = 1; i <= n; i ++ ){
for (int j = m; j >= 0; j -- ){
for (int k = 0; k < s[i]; k ++ ){
if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[m] << endl;
return 0;
}4.2.5 超大背包
// 当物品质量过高，则将价值和质量转换
int f[maxn]; // f[i]为价值为i下的最小体积
void solve()
{
cin >> n >> m;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i ++ ){
int w, v;
cin >> v >> w;
// 用价值上限暴力枚举
for (int j = 100000; j >= w; j -- ) f[j] = min(f[j], f[j - w] + v);
}
int ans = 0;
for (int i = 1; i <= 100000; i ++ ){
if (f[i] <= m) ans = max(ans, i); // 暴力枚举所有价值，当体积能装下即为一组合法解
}
cout << ans << endl;
}4.2.6 二维费用背包(有物品数量限制的背包) O(nmk)
int n, V, M;
int f[maxn][maxn]; // 表示不超过i的第一费用，j的第二费用的最大价值。
int main()
{
cin >> n >> V >> M; // M为第二重最大费用，或为物品数量限制
for (int i = 1; i <= n; i ++ ){
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; j -- ){
for (int k = M; k >= m; k -- ){ // 第二重费用，或为物品数量限制
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
}
}
cout << f[V][M] << endl;
}4.2.7 混合背包
// 01背包，完全背包，多重背包的混合
// 考虑将01背包和完全背包转化为多重背包，再使用二进制优化求解多重背包
int n, m, v[100010], w[100010], dp[100010];
int main()
{
cin >> n >> m; // n件物品，容量为m
int cnt = 1;
for(int i = 1; i <= n; i ++)
{
int a, b, s;
cin >> a >> b >> s; //a体积，b价值
int k = 1; // 幂次
if(s < 0) s = 1; // s<0，01背包，只能拿一个
else if(s == 0) s = m / a; // s=0,完全背包，最多拿m/a个
while(k <= s)
{
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
cnt ++;
}
if(s > 0)
{
v[cnt] = s * a;
w[cnt] = s * b;
cnt ++ ;
}
}
for(int i = 1; i <= cnt; i ++)
{
for(int j = m; j >= v[i]; j -- )
{
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[m];
}4.2.6 背包问题输出方案
//用res[i]表示背包容量为i时上次选择了第几个物品.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 101000;
int n, m;
int dp[maxn], res[maxn];
int v[maxn], w[maxn];
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; i ++ ) {
for (int j = v[i]; j <= m; j ++ ) {
if (dp[i - 1][j] < dp[i - 1][j - v[i]] + w[i]) {
res[j] = v[i];
dp[j] = dp[j - v[i]] + w[i];
}
}
}
printf("%d\n", dp[m]);
vector<int> ans;
int now = dp[m];
while (res[now] != 0) {
ans.push_back(res[now]);
now -= res[now];
}
for (int i = ans.size() - 1; i >= 0; i -- ) {
printf("%lld ", ans[i]);
}
}4.3 区间DP O(n^3)
int f[maxn][maxn], g[maxn][maxn]; // 合并i~j所需的最小/最大价值
int s[maxn]; // 原数组的前缀和
int w[maxn];
for (int i = 1; i <= n; i ++ ) {
cin >> w[i];
w[i + n] = w[i]; // 若有环形要求
}
for (int i = 1; i <= n * 2; i ++ ) s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len ++ ) { // 枚举区间长度
for (int l = 1; l + len - 1 <= n * 2; l ++ ) { // 枚举左端点 (若无环形则到n)
int r = l + len - 1; // 找到右端点
if (l == r) f[l][r] = g[l][r] = 0;
else {
for (int k = l; k < r; k ++ ) { // 枚举分界点
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); // minvalue
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]); // maxvalue
}
}
}
}
int mi = inf, mx = -inf;
for (int i = 1; i <= n; i ++ ) {
// 若无环形则直接f[1][n];
mi = min(mi, f[i][i + n - 1]);
mx = max(mx, g[i][i + n - 1]);
}
cout << mi << endl;
cout << mx << endl;
/*
将ax和ax+1合并为ax*ax+1，获得(ax-ax+1)^2
注：不用考虑合并的和得到的分数计算方式不相等，合并完后就是改变ax和ax+1的值，直接照题目计算即可
*/
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
s[i][i] = a[i];
for (int j = i + 1; j <= n; j++) {
s[i][j] = s[i][j - 1] * a[j] % mod;
}
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++) {
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + (s[l][k] - s[k + 1][r]) * (s[l][k] - s[k + 1][r]));
}
}
}
cout << dp[1][n] << endl;
}4.4 树形DP
// 1.树中最长路径，求距离型
int dfs(int u, int f) {
int dist = 0;
int d1 = 0, d2 = 0; // d1为最长路径，d2为次长路径
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == f) continue;
int d = dfs(j, u) + w[i];
dist = max(dist, d);
if (d >= d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;
}
ans = max(ans, d1 + d2);
return dist;
}
int main () {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
cout << ans << endl;
}
// 4.5 状压DP
4.6 数位DP
// 统计0~N有多少位含i
int dgt(int n) {
int res = 0;
while (n) ++ res, n /= 10;
return res;
}
int count (int n, int i) {
int res = 0, d = dgt(n);
for (int j = 1; j <= d; j ++ ) {
int p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10;
if (i) res += l * p;
if (!i && l) res += (l - 1) * p;
if ( (dj > i) && (i || l) ) res += p;
if ( (dj == i) && (i || l) ) res += r + 1;
}
return res;
}
// 统计数位上至少有k个某数
#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
int f[maxn][maxn];
int k, b;
void init () {
for (int i = 0; i < maxn; i ++ ) {
for (int j = 0; j <= i; j ++ ) {
if (!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
}
}
int dp (int n) {
if (!n) return 0;
vector<int> nums;
while (n) nums.push_back(n % b), n /= b;
int res = 0;
int ls = 0;
for (int i = nums.size() - 1; i >= 0; i -- ) {
int x = nums[i];
if (x) {
res += f[i][k - ls];
if (x > 1) {
if (k - ls - 1 >= 0) res += f[i][k - ls - 1];
break;
}
else {
ls ++ ;
if (ls > k) break;
}
}
if (!i && ls == k) res ++ ;
}
return res;
}
int main () {
init ();
int l, r;
cin >> l >> r >> k >> b;
cout << dp(r) << ' ' << dp(l - 1) << endl;
}
// 统计l~r中有多少个满足条件的数（单调增，减，不出现某数等）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 15;
int f[maxn][maxn];
void init () {
for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;
for (int i = 2; i < maxn; i ++ ) {
for (int j = 0; j <= 9; j ++ ) {
for (int k = j; k <= 9; k ++ ) {
f[i][j] += f[i - 1][k];
}
}
}
}
int dp(int n) {
if (!n) return 1;
vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;
int res = 0;
int ls = 0;
for (int i = nums.size() - 1; i >= 0; i -- ) {
int x = nums[i];
for (int j = ls; j < x; j ++ ) {
res += f[i + 1][j];
}
if (x < ls) break;
ls = x;
if (!i) res ++ ;
}
return res;
}
int main () {
init();
int l, r;
while (cin >> l >> r) {
cout << dp(r) - dp(l - 1) << endl;
}
}4.7 单调队列优化DP
//单调队列常用来优化：i的前m个范围内区间的最值问题。（注意，此处的范围都是一个定值
//n个物品中，连续m个中至少选出一个，总价值最小。
//或 不能连续k个在一起，即至少从k+1个中选出一个不选。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, m;
int w[maxn], dp[maxn];
int q[maxn];
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++ ) {
while (hh <= tt && i - q[hh] > m) hh ++ ;
dp[i] = dp[q[hh]] + w[i];
while (hh <= tt && dp[q[tt]] >= dp[i]) tt -- ;
q[ ++ tt] = i;
}
if (n + 1 - m > q[hh]) hh ++ ;
printf("%d\n", dp[q[hh]]);
}
4.8 斜率优化DP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1000010;
int n, S;
int q[maxn];
int st[maxn], sc[maxn], f[maxn];
signed main () {
scanf("%lld%lld", &n, &S);
for (int i = 1; i <= n; i ++ ) {
scanf("%lld %lld", st + i, sc + i);
st[i] += st[i - 1];
sc[i] += sc[i - 1];
}
int hh = 0, tt = 0;
q[0] = 0;
for (int i = 1; i <= n; i ++ ) {
while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (sc[q[hh + 1]] - sc[q[hh]]) * (st[i] + S)) // 由于K单调，因此直接维护。否则可以二分
hh ++ ;
f[i] = f[q[hh]] + S * (sc[n] - sc[q[hh]]) + st[i] * (sc[i] - sc[q[hh]]);
while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt]]) >= (f[i] - f[q[tt]]) * (sc[q[tt]] - sc[q[tt - 1]])) // 维护下凸包
tt -- ;
q[ ++ tt] = i;
}
printf("%lld\n", f[n]);
}5. 字符串
5.1 KMP
const int mxn = 1e6 + 100;
struct KMP {
int ne[mxn], len;
string t;
void clear() {
len = ne[0] = ne[1] = 0;
}
//下标从1开始
//string 转 char ，在末尾加'\0'
void init (string s) {
len = sz(s) - 1;
t = s;
for (int i = 2; i <= len; i ++ ) {
ne[i] = ne[i - 1];
while (ne[i] && s[i] != s[ne[i] + 1]) ne[i] = ne[ne[i]];
ne[i] += (s[i] == s[ne[i] + 1]);
}
}
// 求所有在s串中的start_pos.
vector<int> match (string s) {
int len_s = sz(s) - 1;
vector<int> st_pos(0);
for (int i = 1, j = 1; i <= len_s;) {
while (j != 1 && s[i] != t[j]) j = ne[j - 1] + 1;
if (s[i] == t[j]) j ++ , i ++ ;
else i ++ ;
if (j == len + 1) {
st_pos.pb(i - j + 1);
j = ne[len] + 1;
}
}
return st_pos;
}
void debug () {
for (int i = 0; i <= len; i ++ ) {
printf("[debug] nxt[%d]=%d\n", i, ne[i]);
}
}
/* 循环周期 形如 acaca 中 ac 是一个合法周期 */
vector<int> periodic() {
vector<int> ret;
int now = len;
while (now) {
now = ne[now];
ret.pb(len - now);
}
return ret;
}
/* 循环节 形如 acac 中ac、acac是循环节，aca不是*/
vector<int> periodic_loop() {
vector<int> ret;
for (int x : periodic()) {
if (len % x == 0) ret.pb(x);
}
return ret;
}
int min_periodic_loop() {
return periodic_loop()[0];
}
}kmp;5.2 Manacher
struct Manacher {
int lc[maxn];
string ch;
int N;
Manacher(string s) {init(s); manacher();}
/* s 1 bas */
void init (string s) {
int n = sz(s) - 1;
ch.resize(n * 2 + 10);
ch[n * 2 + 1] = '#';
ch[0] = '@';
ch[n * 2 + 2] = '\0';
for (int i = n; i >= 1; i -- ) {
ch[i * 2] = s[i]; ch[i * 2 - 1] = '#';
}
N = 2 * n + 1;
}
void manacher() {
lc[1] = 1; int k = 1;
for (int i = 2; i <= N; i ++ ) {
int p = k + lc[k] - 1;
if (i <= p) {
lc[i] = min(lc[2 * k - i], p - i + 1);
}
else lc[i] = 1;
while (ch[i + lc[i]] == ch[i - lc[i]]) lc[i] ++ ;
if (i + lc[i] > k + lc[k]) k = i;
}
}
void debug () {
puts(ch.c_str());
for (int i = 1; i <= N; i ++ ) {
printf("lc[%d]=%d\n", i, lc[i]);
}
}
};
void solve() {
string s; cin >> s;
s = " " + s;
Manacher manacher(s);
manacher.debug();
}5.3 Hash
const int sigma = 60 * 60; /* 字符集大小 */
const int HASH_CNT = 2; /* hash次数 */
int s[maxn];
/* char* 1-bas
* sum[i] = s[i]+s[i-1]*Seed+s[i-2]*Seed^2+...+s[1]*Seed^(i-1)*/
ULL Prime_Pool[] = {1998585857ul, 23333333333ul};
ULL Seed_Pool[] = {911, 146527, 19260817, 91815541};
ULL Mod_Pool[] = {29123, 998244353, 1000000009, 4294967291ull};
struct Hash {
ULL seed, mod;
ULL base[maxn], sum[maxn];
int perm[sigma];
void init (int seedindex, int modindex) {
seed = Seed_Pool[seedindex], mod = Mod_Pool[modindex];
base[0] = 1;
for (int i = 1; i <= n; i ++ ) {
base[i] = base[i - 1] * seed % mod;
}
for (int i = 1; i <= n; i ++ ) {
sum[i] = (sum[i - 1] * seed % mod + s[i]) % mod;
}
}
/*random_shuffle 离散化id，防止kill_hash*/
void index_init(int seedindex, int modindex) {
seed = Seed_Pool[seedindex], mod = Mod_Pool[modindex];
base[0] = 1;
for (int i = 1; i <= n; i ++ ) {
base[i] = base[i - 1] * seed % mod;
}
iota (perm + 1, perm + sigma + 1, 1);
random_shuffle(perm + 1, perm + sigma + 1);
for (int i = 1; i <= n; i ++ ) {
sum[i] = (sum[i - 1] * seed % mod + perm[s[i]]) % mod;
}
}
ULL gethash (int l, int r) {
return (sum[r] - sum[l - 1] * base[r - l + 1] % mod + mod) % mod;
}
}hasher[HASH_CNT];
inline pair<ULL, ULL> hashrange(int l, int r) {
return mkp(hasher[0].gethash(l, r), hasher[1].gethash(l, r));
}
map<char, int> id; int idcnt;
void solve() {
read(n), read(m);
string a; cin >> a;
for (int i = 0; i < n; i ++ ) {
if (!id.count(a[i])) id[a[i]] = ++ idcnt;
s[i + 1] = id[a[i]];
}
for (int i = 0; i < HASH_CNT; i ++ ) hasher[i].index_init(i, i);
while (m -- ) {
int l1, r1, l2, r2;
read(l1), read(r1), read(l2), read(r2);
if (hashrange(l1, r1) == hashrange(l2, r2)) puts("Yes");
else puts("No");
}
}5.4 AC自动机
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010;
queue<int> q;
//int vis[maxn]; 用于做出现次数
struct Aho_Corasick_Automaton {
int c[maxn][26], fail[maxn], cnt, val[maxn];
// int flag[maxn], in[maxn], ans[maxn]; // 用于做出现次数
void ins (string s, int x) { // 不加x,即为出现个数
int len = s.size();
int now = 0;
for (int i = 0; i < len; i ++ ) {
int v = s[i] - 'a';
if (!c[now][v]) c[now][v] = ++ cnt;
now = c[now][v];
}
// if (!flag[now]) flag[now] = x; // 用于做出现次数
// val[x] = flag[now];
// val[now] ++ ; // 用于做出现个数
}
void build() {
for (int i = 0; i < 26; i ++ ) {
if (c[0][i]) {
fail[c[0][i]] = 0;
q.push(c[0][i]);
}
}
while (q.size()) {
int t = q.front(); q.pop();
for (int i = 0; i < 26; i ++ ) {
if (c[t][i]) {
fail[c[t][i]] = c[fail[t]][i];
// in[fail[c[t][i]]] ++ ; // 用于做出现次数
q.push(c[t][i]);
}
else c[t][i] = c[fail[t]][i];
}
}
}
void query (char *s) {
int len = strlen(s);
int now = 0;
// int ans = 0;
for (int i = 0; i < len; i ++ ) {
now = c[now][s[i] - 'a'];
ans[now] ++ ; // 用于做出现次数
// for (int t = now; t && ~val[t]; t = fail[t]) { // 用于做出现个数
//
// ans += val[t], val[t] = -1;
// }
}
// return ans; 最终出现个数
}
// void topsort() { // 用于做出现次数
// for (int i = 1; i <= cnt; i ++ ) {
// if (!in[i]) q.push(i);
// }
// while (q.size()) {
// int t = q.front(); q.pop();
// vis[flag[t]] = ans[t];
// int v = fail[t];
// in[v] -- ;
// ans[v] += ans[t];
// if (!in[v]) q.push(v);
// }
// }
void clear () {
cnt = 0;
memset(c, 0, sizeof c);
memset(val, 0, sizeof val);
memset(fail, 0, sizeof fail);
// memset(flag, 0, sizeof flag); // 用于做出现次数
// memset(ans, 0, sizeof ans);
// memset(in, 0, sizeof in);
}
}AC;
int n;
string p[200];
char t[1000010];
// vis[AC.val[i]] 第i个串的出现个数.
int main () {
while (scanf("%d", &n), n) {
AC.clear();
for (int i = 1; i <= n; i ++ ) {
cin >> p[i];
AC.ins(p[i], i);
}
AC.build();
scanf("%s", t);
AC.query(t);
AC.topsort();
int mx = 0;
for (int i = 1; i <= n; i ++ ) {
mx = max(mx, vis[AC.val[i]]);
// printf("%d\n", vis[AC.val[i]]);
}
printf("%d\n", mx);
for (int i = 1; i <= n; i ++ ) {
if (vis[AC.val[i]] == mx) cout << p[i] << endl;
}
}
}5.5 最小表示法
#include <bits/stdc++.h>
using namespace std;
char s[1000];
int main () {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i ++ ) {
s[n + i] = s[i];
}
int i = 1, j = 2, k;
while (i <= n && j <= n) {
for (k = 0; k < n && s[i + k] == s[j + k]; k ++ );
if (k == n) break;
if (s[i + k] > s[j + k]) {
i += k + 1;
if (i == j) i ++ ;
}
else {
j += k + 1;
if (i == j) j ++ ;
}
}
int ans = min(i, j);
for (int i = ans; i <= ans + n - 1; i ++ ) printf("%c", s[i]);
}5.6 Trie
// 字典树
const int mxn = 1e6 + 100;
struct Trie {
int nxt[mxn << 1][26], cnt[mxn << 1];
int c = 0;
void clear() {
c = 0;
ms(nxt[0], 0);
ms(cnt, 0);
}
inline int newnode () {
c ++ ;
return c;
}
void insert (string s) {
int u = 0, now = 0;
while (now < sz(s)) {
u = insert(u, s[now] - 'a');
now ++ ;
}
cnt[u] ++ ;
}
inline int insert (int pre, int ch) {
return nxt[pre][ch] ? nxt[pre][ch] : nxt[pre][ch] = newnode();
}
inline int query (string s) {
int u = 0, now = 0;
while (now < sz(s)) {
if (!nxt[u][s[now] - 'a']) return 0;
else u = nxt[u][s[now] - 'a'];
now ++ ;
}
return cnt[u];
}
}trie;
void solve() {
read(n);
for (int i = 1; i <= n; i ++ ) {
string op, a;
cin >> op >> a;
if (op == "I") trie.insert(a);
else printf("%lld\n", trie.query(a));
}
}
// 01trie 最大区间异或和
const int mxn = 5e5 + 100;
struct Tire {
int nxt[mxn << 2][2], l[mxn << 2];
int cnt, ansl, ansr, ansv;
inline void init () {
cnt = 0; ansv = -1;
ms(nxt[0], 0);
ms(l, 0x3f);
}
inline int create () {
cnt ++ ;
ms(nxt[cnt], 0);
return cnt;
}
inline void insert (int id, int x) {
int u = 0;
for (int i = 31; i >= 0; i -- ) {
int t = ((x >> i) & 1);
if (!nxt[u][t]) nxt[u][t] = create();
u = nxt[u][t];
}
l[u] = id;
// l[u] = min(l[u], id);
}
inline void query (int id, int x) {
int u = 0, res = 0;
// de(ansv); de(x);
for (int i = 31; i >= 0; i -- ) {
int t = ((x >> i) & 1);
if (nxt[u][!t]) {
u = nxt[u][!t];
res += 1ll << i;
}
else u = nxt[u][t];
}
// de(id); de(res);
// if (res == ansv) {
// if (l[u] < ansl) {
// ansl = l[u]; ansr = id;
// }
// }
if (res > ansv) {
ansv = res; ansl = l[u]; ansr = id;
}
}
}trie;
void solve() {
read(n);
trie.init(); trie.insert(0, 0);
int sum = 0;
for (int i = 1; i <= n; i ++ ) {
int x; read(x); sum ^= x;
trie.query(i, sum); trie.insert(i, sum);
}
printf("%lld %lld %lld\n", trie.ansv, trie.ansl + 1, trie.ansr);
}
// 可持久化01trie
const int mxn = 6e5 + 100;
struct Tire {
int nxt[mxn * 25][2], sum[mxn * 25];
int root[mxn * 25];
int cnt;
inline void init () {
cnt = 0;
ms(nxt[0], 0);
ms(root, 0);
ms(sum, 0);
}
inline int create () {
cnt ++ ;
ms(nxt[cnt], 0);
return cnt;
}
inline int insert (int x, int pre) {
int u = ++ cnt, t = u;
for (int i = 30; i >= 0; i -- ) {
int t = ((x >> i) & 1);
nxt[u][0] = nxt[pre][0], nxt[u][1] = nxt[pre][1];
sum[u] = sum[pre] + 1;
nxt[u][t] = ++ cnt;
u = nxt[u][t], pre = nxt[pre][t];
}
sum[u] = sum[pre] + 1;
return t;
}
inline int query (int x, int l, int r) {
int res = 0;
for (int i = 30; i >= 0; i -- ) {
int t = !((x >> i) & 1);
if (sum[nxt[r][t]] - sum[nxt[l][t]] > 0) {
res |= (1ll << i);
l = nxt[l][t], r = nxt[r][t];
}
else l = nxt[l][!t], r = nxt[r][!t];
}
return res;
}
}trie;
void solve() {
read(n), read(m);
int now = 0;
n ++ ;
trie.root[1] = trie.insert(now, trie.root[0]);
for (int i = 2; i <= n; i ++ ) {
int x; read(x);
now ^= x;
trie.root[i] = trie.insert(now, trie.root[i - 1]);
}
while (m -- ) {
char op[2];
scanf("%s", op);
if (*op == 'A') {
int x; read(x); now ^= x;
n ++ ;
trie.root[n] = trie.insert(now, trie.root[n - 1]);
}
else {
int l, r, x;
read(l), read(r), read(x);
int tmp = now ^ x;
ll ans = trie.query(tmp, trie.root[l - 1], trie.root[r]);
printf("%lld\n", ans);
}
}
}6 杂项
6.1 高精度
__int128使用（kuangbin模板）（范围：-2^127 ~ 2^127， 约10^38，longlong范围10^19）
#include <bits/stdc++.h>
using namespace std;
inline __int128 read(){
__int128 x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(__int128 x){
if(x < 0){
putchar('-'); x = -x;
}
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
int main(void){
__int128 a = read();
__int128 b = read();
print(a + b);
cout << endl;
return 0;
}大整数类（压9位）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Wint:vector<ll>
{
const static ll BIT=1e9;
Wint(ll n=0) {push_back(n);check();}
Wint& operator=(const char* num)
{
int Len=strlen(num)-1; clear();
for(int i=Len;i>=0;i-=9)
{
push_back(0); ll w=1;
for(int j=i;j>i-9&&j>=0;--j)
back()+=(num[j]^48)*w,w*=10;
}
return *this;
}
Wint& check()
{
while(!empty()&&!back()) pop_back();
if(empty()) return *this;
for(int i=1;i<size();++i)
(*this)[i]+=(*this)[i-1]/BIT,
(*this)[i-1]%=BIT;
while(back()>=BIT)
{
push_back(back()/BIT);
(*this)[size()-2]%=BIT;
}
return *this;
}
};
bool operator<(Wint a,Wint b)
{
if(a.size()!=b.size()) return a.size()<b.size();
for(int i=a.size()-1;i>=0;--i)
if(a[i]!=b[i]) return a[i]<b[i];
return 0;
}
bool operator>(Wint a,Wint b) {return b<a;}
bool operator<=(Wint a,Wint b) {return !(a>b);}
bool operator>=(Wint a,Wint b) {return !(a<b);}
bool operator!=(Wint a,Wint b) {return a<b||b<a;}
bool operator==(Wint a,Wint b) {return !(a<b)&&!(b<a);}
Wint& operator+=(Wint &a,Wint b)
{
if(a.size()<b.size()) a.resize(b.size());
for(int i=0;i<b.size();++i) a[i]+=b[i];
return a.check();
}
Wint operator+(Wint a,Wint b) {return a+=b;}
Wint& operator-=(Wint &a,Wint b)
{
for(int i=0;i<b.size();a[i]-=b[i],++i)
if(a[i]<b[i])
{
int j=i+1;
while(!a[j]) ++j;
while(j>i) --a[j],a[--j]+=Wint::BIT;
}
return a.check();
}
Wint operator-(Wint a,Wint b) {return a-=b;}
Wint operator*(Wint a,Wint b)
{
if(a.empty()&&b.empty()) return a;
Wint n; n.assign(a.size()+b.size()-1,0);
for(int i=0;i<a.size();++i)
for(int j=0;j<b.size();++j)
n[i+j]+=a[i]*b[j];
return n.check();
}
Wint& operator*=(Wint &a,Wint b) {return a=a*b;}
Wint operator/(Wint a,int b)
{
Wint n; bool wp=0; ll t=0;
for(int i=a.size()-1;i>=0;--i)
{
t=t*Wint::BIT+a[i];
if(wp||t/b) wp=1,n.push_back(t/b);
t%=b;
}
reverse(n.begin(),n.end());
return n;
}
Wint& operator/=(Wint &a,int b) {return a=a/b;}
void readX(Wint &n) {char s[100010]; scanf("%s",s); n=s;}
void writeX(Wint n)
{
if(n.empty()) {putchar('0'); return;}
int Len=n.size()-1; printf("%lld",n[Len]);
for(int i=Len-1;i>=0;--i) printf("%09lld",n[i]);
}6.2 二维前缀和
//构造前缀和矩阵
a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
//求x1, y1, x2, y2为边界的子矩阵之和
a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];6.3 双指针
6.4 ST表
// 可换成 max, min, gcd
void init () {
for (int j = 0; j < 20; j ++ ) {
for (int i = 1; i + (1 << j) - 1 <= n; i ++ ) {
if (!j) dp[i][j] = q[i];
else dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
}
}
}
int query (int l, int r) {
int k = log2(r - l + 1);
return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}6.5 快读函数 read()
// 仅支持整型
template <typename _T>
inline void read(_T &f) {
f = 0; _T fu = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
f *= fu;
}
//重载流输入型
struct IOS{
template<typename ATP>IOS& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
io >> n;
6.6 模拟退火
/*
求费马点型
在二维平面上有 n 个点，第 i 个点的坐标为 (xi,yi)。
请你找出一个点，使得该点到这 n 个点的距离之和最小。
该点可以选择在平面中的任意位置，甚至与这 n 个点的位置重合。
*/
#define x first
#define y second
typedef pair<double, double> PII;
const int maxn = 110;
int n;
PII q[maxn];
double ans = 1e8;
double rand (double l, double r) {
return (double)rand() / RAND_MAX * (r - l) + l;
}
double dis (PII a, PII b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double calc (PII p) {
double res = 0;
for (int i = 1; i <= n; i ++ ) {
res += dis(p, q[i]);
}
ans = min(ans, res);
return res;
}
void simulate_anneal () {
PII cur(rand(0, 10000), rand(0, 10000));
for (double t = 1e4; t > 1e-4; t *= 0.9) {
PII np(rand(cur.x - t, cur.x + t), rand(cur.y - t, cur.y + t));
double d = calc(np) - calc(cur);
if (exp(-d / t) > rand(0, 1)) cur = np;
}
}
int main () {
srand(time(NULL));
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &q[i].first, &q[i].second);
// 或 while ((double)clock()/CLOCKS_PER_SEC<0.8)
for (int i = 1; i <= 100; i ++ )
simulate_anneal();
printf("%.0lf\n", ans);
}6.7 STL
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
int has = s.find('xxxx');
if (has != string::npos) 含xxx字符
szie()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址 代表可以用printf输出string类
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bit.size() 返回大小（位数）
bit.count() 返回1的个数
bit.any() 返回是否有1
bit.none() 返回是否没有1
bit.set() 全都变成1
bit.set(p) 将第p + 1位变成1（bitset是从第0位开始的！）
bit.set(p, x) 将第p + 1位变成x
bit.reset() 全都变成0
bit.reset(p) 将第p + 1位变成0
bit.flip() 全都取反
bit.flip(p) 将第p + 1位取反
bit.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错
bit.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
bit.to_string() 返回它转换为string的结果6.8 离散化
vector<int> v;
for (int i = 1; i <= n; i ++ ) {
read(q[i]); v.pb(q[i]);
}
sort(all(v));
v.erase(unique(all(v)), v.end());
for (int i = 1; i <= n; i ++ ) {
q[i] = lower_bound(all(v), q[i]) - v.begin() + 1;
}6.9 随机数
mt19937 sed(time(nullptr));
uniform_int_distribution<int> range(l, r); // l到r内随机数
cout << range(sed) << endl; 
