自用模板积累（持续更新）
前言
带*为下标从1开始，否则为从0开始
常用框架
//<iomanip><sstream><queue>
#define ll long long
#define vec vector<ll>
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define x first
#define y second
#define mk make_pair
#define pii pair<ll,ll>
#define db(x) cout<<(#x)<<':'<<(x)
//线段树宏定义可能弃用
#define tinfo ll rt,ll l,ll r
#define sl rt<<1,l,mid
#define sr rt<<1|1,mid+1,r
#define mid (l+r>>1)<<endl;
const double pi=acos(-1.0);
void INIT() {
}
void solve() {
}
int main() {
#ifndef ONLINE_JUDGE
while(true)
#endif
{
#ifndef ONLINE_JUDGE
INIT();
#endif
// ll t;
// scanf("%lld",&t);
// while(t--)
solve();
}
return 0;
}
基础算法
快速排序*
void qsort(ll l,ll r)
{
if(l>=r) return;
ll val=arr[l],p=l,q=r;
while(p<q)
{
while(p<q&&arr[q]>val) q--;
if(p<q){
arr[p]=arr[q];p++;}
while(p<q&&arr[p]<val) p++;
if(p<q){
arr[q]=arr[p];q--;}
}
arr[p]=val;
qsort(l,p-1);
//if(m-1>p) 求第m小数
qsort(p+1,r);
}
并查集
无权+路径压缩+启发式合并
ll find(ll x) {
return x==pre[x]?x:pre[x]=find(pre[x]);}
void merge(ll u,ll v) {
ll fu=find(u),fv=find(v);
if(height[fu]>height[fv]) pre[fv]=fu;
else pre[fu]=fv;
if(height[fu]==height[fv]) ++height[fv];
}
带权+路径压缩
ll find(ll x) {
if(x==pre[x]) return x;
ll fx=pre[x];
pre[x]=find(pre[x]);
val[x]+=val[fx];
return pre[t];
}
void unionn(ll a,ll b,ll value) {
ll fa=pre[a],fb=pre[b];
val[fa]=val[b]+value-val[a];
pre[fa]=fb;
}
高精度（输入输出均为逆序字符串）
加/乘 通用模板
string [add@mult](string aa,string bb) {
int cnta=aa.length(),cntb=bb.length(),cntc=[max(cnta,cntb)+1@cnta+cntb+1];
int a[N],b[N],c[N];
clr(a,0);clr(b,0);clr(c,0);
rep(i,0,cnta) a[i]=aa[i]-'0';
rep(i,0,cntb) b[i]=bb[i]-'0';
[rep(i,0,cntc) c[i]=a[i]+b[i];@
rep(i,0,cnta) rep(j,0,cntb) c[i+j]+=a[i]*b[j];]
ll t=0;
rep(i,0,cntc) {
c[i]+=t;
t=c[i]/10;
c[i]%=10;
}
while(c[cntc]==0&&cntc) --cntc;
string cc;
rep(i,0,cntc+1) cc+=c[i]+'0';
return cc;
}
数论
拓展欧几里得
ll exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {
x=1;
y=0;
return a;
}
ll t=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return t;
}
逆元（拓欧，最小非负整数解，特判）
//qpow(val,p-2)，费马小定理（val的逆元，p为质数）
//i^-1=-p/i*(p%i)^-1
ll inel(ll a,ll b,ll c,ll &x,ll &y) {
ll gcd=exgcd(a,b,x,y);
if(c%gcd!=0) return 0;
ll t;
if(b) {
t=b/gcd;
x=(x*c/gcd%t+abs(t))%t;
}
if(a) {
t=a/gcd;
y=(y*c/gcd%t+abs(t))%t;
}
return gcd;
}
质数
线性欧拉质数筛
bitset<N> notprime;
vec prime;
ll phi[N];
void getprime(ll n) {
phi[1]=1;
for(ll i=2; i<=n; ++i) {
if(!notprime[i]) {
prime.pb(i);
phi[i]=i-1;
}
for(ll j=0; j<prime.size()&&i*prime[j]<=n; ++j) {
notprime[i*prime[j]]=true;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
质数个数
ll count(ll x) {
ll ans=0;
for(ll i=0; i<prime.size()&&prime[i]*prime[i]<=x; ++i) {
for(; x%prime[i]==0; ++ans) x/=prime[i];
}
if(x!=1) ++ans;
return ans;
}
动态规划
状压dp
位运算
// 获取 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); }
ll lowbit(ll x) {
return x&(-x);}
内建函数
__builtin_clzll(n)//前导0的个数
31-__builtin_clzll(n);//取对数
__builtin_ffsll(n)//末尾最后一个1的位置，位置从1开始
__builtin_ctzll(n)//末尾连续0的个数
__builtin_clrsbll(n)//符号位为0时返回n前导0的个数-1，否则返回前导1的个数-1。
int __builtin_parityll(unsigned int x)//1的个数的奇偶性。
__builtin_popcountll(n);//二进制1的个数
字符串
Trie树
struct node {
ll nxt[26];
} trie[N];
ll cont;
void insert(string s) {
ll p=0;
for(ll i=0; i<s.length(); ++i) {
ll &to=trie[p].nxt[str[i]-'a'];
if(to) p=to;
else {
p=to=++cont;
memset(trie+p,0,sizeof trie[p]);
}
}
}
ll query(string s) {
ll p=0,ans=0;
for(ll i=0; i<s.length(); ++i) {
ll &to=trie[p].nxt[s[i]-'a'];
if(to) {
p=to;
ans+=i位置匹配成功;
} else 匹配失败;
}
ans+=匹配成功;
return ans;
}
void init() {
memset(trie,0,sizeof trie[0]);
cont=0;
}
拓展kmp（标准kmp板子？你还没记住？）
//pre[i]为i位置（右开）最长公共前后缀
//if(t[++p]==t[++q]) pre[q]=pre[p]; else pre[q]=p; 优化
//p=pre[p];重叠 p=0;不重叠
//lent-nxt[lent]首尾添加能构成的最小循环节长度
//注意体会与manacher思想的相似性，nxt决定ext，带-x的下标一般是模式串的，为了与主串统一到0下标开始
vec exprekmp(string s) {
ll len=s.length();
vec nxt(len);
nxt[0]=len;
for(ll i=1,l=0,r=0; i<len; ++i) {
if(i+nxt[i-l]>=r) {
if(i>r) r=i;
while(r<len&&s[r]==s[r-i]) ++r;
nxt[i]=r-i;
l=i;
} else nxt[i]=nxt[i-l];
}
return nxt;
}
vec exkmp(string s,string t) {
ll lens=s.length(),lent=t.length();
vec nxt=exprekmp(t),ext(lens);
for(ll i=0,l=0,r=0; i<lens; ++i) {
if(i+nxt[i-l]>=r) {
if(i>r) r=i;
while(r<lens&&s[r]==t[r-i]) ++r;
ext[i]=r-i;
l=i;
} else ext[i]=nxt[i-l];
}
return ext;
}
manacher
//?奇下标偶长度，字符偶下标和奇长度，与前一个?结合
//中间位置（右开）=原始下标：i-1>>1;原始长度：len-1>>1
//起始位置：i-rds[i]>>1，结束位置（右开）：i+rds[i]-1>>1;
//回文长度：rds[i]-1；
vec manacher(string raw) {
string s="!?";
for(auto v:raw) {
s+=v;
s+='?';
}
ll len=s.length();
vec rds(len);
for(ll i=0,l=0,r=0; i<len; ++i) {
rds[i]=r>i?min(rds[2*l-i],r-i):1;
while(s[i+rds[i]]==s[i-rds[i]]) ++rds[i];
if(i+rds[i]>r) r=i+rds[l=i];
}
return rds;
}
图论
二分图最大匹配（前向星）
ll hd[N],pre[N];
bitset<N> vis;
ll to[2*N],nxt[2*N];
ll n,m,k,cnt;//n匹配点数量，m被匹配点数量，k边数量
bool dfs(ll u) {
for(ll i=hd[u]; i; i=nxt[i]) {
if(vis[to[i]]) continue;
vis[to[i]]=true;
if(!pre[to[i]]||dfs(pre[to[i]])) {
pre[to[i]]=u;
return true;
}
}
return false;
}
while(k--) {
ll u,v;
cin>>u>>v;
add(u,v+n);
add(v+n,u);
}
ll cnt=0;
for(ll i=1; i<=n; ++i) {
vis.reset();
cnt+=dfs(i);
}
cout<<cnt<<endl;
最短路径
Dij
邻接矩阵
ll n,s,e;
ll dis[maxn],g[maxn][maxn];
bool vis[maxn];
//g[ta][tb]=g[tb][ta]=min(g[ta][tb],tc);
dis[s]=0;
while(s!=e)
{
ll mindis=inf,idx;
vis[s]=true;
rep(i,0,n)
{
dis[i]=min(dis[i],dis[s]+g[s][i]);
if(!vis[i]&&dis[i]<mindis) mindis=dis[idx=i];
}
if(mindis==inf) break;
s=idx;
}
cout<<dis[e]<<endl;
堆优化+前向星
ll n,m;
ll dis[maxn],hd[maxn];
bool vis[maxn];
ll cnt;
ll to[maxm],w[maxm],nxt[maxm];
ll ta,tb,tc,s,e;
struct node {
ll s,w;
bool operator<(const node &a)const {
return a.w<w; //与condition()同步
}
};
priority_queue<node> que;
//init
memset(dis,inf,sizeof dis);
memset(vis,0,sizeof vis);
memset(hd,0,sizeof hd)//*******WARNING********
cnt=0;
//in
cin>>n>>m;
rep(i,0,m) {
cin>>ta>>tb>>tc;
w[++cnt]=tc;
to[cnt]=tb;
nxt[cnt]=hd[ta];
hd[ta]=cnt;
}
cin>>s>>e;
//dij
dis[s]=0;
que.push(node{
s,0});
while(!que.empty()) {
node t=que.top();
que.pop();
if(vis[t.s]) continue;//易忘
vis[t.s]=true;
for(ll i=hd[t.s]; i; i=nxt[i]) {
if(dis[t.s]+w[i]<dis[to[i]])//易忘
//if(condition(stucture(dis[pnt],w[i]),dis[to[i]])) <条件>的<结构> ex. min(dis[pnt],w[i])>dis[to[i]] 最大的路径的边的最小值
{
dis[to[i]]=dis[t.s]+w[i];
que.push(node{
to[i],dis[to[i]]});
}
}
}
//out
cout<<dis[e]<<endl;
树
最小生成树（Prim）（邻接矩阵无优化）*
int prim() {
int ans=0;
vis.reset();
dis[1]=0;
vis[1]=true;
for(int i=1; i<=n; i++) {
dis[i]=graph[1][i];
}
for(int i=0; i<n-1; i++) {
int mindis=inf,index;
for(int j=1; j<=n; j++) {
if(vis[j]==false&&dis[j]<mindis) {
mindis=dis[j];
index=j;
}
}
ans+=mindis;
vis[index]=true;
for(int j=1; j<=n; j++) {
if(vis[j]==false) {
dis[j]=min(graph[index][j],dis[j]);
}
}
}
return ans;
}
双向链表遍历*
vector<ll> graph[N];
ll n;
void dfs(ll p,ll fa) {
if(graph[p].size()==1) return;//判断叶节点
for(auto v:graph[p]) {
if(v==fa) continue;
dfs(v,p);
}
}
cin>>n;
graph[0].push_back(1);
graph[1].push_back(0);
for(ll i=0; i<n-1; ++i) {
ll a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1,0);
二叉树
先序遍历+中序遍历->后序遍历（dfs）
int n;
int pre[maxn];
int in[maxn];
bool head;
void build(int la,int ra,int lb,int rb) {
if(la==ra) return;
if(la+1==ra) {
if(head) {
printf("%d",pre[la]);
head=false;
} else printf(" %d",pre[la]);
return;
}
int p=lb;
while(in[p]!=pre[la]&&p<rb)p++;
build(la+1,la+1+p-lb,lb,p);
build(la+1+p-lb,ra,p+1,rb);
if(head) {
printf("%d",pre[la]);
head=false;
} else printf(" %d",pre[la]);
}
while(~scanf("%d",&n)) {
head=true;
rep(i,0,n) scanf("%d",&pre[i]);
rep(i,0,n) scanf("%d",&in[i]);
build(0,n,0,n);
puts("");
}
查询/修改
树状数组*
ll tree[maxn];
void update(ll x,ll v) {
while(x<=n) {
tree[x]+=v;
x+=lowbit(x);
}
}
ll getsum(ll x) {
ll ans=0;
while(x) {
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
ll query(ll l,ll r) {
return getsum(r)-getsum(l-1);
}
线段树
void pushup(ll rt) {
//要维护操作
tree[rt]=operation(tree[rt<<1],tree[rt<<1|1]);
}
ll query(tinfo,ll tl,ll tr) {
if(tl<=l&&tr>=r) return tree[rt];
ll ans;
//pushdown(rt,l,r); 区间更新使用
if(tl<=mid) ans operation=query(sl,tl,tr);
if(tr>mid) ans operation=query(sr,tl,tr);
return ans;
}
标准线段树（带区间更新）*
#define mid (l+r>>1)
#define sl rt<<1,l,mid
#define sr rt<<1|1,mid+1,r
#define tdata 1,1,n
#define tinfo ll rt,ll l,ll r
ll tree[maxn<<2];
ll lzy[maxn<<2];
ll arr[maxn];
ll n;
void pushdown(tinfo) {
if(!lzy[rt]) return;
tree[rt<<1]+=lzy[rt]*(mid-l+1);
tree[rt<<1|1]+=lzy[rt]*(r-mid);
lzy[rt<<1]+=lzy[rt];
lzy[rt<<1|1]+=lzy[rt];
lzy[rt]=0;
}
void build(tinfo) {
if(l==r) {
tree[rt]=arr[l];
return;
}
build(sl);
build(sr);
pushup(rt);
}
//单点更新
void update(tinfo,ll p,ll w) {
if(l==r) {
//更新操作
tree[rt] operation=w;
return ;
}
if(p>mid) update(sr,p,w);
else update(sl,p,w);
pushup(rt);
}
//区间更新
void update(tinfo,ll tl,ll tr,ll v) {
if(tl<=l&&tr>=r) {
tree[rt]=(r-l+1)*v;
lzy[rt]=v;
return;
}
pushdown(rt,l,r);
if(tl<=mid)update(sl,tl,tr,v);
if(tr>mid) update(sr,tl,tr,v);
pushup(rt);
}
可持久化线段树（暂不支持区间更新）*
#define tinfo ll rt,ll l,ll r
#define sl sonl[rt],l,mid
#define sr sonr[rt],mid+1,r
#define mid (l+r>>1)
const ll M=N*(64-__builtin_clzll(N))+10;
ll arr[N];
ll sonl[M],sonr[M],tree[M],cnt;
ll build(tinfo) {
rt=++cnt;
if(l==r) {
tree[rt]=arr[l];
return rt;
}
sonl[rt]=build(sl);
sonr[rt]=build(sr);
pushup(rt);
return rt;
}
ll update(tinfo,ll p,ll v) {
ll rtnew=++cnt;
if(l==r) {
tree[rtnew]=v;
return cnt;
}
if(p<=mid) {
sonl[rtnew]=update(sl,p,v);
sonr[rtnew]=sonr[rt];
} else {
sonl[rtnew]=sonl[rt];
sonr[rtnew]=update(sr,p,v);
}
pushup(rtnew);
return rtnew;
}
稀疏表（Sparse Table）
ll st[20][N];
ll log(ll x) {
return 63-__builtin_clzll(x);
}
void stable() {
ll logn=log(n);
for(int i=0; i<n; i++)
st[0][i]=cha[i];
for(int i=1; i<=logn; i++)
for(int j=0; j+(1<<i)<=n; j++)//<=号
st[i][j]=__gcd(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
ll query(ll l,ll r) {
ll logn=log(r-l);
return __gcd(st[logn][l],st[logn][r-(1<<logn)]);
}
