这是一篇模板的整理
慢慢积累吧qwq
窝可以的！！
1 | inline int read(){ |
数据结构
树状数组
1 |
|
线段树
1 |
|
树链剖分
https://www.luogu.com.cn/problem/P33841
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
using namespace std;
typedef long long ll;
const int N=100000;
//父亲节点，节点深度，子树节点个数，重儿子，所在链的顶端节点，节点dfs序，dfs序所对节点编号
int fa[N+10],dep[N+10],sz[N+10],son[N+10],top[N+10],seg[N+10],rev[N+10];
int n,m,root;
ll p,num[N+10],add[4*N+10],sum[4*N+10];
int tot=1,head[N+10];
struct EDGE{
int to,nxt;
}edge[2*N+10];
void add_edge(int u,int v){
edge[++tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}
void dfs1(int x,int f){ //当前节点，父亲节点
sz[x]=1;
fa[x]=f;
dep[x]=dep[f]+1;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y!=f){
dfs1(y,x);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
}
void dfs2(int x,int t){ //当前节点，重链顶端
top[x]=t;
seg[x]=++seg[0];
rev[seg[0]]=x;
if(!son[x]) return;
dfs2(son[x],t);
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
void build(int k,int l,int r){
if(l==r){
sum[k]=num[rev[l]];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}
void pushdown(int k,int l,int r){
if(!add[k]) return;
int mid=(l+r)>>1;
sum[k<<1]=(sum[k<<1]+add[k]*(mid-l+1))%p;
add[k<<1]=(add[k<<1]+add[k])%p;
sum[k<<1|1]=(sum[k<<1|1]+add[k]*(r-mid))%p;
add[k<<1|1]=(add[k<<1|1]+add[k])%p;
add[k]=0;
}
void ask_add(int k,int l,int r,int ql,int qr,ll d){
if(ql<=l&&r<=qr){
add[k]=(add[k]+d)%p;
sum[k]=(sum[k]+d*(r-l+1))%p;
return;
}
pushdown(k,l,r);
int mid=(l+r)>>1;
if(ql<=mid) ask_add(k<<1,l,mid,ql,qr,d);
if(qr>=mid+1) ask_add(k<<1|1,mid+1,r,ql,qr,d);
sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}
ll ask_sum(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return sum[k];
}
pushdown(k,l,r);
int mid=(l+r)>>1;
ll val=0;
if(ql<=mid) val=(val+ask_sum(k<<1,l,mid,ql,qr))%p;
if(qr>=mid+1) val=(val+ask_sum(k<<1|1,mid+1,r,ql,qr))%p;
return val;
}
ll ask_path(int x,int y,ll d){
ll val=0;
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]>dep[fy]) swap(x,y),swap(fx,fy);
if(d==0) val=(val+ask_sum(1,1,seg[0],seg[fy],seg[y]))%p;
else ask_add(1,1,seg[0],seg[fy],seg[y],d);
y=fa[fy];fy=top[y];
}
if(dep[x]>dep[y]) swap(x,y);
if(d==0){//求和
val=(val+ask_sum(1,1,seg[0],seg[x],seg[y]))%p;
return val;
}
else{//给x到y所有节点都加d
ask_add(1,1,seg[0],seg[x],seg[y],d);
return 0;
}
}
int main(){
scanf("%d%d%d%lld",&n,&m,&root,&p);
for(int i=1;i<=n;++i){
scanf("%lld",&num[i]);
num[i]%=p;
}
for(int i=1;i<=n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y),add_edge(y,x);
}
dfs1(root,0);
dfs2(root,root);
build(1,1,seg[0]);
for(int i=1;i<=m;i++){
int t;
scanf("%d",&t);
if(t==1){ //1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
int x,y;ll z;
scanf("%d%d%lld",&x,&y,&z);
if(z==0) continue;
ask_path(x,y,z%p);
}
if(t==2){ //2 x y 表示求树从x到y结点最短路径上所有节点的值之和
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",ask_path(x,y,0));
}
if(t==3){ // 3 x z 表示将以x为根节点的子树内所有节点值都加上z
int x;ll z;
scanf("%d%lld",&x,&z);
ask_add(1,1,seg[0],seg[x],seg[x]+sz[x]-1,z%p);
}
if(t==4){ //4 x 表示求以x为根节点的子树内所有节点值之和
int x;
scanf("%d",&x);
printf("%lld\n",ask_sum(1,1,seg[0],seg[x],seg[x]+sz[x]-1));
}
}
return 0;
}
图论
并查集
1 | int find(int x)//找父节点 |
最短路
dijkstra+堆优化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
using namespace std;
const int maxn=2e5+5;
int first[maxn],next[maxn],d[maxn],tot=0;
bool used[maxn];
struct edge{
int from,to,cost;
}es[maxn];
struct node{
int num,d;
};
bool operator <(node a,node b){
return a.d>b.d;
}
priority_queue<node> q;
void init(){
memset(first,-1,sizeof(first));
memset(d,0x3f,sizeof(d));
memset(used,0,sizeof(used));
tot=0;
}
void build(int f,int t,int d){
es[++tot]=(edge){f,t,d};
next[tot]=first[f];
first[f]=tot;
}
void dijkstra(int s){
q.push((node){s,0});
d[s]=0;
used[s]=1;
while(!q.empty()){
int now=q.top().num;
int dist=q.top().d;
q.pop();
used[now]=1;
for(int i=first[now];i!=-1;i=next[i]){
int v=es[i].to;
if(d[v]>d[now]+es[i].cost){
d[v]=d[now]+es[i].cost;
if(!used[v]) q.push((node){v,d[v]});
}
}
}
}
int main(){
init();
int t,c,ts,te;
scanf("%d%d%d%d",&t,&c,&ts,&te);
for(int i=1;i<=c;i++){
int f,t,d;
scanf("%d%d%d",&f,&t,&d);
build(f,t,d);
build(t,f,d);
}
dijkstra(ts);
cout<<d[te];
return 0;
}
tarjan缩点+拓扑排序
1 |
|
二分图
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6808
dinic+离散化，复杂度$O(n\sqrt n)$
1 |
|
网络流
dinic
1 |
|
数论
威尔逊定理
$(p−1)!≡−1(mod p)$当且仅当$p$为素数时成立；
扩展欧拉函数
令$m=2^{2^{2^{…}}}$，即求$m%p$。
考虑到m和p不一定互质，易想到扩展欧拉函数：
因此，令$f(p)=m\%p$，则有
于是可以递归求解，复杂度约为$O(\sqrt p * \log p)$
gcd
1 | int gcd(int a,int b){ |
exgcd
1 | ll exgcd(ll l,ll r,ll &x,ll &y) |
快速幂取模
1 | int qpow(int a,int b,int mod){ |
逆元
1 | int inv(int a) { |
线性求组合数
1 | inline void init(ll n){ |
判断素数
暴力判断 复杂度$O(\sqrt n)$1
2
3
4
5
6int Prime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}
欧拉筛 复杂度$O(n)$1
2
3
4
5
6
7
8
9
10
11
12
13bool isPrime[n];
vector<int> prime;
int Prime(int n){
for(int i=2;i<=n;i++){
if(isPrime[i]) prime.push_back(i);
for(int j=0;j<prime.size();j++){
if(i*prime[j]>n) break;
isPrime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}
欧拉函数
暴力求 复杂度$O(\sqrt(n))$1
2
3
4
5
6
7
8
9int phi(int x){
int ret=x;
for(int i=2;i*i<=x;i++){
if(x%i==0) ret-=ret/i;
while(x%i==0) x/=i;
}
if(x>1) ret-=ret/x;
return ret;
}
线性筛 复杂度$O(n)$1
2
3
4
5
6
7
8void Euler(){
phi[1]=1;
for(int i=2;i<MAXN;i++) phi[i]=i;
for(int i=2;i<MAXN;i++){
if(phi[i]==i)
for(int j=i;j<MAXN;j+=i) phi[j]-=phi[j]/i;
}
}
min25筛
1 |
|
中国剩余定理
1 |
|
线性基
1 |
|
计算几何
极角排序
1 | struct node{ |
圆的反演
hdu6097
1 |
|
字符串
KMP
1 |
|
扩展kmp
1 |
|
马拉车
1 |
|
trie树
1 |
|
01trie树
1 | //01trie树处理异或最值问题 |
ac自动机
1 |
|