ACM竞赛模板——旧忆

基础

语法基础

匿名函数

1
2
3
4
5
6
7
   function<int(int, int)> add = [&](int a, int b) -> int {
return a + b;
};

auto add = [&](int a, int b) -> int {
return a + b;
};

算法基础

排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int q[],int l,int r)
{
if(l>=r) return;
int i=l-1,j=r+1,x=q[l+r>>1];
while(i<j)
{
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j),quick_sort(q,j+1,r);
}

快速排序求区间第k小数

1
2
3
4
5
6
7
8
9
10
11
12
//得到q[l~r]中第k小的数
int quick_sort(int q[],int l,int r,int k){
if(l>=r) return q[l];
int i=l-1,j=r+1,x=q[l+r>>1];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
if(j-l+1>=k) return quick_sort(q,l,j,k);
else return quick_sort(q,j+1,r,k-(j-l+1));
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge_sort(int q[],int l,int r){
if(l>=r) return;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int i=0;i<k;i++) q[l+i]=tmp[i];
}

求区间逆序对数量

应用:把一个无序的序列变成有序的序列,每次操作可以交换相邻两个数,最少需要的操作次数是这个序列的逆序对数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LL merge_sort(vector<int> &q,int l,int r){
if(l>=r) return 0;
int mid=l+r>>1;
LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++];
else{
tmp[k++]=q[j++];
res+=mid-i+1;
}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int i=0;i<k;i++) q[l+i]=tmp[i];
return res;
}

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int bsearch_l(int q[],int l,int r){
while(l<=r){
int mid=l+r>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
return l;
}
int bsearch_r(int q[],int l,int r){
while(l<=r){
int mid=l+r+1>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
return l-1;
}

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 获取 a 的第 b 位,最低位编号为 0
int getbit(int a, int b) { return (a >> b) & 1; }
// 将 a 的第 b 位设置为 0 ,最低位编号为 0
int unsetbit(int a, int b) { return a & ~(1 << b); }
// 将 a 的第 b 位设置为 1 ,最低位编号为 0
int setbit(int a, int b) { return a | (1 << b); }
// 将 a 的第 b 位取反 ,最低位编号为 0
int flapbit(int a, int b) { return a ^ (1 << b); }
//快速判断x是否是2的幂次
int is_pow2(int x) { return (x & (x - 1) == 0); }
//得到一个数最低的一个1及其后面的所有位
inline int lowbit(int x){ return x & (-x); }
//统计x二进制表示下1的个数
inline int count1(int x)
{
int cnt = 0;
while(x){
x = x & (x - 1);
//x -= lowbit(x);
cnt ++;
}
return cnt;
}

去掉最后一位 | (101101->10110) | x >> 1
在最后加一个0 | (101101->1011010) | x < < 1
在最后加一个1 | (101101->1011011) | x < < 1+1
把最后一位变成1 | (101100->101101) | x | 1
把最后一位变成0 | (101101->101100) | x | 1-1
最后一位取反 | (101101->101100) | x ^ 1
把右数第k位变成1 | (101001->101101,k=3) | x | (1 < < (k-1))
把右数第k位变成0 | (101101->101001,k=3) | x & ~ (1 < < (k-1))
右数第k位取反 | (101001->101101,k=3) | x ^ (1 < < (k-1))
取末三位 | (1101101->101) | x & 7
取末k位 | (1101101->1101,k=5) | x & ((1 < < k)-1)
取右数第k位 | (1101101->1,k=4) | x >> (k-1) & 1
把末k位变成1 | (101001->101111,k=4) | x | (1 < < k-1)
末k位取反 | (101001->100110,k=4) | x ^ (1 < < k-1)
把右边连续的1变成0 | (100101111->100100000) | x & (x+1)
把右起第一个0变成1 | (100101111->100111111) | x | (x+1)
把右边连续的0变成1 | (11011000->11011111) | x | (x-1)
取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1
去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1))
判断奇数 (x&1)==1
判断偶数 (x&1)==0
取右边第一个1所在位置 x&-x

  • 十进制a、b,判断是否存在a的第i位为0,b的第i位为1

    1
    2
    if ((a&b)<b) 存在a的第i位为0,b的第i位为1
    else 不存在
  • 异或性质:

    • 与加法的关系:$a+b≡a\oplus(mod\ 2)$

      注意奇偶性

数据结构

队列

单调队列

1
2
3
4
5
6
7
8
9
//b[i]表示以i为右端点的连续k个数的最小值
int n,k,a[N],b[N];
deque<int> q;
for(int i=1;i<=n;i++){
while(q.size()&&a[i]<=a[q.back()]) q.pop_back();
q.push_back(i);
if(i-k>=1&&i-k==q.front()) q.pop_front();
if(i>=k) b[i]=a[q.front()];
}

单调栈

1
2
3
4
5
6
7
8
//lmin[i]表示a[i]左边第一个比它小的数
int a[N],stk[N],tt,lmin[N];
for(int i=1;i<=n;i++){
while(tt&&stk[tt]>=a[i]) tt--;
if(!tt) lmin[i]=-1;
else lmin[i]=stk[tt];
stk[++tt]=a[i];
}

并查集

并查集基础

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct DSU {
vector<int> p, siz;
DSU(int n) : p(n+1), siz(n+1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
siz[x] += siz[y];
p[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};

带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct DSU {
vector<int> p, siz, d;
DSU(int n) : p(n+1), siz(n+1, 1), d(n+1) { iota(p.begin(), p.end(), 0); }
int find(int x){
if(p[x]!=x){
int rt=find(p[x]);
d[x]+=d[p[x]];
p[x]=rt;
}
return p[x];
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
siz[x] += siz[y];
code:...
p[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};

分块

莫队算法

例题:HH的项链

题意:n个数,多次询问区间不同数的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi = 0;

const int N = 5e4 + 10, M = 2e5 + 10, K = 1e6 + 10;
int n, m;
int a[N];
int cnt[K], sum;
int block;
int ans[M];

struct Query {
int id, l, r;
}q[M];

inline int get(int x) {
return x / block;
}

bool cmp(const Query& a, const Query& b) {
int i = get(a.l), j = get(b.l);
if(i != j) return i < j;
return i & 1 ? a.r < b.r : a.r > b.r;
}

inline void add(int x) {
if(++cnt[x] == 1) {
sum++;
}
}

inline void del(int x) {
if(--cnt[x] == 0) {
sum--;
}
}

void solve(){
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> m;
block = max(1LL, (int)sqrt(1.0 * n * n / m));
for(int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
q[i] = {i, l, r};
}
sort(q + 1, q + 1 + m, cmp);
for(int i = 1, l = 1, r = 0; i <= m; i++) {
while(l > q[i].l) {
add(a[--l]);
}
while(r < q[i].r) {
add(a[++r]);
}
while(l < q[i].l) {
del(a[l++]);
}
while(r > q[i].r) {
del(a[r--]);
}
ans[q[i].id] = sum;
}
for(int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

CDQ分治

给定 $n$ 个元素(编号 $1 \sim n$),其中第 $i$ 个元素具有 $a_i,b_i,c_i$ 三种属性。 设 $f(i)$ 表示满足以下 $4$ 个条件: 1. $a_j \le a_i$ 2. $b_j \le b_i$ 3. $c_j \le c_i$ 4. $j \neq i$ 的 $j$ 的数量。 对于 $d \in [0,n)$,求满足 $f(i) = d$ 的 $i$ 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi = 0;


struct Node {
int a, b, c;
int cnt;
int res;

bool operator!=(Node& w) const {
if(a != w.a || b != w.b || c != w.c) return true;
return false;
}
};

bool cmpA(Node& x, Node& y) {
if(x.a != y.a) return x.a < y.a;
if(x.b != y.b) return x.b < y.b;
return x.c < y.c;
}

bool cmpB(Node& x, Node& y) {
if(x.b != y.b) return x.b < y.b;
return x.c < y.c;
}

int n, m, k, ans[100005];
Node e[100005];

int tr[200005];
inline int lowbit(int x){
return x&-x;
}
void add(int x,int c){
for(int i=x;i<=k;i+=lowbit(i)){
tr[i]+=c;
}
return;
}
int sum(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}

void CDQ(int l, int r) {
if(l == r) return;
int mid = (l + r) / 2;
CDQ(l, mid), CDQ(mid + 1, r);
sort(e + l, e + mid + 1, cmpB), sort(e + mid + 1, e + r + 1, cmpB);
int i = l, j = mid + 1;
while(j <= r) {
while(i <= mid && e[i].b <= e[j].b) {
add(e[i].c, e[i].cnt);
i++;
}
e[j].res += sum(e[j].c);
j++;
}
for(int k = l; k < i; k++) add(e[k].c, -e[k].cnt);
return;
}

void solve(){
cin >> n >> k;
int Q = n;
map<array<int, 3>, int> mp;
for(int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
mp[{a, b, c}]++;
}
n = 0;
for(auto &[x, cnt]: mp) {
e[++n] = {x[0], x[1], x[2], cnt, 0};
}
sort(e + 1, e + 1 + n, cmpA);
CDQ(1, n);
for(int i = 1; i <= n; i++) ans[e[i].res + e[i].cnt - 1] += e[i].cnt;
for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
return;
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

树的基础

树的重心

概念:以树的重心为整棵树的根时,它的最大子树最小(也就是删除该点后最大联通块最小)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> v;
int ans=N;
bool st[N];

int dfs(int u){
st[u]=true;
int res=0,sum=1;
for(auto i:v[u]){
if(!st[i]){
int s=dfs(i);
res=max(res,s);
sum+=s;
}
}
res=max(res,n-sum);
ans=min(res,ans);
return sum;
}
//vector建图
dfs(1);
//返回的ans即为树的重心
树的直径

树的直径,是指树上最长的一条链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<PII>> v;
int ans;

int dfs(int u,int fa){
int dist=0;
int d1=0,d2=0;
for(auto it:v[u]){
int j=it.first,w=it.second;
if(j==fa) continue;
int d=dfs(j,u)+w;
dist=max(dist,d);

if(d>=d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return dist;
}
//多组数据初始化ans=0
dfs(1,-1);
//ans即为树的直径
树的中心

概念:以树的中心为整棵树的根时,从该根到每个叶子节点的最长路径最短

该点到树中其他结点的最远距离最近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// Problem: 树的中心
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1075/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 0;

const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e4 + 10;
int n;
vector<PII> edge[N];
int d1[N], d2[N], p1[N], up[N];
bool is_leaf[N];

void dfs_d(int u, int father) {
d1[u] = d2[u] = -INF;
for(auto [v, w]: edge[u]) {
if(v == father) continue;
dfs_d(v, u);
if(d1[v] + w >= d1[u]) {
d2[u] = d1[u], d1[u] = d1[v] + w;
p1[u] = v;
}else if(d1[v] + w > d2[u]) {
d2[u] = d1[v] + w;
}
}
if(d1[u] == -INF) {
d1[u] = d2[u] = 0;
is_leaf[u] = true;
}
}

void dfs_u(int u, int father) {
for(auto [v, w]: edge[u]) {
if(v == father) continue;
if(p1[u] == v) up[v] = w + max(up[u], d2[u]);
else up[v] = w + max(up[u], d1[u]);
dfs_u(v, u);
}
}

void solve() {
cin >> n;
for(int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
edge[a].push_back({b, c});
edge[b].push_back({a, c});
}
dfs_d(1, -1);
dfs_u(1, -1);
int ct, res = INF;
for(int i = 1; i <= n; i++) {
if(res > max(d1[i], up[i])) {
res = max(d1[i], up[i]);
ct = i;
}
}
cout << res << '\n';
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}
LCA(最近公共祖先)
  • 倍增法:祖孙询问
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//N为结点数量,M=log2(N),一般多开2个,开成log2(N)+2
vector<vector<int>> adj;//vector存图
int fa[N][M],depth[N];//fa[i][j]表示结点i往上跳2^j步后的结点,depth[i]表示结点i的深度
//预处理出depth数组和fa数组
void bfs(int root){
memset(depth,0x3f,sizeof depth);
queue<int> q;
q.push(root);
depth[0]=0,depth[root]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto v:adj[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
for(int k=1;k<=M-1;k++){//注意这里的M-1(第1/3处)
fa[v][k]=fa[fa[v][k-1]][k-1];
}
}
}
}
}
//返回结点a,b的祖孙关系
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k=M-1;k>=0;k--){//注意这里的M-1(第2/3处)
if(depth[fa[a][k]]>=depth[b]){
a=fa[a][k];
}
}
if(a==b) return a;
for(int k=M-1;k>=0;k--){//注意这里的M-1(第3/3处)
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}

bfs(root);
int p=lca(a,b);
if(p==a) a是b的祖先
else if(p==b) b是a的祖先
else a和b的祖先是p
  • Tarjan算法求多次询问树上任意两点的最短距离(离线)

    时间复杂度O(n+q)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    //N为结点个数,M为询问个数
    int res[M],dist[N],p[N],st[N];
    //res[i]为第i-1个询问的结果,dist[i]为结点i到根节点距离,p[i]为并查集数组
    //st[i]为0表示还没被搜索过,为1表示正在被搜索,为2表示已经被搜索过
    vector<PII> query[M];//存储每个询问
    vector<vector<PII>> edge;//存储边
    int find(int x){//缩点
    if(p[x]!=x) return p[x]=find(p[x]);
    return p[x];
    }
    void dfs(int u,int fa){//预处理每个点到根节点距离
    for(auto it:edge[u]){
    int v=it.first,w=it.second;
    if(v==fa) continue;
    dist[v]=dist[u]+w;
    dfs(v,u);
    }
    }
    void tarjan(int u){
    st[u]=1;
    for(auto it:edge[u]){
    int v=it.first,w=it.second;
    if(!st[v]){
    tarjan(v);
    p[v]=u;
    }
    }
    for(auto it:query[u]){
    int v=it.first,id=it.second;
    if(st[v]==2){
    int ans=find(v);
    res[id]=dist[u]+dist[v]-2*dist[ans];
    }
    }
    st[u]=2;
    }
    void solve(){
    int n,m;cin>>n>>m;
    edge.resize(n+1);
    for(int i=0;i<n-1;i++){
    int x,y,k;cin>>x>>y>>k;
    edge[x].push_back({y,k});
    edge[y].push_back({x,k});
    }
    for(int i=0;i<m;i++){
    int a,b;cin>>a>>b;
    if(a!=b){
    query[a].push_back({b,i});//离线处理询问
    query[b].push_back({a,i});
    }
    }
    for(int i=1;i<=n;i++) p[i]=i;
    dfs(1,-1);
    tarjan(1);
    for(int i=0;i<m;i++) cout<<res[i]<<endl;
    }

虚树

虚树的构建
1.先预处理原树的lca和dfs序,然后用栈维护关键点,构造虚树。

2. 对k个查询点按dfs序排序,先加入根节点,再按顺序加入查询点。3.栈维护从根向下的一条链上的关键点,按深度从小到大存储。
当加入a[x]后,满足s[1]= root,s[top] = a[x], s[x]为s[x 一1]的后代。4.现在考虑加入查询点a[i],设lca= LCA(s[top],a[i]),分两类讨论:

(1) lca = s[top],即a[i]是s[top]子树内的节点。直接把a[i]入栈。

(2) lca ≠ s[top],即a[i]不是 s[top]子树内的节点(如图)。
lca下面路径上的关键点都应出栈, 出栈时从s[top -1]向s[top]连边。注意:当dep[s[top-1]]<dep[lca]时,停止出栈。此时,
①如果lca = s[top],说明lca已在栈中,那么直接把a[i]入栈。

②如果lca ≠ s[top],说明lca不在栈中, s[top]依然在lca的下面。
先从lca向s[top]连一条边,再把 s[top]出栈,把lca入栈,把a[i]入栈。

枚举结束后,还要把最后一条链上的关键点连边,出栈。

例题:

给定一个树,q次询问:

每个询问包括点的个数k,接下来是k个点。

从这棵树中选一点使得到这k个点的最大距离最小,求这个最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;
const int N = 1e5 + 10, M = 19;
int n, q;
vector<vector<int>> adj;
vector<int> ve;
int dfn[N], tms;

int fa[N][M],depth[N];
void bfs(int root){
memset(depth,0x3f,sizeof depth);
queue<int> q;
q.push(root);
depth[0]=0,depth[root]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto v:adj[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
for(int k=1;k<=M-1;k++){//注意这里的M-1(第1/3处)
fa[v][k]=fa[fa[v][k-1]][k-1];
}
}
}
}
}

int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k=M-1;k>=0;k--){//注意这里的M-1(第2/3处)
if(depth[fa[a][k]]>=depth[b]){
a=fa[a][k];
}
}
if(a==b) return a;
for(int k=M-1;k>=0;k--){//注意这里的M-1(第3/3处)
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}

void dfs1(int u, int fa) {
dfn[u] = ++tms;
for(auto v: adj[u]) {
if(v == fa) continue;
dfs1(v, u);
}

}

vector<PII> nadj[N];
int stk[N], top;
int dp[N];
int ans;
void dfs_dp(int u, int fa) {
for(auto [v, w]: nadj[u]) {
if(v == fa) continue;
dfs_dp(v, u);
ans = max(ans, dp[u] + dp[v] + w);
dp[u] = max(dp[u], dp[v] + w);
}
}

void add(int u, int v, int w) {
nadj[u].push_back({v, w});
nadj[v].push_back({u, w});
}

void solve_q() {
// for(auto tmp: ve) {
// cout << tmp << '\n';
// }
// cout << 1 << '\n'; return;
sort(ve.begin(), ve.end(), [&](int a, int b) {
return dfn[a] < dfn[b];
});
stk[top = 1] = ve[0];
vector<int> rec = ve;
for(int i = 1; i < ve.size(); i++) {
int cur = ve[i];
int l = lca(cur, stk[top]);
if(l == stk[top]) {
stk[++top] = cur;
}else{
while(depth[stk[top - 1]] >= depth[l]) {
add(stk[top - 1], stk[top], depth[stk[top]] - depth[stk[top - 1]]);
top--;
}
if(l == stk[top]) {
stk[++top] = cur;
}else{
add(l, stk[top], depth[stk[top]] - depth[l]);
--top;
stk[++top] = l;
rec.push_back(l);
stk[++top] = cur;
}
}
}
while(top > 1) {
add(stk[top], stk[top - 1], depth[stk[top]] - depth[stk[top - 1]]);
--top;
}
ans = 0;
dfs_dp(rec[0], -1);
cout << (ans + 1) / 2 << '\n';
for(auto x: rec) {
// cout << x << ": \n";
// for(auto [v, w]: nadj[x]) {
// cout << x << ' ' << v << '\n';
// }
nadj[x].clear();
dp[x] = 0;
}
}

void solve(){
cin >> n >> q;
adj.resize(n + 1);
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs1(1, -1);
bfs(1);
while(q--) {
ve.clear();
int k;
cin >> k;
while(k--) {
int x;
cin >> x;
// cout << x << '\n';
ve.push_back(x);
}
solve_q();
}

}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

树状数组

一维树状数组
单点修改区间查询(树状数组的基本功能)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//N为维护的数列长度
int a[N],tr[N];//tr[]维护a[]本身
inline int lowbit(int x){
return x&-x;
}
void add(int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=c;
}
}
int sum(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
for(int i=1;i<=n;i++) add(i,a[i]);//初始化原数组
add(u,d);//tr[u]增加d
sum(r)-sum(l-1)//求tr[l..r]的和
区间修改单点查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//N为维护的数列长度
int a[N],tr[N];//tr[]数组维护a[]的差分数组
inline int lowbit(int x){
return x&-x;
}
void add(int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=c;
}
}
int sum(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
for(int i=1;i<=n;i++) add(i,a[i]-a[i-1]);//初始化原数组
add(l,d),add(r+1,-d);//将区间[l,r]分别加上d
sum(u);//单点查询u
区间修改区间查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template<class T>
struct BIT{
int n;
vector<T> tr1,tr2;
BIT(int n):tr1(n+1),tr2(n+1){
this->n=n;
}
BIT(int n,T a[]):tr1(n+1),tr2(n+1){
this->n=n;
for(int i=1;i<=n;i++){
add(tr1,i,a[i]-a[i-1]);
add(tr2,i,i*(a[i]-a[i-1]));
}
}
T sum(int l,int r){
return prefix_sum(r)-prefix_sum(l-1);
}
void add(int l,int r,T d){
add(tr1,l,d),add(tr1,r+1,-d);
add(tr2,l,l*d),add(tr2,r+1,(r+1)*-d);
}
private:
inline int lowbit(int x){return x&-x;}
void add(vector<T> &tr,int x,T c){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=c;
}
}
T sum(vector<T> &tr,int x){
T res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
T prefix_sum(int x){
return sum(tr1,x)*(x+1)-sum(tr2,x);
}
};
权值树状数组查询第k小
1
2
3
4
5
6
7
8
9
10
11
12
// 权值树状数组查询第 k 小
int kth(int k) {
int sum = 0, x = 0;
for (int i = log2(n); ~i; --i) {
x += 1 << i; // 尝试扩展
if (x >= n || sum + t[x] >= k) // 如果扩展失败
x -= 1 << i;
else
sum += t[x];
}
return x + 1;
}
二维树状数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N = 2050;
int n,m;
int t1[N][N],t2[N][N],t3[N][N],t4[N][N];
inline lowbit(int x){
return x&-x;
}
void add(int x,int y,int d){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j)){
t1[i][j] += d; t2[i][j] += x*d;
t3[i][j] += y*d; t4[i][j] += x*y*d;
}
}
int sum(int x,int y){
int ans = 0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans += (x+1)*(y+1)*t1[i][j] - (y+1)*t2[i][j] - (x+1)*t3[i][j] + t4[i][j];
return ans;
}
int sum(int x1, int y1, int x2, int y2) {
return sum(x2,y2)+sum(x1-1,y1-1)-sum(x1-1,y2)-sum(x2,y1-1);
}
void add(int x1, int y1, int x2, int y2, int d) {
add(x1,y1,d);add(x2+1,y2+1,d);
add(x1,y2+1,-d);add(x2+1,y1,-d);
}

线段树

不带懒标记的线段树

模板(区间最大子段和)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
template<class Info>
struct SegmentTree {
int n;
vector<Info> info;
SegmentTree() : n(0) {}
SegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
SegmentTree(vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(vector(n_ + 1, v_));
}
template<class T>
void init(vector<T> init_) {
n = init_.size() - 1;
info.assign(n * 4 + 5, Info());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = {init_[l], init_[l], init_[l], init_[l]};
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pushup(p);
};
build(1, 1, n);
}
void pushup(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void modify(int p, int l, int r, int x, const Info &v) {
if (l == r) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x <= m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m + 1, r, x, v);
}
pushup(p);
}
void modify(int pos, const Info &v) {
modify(1, 1, n, pos, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 1, n, l, r);
}
};

struct Info {
int sum = 0;
int mx = -INF, lmx = -INF, rmx = -INF;
};

Info operator+(Info a, Info b) {
int sum = a.sum + b.sum;
int mx = max({a.mx, b.mx, a.rmx + b.lmx});
int lmx = max({a.lmx, a.sum + b.lmx});
int rmx = max({a.rmx + b.sum, b.rmx});
return {sum, mx, lmx, rmx};
}
带懒标记的线段树

模板(区间修改区间加减区间求最值)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
template<class Info, class Tag>
struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(vector(n_ + 1, v_));
}
template<class T>
void init(vector<T> init_) {
n = init_.size() - 1;
info.assign(n * 4 + 5, Info());
tag.assign(n * 4 + 5, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = {init_[l]};
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pushup(p);
};
build(1, 1, n);
}
void pushup(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void pushdown(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (l == r) {
info[p] = v;
return;
}
int m = (l + r) / 2;
pushdown(p);
if (x <= m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m + 1, r, x, v);
}
pushup(p);
}
void modify(int p, const Info &v) {
modify(1, 1, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
pushdown(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 1, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l > y || r < x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
pushdown(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m + 1, r, x, y, v);
pushup(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 1, n, l, r, v);
}

};

struct Tag {
int add = 0, to = INF;
void apply(Tag t) { //两个懒标记结合
if(t.to != INF) {
add = 0, to = t.to;
}
add += t.add;
}
};

struct Info {
int mx = -INF;
void apply(Tag t) { //懒标记作用到信息上
if(t.to != INF) {
mx = t.to;
}
mx += t.add;
}
};
Info operator+(Info a, Info b) {
return {max(a.mx, b.mx)};
}

区间加减区间求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define int long long
#define ls u<<1
#define rs u<<1|1

const int N=1e5+10;
int n,m;
int w[N];
struct Node{
int l,r;
int sum,add;
}tr[N*4];

void pushup(int u){
tr[u].sum=tr[ls].sum+tr[rs].sum;
}

void pushdown(int u){
if(tr[u].add){
tr[ls].add+=tr[u].add,tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[u].add;
tr[rs].add+=tr[u].add,tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[u].add;
tr[u].add=0;
}
}

void build(int u,int l,int r){
if(l==r) tr[u]={l,r,w[r],0};
else{
tr[u]={l,r};
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(u);
}
}

void modify(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(ls,l,r,d);
if(r>mid) modify(rs,l,r,d);
pushup(u);
}
}

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(ls,l,r);
if(r>mid) sum+=query(rs,l,r);
return sum;
}

void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
char op;
int l,r,d;
while(m--){
cin>>op;
if(op=='C'){
cin>>l>>r>>d;
modify(1,l,r,d);
}else{
cin>>l>>r;
cout<<query(1,l,r)<<endl;
}
}
}

bool multi=false;

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}
return 0;
}

区间赋值区间求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>

using namespace std;

bool multi=0;

const int N = 1e5 + 10;
int n,q;
int a[N];

struct Node{
int l, r;
int sum, flag;
}tr[N * 4];

void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u){
if(tr[u].flag != -1){
tr[u << 1].sum = tr[u].flag * (tr[u << 1].r - tr[u << 1].l + 1);
tr[u << 1 | 1].sum = tr[u].flag * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
tr[u << 1].flag = tr[u << 1 | 1].flag = tr[u].flag;
tr[u].flag = -1;
}
}

void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, a[r], -1};
return;
}
tr[u] = {l, r, 0, -1};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}

void modify(int u, int l, int r, int x){

if(tr[u].l >= l && tr[u].r <= r){
tr[u].flag = x;
tr[u].sum = tr[u].flag * (tr[u].r - tr[u].l + 1);
}else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, x);
if(r > mid) modify(u << 1 | 1, l, r, x);
pushup(u);
}
}

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;
}

void solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
int q;
cin >> q;
while(q --){
int op, l, r;
cin >> op >> l >> r;
if(op == 0){
cout << query(1, l, r)<< '\n';
}else{
int x;
cin >> x;
modify(1, l, r, x);
}
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct Tag {
int to = INF;
void operator+=(Tag t) { //两个懒标记结合
if(t.to != INF) {
to = t.to;
}
}
};
struct Info {
int sum = 0, l = 0, r = 0;
friend Info operator+(Info a, Info b) {
return {a.sum + b.sum, a.l, b.r};
}
void operator+=(Tag t) {
if(t.to != INF) {
sum = t.to * (r - l + 1);
}
}
};
struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
void pushup(int u) {
info[u] = info[u << 1] + info[u << 1 | 1];
}
void build(int u, int l, int r) {
info[u].l = l, info[u].r = r;
if(l == r) {
// info[u] = {}
return;
}
int m = (l + r) >> 1;
build(u << 1, l, m), build(u << 1 | 1, m + 1, r);
pushup(u);
}

LazySegmentTree(int n_):n(n_) {
info.assign(n_ * 4 + 5, Info());
tag.assign(n_ * 4 + 5, Tag());
build(1, 1, n_);
}
void pushdown(int u) {
info[u << 1] += tag[u];
tag[u << 1] += tag[u];
info[u << 1 | 1] += tag[u];
tag[u << 1 | 1] += tag[u];
tag[u] = Tag();
}
Info rangeQuery(int u, int l, int r, int x, int y) {
if(l > y || r < x) {
return Info();
}
if(l >= x && r <= y) {
return info[u];
}
int m = (l + r) >> 1;
pushdown(u);
return rangeQuery(u << 1, l, m, x, y) + rangeQuery(u << 1 | 1, m + 1, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 1, n, l, r);
}
void rangeApply(int u, int l, int r, int x, int y, Tag v) {
if(l > y || r < x) {
return;
}
if(l >= x && r <= y) {
tag[u] += v;
info[u] += v;
return;
}
int m = (l + r) >> 1;
pushdown(u);
rangeApply(u << 1, l, m, x, y, v);
rangeApply(u << 1 | 1, m + 1, r, x, y, v);
pushup(u);
}
void rangeApply(int l, int r, Tag v) {
return rangeApply(1, 1, n, l, r, v);
}

};

区间乘区间加区间求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ls u<<1
#define rs u<<1|1
bool multi=0;
int n,p,m;
const int N=1e5+10;
int w[N];

struct Node{
int l,r;
int sum,add,mul;
}tr[N*4];

void pushup(int u){
tr[u].sum=(tr[ls].sum+tr[rs].sum)%p;
}

void eval(Node &t,int add,int mul){
t.sum=(t.sum*mul+(t.r-t.l+1)*add)%p;
t.mul=t.mul*mul%p;
t.add=(t.add*mul+add)%p;
}

void pushdown(int u){
eval(tr[ls],tr[u].add,tr[u].mul);
eval(tr[rs],tr[u].add,tr[u].mul);
tr[u].add=0,tr[u].mul=1;
}

void build(int u,int l,int r){
if(l==r) tr[u]={l,r,w[r],0,1};
else{
tr[u]={l,r,0,0,1};
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(u);
}
}

void modify(int u,int l,int r,int add,int mul){
if(tr[u].l>=l&&tr[u].r<=r) eval(tr[u],add,mul);
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(ls,l,r,add,mul);
if(r>mid) modify(rs,l,r,add,mul);
pushup(u);
}
}

int query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
int sum=0;
if(l<=mid) sum=query(ls,l,r);
if(r>mid) sum=(sum+query(rs,l,r))%p;
return sum;
}
}

void solve(){
cin>>n>>p;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);

cin>>m;
int t,l,r,d;
while(m--){
cin>>t>>l>>r;
if(t==1){
cin>>d;
modify(1,l,r,0,d);
}else if(t==2){
cin>>d;
modify(1,l,r,d,1);
}else{
cout<<query(1,l,r)<<'\n';
}
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}

return 0;
}

区间整体query的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u];
}else{
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid){
return query(u<<1,l,r);
}else if(l>mid){
return query(u<<1|1,l,r);
}else{
Node res;
Node left=query(u<<1,l,r),right=query(u<<1|1,l,r);
pushup(res,left,right);
return res;
}
}
}
线段树合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;

const int N = 1e5 + 10, M = 18, V = 1e5;
int n, m;
vector<vector<int>> adj;
int tridx, rt[N];
struct Tree {
int ls, rs;
int cnt, idx;
}tr[N * 4 * 17];
int fa[N][M],depth[N];//fa[i][j]表示结点i往上跳2^j步后的结点,depth[i]表示结点i的深度
//预处理出depth数组和fa数组
void bfs(int root){
memset(depth,0x3f,sizeof depth);
queue<int> q;
q.push(root);
depth[0]=0,depth[root]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto v:adj[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
for(int k=1;k<=M-1;k++){//注意这里的M-1(第1/3处)
fa[v][k]=fa[fa[v][k-1]][k-1];
}
}
}
}
}
//返回结点a,b的祖孙关系
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k=M-1;k>=0;k--){//注意这里的M-1(第2/3处)
if(depth[fa[a][k]]>=depth[b]){
a=fa[a][k];
}
}
if(a==b) return a;
for(int k=M-1;k>=0;k--){//注意这里的M-1(第3/3处)
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}

void pushup(Tree& p, Tree& l, Tree& r) {
if(l.cnt >= r.cnt) {
p.idx = l.idx;
}else{
p.idx = r.idx;
}
p.cnt = max(l.cnt, r.cnt);
}
void pushup(int u) {
pushup(tr[u], tr[tr[u].ls], tr[tr[u].rs]);
}

void modify(int& u, int l, int r, int x, int d) {
if(!u) u = ++tridx;
if(l == r) {
tr[u].cnt += d;
tr[u].idx = x;
return;
}
int mid = (l + r) / 2;
if(x <= mid) modify(tr[u].ls, l, mid, x, d);
else modify(tr[u].rs, mid + 1, r, x, d);
pushup(u);
}
void merge(int &p, int q, int l, int r) {
if(!p || !q) {
p += q;
return;
}
if(l == r) {
tr[p].cnt += tr[q].cnt;
}else{
int mid = (l + r) / 2;
merge(tr[p].ls, tr[q].ls, l, mid);
merge(tr[p].rs, tr[q].rs, mid + 1, r);
pushup(p);
}
}
int ans[N];
void dfs1(int u, int father) {
for(auto v: adj[u]) {
if(v == father) continue;
dfs1(v, u);
merge(rt[u], rt[v], 0, V);
}
ans[u] = tr[rt[u]].idx;
}

void solve(){
cin >> n >> m;
adj.assign(n + 1, vector<int>());
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs(1);
// modify(rt[5], 0, V, 2, 1);
// cout << tr[rt[5]].cnt << '\n';
// return;
while(m--) {
int x, y, z;
cin >> x >> y >> z;
int p = lca(x, y);
modify(rt[x], 0, V, z, 1);
modify(rt[y], 0, V, z, 1);
modify(rt[p], 0, V, z, -1);
if(p != 1) {
modify(rt[fa[p][0]], 0, V, z, -1);
}
}
dfs1(1, -1);
for(int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}
可持久化线段树(主席树)

求区间第k小数(静态)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
bool multi=0;
const int N = 1e5 + 10;
int n, m;
int a[N];
vector<int> nums;
struct Node{
int l, r;
int cnt;
}tr[N * 4 + N * 17];
int root[N], idx;
int build(int l, int r){
int p = ++idx;
if(l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid),tr[p].r = build(mid + 1, r);
return p;
}
int find(int x){
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int insert(int p, int l, int r, int x){
int q = ++ idx;
tr[q] = tr[p];
if(l == r){
tr[q].cnt ++;
return q;
}
int mid = l + r >> 1;
if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[q].r, mid + 1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
int query(int q, int p, int l, int r, int k){
if(l == r) return r;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if(k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
root[0] = build(0, nums.size() - 1);
for(int i = 1; i <= n; i++){
root[i] = insert(root[i-1], 0, nums.size() - 1, find(a[i]));
}
while(m -- ){
int l, r, k;
cin >> l >> r >> k;
cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << '\n';
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}
return 0;
}
线段树套线段树

矩阵查最值

封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
struct SegmentTree2d{

int Vx, Vy;

struct Info {
int mx = -1;
friend Info operator+(Info a, Info b) {
return {max(a.mx, b.mx)};
}
};

struct Tree {
int l = 0, r = 0;
Info info;
}tr[1000000];
int root1 = 0, idx = 0;
int root[1000000];

void init(int Vx_, int Vy_) {
Vx = Vx_, Vy = Vy_;
for(int i = 1; i <= idx; i++) {
root[i] = 0;
tr[i] = Tree();
}
root1 = idx = 0;
}

void cgy(int &u, int y1, int y2, int y3, Info info) {
if(!u) u = ++idx;
if(y1 == y2) {
tr[u].info = tr[u].info + info;
return;
}
int mid = (y1 + y2) / 2;
if(y3 <= mid) {
cgy(tr[u].l, y1, mid, y3, info);
}else{
cgy(tr[u].r, mid + 1, y2, y3, info);
}
tr[u].info = tr[tr[u].l].info + tr[tr[u].r].info;
}

void cgx(int &u, int x1, int x2, int y1, int y2, int x3, int y3, Info info) {
if(!u) u = ++idx;
cgy(root[u], y1, y2, y3, info);
if(x1 == x2) return;
int mid = (x1 + x2) / 2;
if(x3 <= mid) {
cgx(tr[u].l, x1, mid, y1, y2, x3, y3, info);
}else{
cgx(tr[u].r, mid + 1, x2, y1, y2, x3, y3, info);
}
}

Info queryy(int u, int y1, int y2, int qy1, int qy2) {
if(!u) return Info();
if(qy1 <= y1 && y2 <= qy2) return tr[u].info;
int mid = (y1 + y2) / 2;
Info res;
if(qy1 <= mid) {
Info tmp = queryy(tr[u].l, y1, mid, qy1, qy2);
res = res + tmp;
}
if(qy2 > mid) {
Info tmp = queryy(tr[u].r, mid + 1, y2, qy1, qy2);
res = res + tmp;
}
return res;
}

Info queryx(int u, int x1, int x2, int y1, int y2, int qx1, int qx2, int qy1, int qy2) {
if(!u) return Info();
if(qx1 <= x1 && x2 <= qx2) return queryy(root[u], y1, y2, qy1, qy2);
int mid = (x1 + x2) / 2;
Info res;
if(qx1 <= mid) {
Info tmp = queryx(tr[u].l, x1, mid, y1, y2, qx1, qx2, qy1, qy2);
res = res + tmp;
}
if(qx2 > mid) {
Info tmp = queryx(tr[u].r, mid + 1, x2, y1, y2, qx1, qx2, qy1, qy2);
res = res + tmp;
}
return res;
}

Info query(int qx1, int qx2, int qy1, int qy2) {
return queryx(root1, 1, Vx, 1, Vy, qx1, qx2, qy1, qy2);
}

void modify(int x, int y, Info info) {
cgx(root1, 1, Vx, 1, Vy, x, y, info);
}
}tr;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;

const int N = 100000 * 40;
int n, m;
struct Node {
int l, r, v;
}g[100005];

struct Info {
int mx = -INF, mn = INF;
};

struct Tree {
int l, r, mx = -INF, mn = INF;
}t1[N], t2[N]; //N * logV
int root1, root[N], idx1, idx2;

void cgy(int &u, int L, int R, int i) {
if(!u) u = ++idx2;
if(L == R) {
t2[u].mx = max(t2[u].mx, g[i].v);
t2[u].mn = min(t2[u].mn, g[i].v);
return;
}
int MID = (L + R) / 2;
if(g[i].r <= MID) {
cgy(t2[u].l, L, MID, i);
}else{
cgy(t2[u].r, MID + 1, R, i);
}
t2[u].mx = max(t2[t2[u].l].mx, t2[t2[u].r].mx);
t2[u].mn = min(t2[t2[u].l].mn, t2[t2[u].r].mn);
}

void cgx(int &u, int L, int R, int i) {
if(!u) u = ++idx1;
cgy(root[u], 1, 3000, i);
if(L == R) return;
int MID = (L + R) / 2;
if(g[i].l <= MID) {
cgx(t1[u].l, L, MID, i);
}else{
cgx(t1[u].r, MID + 1, R, i);
}
}

Info queryy(int u, int L, int R, int qly, int qry) {
if(!u) return Info();
if(qly <= L && R <= qry) return {t2[u].mx, t2[u].mn};
int MID = (L + R) / 2;
Info res;
if(qly <= MID) {
Info tmp = queryy(t2[u].l, L, MID, qly, qry);
res = {max(res.mx, tmp.mx), min(res.mn, tmp.mn)};
}
if(qry > MID) {
Info tmp = queryy(t2[u].r, MID + 1, R, qly, qry);
res = {max(res.mx, tmp.mx), min(res.mn, tmp.mn)};
}
return res;
}

Info queryx(int u, int L, int R, int qlx, int qrx, int qly, int qry) {
if(!u) return Info();
if(qlx <= L && R <= qrx) return queryy(root[u], 1, 3000, qly, qry);
int MID = (L + R) / 2;
Info res;
if(qlx <= MID) {
Info tmp = queryx(t1[u].l, L, MID, qlx, qrx, qly, qry);
res = {max(res.mx, tmp.mx), min(res.mn, tmp.mn)};
}
if(qrx > MID) {
Info tmp = queryx(t1[u].r, MID + 1, R, qlx, qrx, qly, qry);
res = {max(res.mx, tmp.mx), min(res.mn, tmp.mn)};
}
return res;
}

void solve(){
cout << 500000 * log2(5e5) * log2(5e5) << '\n';
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> g[i].l >> g[i].r >> g[i].v;
cgx(root1, 1, 3000, i);
}
int last = 0;
for(int i = 1; i <= m; i++) {
int op;
cin >> op;
if(op == 1) {
cin >> g[i].l >> g[i].r >> g[i].v;
g[i].l ^= last, g[i].r ^= last;
cgx(root1, 1, 3000, i);
}else{
int ql, qr;
cin >> ql >> qr;
ql ^= last, qr ^= last;
Info val = queryx(root1, 1, 3000, ql, qr, ql, qr);
last = val.mx - val.mn;
if(abs(last) > INF) {
last = 0;
}
cout << last << '\n';
}
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

splay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 0;

const int N = 5e5 + 10, INF = 1e9;

int n, m;
struct Node {
int s[2], p, v;
int rev, same;
int size, sum, ms, ls, rs;

void init(int _v, int _p) {
s[0] = s[1] = 0, p = _p, v = _v;
rev = same = 0;
size = 1, sum = ms = v;
ls = rs = max(v, 0LL);
}
}tr[N];
int root, nodes[N], tt;
int w[N];

void pushup(int x) {
auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
u.size = l.size + r.size + 1;
u.sum = l.sum + r.sum + u.v;
u.ls = max(l.ls, l.sum + u.v + r.ls);
u.rs = max(r.rs, r.sum + u.v + l.rs);
u.ms = max(max(l.ms, r.ms), l.rs + u.v + r.ls);
}

void pushdown(int x){
auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
if (u.same)
{
u.same = u.rev = 0;
if (u.s[0]) l.same = 1, l.v = u.v, l.sum = l.v * l.size;
if (u.s[1]) r.same = 1, r.v = u.v, r.sum = r.v * r.size;
if (u.v > 0)
{
if (u.s[0]) l.ms = l.ls = l.rs = l.sum;
if (u.s[1]) r.ms = r.ls = r.rs = r.sum;
}
else
{
if (u.s[0]) l.ms = l.v, l.ls = l.rs = 0;
if (u.s[1]) r.ms = r.v, r.ls = r.rs = 0;
}
}
else if (u.rev)
{
u.rev = 0, l.rev ^= 1, r.rev ^= 1;
swap(l.ls, l.rs), swap(r.ls, r.rs);
swap(l.s[0], l.s[1]), swap(r.s[0], r.s[1]);
}
}

void rotate(int x) {
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}

void splay(int x, int k) {
while (tr[x].p != k)
{
int y = tr[x].p, z = tr[y].p;
if (z != k)
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
if (!k) root = x;
}

int kth(int k) {
int u = root;
while (u)
{
pushdown(u);
if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
else if (tr[tr[u].s[0]].size + 1 == k) return u;
else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
}
return -1;
}

int build(int l, int r, int p) {
int mid = l + r >> 1;
int u = nodes[tt -- ];
tr[u].init(w[mid], p);
if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
if (mid < r) tr[u].s[1] = build(mid + 1, r, u);
pushup(u);
return u;
}

int build(int l, int r, int p) {
// int mid = l + r >> 1;
// int u = ++idx;
// tr[u].init(mid, p);
// if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
// if (mid < r) tr[u].s[1] = build(mid + 1, r, u);
// push_up(u);
// return u;
// }

void dfs(int u) {
if(tr[u].s[0]) dfs(tr[u].s[0]);
if(tr[u].s[1]) dfs(tr[u].s[1]);
nodes[++tt] = u;
}

void solve() {
for(int i = 1; i < N; i++) nodes[++tt] = i;
cin >> n >> m;
tr[0].ms = w[0] = w[n + 1] = -INF;
for(int i = 1; i <= n; i++) cin >> w[i];
root = build(0, n + 1, 0);
string op;
while(m--) {
cin >> op;
if(op == "INSERT") {//插入一个序列
int posi, tot;
cin >> posi >> tot;
for(int i = 0; i < tot; i++) cin >> w[i];
int l = kth(posi + 1), r = kth(posi + 2);
splay(l, 0), splay(r, l);
int u = build(0, tot - 1, r);
tr[r].s[0] = u;
pushup(r), pushup(l);
}else if(op == "DELETE") {//删除一段区间
int posi, tot;
cin >> posi >> tot;
int l = kth(posi), r = kth(posi + tot + 1);
splay(l, 0), splay(r, l);
dfs(tr[r].s[0]);
tr[r].s[0] = 0;
pushup(r), pushup(l);
}else if(op == "MAKE-SAME") {//整体修改为一个树
int posi, tot, c;
cin >> posi >> tot >> c;
int l = kth(posi), r = kth(posi + tot + 1);
splay(l, 0), splay(r, l);
auto &son = tr[tr[r].s[0]];
son.same = 1, son.v = c, son.sum = c * son.size;
if(c > 0) son.ms = son.ls = son.rs = son.sum;
else son.ms = c, son.ls = son.rs = 0;
pushup(r), pushup(l);
}else if(op == "REVERSE") {//翻转区间
int posi, tot;
cin >> posi >> tot;
int l = kth(posi), r = kth(posi + tot + 1);
splay(l, 0), splay(r, l);
auto &son = tr[tr[r].s[0]];
son.rev ^= 1;
swap(son.ls, son.rs);
swap(son.s[0], son.s[1]);
pushup(r), pushup(l);
}else if(op == "GET-SUM") {//区间求和
int posi, tot;
cin >> posi >> tot;
int l = kth(posi), r = kth(posi + tot + 1);
splay(l, 0), splay(r, l);
cout << tr[tr[r].s[0]].sum << '\n';
}else cout << tr[root].ms << '\n';//求总的最大子段和
}
}

signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

树链剖分

树剖+线段树

给定一棵树,树中包含 n 个节点(编号 1∼n),其中第 i 个节点的权值为 ai。

初始时,11 号节点为树的根节点。

现在要对该树进行 m 次操作,操作分为以下 44 种类型:

  • 1 u v k,修改路径上节点权值,将节点 u 和节点 v 之间路径上的所有节点(包括这两个节点)的权值增加 k。
  • 2 u k,修改子树上节点权值,将以节点 u 为根的子树上的所有节点的权值增加 k。
  • 3 u v,询问路径,询问节点 u 和节点 v 之间路径上的所有节点(包括这两个节点)的权值和。
  • 4 u,询问子树,询问以节点 u 为根的子树上的所有节点的权值和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;
const int N=1e5+10;
int n,m;
int w[N];
vector<vector<int>> edge;
int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N];

struct Tr{
int l,r;
int add,sum;
}tr[N*4];

void dfs1(int u,int father,int depth){
dep[u]=depth,fa[u]=father,sz[u]=1;
for(auto v:edge[u]){
if(v==father) continue;
dfs1(v,u,depth+1);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}

void dfs2(int u,int t){
id[u]=++cnt,nw[cnt]=w[u],top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(auto v:edge[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}

void pushup(int u){
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u){
auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.add){
left.add+=root.add,left.sum+=root.add*(left.r-left.l+1);
right.add+=root.add,right.sum+=root.add*(right.r-right.l+1);
root.add=0;
}
}

void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,0,nw[r]};
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}

void update(int u,int l,int r,int k){
if(l<=tr[u].l&&r>=tr[u].r){
tr[u].add+=k;
tr[u].sum+=k*(tr[u].r-tr[u].l+1);
return;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) update(u<<1,l,r,k);
if(r>mid) update(u<<1|1,l,r,k);
pushup(u);
}

void update_tree(int u,int k){
update(1,id[u],id[u]+sz[u]-1,k);
}

void update_path(int u,int v,int k){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(1,id[top[u]],id[u],k);
u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
update(1,id[v],id[u],k);
}

int query(int u,int l,int r){
if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid) res+=query(u<<1,l,r);
if(r>mid) res+=query(u<<1|1,l,r);
return res;
}

int query_path(int u,int v){
int res=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=query(1,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
res+=query(1,id[v],id[u]);
return res;
}

int query_tree(int u){
return query(1,id[u],id[u]+sz[u]-1);
}

void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
edge.resize(n+1);
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
dfs1(1,-1,1);
dfs2(1,1);
build(1,1,n);
cin>>m;
while(m--){
int t,u,v,k;
cin>>t>>u;
if(t==1){
cin>>v>>k;
update_path(u,v,k);
}else if(t==2){
cin>>k;
update_tree(u,k);
}else if(t==3){
cin>>v;
cout<<query_path(u,v)<<endl;
}else{
cout<<query_tree(u)<<endl;
}
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT=1;
if(multi) cin>>TTT;
while(TTT--){
solve();
}

return 0;
}

珂朵莉树(ODT)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
struct ODT{
int l,r;
mutable int v;
bool operator<(const ODT &x) const{
return l<x.l;
}
ODT(int L,int R,int V):l(L),r(R),v(V){};
};
set<ODT> s;
//将包含pos的区间分开成l到pos-1和pos到r
auto split(int pos) {
auto it=s.lower_bound(ODT(pos,0,0));
if(it!=s.end()&&it->l==pos) return it;
it--;
int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert(ODT(l,pos-1,v));
return s.insert(ODT(pos,r,v)).first;
}
//将l到r赋值为v
void assign(int l,int r,int v){
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(ODT(l,r,v));
}
//l到r区间加x
void add(int l,int r,int x){
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++){
it->v+=x;
}
}
//求从l到r的和
int sum(int l,int r){
int res=0;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++){
res+=(it->v)*(it->r-it->l+1);
}
return res;
}
//求从l到r的第k大数
int kth(int l, int r, int k) {
auto itr=split(r+1),itl=split(l);
vector<pair<int,int>> v;
for(auto it=itl;it!=itr;it++){
v.push_back({it->v, it->r - it->l + 1});
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++){
if(k <= v[i].second) return v[i].first;
k -= v[i].second;
}
return -1;
}
//a ^ b mod p
long long qpow(long long a,long long b,long long p){
a%=p;
long long res=1%p;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
//求从l到r的平方和
int calc(int l, int r, int x, int mod) {
int ans = 0;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++){
ans = (ans + qpow(it->v, x, mod) * (it->r - it->l + 1)) % mod;
}
return ans;
}

树上启发式合并(dsu on tree)

例题:Lomsat gelral

树的节点有颜色$c_i$,一种颜色占领了一个子树,当且仅当没有其他颜色在这个子树中出现得比它多(可能有多个)。求占领每个子树的所有颜色之和。

核心:先求每个轻儿子所在子树的信息每次求完清空,最后求重儿子所在子树求完不清空回溯到当前结点时保留这个重儿子所在子树的颜色信息,然后再累加上每个轻儿子所在子树的信息。

时间复杂度$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi = 0;

const int N = 1e5 + 10;
int n;
int c[N], son[N], sz[N];
int sum, mx, cnt[N], ans[N];
vector<vector<int>> adj;

void dfs_son(int u, int father) {
sz[u] = 1;
for(auto v: adj[u]) {
if(v == father) continue;
dfs_son(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}

void update(int u, int father, int sgn, int pson) {
cnt[c[u]] += sgn;
if(cnt[c[u]] > mx) mx = cnt[c[u]], sum = c[u];
else if(cnt[c[u]] == mx) sum += c[u];

for(auto v: adj[u]) {
if(v == father || v == pson) continue;
update(v, u, sgn, pson);
}

}

void dfs(int u, int father, int op) {
for(auto v: adj[u]) {
if(v == father || v == son[u]) continue;
dfs(v, u, 0);
}
if(son[u]) dfs(son[u], u, 1);
update(u, father, 1, son[u]);
ans[u] = sum;
if(!op) update(u, father, -1, 0), sum = mx = 0;
}

void solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
adj.assign(n + 1, vector<int>());
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs_son(1, -1);
dfs(1, -1, 1);
for(int i = 1; i <= n; i++) {
cout << ans[i] << " \n" [i == n];
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

ST表(RMQ问题)

求区间最大/ 小数

时间复杂度:预处理O($nlogn$) 在线查找O($1$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//N为原数组个数,M为log2(N),一般多开2个,开成log2(N)+2
template<class T>
struct RMQ{
vector<vector<T>> f;
RMQ(int n, T w[]):f(n+1,vector<T>(log2(n)+2)){
int t=log2(n)+2;
for(int j=0;j<t;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(!j){
f[i][j]=w[i];
}else{
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
}
}
T query(int l,int r){
int len=r-l+1;
int k=log2(len);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
};
RMQ<int> rmq(n,a);
rmq.query(l,r);
//注意:原数组要从1开始存储
//区间[a,b]的最大/小值:query(a,b)

维护区间最大次大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, H = 20;
int f[N][H], f1[N][H], l[N][H], r[N][H];
void init(int n) {
for (int j = 1; j < H; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int t = i + (1 << (j - 1)), fl = f[i][j - 1], fr = f[t][j - 1];
f[i][j] = max(fl, fr);
if (fl == fr) l[i][j] = l[i][j - 1], r[i][j] = r[t][j - 1];
else if (fl > fr) l[i][j] = l[i][j - 1], r[i][j] = r[i][j - 1];
else l[i][j] = l[t][j - 1], r[i][j] = r[t][j - 1];
f1[i][j] = max(f1[i][j - 1], f1[t][j - 1]);
if (fl != fr) f1[i][j] = max(f1[i][j], min(fl, fr));
}
}
}
typedef pair<int, int> pii;
pii qry(int x, int y) {
int t = log2(y - x + 1), tt = y - (1 << t) + 1, fl = f[x][t], fr = f[tt][t];
int max1 = max(fl, fr), max2 = max(f1[x][t], f1[tt][t]);
if (fl != fr) max2 = max(max2, min(fl, fr));
bool mul_max1 = 0;
if (fl == fr) mul_max1 = l[x][t] != r[tt][t];
else if (fl > fr) mul_max1 = l[x][t] != r[x][t];
else mul_max1 = l[tt][t] != r[tt][t];
if (mul_max1) max2 = max1;
return {max1, max2};
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> f[i][0], l[i][0] = r[i][0] = i;
init(n);
while (q--) {
int x, y; cin >> x >> y;
pii t = qry(x, y); cout << t.first << ' ' << t.second << '\n';
}
return 0;
}

扫描线

矩形面积并

  • 线段树(时间复杂度)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 0;
int T = 1;

const int N = 1e5 + 10;
int n;
struct Seg{
double x, y1, y2;
int k;
bool operator<(const Seg &w) const{
return x < w.x;
}
}seg[N * 2];

struct Node{
int l, r;
int cnt;
double len;
}tr[N * 8];
vector<double> ys;

int find(double y)
{
return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void build(int u, int l, int r) {
tr[u]={l, r, 0, 0};
if(l != r) {
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}

void pushup(int u) {
if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
else if(tr[u].l != tr[u].r) {
tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}else tr[u].len = 0;
}

void modify(int u, int l, int r, int k)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].cnt += k;
pushup(u);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
pushup(u);
}
}

void solve() {
cout << "Test case #" << T << '\n';
cout << "Total explored area: ";
ys.clear();
int m = 0;
for(int i = 0; i < n; i++) {
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
seg[m++] = {x1, y1, y2, 1};
seg[m++] = {x2, y1, y2, -1};
ys.push_back(y1), ys.push_back(y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
build(1, 0, ys.size() - 2);
sort(seg, seg + m);
double res = 0;
for(int i = 0; i < m; i++) {
if(i) res += tr[1].len * (seg[i].x -seg[i - 1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
}
cout << fixed << setprecision(2) << res << "\n\n";
}

signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while(cin >> n, n){
solve();
T++;
}

return 0;
}
  • 计算几何(时间复杂度)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 0;

const int N = 1010;
int n;
struct Point{
int x,y;
bool operator<(const Point &B) const{
return x<B.x||x==B.x&&y<B.y;
}
}l[N], r[N], q[N];
vector<int> xs;

ll range_area(int a, int b) {
int cnt = 0;
for(int i = 0; i < n; i++)
if(l[i].x <= a && r[i].x >= b)
q[cnt++] = {l[i].y, r[i].y};
if(!cnt) return 0;
sort(q, q + cnt);
ll res = 0;
int st = q[0].x, ed = q[0].y;
for(int i = 1; i < cnt; i++) {
if(q[i].x <= ed) ed = max(ed, q[i].y);
else{
res += ed - st;
st = q[i].x, ed = q[i].y;
}
}
res += ed - st;
return res * (b - a);
}

void solve() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> l[i].x >> l[i].y >> r[i].x >> r[i].y;
xs.push_back(l[i].x); xs.push_back(r[i].x);
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
ll res = 0;
for(int i = 0; i + 1 < xs.size(); i++) {
res += range_area(xs[i], xs[i + 1]);
}
cout << res << '\n';
}

signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

二维数点

二位前缀和思想+树状数组(离线)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int tr[N], ans[N];
struct Node {
int x, y, sgn, id;
bool operator<(const Node &w) const{
return x < w.x;
}
};
inline int lowbit(int x){
return x&-x;
}
void add(int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=c;
}
}
int presum(int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
vector<Node> op;
vector<PII> p;//被数点
void insert_op(int x1, int y1, int x2, int y2, int id) {//存入所有[x1,y1,x2,y2]的矩形
op.push_back((Node){x2, y2, 1, id});
op.push_back((Node){x1 - 1, y1 - 1, 1, id});
op.push_back((Node){x1 - 1, y2, -1, id});
op.push_back((Node){x2, y1 - 1, -1, id});
}
void count_point() {
sort(p.begin(), p.end());
sort(op.begin(), op.end());
int cur = 0;
for(auto [x, y, sgn, id]: op) {
while(cur < (int)p.size() && p[cur].first <= x) add(p[cur++].second, 1);
ans[id] += sgn * presum(y);
// cout << x << ' ' << y << ' ' << sgn * presum(y) << '\n';
}
}

图论

建图优化

线段树建图优化

例题:n个点,m条边,s是起点,问点s到点1~n的最短距离

有三种边:接下来的 q 行表示 q 种方案。

  • 输入 1 v u w 表示第一种方案,从v向u连边,权值为w
  • 输入 2 v l r w 表示第二种方案,从v向$[l,r]$区间连边,权值为w
  • 输入 3 v l r w 表示第三种方案,从$[l,r]$区间向v连边,权值为w

这里的线段树实际上有两个,分别为u和u+D,左树从上往下,右数从下往上,区间向点连边从右树结点连出,点向区间连入到左树结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// Problem: B. Legacy
// Contest: Codeforces - Codeforces Round 406 (Div. 1)
// URL: https://codeforces.com/contest/786/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 0;

const int N = 1e5 + 10, M = 1e6 + 10, D = 5e5;

int n, m, s;

struct Node{
int l, r;
}tr[N * 4];
vector<pair<int, int>> g[M];
int dist[M], leaf[M];

inline void build(int u, int l, int r) {
tr[u] = {l, r};
if(l == r) {
leaf[l] = u;
return;
}
int mid = (l + r) / 2;
g[u].push_back({u << 1, 0});
g[u].push_back({u << 1 | 1, 0});
g[(u << 1) + D].push_back({u + D, 0});
g[(u << 1 | 1) + D].push_back({u + D, 0});
build(u << 1, l, mid),build(u << 1 | 1, mid + 1, r);
}

inline void connect(int u, int l, int r, int v, int w, int op) {
if(l <= tr[u].l && tr[u].r <= r) {
if(op) g[u + D].push_back({v, w});
else g[v].push_back({u, w});
return;
}
int mid = (tr[u].l + tr[u].r) / 2;
if(l <= mid) connect(u << 1, l, r, v, w, op);
if(r > mid) connect(u << 1 | 1, l, r, v, w, op);
}

void dijkstra(){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
heap.push({0, leaf[s]});
memset(dist, 0x3f, sizeof dist);
dist[leaf[s]] = 0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int u = t.second, distance = t.first;
if(dist[u]<distance) continue;
for(auto it:g[u]){
int v=it.first,w=it.second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
heap.push({dist[v], v});
}
}
}
}

void solve() {
cin >> n >> m >> s;
build(1, 1, n);
for(int i = 0; i < m; i++) {
int op;
cin >> op;
if(op == 1) {
int u, v, w;
cin >> u >> v >> w;
g[leaf[u]].push_back({leaf[v], w});
} else {
int v, l, r, w;
cin >> v >> l >> r >> w;
connect(1, l, r, leaf[v], w, op % 2);
}
}
for(int i = 1; i <= n; i++) {
g[leaf[i]].push_back({leaf[i] + D, 0}),g[leaf[i] + D].push_back({leaf[i], 0});
}
dijkstra();
for(int i = 1; i <= n; i++) {
if(dist[leaf[i]] == 0x3f3f3f3f3f3f3f3f) cout << -1 << " \n" [i == n];
else cout << dist[leaf[i]] << " \n" [i == n];
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

前后缀建图优化

例题:以2-SAT为背景。你有 n 张卡片,第 i 张卡片正面写着一个数字 ai,反面写着一个数字 bi,现在你可以摆放卡片(规定每张卡片朝上的面),询问是否存在一种摆放方式,使得任意两张不同的卡片朝上面所写的数字都是互质的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Problem: F - Coprime Solitaire
// Contest: AtCoder - AtCoder Beginner Contest 210
// URL: https://atcoder.jp/contests/abc210/tasks/abc210_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

bool multi = 0;

bool st[2000005],ispr[2000005];
int prime[2000005],pcnt;
void get_primes(int n){
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[pcnt++]=i;
for(int j=0;prime[j]<=n/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}

int n;
int a[30005], b[30005];

vector<int> v[2000005];
int nw;

const int N = 20000005, M = 20000005;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts, stk[N], top;
int id[N], cnt;
bool ins[N];

void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
dfn[u] = low[u] = ++ ts;
stk[++top] = u, ins[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(ins[j]) low[u] = min(low[u], dfn[j]);
}
if(low[u] == dfn[u]) {
int y;
cnt++;
do {
y = stk[top--], ins[y] = false, id[y] = cnt;
}while(y != u);
}
}

int nt(int x) {
return x > n ? x - n : x + n;
}

void solve() {
memset(h, -1, sizeof h);
get_primes(2000002);
for(int i = 0; i < pcnt; i++) {
ispr[prime[i]] = true;
}
cin >> n;
nw = n * 2;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= a[i] / j; j++) {
if(a[i] % j == 0) {
if(ispr[j]) v[j].push_back(i);
else if(ispr[a[i] / j]) v[a[i] / j].push_back(i);
}
}
for(int j = 1; j <= b[i] / j; j++) {
if(b[i] % j == 0) {
if(ispr[j]) v[j].push_back(i + n);
else if(ispr[b[i] / j]) v[b[i] / j].push_back(i + n);
}
}
}

for(int i = 1; i <= 2000000; i++) {
for(int j = 0; j < v[i].size(); j++) {
++nw;
add(nw, nt(v[i][j]));
if(j) add(v[i][j], nw - 1), add(nw, nw - 1);
}
for(int j = (int)v[i].size() - 1; j >= 0; j--) {
++nw;
add(nw, nt(v[i][j]));
if(j < (int)v[i].size() - 1) add(v[i][j], nw - 1), add(nw, nw - 1);
}
}
for(int i = 1; i <= n * 2; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for(int i = 1; i <= n; i++) {
// cout << id[i] << ' ' << id[i + n] << '\n';
if(id[i] == id[i + n]) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

树链剖分+线段树优化建图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

bool multi = 0;

const int N = 1e5 + 10, M = 8e5 + 10, D = 4e5;

int n, m, s;

struct Node{
int l, r;
}tr[N * 4];
vector<int> edge[M];
vector<pair<int, int>> g[M];
int dist[M], leaf[N];

inline void build(int u, int l, int r) {
tr[u] = {l, r};
if(l == r) {
leaf[l] = u;
return;
}
int mid = (l + r) / 2;
g[u].push_back({u << 1, 0});
g[u].push_back({u << 1 | 1, 0});
g[(u << 1) + D].push_back({u + D, 0});
g[(u << 1 | 1) + D].push_back({u + D, 0});
build(u << 1, l, mid),build(u << 1 | 1, mid + 1, r);
}

inline void connect(int u, int l, int r, int v, int w, int op) {
if(l <= tr[u].l && tr[u].r <= r) {
if(op) g[u + D].push_back({v, w});
else g[v].push_back({u, w});
return;
}
int mid = (tr[u].l + tr[u].r) / 2;
if(l <= mid) connect(u << 1, l, r, v, w, op);
if(r > mid) connect(u << 1 | 1, l, r, v, w, op);
}

void dijkstra(){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
heap.push({0, leaf[s]});
memset(dist, 0x3f, sizeof dist);
dist[leaf[s]] = 0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int u = t.second, distance = t.first;
if(dist[u]<distance) continue;
for(auto it:g[u]){
int v=it.first,w=it.second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
heap.push({dist[v], v});
}
}
}
}

int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N];

void dfs1(int u,int father,int depth){
dep[u]=depth,fa[u]=father,sz[u]=1;
for(auto v:edge[u]){
if(v==father) continue;
dfs1(v,u,depth+1);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}

void dfs2(int u,int t){
id[u]=++cnt,top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(auto v:edge[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}

void update_path(int u,int v,int a){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
connect(1, id[top[u]], id[u], leaf[id[a]], 1, 0);
u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
connect(1, id[v], id[u], leaf[id[a]], 1, 0);
}

void solve() {
cin >> n >> m;
// exit(0);
for(int i = 2; i <= n; i++) {
int x;
cin >> x;
edge[x].push_back(i);
edge[i].push_back(x);
}
dfs1(1,-1,1);
dfs2(1,1);
build(1, 1, n);
for(int i = 1; i <= n; i++) {
g[leaf[i]].push_back({leaf[i] + D, 0}),g[leaf[i] + D].push_back({leaf[i], 0});
}
while(m--) {
int u, v;
cin >> u >> v;
update_path(u, v, u);
update_path(u, v, v);
}
s = id[1];
dijkstra();
for(int i = 2; i <= n; i++) {
if(dist[leaf[id[i]]] == 0x3f3f3f3f) cout << -1 << " \n" [i == n];
else cout << dist[leaf[id[i]]] << " \n" [i == n];
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

tarjan

有向图的强连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int n,m;
const int N=1e5+10;
vector<vector<PII>> g,ng;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int dist[N];

void tarjan(int u){
dfn[u]=low[u]=++timestamp;
stk[++top]=u,in_stk[u]=true;

for(auto it:g[u]){
int v=it.first;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(in_stk[v]){
low[u]=min(low[u],dfn[v]);
}
}

if(dfn[u]==low[u]){
++scc_cnt;
int v;
do{
v=stk[top--];
in_stk[v]=false;
id[v]=scc_cnt;
sz[scc_cnt]++;
}while(v!=u);
}
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for(int i=1;i<=n;i++){
for(auto it:g[i]){
int j=it.first,w=it.second;
int a=id[i],b=id[j];
if(a!=b){
ng[a].push_back({b,w});
}
}
}

无向图的双连通分量

边的双连通分量

边的双连通分量:图中任意两不同点之间都有至少两条边不重复的路径。

求将无向图转化为边的双连通分量需要连接的最少边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
l#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;

const int N=5010,M=20010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u,int from){
dfn[u]=low[u]=++timestamp;
stk[++top]=u;

for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tarjan(j,i);
low[u]=min(low[u],low[j]);
if(dfn[u]<low[j]){
is_bridge[i]=is_bridge[i^1]=true;
}
}else if(i!=(from^1)){
low[u]=min(low[u],dfn[j]);
}
}

if(dfn[u]==low[u]){
++dcc_cnt;
int y;
do{
y=stk[top--];
id[y]=dcc_cnt;
}while(y!=u);
}
}

void solve(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}

tarjan(1,-1);

for(int i=0;i<idx;i++){
if(is_bridge[i])
d[id[e[i]]]++;
}

int cnt=0;
for(int i=1;i<=dcc_cnt;i++){
if(d[i]==1) cnt++;
}
cout<<(cnt+1)/2<<endl;
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT=1;
if(multi) cin>>TTT;
while(TTT--){
solve();
}

return 0;
}

点的双连通分量

点的双连通分量:图中任意两不同点之间都有至少两条点不重复的路径。

求将无向图转化为点的双连通分量需要连接的最少边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;
const int N=10010,M=30010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root,ans;

void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u){
dfn[u]=low[u]=++timestamp;

int cnt=0;
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]);
if(low[j]>=dfn[u]) cnt++;
}else low[u]=min(low[u],dfn[j]);
}

if(u!=root) cnt++;

ans=max(ans,cnt);
}

void solve(){
memset(dfn,0,sizeof dfn);
memset(h,-1,sizeof h);
idx=timestamp=0;

while(m--){
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}

ans=0;
int cnt=0;
for(root=0;root<n;root++){
if(!dfn[root]){
cnt++;
tarjan(root);
}
}
cout<<ans+cnt-1<<endl;
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT=1;
if(multi) cin>>TTT;
while(cin>>n>>m,n||m){
solve();
}

return 0;
}

拓扑序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<vector<int>> edge;
int d[N];//点的入度
vector<int> res;//存储拓扑序
void topsort(){//将拓扑序存入res中
queue<int> q;
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i);
res.push_back(i);
}
}
while(q.size()){
int t=q.front();
q.pop();
for(auto i:edge[t]){
d[i]--;
if(d[i]==0){
res.push_back(i);
q.push(i);
}
}
}
}
//读边时需要记录每个点的入度
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
d[b]++,edge[a].push_back(b);
}
topsort();

传递闭包

floyd算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i = 1; i <= n; i ++)//初始化
for(int j = 1; j <= n; j ++) d[i][j] = (i == j);

for(int i = 0; i < m; i ++){
int u, v;cin >> u >> v;
d[u][v] = 1;
}
void Floyd(){
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
if(d[i][k])
for(int j = 1; j <= n; j++)
if(d[k][j])
d[i][j] = 1;
}

最短路

Dijkstra(仅有正权边)

  • *朴素版本O($n^{2}$)
  • 稠密图常用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int g[N][N],dist[N];//
bool st[N];
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;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]=true;

for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
if(dist[n]==0x3f3f3f3f3f3f3f3f){//如果是int应该为0x3f3f3f3f
return -1;
}else{
return dist[n];
}
}
memset(g,0x3f,sizeof g);
//读入边
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
cout<<dijkstra()<<endl;
  • 堆优化版O($mlogn$)

  • 稀疏图常用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    vector<vector<pair<int,int>>> edge;
    int dist[N];
    int dijkstra(){
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    while(heap.size()){
    auto t=heap.top();
    heap.pop();
    int u = t.second, distance = t.first;
    if(dist[u]<distance) continue;
    for(auto it:edge[u]){
    int v=it.first,w=it.second;
    if(dist[v] > dist[u] + w){
    dist[v] = dist[u] + w;
    heap.push({dist[v], v});
    }
    }
    }
    if(dist[n] == 0x3f3f3f3f3f3f3f3f){
    return -1;
    }else{
    return dist[n];
    }
    }
    edge[a].push_back({b,c});
    cout<<disjkstra()<<endl;

Bellman-ford(存在负权边,有边数限制)

时间复杂度O(nm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n,m,k;
int dist[N],last[N];//N为结点数
struct Edge{
int a,b,c;
}edges[M];//M为边数
void bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(last,dist,sizeof dist);
for(int i=0;i<m;i++){
auto e=edges[i];
dist[e.b]=min(dist[e.b],last[e.a]+e.c);
}
}
}
for(int i=0;i<m;i++){
int x,y,z;cin>>x>>y>>z;
edge[i]={x,y,z};
}
bellman_ford();
如果dist[n]>0x3f3f3f3f/2,说明k步内不可达,反之可达,dist[n]即为最短路

Spfa(存在负权边,可判断负环)

时间复杂度最好O(n),最坏O(nm)

  • spfa求最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int dist[N];
bool st[N];//判断结点是否在队列中
vector<vector<PII>> edge;
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
st[1]=true;
while(q.size()){
int u=q.front();
q.pop();
st[u]=false;
for(auto it:edge[u]){
int v=it.first,w=it.second;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
if(!st[v]){
q.push(v);
st[v]=true;
}
}
}
}

return dist[n];
}
int t=spfa();
如果t==0x3f3f3f3f,说明不可达,反之不可达,t即为最短路
  • 判断负环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    int dist[N],cnt[N];//注意把dist[0]建成超级源点,
    bool st[N];
    bool spfa(){
    queue<int> q;//如果被数据卡TLE,可尝试换成stack
    //这步相当于建了一个分别连向1~n,边权为0的虚拟源点0
    for(int i=1;i<=n;i++){
    st[i]=true;
    q.push(i);
    }
    while(q.size()){
    int u=q.front();
    q.pop();
    st[u]=false;
    for(auto it:edge[u]){
    int v=it.first,w=it.second;
    if(dist[j]>dist[u]+w[i]){
    dist[j]=dist[u]+w[i];
    cnt[j]=cnt[u]+1;
    if(cnt[j]>=n) return true;
    if(!st[j]){
    q.push(j);
    st[j]=true;
    }
    }
    }
    }
    return false;
    }
    注意:建边
    if(spfa()) 存在负环
    else 不存在负环

Floyd(预处理出任意两边距离)

时间复杂度O($n^3$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int d[N][N];
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
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;
}
}
//读入边
int x,y,z;cin>>x>>y>>z;
d[x][y]=min(d[x][y],z);
floyd();
//[x][y]>INF/2,说明x不能到达y,反正最短路为d[x][y]

无向图求最小环(Floyd)

注意这里INF不能取0x3f3f3f3f3f3f3f3f,因为3*INF会爆long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 1e13;

bool multi = 0;

const int N = 110;
int n, m;
int dist[N][N], edge[N][N];

void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i != j) dist[i][j] = edge[i][j] = INF;
}
}
for(int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
dist[u][v] = dist[v][u] = edge[u][v] = edge[v][u] = min(dist[u][v], w);
}
int ans = INF;
for(int k = 1; k <= n; k++) {
for(int i = 1; i < k; i++) {
for(int j = i + 1; j < k; j++) {
ans = min(ans, dist[i][j] + edge[i][k] + edge[k][j]);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
if(ans == INF) {
cout << "No solution.\n";
}else{
cout << ans << '\n';
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

最小生成树

Prim算法

时间复杂度O($n^2$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int g[N][N];
int dist[N];
bool st[N];
int prim(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
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(dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;
res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
}
return res;
}
memset(g,0x3f,sizeof g);
//读入边
for(int i=0;i<m;i++){
int u,v,w;cin>>u>>v>>w;
g[u][v]=g[v][u]=min(g[u][v],w);
}
int t=prim();
如果prim()==0x3f3f3f3f,说明不能形成最小生成树,反之t即最小生成树

Kruskal算法

时间复杂度O($mlogm$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//N为最大结点数,M为最大边数
int fa[N],res;
struct Edge{
int a,b,w;
bool operator<(const Edge& E) const{
return w<E.w;
}
}edge[M];
int find(x){
if(fa[x]!=x) return fa[x]=find(fa[x]);
return fa[x];
}
void kruskal(){
for(int i=0;i<m;i++){
int pa=find(edg[i].a),pb=find(edg[i].b);
if(pa!=pb){
cnt++;
res+=edg[i].w;
p[pa]=pb;
}
}
}
//用并查集记得初始化fa数组
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=0;i<m;i++){
int a,b,w;cin>>a>>b>>w;
edge[i]={a,b,w};
}
sort(edge,edge+m);
kruskal();
if(cnt<n-1) 说明不能形成最小生成树
else res是最小生成树

Kruskal重构树

性质:原图中的两点u、v在Kruskal重构树上的LCA的点权是原图中u到v的所有路径中最大边的最小值(从小到大排序边)(最小边的最大值,从大到小排序边)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi = 0;

const int N = 1e5 + 10, M = 3e5 + 10, INF = 1e18;
const int LOG = 19;
int n, m, q;
int p[N * 2], depth[N * 2], fa[N * 2][LOG];
int w[N * 2];
struct Node {
int a, b, c;
bool operator<(const Node &w) const{
return c > w.c;
}
}G[M];

vector<vector<int>> adj;

void bfs(int stt) {
queue<int> q;
q.push(stt);
depth[stt] = 1;
while(q.size()) {
int u = q.front();
q.pop();
for(auto v: adj[u]) {
if(depth[v] > depth[u] + 1) {
depth[v] = depth[u] + 1;
q.push(v);
fa[v][0] = u;
for(int k = 1; k < LOG; k++) {
fa[v][k] = fa[fa[v][k - 1]][k - 1];
}
}
}
}
}

int lca(int a, int b) {
if(depth[a] < depth[b]) swap(a, b);
for(int k = LOG - 1; k >= 0; k--) {
if(depth[fa[a][k]] >= depth[b]) {
a = fa[a][k];
}
}
if(a == b) return a;
for(int k = LOG - 1; k >= 0; k--) {
if(fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}

inline int find(int x) {
if(p[x] != x) return p[x] = find(p[x]);
return p[x];
}

void solve(){
cin >> n >> m >> q;
adj.resize(n * 2);
for(int i = 1; i <= n * 2; i++) {
p[i] = i;
depth[i] = INF;
}
for(int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
G[i] = {a, b, c};
}
sort(G, G + m);
int tot = n;
for(int i = 0; i < m; i++) {
int a = G[i].a, b = G[i].b, c = G[i].c;
int pa = find(a), pb = find(b);
if(pa != pb) {
p[pa] = p[pb] = ++tot;
w[tot] = c;
adj[tot].push_back(pa);
adj[tot].push_back(pb);
}
}

for(int i = 1; i <= tot; i++) {
if(p[i] == i && depth[i] == INF) {
bfs(i);
}
}

while(q--) {
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if(pa != pb) {
cout << -1 << '\n';
}else{
cout << w[lca(a, b)] << '\n';
}
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// Problem: G. Vlad and the Mountains
// Contest: Codeforces - Codeforces Round 888 (Div. 3)
// URL: https://codeforces.com/contest/1851/problem/G
// Memory Limit: 256 MB
// Time Limit: 5000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 1;

const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 4e5 + 10, M = 20;
int n, m;
int p[N];
struct Node{
int a, b, c;
bool operator<(const Node &w) const {
return c < w.c;
}
}G[N];
vector<vector<int>> adj;
int w[N];
int h[N];
int tot;
int depth[N], fa[N][20];

int find(int x) {
if(p[x] != x) return p[x] = find(p[x]);
return p[x];
}

void bfs(int root){
queue<int> q;
q.push(root);
depth[0]=0,depth[root]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto v:adj[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
for(int k=1;k<=M-1;k++){//注意这里的M-1(第1/3处)
fa[v][k]=fa[fa[v][k-1]][k-1];
}
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k=M-1;k>=0;k--){//注意这里的M-1(第2/3处)
if(depth[fa[a][k]]>=depth[b]){
a=fa[a][k];
}
}
if(a==b) return a;
for(int k=M-1;k>=0;k--){//注意这里的M-1(第3/3处)
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}

void solve() {
cin >> n >> m;
for(int i = 1; i < n * 2; i++) {
w[i] = 0;
depth[i] = INF;
for(int j = 0; j < M; j++) {
fa[i][j] = 0;
}
}
adj.clear();
adj.resize(n * 2);
for(int i = 1; i < n * 2; i++) p[i] = i;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 0; i < m; i++) {
cin >> G[i].a >> G[i].b;
G[i].c = max(h[G[i].a], h[G[i].b]);
}
tot = n;
sort(G, G + m);
for(int i = 0; i < m; i++) {
int a = G[i].a, b = G[i].b, c = G[i].c;
int pa = find(a), pb = find(b);
if(pa != pb) {

++tot;
p[pa] = p[pb] = tot;
w[tot] = c;
adj[tot].push_back(pa);
adj[tot].push_back(pb);
}
}
for(int i = 1; i <= tot; i++) {
if(p[i] == i && depth[i] == INF) {
bfs(i);
}
}
int q;
cin >> q;
while(q--) {
int a, b, e;
cin >> a >> b >> e;
if(find(a) != find(b) || w[lca(a, b)] > h[a] + e) {
cout << "NO\n";
}else{
cout << "YES\n";
}
}
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

二分图

二分图判定(染色法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int color[N];
vector<vector<int>> edge;//vector建图
bool dfs(int u, int c)
{
color[u] = c;
for (auto v:edge[u])
{
if (!color[v])
{
if (!dfs(v, 3 - c)) return false;
}
else if (color[v] == c) return false;
}
return true;
}

//遍历每个结点,分别对每一个为染色的点进行染色
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (!color[i])
{
if (!dfs(i, 1))
{
flag = false;
break;
}
}
if (flag) 给定图是二分图
else 给定图不是二分图

匈牙利算法(二分图的最大匹配)

必须从1开始计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int match[N];//match[i]表示左半部第i个结点匹配的右半部结点
bool st[N];//st[i]表示左半部点i是否已经匹配上
vector<vector<int>> adj;
bool find(int x){
for(auto v:adj[x]){
if(!st[v]){
st[v]=true;
if(!match[v]||find(match[v])){
match[v]=x;
return true;
}
}
}
return false;
}
//建边:只建单向边
//如:接下来 m 行,每行包含两个整数 u 和 v,表示左半部点集中的点 u 和右半部点集中的点 v
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
adj[u].push_back(v);
}
//找二分图最大匹配
for(int i=1;i<=n1;i++){
memset(st,0,sizeof st);
if(find(i)) cnt++;
}
//得到的cnt即为二分图的最大匹配

网络流

最大流

Dinic算法求最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int N = , M = , INF = 1e8;
int m,n,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N];

void add(int a,int b,int c){
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs(){
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int ver=e[i];
if(d[ver]==-1&&f[i]){
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}

int find(int u,int limit){
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=ne[i]){
cur[u]=i;
int ver=e[i];
if(d[ver]==d[u]+1&&f[i]){
int t=find(ver,min(f[i],limit-flow));
if(!t) d[ver]=-1;
f[i]-=t,f[i^1]+=t,flow+=t;
}
}
return flow;
}

int dinic(){
int r=0,flow;
while(bfs()) while(flow=find(S,INF)) r+=flow;
return r;
}
//源点是S,汇点是T
//注意初始化:memset(h,-1,sizeof h);
无源汇上下界可行流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

const int N = 210, M = (10200 + N) * 2, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], l[M], ne[M], idx;//l数组记录每条边的容量下界
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (d[ver] == -1 && f[i])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}

int find(int u, int limit)
{
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}

int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}

void solve(){
cin>>n>>m;
S=0,T=n+1;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,c,d);
A[a]-=c,A[b]+=c;//A数组记录点i所有入边的容量下界之和减去出边的容量下界之和
}
int tot=0;
for(int i=1;i<=n;i++){//保证流量守恒
if(A[i]>0) add(S,i,0,A[i]),tot+=A[i];//tot为源点的出边容量之和
else if(A[i]<0) add(i,T,0,-A[i]);
}
if(dinic()!=tot) cout<<"NO\n";
else {
cout<<"YES\n";
for(int i=0;i<m*2;i+=2){
cout<<f[i^1]+l[i]<<'\n';//该边的流量加上该边的流量下界
}
}
}
有源汇上下界最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
const int N = 210, M = (N + 10000) * 2, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (d[ver] == -1 && f[i])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}

int find(int u, int limit)
{
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}

int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}

void solve(){
int s,t;
cin>>n>>m>>s>>t;
S=0,T=n+1;
memset(h,-1,sizeof h);
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,d-c);
A[a]-=c,A[b]+=c;
}

int tot=0;
for(int i=1;i<=n;i++){
if(A[i]>0) add(S,i,A[i]),tot+=A[i];
else if(A[i]<0) add(i,T,-A[i]);
}

add(t,s,INF);
if(dinic()<tot) cout<<"No Solution"<<endl;
else{
int res=f[idx-1];
S=s,T=t;
f[idx-1]=f[idx-2]=0;
cout<<res+dinic()<<endl;
}
}
有源汇上下界最小流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
const int N = 50010, M = (N + 125003) * 2, INF = 2147483647;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (d[ver] == -1 && f[i])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}

int find(int u, int limit)
{
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}

int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}

void solve(){
int s,t;
cin>>n>>m>>s>>t;
S=0,T=n+1;
memset(h,-1,sizeof h);
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,d-c);
A[a]-=c,A[b]+=c;
}

int tot=0;
for(int i=1;i<=n;i++){
if(A[i]>0) add(S,i,A[i]),tot+=A[i];
else if(A[i]<0) add(i,T,-A[i]);
}

add(t,s,INF);
if(dinic()<tot) cout<<"No Solution"<<endl;
else{
int res=f[idx-1];
S=t,T=s;
f[idx-1]=f[idx-2]=0;
cout<<res-dinic()<<endl;
}
}
多源汇最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve(){
int sc,tc;
cin>>n>>m>>sc>>tc;
S=0,T=n+1;
memset(h,-1,sizeof h);
while(sc--){
int x;
cin>>x;
add(S,x,INF);
}
while(tc--){
int x;
cin>>x;
add(x,T,INF);
}
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<dinic()<<endl;
}
关键边

定义:只给其扩大容量之后整个流网络的最大流能够变大,对于这样的边我们称之为关键边。

求关键边的数量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void dfs(int u, bool st[], int t)
{
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = i ^ t, ver = e[i];//t=1时为反向边,反之为正向边
if (f[j] && !st[ver])
dfs(ver, st, t);
}
}

int main()
{
scanf("%d%d", &n, &m);
S = 0, T = n - 1;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}

dinic();//跑一遍最大流
dfs(S, vis_s, 0);//记录所有能从S经过残留网络中流量大于0的边能到的点
dfs(T, vis_t, 1);////记录所有能从T经过残留网络中流量大于0的边能到的点,这里走的就是反向边

int res = 0;//遍历所有正向边,如果这条边的起点能被S走到且终点能走到T并且这条边在残留网络中为正即没有满流则说明这条边是关键边
for (int i = 0; i < m * 2; i += 2)
if (!f[i] && vis_s[e[i ^ 1]] && vis_t[e[i]])
res ++ ;

printf("%d\n", res);
return 0;
}

最小割

Dinic算法求最小割

代码与Dinic算法求最大流相同,因为最大流=最小割

最大权闭合子图

定义:所有闭合子图中点权之和最大的图,闭合图指图中所有点沿着边能到达的所有点都必须在该点集中。

建图:源点S向所有正权边连一条容量为该点权的边,所有负权边向汇点连一条容量为该点权相反数的边,图中原有边容量为正无穷。正权点点权和减去最小割即为最大权闭合子图的最大权值。

最大密度子图

定义:给定无向图$G=(V,E)$,其子图记为$G’=(V’,E’)$,在所有子图构成的集合中,密度$D=\frac {E’} {V’}$最大的元素称为最大密度子图。

最小点权覆盖集

定义:图中所有边的两个端点至少有一个在点集中所构成的点权之和最小的点的集合。

这个问题是NP完全问题,只能通过爆搜完成,而最小割模型的最小点权覆盖集是对于一个二分图而言的。

建图:首先该图是个二分图,分成左右两部分点集,只有左右两个点集之间右边。从源点向所有左部结点连一条容量为该点权值的边,从右部结点向汇点连一条容量为该点权值的边,中间的边容量为正无穷。求出的最小割即为最小权点覆盖。

如何找方案:从源点沿着残留网络容量大于0的边搜到的点记为集合S,剩下的点记为集合T,若边E(根据割边的定义,这里只枚举正向边)的两点a,b分别在S,T集合,则该边为割边。

最大点权独立集

定义:任意两点中间不存在边的点权之和最大的点的集合。

同“最小点权覆盖集”,也是NP完全问题,这里的最小割模型同样对于二分图而言。

最大点权独立集= 所有点的权值之和 - 最小点权覆盖集(同上)

费用流

EK+spfa求最小费用最大流

求最小费用最大流转为最大费用最大流时:

  • 可以将spfa中的memset(d, 0x3f, sizeof d);改为memset(d, -0x3f, sizeof d);,以及松弛操作符号取反即可。

  • 或者直接将费用取反。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

using namespace std;

const int N = 5010, M = 100010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[i] && d[ver] > d[t] + w[i])
{
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}

return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
flow = cost = 0;
while (spfa())
{
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}

int main()
{
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
}

int flow, cost;
EK(flow, cost);
printf("%d %d\n", flow, cost);
for (int i = 0; i < idx; i += 2)
{
f[i] += f[i ^ 1], f[i ^ 1] = 0;
w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
}
printf("%d\n", -EK(flow, cost));

return 0;
}
二分图最优匹配

例题:有 $n$ 件工作要分配给 $n $个人做。第 $i$ 个人做第 $j$件工作产生的效益为 $c[i][j]$试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案。对于给定的 $n$ 件工作和 $n$ 个人,计算最优分配方案和最差分配方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
const int N = 110, M = 5210, INF = 1e8;

int n, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[i] && d[ver] > d[t] + w[i])
{
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}

int EK()
{
int cost = 0;
while (spfa())
{
int t = incf[T];
cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
return cost;
}

int main()
{
scanf("%d", &n);
S = 0, T = n * 2 + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
add(S, i, 1, 0);
add(n + i, T, 1, 0);
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
int c;
scanf("%d", &c);
add(i, n + j, 1, c);
}

printf("%d\n", EK());

for (int i = 0; i < idx; i += 2)
{
f[i] += f[i ^ 1], f[i ^ 1] = 0;
w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
}
printf("%d\n", -EK());

return 0;
}
最大权不相交路径

用容量控制经过该点(拆点)或该边的次数,用费用表示经过该点累加的权值,求最大费用最大流。

网格图模型

对于某个点可以走无限次次但只有一次能获得价值可以采用拆点,然后分成两个边,其中一个边容量为1,费用为该点价值;另一条边容量为正无穷,费用为0。

网络流模型的常用技巧

拆点技巧

对于限制点的经过次数,我们可以把一个点拆成入点和出点,从入点向出点连一条容量为能经过该点的次数。

还原流网络
1
2
3
4
5
for (int k = 0; k < idx; k += 2)
{
f[k] += f[k ^ 1];
f[k ^ 1] = 0;
}

欧拉回路

输入第一行包含一个整数,t=1为无向图,t=2为有向图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;

const int N = 100010, M = 400010;

int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
for (int &i = h[u]; ~i;)
{
if (used[i])
{
i = ne[i];
continue;
}

used[i] = true;
if (type == 1) used[i ^ 1] = true;

int t;

if (type == 1)
{
t = i / 2 + 1;
if (i & 1) t = -t;
}
else t = i + 1;

int j = e[i];
i = ne[i];
dfs(j);

ans[ ++ cnt] = t;
}
}

int main()
{
scanf("%d", &type);
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);

for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
if (type == 1) add(b, a);
din[b] ++ , dout[a] ++ ;
}

if (type == 1)
{
for (int i = 1; i <= n; i ++ )
if (din[i] + dout[i] & 1)
{
puts("NO");
return 0;
}
}
else
{
for (int i = 1; i <= n; i ++ )
if (din[i] != dout[i])
{
puts("NO");
return 0;
}
}

for (int i = 1; i <= n; i ++ )
if (h[i] != -1)
{
dfs(i);
break;
}

if (cnt < m)
{
puts("NO");
return 0;
}

puts("YES");
for (int i = cnt; i; i -- ) printf("%d ", ans[i]);
puts("");

return 0;
}

2-SAT

时间复杂度:O(n+m)

建图:当u被选择时,v一定被选择,则u向v连边。

第一行包含两个整数 n,m。接下来 m 行,每行包含四个整数 i,a,j,b,用来描述一个条件,表示 “xi 为 a 或 xj 为 b”。输出任意一组解或报告无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;

const int N=2e6+10,M=2e6+10;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],ts,stk[N],top;
int id[N],cnt;
bool ins[N];

void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u){
dfn[u]=low[u]=++ts;
stk[++top]=u,ins[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(ins[j]) low[u]=min(low[u],dfn[j]);
}
if(low[u]==dfn[u]){
int y;
cnt++;
do{
y=stk[top--],ins[y]=false,id[y]=cnt;
}while(y!=u);
}
}

bool multi=0;
void solve(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int i,a,j,b;
cin>>i>>a>>j>>b;
i--,j--;
add(2*i+!a,2*j+b);
add(2*j+!b,2*i+a);
}

for(int i=0;i<n*2;i++){
if(!dfn[i]){
tarjan(i);
}
}

for(int i=0;i<n;i++){
if(id[i*2]==id[i*2+1]){
cout<<"IMPOSSIBLE"<<endl;
return;
}
}
cout<<"POSSIBLE"<<endl;
for(int i=0;i<n;i++){
if(id[i*2]<id[i*2+1]){
cout<<"0 ";
}else{
cout<<"1 ";
}
}
cout<<endl;
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT=1;
if(multi) cin>>TTT;
while(TTT--){
solve();
}

return 0;
}

差分约束

存在负环时无解
记得建立一个超级源点,连向所有点

  • 最长路:

    求最小差值(至少)
    A-B<=W$\Longrightarrow$连一条由B->A,边权为W的边
    A>=C$\Longrightarrow$连一条0->A,边权为C的边

  • 最短路:

    求最大差值(最多)
    A-B<=W$\Longrightarrow$连一条由B->A,边权为W的边
    A<=C$\Longrightarrow$连一条0->A,边权为C的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int cnt[N],dist[N];;
bool st[N];
bool spfa(){//求最长路
queue<int> q;//若TLE可尝试改成stack
memset(dist,-0x3f,sizeof dist);//最长路:-0x3f,最短路:0x3f
q.push(0);
dist[0]=0;
st[0]=true;
//count若tle可尝试去掉有关count的注释,运行一定次数提前跳出循环
//int count=0;
while(q.size()){
int u=q.front();
q.pop();
st[u]=false;
for(auto it:edge[u]){
int v=it.first,w=it.second;
if(dist[v]<dist[u]+w){//最长路:小于号,最短路:大于号
dist[v]=dist[u]+w;
cnt[v]=cnt[u]+1;
//if(++count>1000000) return false;
if(cnt[v]>=n+1) return false;
if(!st[v]){
q.push(v);
st[v]=true;
}
}
}
}
return true;
}

for(int i=0;i<k;i++){
int x,a,b;cin>>x>>a>>b;
edge[a].push_back({b,1});
}
//0号点为超级源点
for(int i=1;i<=n;i++) edge[0].push_back({i,1});//求最长路情况下:xi>=x0+1(而x0=0,即所有xi>=0)

if(!spfa()) 无解
else 所有dist[i]即x[i]的一组解

仙人掌

给一个N个点M条边的仙人掌。仙人掌定义如下:

任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

有 Q 组询问,每次询问两点之间的最短路径。

第一行包含三个整数,分别表示 N,M,Q。

下接 M 行,每行三个整数 v,u,w 表示一条无向边 v−u,长度为 w。

最后 Q 行,每行两个整数 v,u 表示一组询问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=0;

const int N = 12010, M = N * 3;

int n, m, Q, new_n;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
int dfn[N], low[N], cnt;
int s[N], stot[N], fu[N], fw[N], fe[N];
int fa[N][14], depth[N], d[N];
int A,B;

void add(int h[], int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void build_circle(int x, int y, int z){
int sum = z;
for(int k = y; k != x; k = fu[k]){
s[k] = sum;
sum += fw[k];
}
s[x] = stot[x] = sum;
add(h2, x, ++new_n, 0);
for(int k = y; k != x; k = fu[k]){
stot[k] = sum;
add(h2, new_n, k, min(s[k], sum - s[k]));
}
}

void tarjan(int u, int from){
dfn[u] = low[u] = ++cnt;
for(int i = h1[u]; ~i; i = ne[i]){
int j = e[i];
if(!dfn[j]){
fu[j] = u, fw[j] = w[i], fe[j] = i;
tarjan(j, i);
low[u] = min(low[u], low[j]);
if(dfn[u] < low[j]) add(h2, u, j, w[i]);
}else if(i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
}
for(int i = h1[u]; ~i; i = ne[i]){
int j = e[i];
if(dfn[u] < dfn[j] && fe[j] != i)
build_circle(u, j, w[i]);
}
}

void dfs_lca(int u, int father){
depth[u] = depth[father] + 1;
fa[u][0] = father;
for(int k = 1; k <= 13; k++)
fa[u][k] = fa[fa[u][k - 1]][k - 1];
for(int i = h2[u]; ~i; i = ne[i]){
int j = e[i];
d[j] = d[u] + w[i];
dfs_lca(j, u);
}
}

int lca(int a, int b){
if(depth[a] < depth[b]) swap(a, b);
for(int k = 13; k >= 0; k--)
if(depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if(a == b) return a;
for(int k = 13; k >= 0; k--)
if(fa[a][k] != fa[b][k]){
a = fa[a][k];
b = fa[b][k];
}
A = a, B = b;
return fa[a][0];
}

void solve(){
cin >> n >> m >> Q;
new_n = n;
memset(h1, -1, sizeof h1);
memset(h2, -1, sizeof h2);
while(m--){
int a, b, c;
cin >> a >> b >> c;
add(h1, a, b, c), add(h1, b, a, c);
}

tarjan(1, -1);

dfs_lca(1, 0);

while(Q--){
int a, b;
cin >> a >> b;
int p = lca(a, b);
if(p <= n) cout << d[a] + d[b] - d[p] * 2 << '\n';
else {
int da = d[a] - d[A], db= d[b] - d[B];
int l = abs(s[A] - s[B]);
int dm = min(l, stot[A] - l);
cout << da + dm + db << '\n';
}
}
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}

return 0;
}

数学

数论

龟速乘

1
2
3
4
5
6
7
8
9
10
int Mul(int a, int b, int p){
int res = 0;
while(b){
if(b&1){
res = (res + a) % p;
}
b >>= 1, a = (a * 2) % p;
}
return res;
}

快速幂

1
2
3
4
5
6
7
8
9
10
//a ^ b mod p
int qpow(int a,int b,int p){
long long res=1%p;
while(b){
if(b&1) res=res*a%p;
a=(long long)a*a%p;
b>>=1;
}
return res;
}

矩阵快速幂加速递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct matrix{
int m[N][N];
matrix() { memset(m, 0, sizeof m); }
};
matrix operator*(const matrix &a, const matrix &b){
matrix c;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
c.m[i][j] = ( c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
return c;
}

matrix pow_matrix(matrix a, int n){
matrix ans;
for(int i = 0; i < N; i++) ans.m[i][i] = 1;
while(n) {
if(n&1) ans = ans * a;
a = a * a;
n >>= 1;
}
return ans;
}

逆元

快速幂

求$a^{-1}$%p

1
qpow(a,p-2,p);
扩展欧几里得求逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct INV{
public:
long long get(long long x,long long P){
long long a,b;
exgcd(x,P,a,b);
return (a%P+P)%P;
}
private:
long long exgcd(long long a,long long b,long long &x,long long &y){
if(!b){
x=1,y=0;
return a;
}
long long d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
};

欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
//返回1~x中与x互质的数的个数
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;
}

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int primes[N],cnt,int euler[N];
bool st[N];
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);
}
}
}

质数

试除法判断质数
1
2
3
4
5
6
7
bool is_prime(int x){
if(x<2) return false;
for(int i=2;i<=x/i;i++){
if(x%i==0) return false;
}
return true;
}
分解质因数
1
2
3
4
5
6
7
8
9
10
11
12
vector<pair<int,int>> divide(int x){
vector<pair<int,int>> divs;
for(int i=2;i<=x/i;i++){
if(x%i==0){
int cnt=0;
while(x%i==0) cnt++,x/=i;
divs.push_back({i,cnt});
}
}
if(x>1) divs.push_back({x,1});
return divs;
}
筛质数

1.朴素做法O(nlogn)

1
2
3
4
5
6
7
8
9
10
bool st[N];
int primes[N],cnt;
void get_primes2(){
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=i;j<=n;j+=i){
st[j]=true;
}
}
}

2.诶氏筛法 O(nloglogn)

1
2
3
4
5
6
7
8
9
10
bool st[N];
int primes[N],cnt;
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;j<=n;j+=i) st[j]=true;
}
}
}

3.线性筛O(n)

1
2
3
4
5
6
7
8
9
10
11
12
bool st[N];
int prime[N],cnt;
void get_primes(int n){
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}

约数

试除法求约数
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> get_divisors(int n){
vector<int> divs;
for(int i=1;i<=n/i;i++)
{
if(n%i==0){
divs.push_back(i);
if(n/i!=i) divs.push_back(n/i);
}
}
sort(divs.begin(),divs.end());
return divs;
}

gcd/lcm

1
2
3
4
5
6
7
8
9
gcd:
//辗转相除法
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
//调用函数
__gcd(a,b);
lcm:
a*b/__gcd(a,b);

扩展欧几里得算法

定理引入:

裴蜀定理:设a, b是不全为零的整数,则存在整数x, y使得ax+by=gcd(a,b) ——OIWIKI

  • 扩展欧几里得算法

    求$ax+by=gcd(a,b)$的一组可行解

1
2
3
4
5
6
7
8
9
10
11
12
//返回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;
}
int a,b,x,y;cin>>a>>b;
exgcd(a,b,x,y);//x,y即为方程的一组解
  • 求解更一般的方程$ax+by=c$

    设$d=gcd(a,b)$,当且仅当$d|c$时有解 $c\bmod gcd(a,mb)$

    通解=特解+齐次解

    特解:

    $x_1=x_0c/d,y_1=y_0c/d$

    1
    2
    3
    4
    5
    6
    7
    8
    int exgcd(int a,int b,int &x,int &y);//函数同上
    int a,b,x0,y0,x,y;cin>>a>>b;
    int d=exgcd(a,b,x0,y0);

    //x0和y0为ax+by=gcd(a,b)的一组解
    //x1和y1为ax+by=c的一组特解
    通解:
    x=x1+k*b/d,y=y1-k*a/d,k∈z

    齐次解:

    即$ax+by=0$的解

    通解:

    通解=特解+齐次解

    $x=x_1+kb/d,y=y_1-ka/d,k∈z$

    令$t=b/d(x=x’+kt)$,则对于x的最小非负整数解为$(x’\bmod t+t)\bmod t$

  • 求解一次线性同余方程$ax≡b(\bmod m)$

    等价于求:$ax+my=b$

    1
    2
    3
    4
    int exgcd(int a,int b,int &x,int &y);//函数同上
    int a,b,m,x,y;cin>>a>>b>>m;
    exgcd(a,m,x,y);
    x*a/b即为一组合法解

同余方程组

中国剩余定理(孙子定理)

求解同余方程组形如:

$x \equiv a_1 (\mod m_1)$

$x \equiv a_2 (\mod m_2)$

$\dots$

$x \equiv a_k (\mod m_k)$

条件:$m_1,m_2,\dots,m_k$两两互质.

令$M=\prod_{i=1}^k m_i$,$M_i=\frac M{m_i}$

$t_i$是$M_i$关于$m_i$的逆元,即$M_i\times t_i\equiv 1(\mod m_i)$

$x=\sum_{i=1}^n a_iM_it_i + Mi * k, k∈Z$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// Problem: 曹冲养猪
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1300/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 0;

const int INF = 0x3f3f3f3f3f3f3f3f;

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;
}

void solve() {
int n;
cin >> n;
int M = 1;
vector<int> A(n), B(n);
for(int i = 0; i < n; i++) {
cin >> A[i] >> B[i];
M *= A[i];
}
int res = 0;
for(int i = 0; i < n; i++) {
int Mi = M / A[i];
int ti, x;
exgcd(Mi, A[i], ti, x);
res += B[i] * Mi * ti;
}
cout << (res % M + M) % M << '\n';
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}
扩展中国剩余定理

中国剩余定理的扩展版,不需要满足$m_1,m_2,\dots,m_k$两两互质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem: 表达整数的奇怪方式
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/206/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 0;

const int INF = 0x3f3f3f3f3f3f3f3f;

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;
}
//这里的等式为x ≡ mi(mod ai)
void solve() {
int n;
cin >> n;
int a1, m1;
cin >> a1 >> m1;
for(int i = 2; i <= n; i++) {
int a2, m2;
cin >> a2 >> m2;
int k1, k2;
int d = exgcd(a1, a2, k1, k2);
if((m2 - m1) % d) {
cout << -1 << '\n';
return;
}
k1 *= (m2 - m1) / d;
int t = a2 / d;
k1 = (k1 % t + t) % t;
m1 = m1 + a1 * k1;
a1 = abs(a1 * a2 / d);
}
cout << (m1 % a1 + a1) % a1 << '\n';
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

BSGS

条件:$a,p$互质

求$a^x \equiv b(\mod p)$

时间复杂度:O($\sqrt p$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// Problem: BSGS
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3127/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 0;

const int INF = 0x3f3f3f3f3f3f3f3f;
//a ^ x ≡ b(mod p)
int a, p, b;

int bsgs(int a, int b, int p) {
if(1 % p == b % p) return 0;
int k = sqrt(p) + 1;
unordered_map<int, int> mp;
for(int i = 0, j = b % p; i < k; i++) {
mp[j] = i;
j = j * a % p;
}
int ak = 1;
for(int i = 0; i < k; i++) ak = ak * a % p;
for(int i = 1, j = ak; i <= k; i++) {
if(mp.count(j)) return i * k - mp[j];
j = j * ak % p;
}
return -1;
}

void solve() {
int res = bsgs(a, b, p);
if(res == -1) cout << "No Solution\n";
else cout << res << '\n';
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
while (cin >> a >> p >> b, a || p || b) {
solve();
}

return 0;
}

扩展BSGS

求$a^x \equiv b(\mod p)$

不需要满足$a,p$互质的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Problem: 扩展BSGS
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3128/
// Memory Limit: 64 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 0;

const int INF = 0x3f3f3f3f3f3f3f3f;
//a ^ x ≡ b (mod p)
int a, p, 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;
}

int bsgs(int a, int b, int p) {
if(1 % p == b % p) return 0;
int k = sqrt(p) + 1;
unordered_map<int, int> mp;
for(int i = 0, j = b % p; i < k; i++) {
mp[j] = i;
j = j * a % p;
}
int ak = 1;
for(int i = 0; i < k; i++) ak = ak * a % p;
for(int i = 1, j = ak; i <= k; i++) {
if(mp.count(j)) return i * k - mp[j];
j = j * ak % p;
}
return -INF;
}

int exbsgs(int a, int b, int p) {
b = (b % p + p) % p;
if(1 % p == b % p) return 0;
int x, y;
int d = exgcd(a, p, x, y);
if(d > 1) {
if(b % d) return -INF;
exgcd(a / d, p / d, x, y);
return exbsgs(a, b / d * x % (p / d), p / d) + 1;
}else return bsgs(a, b, p);
}

void solve() {
int res = exbsgs(a, b, p);
if(res < 0) cout << "No Solution\n";
else cout << res << '\n';
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
while (cin >> a >> p >> b, a || p || b) {
solve();
}

return 0;
}

Pollard rho

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using i64 = long long;
i64 mul(i64 a, i64 b, i64 m) {
return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
i64 res = 1 % m;
for (; b; b >>= 1, a = mul(a, a, m))
if (b & 1)
res = mul(res, a, m);
return res;
}
bool isprime(i64 n) {
if (n < 2)
return false;
static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int s = __builtin_ctzll(n - 1);
i64 d = (n - 1) >> s;
for (auto a : A) {
if (a == n)
return true;
i64 x = power(a, d, n);
if (x == 1 || x == n - 1)
continue;
bool ok = false;
for (int i = 0; i < s - 1; ++i) {
x = mul(x, x, n);
if (x == n - 1) {
ok = true;
break;
}
}
if (!ok)
return false;
}
return true;
}
std::vector<i64> factorize(i64 n) {
std::vector<i64> p;
std::function<void(i64)> f = [&](i64 n) {
if (n <= 10000) {
for (int i = 2; i * i <= n; ++i)
for (; n % i == 0; n /= i)
p.push_back(i);
if (n > 1)
p.push_back(n);
return;
}
if (isprime(n)) {
p.push_back(n);
return;
}
auto g = [&](i64 x) {
return (mul(x, x, n) + 1) % n;
};
i64 x0 = 2;
while (true) {
i64 x = x0;
i64 y = x0;
i64 d = 1;
i64 power = 1, lam = 0;
i64 v = 1;
while (d == 1) {
y = g(y);
++lam;
v = mul(v, std::abs(x - y), n);
if (lam % 127 == 0) {
d = std::gcd(v, n);
v = 1;
}
if (power == lam) {
x = y;
power *= 2;
lam = 0;
d = std::gcd(v, n);
v = 1;
}
}
if (d != n) {
f(d);
f(n / d);
return;
}
++x0;
}
};
f(n);
std::sort(p.begin(), p.end());
return p;
}

数论函数

莫比乌斯函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int primes[N],cnt;
bool st[N];
int mobius[N];
// 线性筛法,求莫比乌斯函数
void init(int n){
mobius[1]=1;
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
mobius[i]=-1;
}
for(int j=0;primes[j]*i<=n;j++){
int t=primes[j]*i;
st[t]=true;
if(i%primes[j]==0){
mobius[t]=0;
break;
}
mobius[t]=mobius[i]*-1;
}
}
}

线性代数

线性基

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct lb{
ll d[64];
void print(){
for(int i=0;i<=62;i++)if(d[i])printf("%d:%lld\n",i,d[i]);
}
lb(){memset(d,0,sizeof(d));}
void operator +=(ll x){
for(int i=62;i>=0;i--){
if(!(x&(1ll<<i)))continue;
if(d[i])x^=d[i];
else{d[i]=x;break;}
}
}
ll& operator [](int x){
return d[x];
}
void operator +=(lb &x){
for(int i=62;i>=0;i--)if(x[i])*this+=x[i];
}
friend lb operator +(lb &x,lb &y){
lb z=x;
for(int i=62;i>=0;i--)if(y[i])z+=y[i];
return z;
}
ll calc(){//calculate maximum possible
ll res=0;
for(int i=62;i>=0;i--)if((res^d[i])>res)res^=d[i];
return res;
}
};

贪心法求线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;


int n;
int a[60];

bool flag0 = 0;
int lin[60];
void ins(int x) {
for(int i = 51; i >= 0; i--) {
if(x >> i & 1) {
if(!lin[i]) {
lin[i] = x;
return;
}else x ^= lin[i];
}
}
flag0 = true;
}

bool check(int x) {
for(int i = 51; i >= 0; i--) {
if(x >> i & 1) {
if(!lin[i]) return true;
else x ^= lin[i];
}
}
return true;
}

void solve(){
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
ins(a[i]);
}
int ans = 0;
for(int i = 51; i >= 0; i--) {
ans = max(ans, ans ^ lin[i]);
}
cout << ans << '\n';
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

高斯消元求线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Gauss(int a[],int &n){              //高斯消元求线性基
int i,k=1; //k标记当前第几行
long long j = (long long)1<<62; //注意不是63,因为a[i]&(1<<0)时为第1位
for(;j;j>>=1){
for(i=k;i<=n;i++)
if(a[i]&j) break; //找到第j位是1的a[]
if(i > n) continue; //没有第j位是1的a[]
swap(a[i],a[k]); //把这一行换到上面
for(i=1;i<=n;i++) //生成简化阶梯矩阵
if(i != k && a[i]&j) a[i]^=a[k];
k++;
}
k--;
n = k; //线性基中元素的个数
}

求从n个整数序列选取一些(至少一个)数(每个数最多选一次)进行异或运算的所有结果中第k小的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=1;
const int N=1e4+10;
int a[N];
bool zero;
void Gauss(int a[],int &n){ //高斯消元求线性基
int i,k=1; //k标记当前第几行
long long j = (long long)1<<62; //注意不是63
for(;j;j>>=1){
for(i=k;i<=n;i++)
if(a[i]&j) break; //找到第j位是1的a[]
if(i > n) continue; //没有第j位是1的a[]
swap(a[i],a[k]); //把这一行换到上面
for(i=1;i<=n;i++) //生成简化阶梯矩阵
if(i != k && a[i]&j) a[i]^=a[k];
k++;
}
k--;
if(k!=n) zero = true;
else zero = false;
n = k; //线性基中元素的个数
}
long long Query(int a[],int n,long long k){ //第k小异或和
long long ans=0;
if(zero) k--;
if(!k) return 0;
for(int i=n;i;i--){
if(k&1) ans^=a[i];
k >>= 1;
}
if(k) return -1;
return ans;
}

void solve(int t){
cout<<"Case #"<<t<<":\n";
int n,q;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
Gauss(a,n);

cin>>q;
while(q--){
int k;
cin>>k;
cout<<Query(a,n,k)<<'\n';
}

}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
for(int i=1;i<=T;i++){
solve(i);
}

return 0;
}

组合数学

求组合数

杨辉三角预处理所有组合数

c[a][b]表示$C_{a}^{b}$

1
2
3
4
5
6
7
8
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;
}
求单个组合数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Comb{
int n;
vector<int> fact,infact;
Comb(int n) : fact(n+1),infact(n+1){
this->n=n;
fact[0]=infact[0]=1;
for(int i=1;i<=n;i++){
fact[i]=(long long)fact[i-1]*i%mod;
infact[i]=(long long)infact[i-1]*qpow(i,mod-2,mod)%mod;
}
}
long long get(int a,int b){
return (long long)fact[a]*infact[a-b]%mod*infact[b]%mod;
}
private:long long qpow(int a,int k,int p){
long long res=1%p;
while(k){
if(k&1) res=res*a%p;
a=(long long)a*a%p;
k>>=1;
}
return res;
}
};
Lucas定理求组合数

适用于p不固定的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int qmi(int a,int k,int p){
int res=1;
while(k){
if(k&1) res=res*a%p;
a=a*a%p;
k>>=1;
}
return res;
}
int C(int a,int b,int p){
if(b>a) return 0;
int up=1,down=1;
for(int i=1,j=a;i<=b;i++,j--){
up=up*j%p;
down=down*i%p;
}
return up*qmi(down,p-2,p)%p;
}
int lucas(int a,int b,int p){
if(a<p&&b<p) return C(a,b,p);
return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
C(a,b):lucas(a,b,p)
求组合数(高精度)
1
2
3
4
5
6
7
8
9
a,b=map(int,input().split())
res=1
for i in range(a-b+1,a+1):
res*=i

for j in range(1,b+1):
res//=j

print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N=5010;

int primes[N],cnt;
int sum[N];
bool st[N];

void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])primes[cnt++]=i;
for(int j=0;primes[j]*i<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)break;//==0每次漏
}
}
}
// 对p的各个<=a的次数算整除下取整倍数
int get(int n,int p)
{
int res =0;
while(n)
{
res+=n/p;
n/=p;
}
return res;
}
//高精度乘
vector<int> mul(vector<int> a, int b)
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
// while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时才有pop多余的0 b!=0不需要这行
return c;
}

int main()
{
int a,b;
cin >> a >> b;
get_primes(a);

for(int i=0;i<cnt;i++)
{
int p = primes[i];
sum[i] = get(a,p)-get(a-b,p)-get(b,p);//是a-b不是b-a
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )
for (int j = 0; j < sum[i]; j ++ )//primes[i]的次数
res = mul(res, primes[i]);

for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
puts("");

return 0;
}

博弈论

SG函数

例题:n堆石子,每次操作玩家从任意一堆拿去石子,每次拿取的石子数列必须包含于集合s,最后无法操作的人失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n,m;
int s[N],f[N];
//s数组表示每次可以拿的数量,f数组表示每个状态SG的值。
int sg(int x){
if(f[x]!=-1) return f[x];
unordered_set<int> S;
for(int i=0;i<m;i++){
if(x>=s[i]) S.insert(sg(x-s[i]));
}
for(int i=0;;i++){
if(!S.count(i)){
return f[x]=i;
}
}
}

void solve(){
memset(f,-1,sizeof f);
cin>>m;
for(int i=0;i<m;i++) cin>>s[i];
cin>>n;
int res=0;
for(int i=0;i<n;i++){
int x;
cin>>x;
res^=sg(x);
}
if(res){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}

多项式

NTT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Problem: 多项式乘法
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3125/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

bool multi = 0;

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 300010;
const double PI = acos(-1);

int n, m;
struct Complex
{
double x, y;
Complex operator+ (const Complex& t) const
{
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const
{
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const
{
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
}a[N], b[N], c[N];
int rev[N], bit, tot;

void fft(Complex a[], int inv)
{
for (int i = 0; i < tot; i ++ )
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int mid = 1; mid < tot; mid <<= 1)
{
auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
for (int i = 0; i < tot; i += mid * 2)
{
auto wk = Complex({1, 0});
for (int j = 0; j < mid; j ++, wk = wk * w1)
{
auto x = a[i + j], y = wk * a[i + j + mid];
a[i + j] = x + y, a[i + j + mid] = x - y;
}
}
}
}

void solve() {
cin >> n >> m;
for(int i = 0; i <= n; i++) cin >> a[i].x;
for(int i = 0; i <= m; i++) cin >> b[i].x;
while((1 << bit) < n + m + 1) bit++;
tot = 1 << bit;
for(int i = 0; i < tot; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
fft(a, 1), fft(b, 1);
for(int i = 0; i < tot; i++) c[i] = a[i] * b[i];
fft(c, -1);
for(int i = 0; i <= n + m; i++) {
cout << (int)(c[i].x / tot + 0.5) << " \n" [i == n + m];
}
}

void init() {}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

字符串

kmp

  • 版本1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
char s[N],t[N];//s为主串,t为模式串
int ne[N];//ne[]对应t[]
void CalcKMPNext(char t[],int ne[]){
int n=strlen(t+1)+1;
int j=1,k=0;
ne[1]=0;
while(j<n){
if(k==0||t[j]==t[k]){
j++;
k++;
ne[j]=k;
}else k=ne[k];
}
}

int KMPIndex(char s[],char t[]){//若匹配成功,返回第一个匹配的位置,若匹配不成功,返回0
int ns=strlen(s+1);
int nt=strlen(t+1);
int i=1,j=1;
while(i<=ns&&j<=nt){
if(j==0||s[i]==t[j]) i++,j++;
else j=ne[j];
}
if(j>nt) return i-nt;
else return 0;
}
//注意:s和t的存储从1开始
  • 版本2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int ne[N];//前后缀相等且长度最长
    char p[N],s[M];//p是主串,s是模式串
    vector<int> res;
    //求ne的过程
    int i=0,j=0;
    for(i=2,j=0;i<=n;i++){
    while(j&&p[i]!=p[j+1]){
    j=ne[j];
    }
    if(p[i]==p[j+1]) j++;
    ne[i]=j;
    }

    //kmp的匹配过程,将所有模式串在主串出现位置的起始下标保存在res中
    for(i=1,j=0;i<=m;i++){
    while(j&&s[i]!=p[j+1]){
    j=ne[j];
    }
    if(s[i]==p[j+1]) j++;
    if(j==n){
    res.push_back(i-n);
    j=ne[j];//为了观察其后续是否还能跟S数组后面的数配对成功
    }
    }

字符串哈希(双模正反向哈希)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const pair<long long, long long> P(131, 13331);
const long long mod1 = 1e9 + 7, mod2 = 1e9 + 9;
PII operator+(const PII &a, const PII &b) {
return {(a.first + b.first) % mod1, (a.second + b.second) % mod2};
}
PII operator-(const PII &a, const PII &b) {
return {(a.first - b.first + mod1) % mod1, (a.second - b.second + mod2) % mod2};
}
PII operator*(const PII &a, const PII &b) {
return {a.first * b.first % mod1, a.second * b.second % mod2};
}
struct strHash{
int n;
vector<pair<long long, long long>> hz,hf,pz,pf;

strHash(int n,string &str): hz(n+2),pz(n+2),hf(n+2),pf(n+2){
this->n=n;
pz[0]={1, 1};
for(int i=1;i<=n;i++){
hz[i]=hz[i-1]*P+(pair<int, int>){str[i], str[i]};
pz[i]=pz[i-1]*P;
}
pf[n+1]={1, 1};
for(int i=n;i>=1;i--){
hf[i]=hf[i+1]*P+(pair<int, int>){str[i], str[i]};
pf[i]=pf[i+1]*P;
}
}
pair<long long,long long> findz(int l,int r){
return hz[r]-hz[l-1]*pz[r-l+1];
}
pair<long long,long long> findf(int l,int r){
return hf[l]-hf[r+1]*pf[n-r+l];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct strHash{
vector<long long> vmod = {7, 9, 21, 33, 87, 93, 97, 103, 123, 181, 207, 223, 241, 271, 289, 297, 321, 349, 363, 403, 409, 411, 427, 433, 439, 447, 453, 459, 483, 513, 531, 579, 607, 613, 637, 663, 711, 753, 787, 801, 829, 861, 871, 891, 901, 919, 931, 933};
long long P1=131,mod1,P2=13331,mod2;
int n;
vector<long long> hz1,hf1,pz1,pf1,hz2,hf2,pz2,pf2;
strHash(int n,string &str): hz1(n+2),pz1(n+2),hf1(n+2),pf1(n+2),hz2(n+2),pz2(n+2),hf2(n+2),pf2(n+2){
srand(time(0));
random_shuffle(vmod.begin(), vmod.end());
mod1 = 1e9 + vmod[0], mod2 = 1e9 + vmod[1];
this->n=n;
pz1[0]=1;
for(int i=1;i<=n;i++){
hz1[i]=(hz1[i-1]*P1+str[i])%mod1;
pz1[i]=pz1[i-1]*P1%mod1;
}
pf1[n+1]=1;
for(int i=n;i>=1;i--){
hf1[i]=(hf1[i+1]*P1+str[i])%mod1;
pf1[i]=pf1[i+1]*P1%mod1;
}

pz2[0]=1;
for(int i=1;i<=n;i++){
hz2[i]=(hz2[i-1]*P2+str[i])%mod2;
pz2[i]=pz2[i-1]*P2%mod2;
}
pf2[n+1]=1;
for(int i=n;i>=1;i--){
hf2[i]=(hf2[i+1]*P2+str[i])%mod2;
pf2[i]=pf2[i+1]*P2%mod2;
}
}
pair<long long,long long> findz(int l,int r){
return {((hz1[r]-hz1[l-1]*pz1[r-l+1])%mod1+mod1)%mod1,((hz2[r]-hz2[l-1]*pz2[r-l+1])%mod2+mod2)%mod2};
}
pair<long long,long long> findf(int l,int r){
return {((hf1[l]-hf1[r+1]*pf1[n-r+l])%mod1+mod1)%mod1,((hf2[l]-hf2[r+1]*pf2[n-r+l])%mod2+mod2)%mod2};
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
long long mod1, mod2;
struct strHash{
bool isprime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int findPrime(int n) {
while (!isprime(n)) {
n++;
}
return n;
}
long long P1=131, P2=13331;
int n;
vector<long long> hz1,hf1,pz1,pf1,hz2,hf2,pz2,pf2;
strHash(int n,string &str): hz1(n+2),pz1(n+2),hf1(n+2),pf1(n+2),hz2(n+2),pz2(n+2),hf2(n+2),pf2(n+2){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
if(!mod1) {
mod1 = findPrime(rng() % 900000000 + 100000000);
mod2 = findPrime(mod1 + 1);
}
this->n=n;
pz1[0]=1;
for(int i=1;i<=n;i++){
hz1[i]=(hz1[i-1]*P1+str[i])%mod1;
pz1[i]=pz1[i-1]*P1%mod1;
}
pf1[n+1]=1;
for(int i=n;i>=1;i--){
hf1[i]=(hf1[i+1]*P1+str[i])%mod1;
pf1[i]=pf1[i+1]*P1%mod1;
}

pz2[0]=1;
for(int i=1;i<=n;i++){
hz2[i]=(hz2[i-1]*P2+str[i])%mod2;
pz2[i]=pz2[i-1]*P2%mod2;
}
pf2[n+1]=1;
for(int i=n;i>=1;i--){
hf2[i]=(hf2[i+1]*P2+str[i])%mod2;
pf2[i]=pf2[i+1]*P2%mod2;
}
}
pair<long long,long long> findz(int l,int r){
return {((hz1[r]-hz1[l-1]*pz1[r-l+1])%mod1+mod1)%mod1,((hz2[r]-hz2[l-1]*pz2[r-l+1])%mod2+mod2)%mod2};
}
pair<long long,long long> findf(int l,int r){
return {((hf1[l]-hf1[r+1]*pf1[n-r+l])%mod1+mod1)%mod1,((hf2[l]-hf2[r+1]*pf2[n-r+l])%mod2+mod2)%mod2};
}
};

Trie树

字符串插入与询问

  • N指结点总数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//注意:此处的N指的是输入字符串的字符数量总和
//如:所有输入的字符串总长度不超过1e5,N取1e5+10;
char str[N];
int tr[N][26],cnt[N],idx;
//往Trie树中插入str字符串
void insert(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!tr[p][u]) tr[p][u]=++idx;
p=tr[p][u];
}
cnt[p]++;
}
//询问str字符串个数
int query(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!tr[p][u]) return 0;
p=tr[p][u];
}
return cnt[p];
}
cin>>str;
//往Trie树中插入str字符串
insert(str);
//询问str字符串个数
query(str);

最大异或对(存储二进制)

如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N=1e5+10,M=N*31;//M为结点总数,最多可能为数的个数*每个数有31位
int a[N],tr[M][2],idx;
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int &s=tr[p][x>>i&1];
if(!s) s=++idx;
p=s;
}
}

int search(int x){
int p=0,res=0;
for(int i=30;i>=0;i--){
int s=x>>i&1;
if(tr[p][!s]){
res+=1<<i;
p=tr[p][!s];
}else p=tr[p][s];
}
return res;
}
insert(a[i]);//插入数
seach(a[i]);//查找所有数中与a[i]异或的结果最大的数

ac自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'

const int N=1e4+10,S=55,M=1e6+10;
//N表示匹配串单词数量,S表示匹配串单词最大长度,M表示原串长度
int n;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int ne[N*S];

void insert(){
int p=0;
for(int i=0;str[i];i++){
int t=str[i]-'a';
if(!tr[p][t]) tr[p][t]=++idx;
p=tr[p][t];
}
cnt[p]++;
}

void build(){
queue<int> q;
for(int i=0;i<26;i++){
if(tr[0][i]) q.push(tr[0][i]);
}
while(q.size()){
int t=q.front();
q.pop();
for(int i=0;i<26;i++){
int p=tr[t][i];
if(!p) tr[t][i]=tr[ne[t]][i];
else{
ne[p]=tr[ne[t]][i];
q.push(p);
}
}
}
}

void solve(){
memset(tr,0,sizeof tr);
memset(cnt,0,sizeof cnt);
memset(ne,0,sizeof ne);
idx=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>str;
insert();
}

build();

cin>>str;

int res=0;
for(int i=0,j=0;str[i];i++){
int t=str[i]-'a';
j=tr[j][t];

int p=j;
while(p){
res+=cnt[p];
cnt[p]=0;
p=ne[p];
}
}
cout<<res<<endl;
}

bool multi=true;

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int T=1;
if(multi) cin>>T;
while(T--){
solve();
}

return 0;
}

manacher

时间复杂度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char b[N];
int p[N];//p[i]表示{以i为中心的最长回文子串的长度+1}

void init(){
int k=0;
b[k++]='$',b[k++]='#';
for(int i=0;i<n;i++) b[k++]=a[i],b[k++]='#';
b[k++]='^';
n=k;
}

void manacher(){
int mr=0,mid;
for(int i=1;i<n;i++){
if(i<mr) p[i]=min(p[mid*2-i],mr-i);
else p[i]=1;
while(b[i-p[i]]==b[i+p[i]]) p[i]++;
if(i+p[i]>mr){
mr=i+p[i];
mid=i;
}
}
}

最小表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//获得字符串s的最小表示法
string get_min(string s){
s+=s;
int i=0,j=1;
while(i<n&&j<n){
int k=0;
while(k<n&&s[i+k]==s[j+k]) k++;
if(k==n) break;
if(s[i+k]>s[j+k]) i+=k+1;
else j+=k+1;
if(i==j) j++;
}
int k=min(i,j);
return s.substr(k,n);
}

计算几何

计算几何基础

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
/*----------计算几何模板----------*/
const double eps = 1e-8,pi = acos(-1.0),INF = 1e30;
int sgn(double x){ //判断x的大小
if(fabs(x) < eps) return 0; //x==0,返回0
else return x<0?-1:1; //x<0返回-1,x>0返回1
}
int dcmp(double x, double y){ //比较两个浮点数
if(fabs(x - y) < eps) return 0; //x==y,返回0
else return x<y ?-1:1; //x<y返回-1,x>y返回1
}
struct Point{
double x, y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator+(Point B){return Point(x+B.x,y+B.y);}
Point operator-(Point B){return Point(x-B.x,y-B.y);}
Point operator*(double k){return Point(x*k,y*k);}
Point operator/(double k){return Point(x/k,y/k);}
bool operator==(Point B){return sgn(x-B.x)==0&&sgn(y-B.y)==0;}
bool operator < (Point B){ //用于sort()排序,先按x排序,再按y排序
return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);
}
};
typedef Point Vector;
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//向量点积
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//向量叉积
double Distance(Point A, Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//两点间距离
double Len(Vector A){return sqrt(Dot(A,A));}//向量长度
double Len2(Vector A){return Dot(A,A);}//向量长度的平方
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));}//向量A与B的夹角
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}//以A,B,C三点构成的平行四边形的面积
Vector Rotate(Vector A, double rad){//将向量A逆时针旋转角度rad
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A){return Vector(-A.y/Len(A), A.x/Len(A));}//求向量A的单位法向量(逆时针)
bool Parallel(Vector A, Vector B){return sgn(Cross(A,B)) == 0;}//判断两个向量是否平行或重合

struct Line{
Point p1,p2; //(1)线上的两个点
Line(){}
Line(Point p1,Point p2):p1(p1),p2(p2){}
Line(Point p,double angle){ //(4)根据一个点和倾斜角 angle 确定直线,0<=angle<pi
p1 = p;
if(sgn(angle - pi/2) == 0){p2 = (p1 + Point(0,1));}
else{p2 = (p1 + Point(1,tan(angle)));}
}
Line(double a,double b,double c){ //(2)ax+by+c=0
if(sgn(a) == 0){
p1 = Point(0,-c/b);
p2 = Point(1,-c/b);
}
else if(sgn(b) == 0){
p1 = Point(-c/a,0);
p2 = Point(-c/a,1);
}
else{
p1 = Point(0,-c/b);
p2 = Point(1,(-c-a)/b);
}
}
};
typedef Line Segment;
//点和直线的位置关系
int Point_line_relation(Point p, Line v){
int c = sgn(Cross(p-v.p1,v.p2-v.p1));
if(c < 0)return 1; //1:p在v的左边
if(c > 0)return 2; //2:p在v的右边
return 0; //0:p在v上
}
//点和线段:0 点不在线段v上;1 点在线段v上
bool Point_on_seg(Point p, Line v){
return sgn(Cross(p-v.p1, v.p2-v.p1)) == 0 && sgn(Dot(p-v.p1,p-v.p2)) <= 0;
}
//求点到直线的距离
double Dis_point_line(Point p,Line v){
return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
}
//点在直线上的投影
Point Point_line_proj(Point p, Line v){
double k = Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
return v.p1+(v.p2-v.p1)*k;
}
//点关于直线的对称点
Point Point_line_symmetry(Point p, Line v){
Point q = Point_line_proj(p,v);
return Point(2*q.x-p.x,2*q.y-p.y);
}
//点到线段的距离
double Dis_point_seg(Point p, Segment v){
if(sgn(Dot(p- v.p1,v.p2-v.p1))<0 || sgn(Dot(p- v.p2,v.p1-v.p2))<0)
return min(Distance(p,v.p1),Distance(p,v.p2));
return Dis_point_line(p,v); //点的投影在线段上
}
//两条直线的位置关系
int Line_relation(Line v1, Line v2){
if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1)) == 0){
if(Point_line_relation(v1.p1,v2)==0) return 1; //1 重合
else return 0; //0 平行
}
return 2; //2 相交
}
//两条直线的交点
Point Cross_point(Point a,Point b,Point c,Point d){ //Line1:ab, Line2:cd
double s1 = Cross(b-a,c-a);
double s2 = Cross(b-a,d-a); //叉积有正负
return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}
//两个线段是否相交
bool Cross_segment(Point a,Point b,Point c,Point d){ //Line1:ab, Line2:cd
double c1 = Cross(b-a,c-a),c2=Cross(b-a,d-a);
double d1 = Cross(d-c,a-c),d2=Cross(d-c,b-c);
return sgn(c1)*sgn(c2) < 0 && sgn(d1)*sgn(d2) < 0; //1相交;0不相交
}
//点和多边形的关系
int Point_in_polygon(Point pt,Point *p,int n){ //点pt,多边形Point *p
for(int i = 0;i < n;i++){ //3:点在多边形的顶点上
if(p[i] == pt) return 3;
}
for(int i = 0;i < n;i++){ //2:点在多边形的边上
Line v=Line(p[i],p[(i+1)%n]);
if(Point_on_seg(pt,v)) return 2;
}
int num = 0;
for(int i = 0;i < n;i++){
int j = (i+1)% n;
int c = sgn(Cross(pt-p[j],p[i]-p[j]));
int u = sgn(p[i].y - pt.y);
int v = sgn(p[j].y - pt.y);
if(c > 0 && u < 0 && v >=0) num++;
if(c < 0 && u >=0 && v < 0) num--;
}
return num != 0; //1:点在内部; 0:点在外部
}
//多边形的面积
double Polygon_area(Point *p, int n){ //Point *p表示多边形
double area = 0;
for(int i = 0;i < n;i++)
area += Cross(p[i],p[(i+1)%n]);
return area/2; //面积有正负,返回时不能简单地取绝对值
}
Point Polygon_center(Point *p, int n){ //求多边形重心
Point ans(0,0);
if(Polygon_area(p,n)==0) return ans;
for(int i = 0;i < n;i++)
ans = ans+(p[i]+p[(i+1)%n])*Cross(p[i],p[(i+1)%n]);
return ans/Polygon_area(p,n)/6;
}
//Convex_hull()求凸包。凸包顶点放在ch中,返回值是凸包的顶点数
int Convex_hull(Point *p,int n,Point *ch){
n = unique(p,p+n)-p; //去除重复点
sort(p,p+n); //对点排序:按x从小到大排序,如果x相同,按y排序
int v=0;
//求下凸包。如果p[i]是右拐弯的,这个点不在凸包上,往回退
for(int i=0;i<n;i++){
while(v>1 && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0) //把后面ch[v-1]改成ch[v-2]也行
v--;
ch[v++]=p[i];
}
int j=v;
//求上凸包
for(int i=n-2;i>=0;i--){
while(v>j && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0) //把后面ch[v-1]改成ch[v-2]也行
v--;
ch[v++]=p[i];
}
if(n>1) v--;
return v; //返回值v是凸包的顶点数
}
//返回p[left]~p[right]的平面最近点对距离
double Get_Closest_Pair(Point p[],int left,int right){
sort(p+left,p+right+1,[](Point A,Point B){
return sgn(A.x-B.x)<0 || (sgn(A.x-B.x)==0 && sgn(A.y-B.y)<0);
});
vector<Point> tmp_p(right-left+10);
function<double(int,int)> Closest_Pair=[&](int left,int right){
double dis = INF;
if(left == right) return dis; //只剩1个点
if(left + 1 == right) return Distance(p[left], p[right]);//只剩2个点
int mid = (left+right)/2; //分治
double d1 = Closest_Pair(left,mid); //求s1内的最近点对
double d2 = Closest_Pair(mid+1,right); //求s2内的最近点对
dis = min(d1,d2);
int k = 0;
for(int i=left;i<=right;i++) //在s1和s2中间附近找可能的最小点对
if(fabs(p[mid].x - p[i].x) <= dis) //按x坐标来找
tmp_p[k++] = p[i];
sort(&tmp_p[0],&tmp_p[k],[](Point A,Point B){return sgn(A.y-B.y)<0;}); //按y坐标排序,用于剪枝。这里不能按x坐标排序
for(int i=0;i<k;i++)
for(int j=i+1;j<k;j++){
if(tmp_p[j].y - tmp_p[i].y >= dis) break; //剪枝
dis = min(dis,Distance(tmp_p[i],tmp_p[j]));
}
return dis; //返回最小距离
};
return Closest_Pair(left,right);
}

struct HLine{
Point p; //直线上一个点
Vector v; //方向向量,它的左边是半平面
double ang; //极角,从x正半轴旋转到v的角度
HLine(){};
HLine(Point p, Vector v):p(p),v(v){ang = atan2(v.y, v.x);}
bool operator < (HLine &L){return ang < L.ang;} //用于排序
};
//点p在线L左边,即点p在线L在外面:
bool OnLeft(HLine L,Point p){return sgn(Cross(L.v,p-L.p))>0;}
Point Cross_point(HLine a,HLine b){ //两直线交点
Vector u=a.p-b.p;
double t=Cross(b.v,u)/Cross(a.v,b.v);
return a.p+a.v*t;
}
vector<Point> HPI(vector<HLine> L){ //求半平面交,返回凸多边形
int n=L.size();
sort(L.begin(),L.end()); //将所有半平面按照极角排序。
int first,last; //指向双端队列的第一个和最后一个元素
vector<Point> p(n); //两个相邻半平面的交点
vector<HLine> q(n); //双端队列
vector<Point> ans; //半平面交形成的凸包
q[first=last=0]=L[0];
for(int i=1;i<n;i++){
//情况1:删除尾部的半平面
while(first<last && !OnLeft(L[i], p[last-1])) last--;
//情况2:删除首部的半平面:
while(first<last && !OnLeft(L[i], p[first])) first++;
q[++last]=L[i]; //将当前的半平面加入双端队列尾部
//极角相同的两个半平面,保留左边:
if(fabs(Cross(q[last].v,q[last-1].v)) < eps){
last--;
if(OnLeft(q[last],L[i].p)) q[last]=L[i];
}
//计算队列尾部半平面交点:
if(first<last) p[last-1]=Cross_point(q[last-1],q[last]);
}
//情况3:删除队列尾部的无用半平面
while(first<last && !OnLeft(q[first],p[last-1])) last--;
if(last-first<=1) return ans; //空集
p[last]=Cross_point(q[last],q[first]); //计算队列首尾部的交点。
for(int i=first;i<=last;i++) ans.push_back(p[i]); //复制。
return ans; //返回凸多边形
}
struct Circle{
Point c; //圆心
double r; //半径
Circle(){}
Circle(Point c,double r):c(c),r(r){}
Circle(double x,double y,double _r){c=Point(x,y);r = _r;}
};
//点与圆的关系
int Point_circle_relation(Point p, Circle C){
double dst = Distance(p,C.c);
if(sgn(dst - C.r) < 0) return 0; //0 点在圆内
if(sgn(dst - C.r) ==0) return 1; //1 圆上
return 2; //2 圆外
}
//直线与圆的关系
int Line_circle_relation(Line v,Circle C){
double dst = Dis_point_line(C.c,v);
if(sgn(dst-C.r) < 0) return 0; //0 直线和圆相交
if(sgn(dst-C.r) ==0) return 1; //1 直线和圆相切
return 2; //2 直线在圆外
}
//线段与圆的关系
int Seg_circle_relation(Segment v,Circle C){
double dst = Dis_point_seg(C.c,v);
if(sgn(dst-C.r) < 0) return 0; //0线段在圆内
if(sgn(dst-C.r) ==0) return 1; //1线段和圆相切
return 2; //2线段在圆外
}
//pa, pb是交点。返回值是交点个数
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
if(Line_circle_relation(v, C)==2) return 0;//无交点
Point q = Point_line_proj(C.c,v); //圆心在直线上的投影点
double d = Dis_point_line(C.c,v); //圆心到直线的距离
double k = sqrt(C.r*C.r-d*d);
if(sgn(k) == 0){ //1个交点,直线和圆相切
pa = q; pb = q; return 1;
}
Point n=(v.p2-v.p1)/ Len(v.p2-v.p1); //单位向量
pa = q + n*k; pb = q - n*k;
return 2; //2个交点
}
//三点确定圆心
Point circle_center(const Point a, const Point b, const Point c){
Point center;
double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;
double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;
double d =a1*b2-a2*b1;
center.x =a.x+(c1*b2-c2*b1)/d;
center.y =a.y+(a1*c2-a2*c1)/d;
return center;
}
//求最小圆覆盖
void min_cover_circle(Point *p, int n, Circle &C){
random_shuffle(p, p + n); //随机函数,打乱所有点。这一步很重要
Point c=p[0];
double r=0; //从第1个点p0开始。圆心为p0,半径为0
for(int i=1;i<n;i++) //扩展所有点
if(sgn(Distance(p[i],c)-r)>0){ //点pi在圆外部
c=p[i]; r=0; //重新设置圆心为pi,半径为0
for(int j=0;j<i;j++) //重新检查前面所有的点。
if(sgn(Distance(p[j],c)-r)>0){ //两点定圆
c.x=(p[i].x + p[j].x)/2;
c.y=(p[i].y + p[j].y)/2;
r=Distance(p[j],c);
for(int k=0;k<j;k++)
if (sgn(Distance(p[k],c)-r)>0){ //两点不能定圆,就三点定圆
c=circle_center(p[i],p[j],p[k]);
r=Distance(p[i], c);
}
}
}
C={c,r};
}

struct Point3{ //三维点
double x,y,z;
Point3(){}
Point3(double x,double y,double z):x(x),y(y),z(z){}
Point3 operator + (Point3 B){return Point3(x+B.x,y+B.y,z+B.z);}
Point3 operator - (Point3 B){return Point3(x-B.x,y-B.y,z-B.z);}
Point3 operator * (double k){return Point3(x*k,y*k,z*k);}
Point3 operator / (double k){return Point3(x/k,y/k,z/k);}
bool operator == (Point3 B){ return sgn(x-B.x)==0 && sgn(y-B.y)==0 && sgn(z-B.z)==0;}
};
typedef Point3 Vector3; //三维向量
double Distance(Vector3 A,Vector3 B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)+ (A.z-B.z)*(A.z-B.z));
}
struct Line3{
Point3 p1,p2;
Line3(){}
Line3(Point3 p1,Point3 p2):p1(p1),p2(p2){}
};
typedef Line3 Segment3; //定义线段,两端点是Point p1,p2
//三维点积
double Dot(Vector3 A,Vector3 B){return A.x*B.x+A.y*B.y+A.z*B.z;}
//求向量A的长度
double Len(Vector3 A){ return sqrt(Dot(A, A));}
//求向量A的长度的平方
double Len2(Vector3 A){ return Dot(A, A);}
//求向量A与B的夹角
double Angle(Vector3 A,Vector3 B){return acos(Dot(A,B)/Len(A)/Len(B));}
//三维叉积
Vector3 Cross(Vector3 A,Vector3 B){
return Point3(A.y*B.z-A.z*B.y, A.z*B.x-A.x*B.z, A.x*B.y-A.y*B.x);
}
//求三个点构成的三角形面积的2倍
double Area2(Point3 A,Point3 B,Point3 C){return Len(Cross(B-A, C-A));}
//三维:点在直线上
bool Point_line_relation(Point3 p,Line3 v){
return sgn( Len(Cross(v.p1-p,v.p2-p))) == 0 && sgn(Dot(v.p1-p,v.p2-p))== 0;
}
double Dis_point_line(Point3 p, Line3 v) //三维:点到直线距离
{ return Len(Cross(v.p2-v.p1,p-v.p1))/Distance(v.p1,v.p2); }
//三维:点到线段距离。
double Dis_point_seg(Point3 p, Segment3 v){
if(sgn(Dot(p- v.p1,v.p2-v.p1)) < 0 || sgn(Dot(p- v.p2,v.p1-v.p2)) < 0)
return min(Distance(p,v.p1),Distance(p,v.p2));
return Dis_point_line(p,v);
}
//三维:点 p 在直线上的投影
Point3 Point_line_proj(Point3 p, Line3 v){
double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
return v.p1+(v.p2-v.p1)*k;
}
struct Plane{
Point3 p1,p2,p3; //平面上的三个点
Plane(){}
Plane(Point3 p1,Point3 p2,Point3 p3):p1(p1),p2(p2),p3(p3){}
};
//平面的法向量
Point3 Pvec(Point3 A, Point3 B, Point3 C){return Cross(B-A,C-A);}
Point3 Pvec(Plane f){return Cross(f.p2-f.p1,f.p3-f.p1);}
//四点共平面
bool Point_on_plane(Point3 A,Point3 B,Point3 C,Point3 D){
return sgn(Dot(Pvec(A,B,C),D-A)) == 0;
}
//两平面平行
int Parallel(Plane f1, Plane f2){ return Len(Cross(Pvec(f1),Pvec(f2))) < eps; }
//两平面垂直
int Vertical(Plane f1, Plane f2){ return sgn(Dot(Pvec(f1),Pvec(f2)))==0; }
//直线与平面的交点
int Line_cross_plane(Line3 u,Plane f,Point3 &p){
Point3 v = Pvec(f); //平面的法向量
double x = Dot(v, u.p2-f.p1);
double y = Dot(v, u.p1-f.p1);
double d = x-y;
if(sgn(x) == 0 && sgn(y) == 0) return -1; //-1:v在f上
if(sgn(d) == 0) return 0; //0:v与f平行
p = ((u.p1 * x)-(u.p2 * y))/d; //v与f相交
return 1;
}
//四面体有向体积*6
double volume4(Point3 a,Point3 b,Point3 c,Point3 d){
return Dot(Cross(b-a,c-a),d-a); }
//最小球覆盖
double min_cover_ball(Point3 *p, int n){
double T=100.0; //初始温度
double delta = 0.98; //降温系数
Point3 c = p[0]; //球心
int pos;
double r; //半径
while(T>eps) { //eps是终止温度
pos = 0; r = 0; //初始:p[0]是球心,半径是0
for(int i=0; i<n; i++) //迭代:找距离球心最远的点
if(Distance(c,p[i])>r){
r = Distance(c,p[i]); //距离球心最远的点肯定在球周上
pos = i;
}
c.x += (p[pos].x-c.x)/r*T; //逼近最后的解
c.y += (p[pos].y-c.y)/r*T;
c.z += (p[pos].z-c.z)/r*T;
T *= delta; //降温
}
return r;
}
/*----------计算几何模板----------*/

自适应辛普森积分

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace SIMPSON{
double eps = 1e-12;
double f(double x){
//积分函数...
}
double simpson(double l, double r){
double mid = (l + r) / 2;
return (r - l) * (f(l) + 4 * f(mid) + f(r)) /6;
}
double asr(double l, double r, double s){
double mid = (l + r) / 2;
double left = simpson(l, mid), right = simpson(mid, r);
if(fabs(left + right - s) < eps) return left + right;
return asr(l, mid, left) + asr(mid, r, right);
}
double area(double l, double r){
return asr(l, r, simpson(l, r));
}
}
using namespace SIMPSON;

圆面积并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

/*----------计算几何模板----------*/
//省略
/*----------计算几何模板----------*/
const int N = 1010;
int n;
Circle c[N];
pair<double, double> q[N];
namespace SIMPSON{
double eps = 1e-8;
double f(double x){//f为积分函数
int cnt = 0;
for (int i = 0; i < n; i ++ )
{
auto X = fabs(x - c[i].c.x), R = c[i].r;
if (dcmp(X, R) < 0){
auto Y = sqrt(R * R - X * X);
q[cnt ++ ] = {c[i].c.y - Y, c[i].c.y + Y};
}
}
if(!cnt) return 0;
sort(q, q + cnt);
double res = 0, st = q[0].first, ed = q[0].second;
for(int i = 1; i < cnt; i++) {
if(q[i].first <= ed) ed = max(ed, q[i].second);
else {
res += ed - st;
st = q[i].first, ed = q[i].second;
}
}
return res + ed - st;
}
double simpson(double l, double r){
double mid = (l + r) / 2;
return (r - l) * (f(l) + 4 * f(mid) + f(r)) /6;
}
double asr(double l, double r, double s){
double mid = (l + r) / 2;
double left = simpson(l, mid), right = simpson(mid, r);
if(fabs(left + right - s) < eps) return left + right;
return asr(l, mid, left) + asr(mid, r, right);
}
double area(double l, double r){
return asr(l, r, simpson(l, r));
}
}
using namespace SIMPSON;
vector<pair<double, double>> segs;

void merge(vector<pair<double, double>> &segs){
sort(segs.begin(),segs.end());
vector<pair<double, double>> new_segs;
double l = -INF, r = -INF;
for (auto& seg: segs)
{
if (dcmp(seg.first, r) <= 0) r = max(r, seg.second);
else
{
if (dcmp(l, -INF)) new_segs.push_back({l, r});
l = seg.first, r = seg.second;
}
}
new_segs.push_back({l, r});
segs = new_segs;
}

bool multi = 0;
void solve() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> c[i].c.x >> c[i].c.y >> c[i].r;
c[i].c = Rotate(c[i].c, 1);//将坐标轴旋转任意角度,避免被卡
segs.push_back({c[i].c.x-c[i].r,c[i].c.x+c[i].r});//将每个圆投影到水平线上然后合并区间,求每个区间积分和。
}
merge(segs);
double res = 0;
for(auto &seg: segs) {
res += area(seg.first, seg.second);
}
cout << fixed << setprecision(12) << res << '\n';
}

signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}

return 0;
}

动态规划

Nim

定义$dp[u][m1][m2][m3][l1][l2][p1][p2][p3]$为取到第$u$位,取模$a1,a2,a3$的余数分别为$m1,m2,m3$,三个数是否受限($l1, l2, l3$), 三个数是否取过1,因为这题答案为0满足但不在题意范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

const int N = 66, mod = 998244353;
int dp[N][15][15][15][2][2][2][2][2][2];
int n, a1, a2, a3;
vector<int> nums;

bool multi = 0;

int dfs(int u, int m1, int m2, int m3, bool l1, bool l2, bool l3, bool p1, bool p2, bool p3) {
if(u == -1 && !m1 && !m2 && !m3 && p1 && p2 && p3) return 1;
else if(u == -1) return 0;
auto &w = dp[u][m1][m2][m3][l1][l2][l3][p1][p2][p3];
if(~w) return w;
int res = 0;
int t1 = l1 ? nums[u] : 1, t2 = l2 ? nums[u] : 1, t3 = l3 ? nums[u] : 1;
for(int i1 = 0; i1 <= t1; i1++) {
for(int i2 = 0; i2 <= t2; i2++) {
int i3 = i1 ^ i2;
if(i3 > t3) continue;
res = (res + dfs(u - 1, (m1 * 2 + i1) % a1, (m2 * 2 + i2) % a2, (m3 * 2 + i3) % a3, l1 & (i1 == nums[u]), l2 & (i2 == nums[u]), l3 & (i3 == nums[u]), i1 | p1, i2 | p2, i3 | p3)) % mod;
}
}
return w = res;
}

void solve() {
cin >> n >> a1 >> a2 >> a3;
while(n) nums.push_back(n % 2), n /= 2;
memset(dp, -1, sizeof dp);
cout << dfs((int)nums.size() - 1, 0, 0, 0, 1, 1, 1, 0, 0, 0) << '\n';
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

恨7不成妻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 1;

const int N = 67, mod = 1e9 + 7;
vector<int> nums;

int p10[20];

void init() {
p10[0] = 1;
for(int i = 1; i <= 20; i++) {
p10[i] = (p10[i - 1] * 10) % mod;
}
}

struct Node {
int sum, sum2, cnt;
};

Node dp[N][20][75][2];

Node dfs(int u, int m1, int m2, bool lim) {
if(u == -1) {
if(m1 && m2) return (Node){0, 0, 1};
else return (Node){0, 0, 0};
}
auto &w = dp[u][m1][m2][lim];
if(~w.sum) return w;
Node res = {0, 0, 0};
int tot = lim ? nums[u] : 9;
for(int i = 0; i <= tot; i++) {
if(i == 7) continue;
auto t = dfs(u - 1, (m1 + i) % 7, (m2 * 10 + i) % 7, lim & (i == nums[u]));
res.sum = (res.sum + i * t.cnt % mod * p10[u] % mod + t.sum) % mod, res.cnt = (res.cnt + t.cnt) % mod;
res.sum2 = (res.sum2 + t.cnt * (i * p10[u] % mod) % mod * (i * p10[u] % mod) % mod + 2 * i * p10[u] % mod * t.sum % mod + t.sum2) % mod;
}
return w = res;
}

Node get(int x) {
nums.clear();
memset(dp, -1, sizeof dp);
while(x) nums.push_back(x % 10), x /= 10;
auto t = dfs((int)nums.size() - 1, 0, 0, 1);
return t;
}

void solve() {
int l, r;
cin >> l >> r;
cout << ((get(r).sum2 - get(l - 1).sum2) % mod + mod) % mod<< '\n';
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

init();

int T = 1;
if (multi) cin >> T;
while (T--) {
solve();
}

return 0;
}

杂项

预备板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi = 0;

void solve() {

}

signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
if(fopen("in.txt","r")){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
int T = 1;
if(multi) cin >> T;
while(T--) {
solve();
}
return 0;
}

对拍

duipai.bat

1
2
3
4
5
6
7
8
9
10
11
12
g++ baoli.cpp -o baoli
g++ std.cpp -o std
g++ make.cpp -o make

:loop
make.exe>make.txt
std.exe<make.txt>std.txt
baoli.exe<make.txt>baoli.txt
fc std.txt baoli.txt
if %errorlevel%==0 goto loop
pause
goto loop

make.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
#define endl '\n'

int rd(int l,int r){
int k=l;
r++;
k+=(1.0*rand()/RAND_MAX)*(r-l);
return k;
}

void make() {
int n = rd(2, 4), m = rd(1, 4);
cout << n << ' ' << m << '\n';
for(int i = 1; i <= m; i++) {
int l = rd(1, n - 1), r = rd(l + 1, n);
cout << l << ' ' << r << '\n';
}
}

signed main(){
srand(time(0));
make();
return 0;
}

自动取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
template<class T>
constexpr T power(T a, long long b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}

constexpr long long mul(long long a, long long b, long long p) {
long long res = a * b - (long long)(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<long long P>
struct MLong {
long long x;
constexpr MLong() : x{} {}
constexpr MLong(long long x) : x{norm(x % getMod())} {}

static long long Mod;
constexpr static long long getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(long long Mod_) {
Mod = Mod_;
}
constexpr long long norm(long long x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr long long val() const {
return x;
}
explicit constexpr operator long long() const {
return x;
}
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
long long v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};

template<>
long long MLong<0LL>::Mod = (long long)(1E18) + 9;

template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(long long x) : x{norm(x % getMod())} {}

static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
long long v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;//模数
using Z = MInt<P>;

高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
vector<int> a;
int sign;

bigint() :
sign(1) {
}

bigint(long long v) {
*this = v;
}

bigint(const string &s) {
read(s);
}

void operator=(const bigint &v) {
sign = v.sign;
a = v.a;
}

void operator=(long long v) {
sign = 1;
if (v < 0)
sign = -1, v = -v;
for (; v > 0; v = v / base)
a.push_back(v % base);
}

bigint operator+(const bigint &v) const {
if (sign == v.sign) {
bigint res = v;

for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
if (i == (int) res.a.size())
res.a.push_back(0);
res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
carry = res.a[i] >= base;
if (carry)
res.a[i] -= base;
}
return res;
}
return *this - (-v);
}

bigint operator-(const bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
bigint res = *this;
for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
carry = res.a[i] < 0;
if (carry)
res.a[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}

void operator*=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
if (i == (int) a.size())
a.push_back(0);
long long cur = a[i] * (long long) v + carry;
carry = (int) (cur / base);
a[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
}

bigint operator*(int v) const {
bigint res = *this;
res *= v;
return res;
}

friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
int norm = base / (b1.a.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize(a.a.size());

for (int i = a.a.size() - 1; i >= 0; i--) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ((long long) base * s1 + s2) / b.a.back();
r -= b * d;
while (r < 0)
r += b, --d;
q.a[i] = d;
}

q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
}

bigint operator/(const bigint &v) const {
return divmod(*this, v).first;
}

bigint operator%(const bigint &v) const {
return divmod(*this, v).second;
}

void operator/=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
long long cur = a[i] + rem * (long long) base;
a[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
}

bigint operator/(int v) const {
bigint res = *this;
res /= v;
return res;
}

int operator%(int v) const {
if (v < 0)
v = -v;
int m = 0;
for (int i = a.size() - 1; i >= 0; --i)
m = (a[i] + m * (long long) base) % v;
return m * sign;
}

void operator+=(const bigint &v) {
*this = *this + v;
}
void operator-=(const bigint &v) {
*this = *this - v;
}
void operator*=(const bigint &v) {
*this = *this * v;
}
void operator/=(const bigint &v) {
*this = *this / v;
}

bool operator<(const bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (a.size() != v.a.size())
return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i])
return a[i] * sign < v.a[i] * sign;
return false;
}

bool operator>(const bigint &v) const {
return v < *this;
}
bool operator<=(const bigint &v) const {
return !(v < *this);
}
bool operator>=(const bigint &v) const {
return !(*this < v);
}
bool operator==(const bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint &v) const {
return *this < v || v < *this;
}

void trim() {
while (!a.empty() && !a.back())
a.pop_back();
if (a.empty())
sign = 1;
}

bool isZero() const {
return a.empty() || (a.size() == 1 && !a[0]);
}

bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}

bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}

long long longValue() const {
long long res = 0;
for (int i = a.size() - 1; i >= 0; i--)
res = res * base + a[i];
return res * sign;
}

friend bigint gcd(const bigint &a, const bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend bigint lcm(const bigint &a, const bigint &b);

void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}

friend istream& operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}

friend ostream& operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1)
stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
for (int i = (int) v.a.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.a[i];
return stream;
}

static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < (int) p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int i = 0; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back((int)(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && !res.back())
res.pop_back();
return res;
}

typedef vector<long long> vll;

static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= 32) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}

int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());

vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);

for (int i = 0; i < k; i++)
a2[i] += a1[i];
for (int i = 0; i < k; i++)
b2[i] += b1[i];

vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i];

for (int i = 0; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = 0; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
}

bigint operator*(const bigint &v) const {
vector<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> b6 = convert_base(v.a, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
while (a.size() & (a.size() - 1))
a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.a.push_back((int) (cur % 1000000));
carry = (int) (cur / 1000000);
}
res.a = convert_base(res.a, 6, base_digits);
res.trim();
return res;
}
};

离散化

1
2
3
4
5
vector<int> nums;
//下标从1开始
inline int get(int x){return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1;}
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());

随机

爬山法

模拟退火

二维平面上给定n个点,求这个平面上任选一点到这个n个点的最小距离和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double MAX_TIME=0.8;
bool multi=0;
typedef pair<double,double> PDD;
#define x first
#define y second
const int N=110;
int n;
PDD q[N];
double ans=1e8;

double rand(double l,double r){
return (double)rand()/RAND_MAX*(r-l)+l;
}

double get_dist(PDD a,PDD b){
double dx=a.x-b.x;
double dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}

double calc(PDD p){
double res=0;
for(int i=0;i<n;i++){
res+=get_dist(p,q[i]);
}
ans=min(res,ans);
return res;
}

void simulate_anneal(){
PDD cur(rand(0,10000),rand(0,10000));
for(double t=1e4;t>=1e-4;t*=0.99){
PDD np(rand(cur.x-t,cur.x+t),rand(cur.y-t,cur.y+t));
double dt=calc(np)-calc(cur);
if(exp(-dt/t)>rand(0,1)) cur=np;
}
}

void solve(){
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i].x>>q[i].y;
}
while((double)clock()/CLOCKS_PER_SEC<MAX_TIME) simulate_anneal();
cout<<fixed<<setprecision(0)<<ans<<endl;
}

signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT=1;
if(multi) cin>>TTT;
while(TTT--){
solve();
}

return 0;
}

读写相关

__int128读写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline __int128 read()
{
__int128 X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}

inline void print(__int128 x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}

快读快写

版本1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct read {
static const int M = 1 << 23;
char buf[M], *S = buf, *P = buf, c, l;
inline char gc() {
return (S == P && (P = (S = buf) + fread(buf, 1, M, stdin), S == P) ? EOF : *S++);
}
template<typename T> read &operator>>(T &x) {
for (c = 0; !isdigit(c); c = gc())
l = c;

for (x = 0; isdigit(c); c = gc())
x = x * 10 + c - '0';

return x = (l ^ 45) ? x : -x, *this;
}
} in;

版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline int read() { 
char c = getchar();
int x = 0, f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void out(int x){
if(x>9) out(x/10);
putchar(x%10+'0');
}

10进制转x进制

1
2
3
4
5
6
7
8
9
10
11
12
13
string dict = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string ten_to_x(int n, int x) //十进制转 x 进制函数。
{
string ans = "";
while (n != 0)
{
ans += dict[n % x];
n /= x;
}
string t = "";
for (int i = ans.length()-1; i >= 0; i--) t += ans[i];
return t;
}