模板
foreverlasting
2018-07-12 13:40:25
各种板子
最小费用最大流（MCMF）：
```
namespace MCMF {
typedef pair<int,int> Pair;
struct E {
int next,to,flow,cost;
E() {}
E(res next,res to,res flow,res cost):next(next),to(to),flow(flow),cost(cost) {}
} edge[M];
int head[N],cnt;
inline void init() {
cnt=-1;
memset(head,-1,sizeof(head));
}
inline void addedge(res u,res v,res x,res y) {
edge[++cnt]=E(head[u],v,x,y),head[u]=cnt;
edge[++cnt]=E(head[v],u,0,-y),head[v]=cnt;
}
int dis[N],flow[N],pre[N],last[N];
bool vis[N];
int q[M],he,ta;
inline int spfa(res S,res T) {
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(flow,inf,sizeof(flow));
he=1,ta=0;
q[++ta]=S;
vis[S]=1,dis[S]=0,pre[T]=-1;
while(he<=ta) {
res now=q[he++];
vis[now]=0;
for(res i=head[now]; ~i; i=edge[i].next) {
res tox=edge[i].to;
if(edge[i].flow>0&&dis[tox]>dis[now]+edge[i].cost) {
dis[tox]=dis[now]+edge[i].cost;
pre[tox]=now;
last[tox]=i;
flow[tox]=min(flow[now],edge[i].flow);
if (!vis[tox])vis[tox]=1,q[++ta]=tox;
}
}
}
return pre[T]!=-1;
}
inline Pair mcmf(res S,res T) {
res maxflow=0,mincost=0;
while(spfa(S,T)) {
res now=T;
maxflow+=flow[T];
mincost+=flow[T]*dis[T];
while (now!=S) {
edge[last[now]].flow-=flow[T];
edge[last[now]^1].flow+=flow[T];
now=pre[now];
}
}
return make_pair(maxflow,mincost);
}
}
```
ST表：
```
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
inline int read() {
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(res w) {
if(w<0)putchar('-'),w=-w;
if(w>9)write(w/10);
putchar(w%10+'0');
}
const int N=1e6+10;
int Max[N][21],Min[N][21];
int n,m;
inline void ST(){
for(res j=1; j<=21; j++)
for(res i=1; i+(1<<j)-1<=n; i++)
Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]),Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
}
inline int QueryMax(res l,res r) {
res k=log2(r-l+1);
return max(Max[l][k],Max[r-(1<<k)+1][k]);
}
inline int QueryMin(res l,res r) {
res k=log2(r-l+1);
return min(Min[l][k],Min[r-(1<<k)+1][k]);
}
int main() {
n=read(),m=read();
for(res i=1; i<=n; i++) Min[i][0]=Max[i][0]=read();
ST();
for(res i=1; i<=m; i++) {
res l=read(),r=read();
write(QueryMax(l,r)),puts("");
}
return 0;
}
```
SAM：
```
namespace SAM {
int siz[N],rt,last,sz;
inline void INIT(){
rt=last=sz=1;
}
struct SAM {
int vis[26],par,len;
inline void init() {
par=len=0;
memset(vis,0,sizeof(vis));
}
}sam[N];
inline void extend(res c) {
res p=last,np=++sz;
sam[np].len=sam[p].len+1;
for(;p&&!sam[p].vis[c];p=sam[p].par)sam[p].vis[c]=np;
if(!p)sam[np].par=rt;
else {
res q=sam[p].vis[c];
if(sam[q].len==sam[p].len+1)sam[np].par=q;
else {
res nq=++sz;
sam[nq]=sam[q];
sam[nq].len=sam[p].len+1;
sam[q].par=sam[np].par=nq;
for(;p&&sam[p].vis[c]==q;p=sam[p].par)sam[p].vis[c]=nq;
}
}
last=np,siz[np]=1;
}
int buc[N],rank[N],ans;
inline void pre() {
for(res i=1;i<=sz;i++)buc[sam[i].len]++;
for(res i=1;i<=sz;i++)buc[i]+=buc[i-1];
for(res i=1;i<=sz;i++)rank[buc[sam[i].len]--]=i;
for(res i=sz;i>=1;i--)siz[sam[rank[i]].par]+=siz[rank[i]];
}
}
```
Splay:
```
inline void rotate(res x){
res y=tr[x].fa,z=tr[y].fa,k=tr[y].son[1]==x,w=tr[x].son[k^1];
if(z)tr[z].son[tr[z].son[1]==y]=x;
tr[x].son[k^1]=y,tr[y].fa=x,tr[x].fa=z;
if(w)tr[w].fa=y;
pushup(y);
}
inline void splay(res x,res w){
while(tr[x].fa!=w){
res y=tr[x].fa,z=tr[y].fa;
if(z!=w)rotate((tr[y].son[0]==x)^(tr[z].son[0]==y)?x:y);
rotate(x);
}
if(!w)rt=x;
pushup(x);
}
```
LCT：
```
namespace LCT {
struct LCT {
int fa,son[2],sz,val,sum;
bool rev;
} tr[N];
int st[N];
inline void pushup(res x) {
res lc=tr[x].son[0],rc=tr[x].son[1];
tr[x].sz=tr[lc].sz+tr[rc].sz+1;
tr[x].sum=tr[lc].sum^tr[rc].sum^tr[x].val;
}
inline void reversed(res x) {
res &lc=tr[x].son[0],&rc=tr[x].son[1];
_swap(lc,rc);
tr[x].rev^=1;
}
inline void pushdown(res x) {
if(tr[x].rev) {
if(tr[x].son[0])reversed(tr[x].son[0]);
if(tr[x].son[1])reversed(tr[x].son[1]);
tr[x].rev=0;
}
}
inline bool nroot(res x) {
return tr[tr[x].fa].son[0]==x||tr[tr[x].fa].son[1]==x;
}
inline void rotate(res x) {
res y=tr[x].fa,z=tr[y].fa,k=tr[y].son[1]==x,w=tr[x].son[k^1];
if(nroot(y))tr[z].son[tr[z].son[1]==y]=x;
tr[x].son[k^1]=y,tr[y].son[k]=w;
if(w)tr[w].fa=y;
tr[y].fa=x,tr[x].fa=z;
pushup(y);
}
inline void splay(res x) {
res i=x,s=0;
st[++s]=x;
while(nroot(i))st[++s]=i=tr[i].fa;
while(s)pushdown(st[s--]);
while(nroot(x)) {
res y=tr[x].fa,z=tr[y].fa;
if(nroot(y))rotate((tr[y].son[0]==x)^(tr[z].son[0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline void access(res x) {
for(res y=0; x; x=tr[y=x].fa)splay(x),tr[x].son[1]=y,pushup(x);
}
inline void makeroot(res x) {
access(x),splay(x),reversed(x);
}
inline void split(res x,res y) {
makeroot(x),access(y),splay(y);
}
inline int findroot(res x) {
access(x),splay(x);
while(tr[x].son[0])pushdown(x),x=tr[x].son[0];
splay(x);
return x;
}
inline bool link(res x,res y) {
makeroot(x);
if(x==findroot(y))return 0;
tr[x].fa=y;
return 1;
}
inline bool cut(res x,res y) {
makeroot(x);
if(x!=findroot(y)||tr[x].sz>2)return 0;
tr[y].fa=tr[x].son[1]=0;
pushup(x);
return 1;
}
}
```
AC自动机：
```
namespace AC {
#define o
struct AC {
int vis[C],fail,sign,end;
} ac[N];
int cnt;
inline int get(char s) {
return s-'o';
}
inline void clean(res x) {
memset(ac[x].vis,0,sizeof(ac[x].vis));
ac[x].sign=ac[x].fail=0;
}
inline void insert(string s,res sig) {
res len=s.size(),now=0;
for(res i=0; i<len; i++) {
if(!ac[now].vis[get(s[i])])ac[now].vis[get(s[i])]=++cnt,fa[cnt]=now,clean(cnt);
now=ac[now].vis[get(s[i])];
}
ac[now].end=1;
}
int q[N],head,tail;
inline void get_fail() {
head=1,tail=0;
for(res i=0; i<C; i++)if(ac[0].vis[i])ac[ac[0].vis[i]].fail=0,q[++tail]=ac[0].vis[i];
while(head<=tail) {
res u=q[head++];
for(res i=0; i<C; i++)
if(ac[u].vis[i])ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i],q[++tail]=ac[u].vis[i];
else ac[u].vis[i]=ac[ac[u].fail].vis[i];
}
}
}
```
网络最大流（DINIC）：
```
namespace Dinic{
const int N=1e4+10,M=2e5+10;
struct E{
int next,to,val;
E() {}
E(res next,res to,res val):next(next),to(to),val(val) {}
}edge[M];
int cnt,head[N],S,T,dep[N],cur[N];
inline void init(){
memset(head,-1,sizeof(head));
cnt=-1;
}
inline void addedge(res u,res v,res w){
edge[++cnt]=E(head[u],v,w),head[u]=cnt;
edge[++cnt]=E(head[v],u,0),head[v]=cnt;
}
int q[N],he,ta;
inline bool bfs(){
memset(dep,0,sizeof(dep));
he=1,ta=0;
dep[S]=1;
q[++ta]=S;
while(he<=ta) {
res u=q[he++];
for(res i=head[u];~i;i=edge[i].next){
res tox=edge[i].to;
if(!dep[tox]&&edge[i].val>0)
dep[tox]=dep[u]+1,q[++ta]=tox;
}
}
if(dep[T])return 1;
return 0;
}
inline int dfs(res u,res flow) {
if(u==T)return flow;
for(res& i=cur[u];~i;i=edge[i].next){
res tox=edge[i].to;
if(dep[tox]==dep[u]+1&&edge[i].val){
res f=dfs(tox,_min(flow,edge[i].val));
if(f>0){
edge[i].val-=f;
edge[i^1].val+=f;
return f;
}
}
}
return 0;
}
inline int dinic() {
res ans=0;
while(bfs()) {
memcpy(cur,head,sizeof(cur));
while(int f=dfs(S,inf))ans+=f;
}
return ans;
}
}
```
左偏树：
```
namespace Lheap{
struct Lheap{
int va,son[2],fa,dis;
}lh[N];
int merge(res x,res y){
if(!x||!y)return x+y;
if((lh[x].va>lh[y].va)||(lh[x].va==lh[y].va&&x>y))_swap(x,y);
lh[x].son[1]=merge(lh[x].son[1],y);
lh[lh[x].son[1]].fa=x;
if(lh[lh[x].son[0]].dis<lh[lh[x].son[1]].dis)_swap(lh[x].son[0],lh[x].son[1]);
lh[x].dis=lh[lh[x].son[1]].dis+1;
return x;
}
int find(res x){
return lh[x].fa?find(lh[x].fa):x;
}
inline void pop(res x){
lh[x].va=-1;
lh[lh[x].son[0]].fa=lh[lh[x].son[1]].fa=0;
merge(lh[x].son[0],lh[x].son[1]);
}
}
```
拉格朗日插值：
```
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=1LL*ret*x%kcz;
y>>=1,x=1LL*x*x%kcz;
}
return ret%kcz;
}
inline void add(res &x,const res &y){
x+=y;
x>=kcz?x-=kcz:1;
x<0?x+=kcz:1;
}
inline int calc(const res &x,const res &n){
res tmp=1,ret=0,p=(n&1)?kcz-1:1;
for(res i=1;i<=n;i++)tmp=1LL*tmp*(x-i)%kcz*qpow(i,kcz-2)%kcz;
for(res i=0;i<=n;i++,p=kcz-p)
add(ret,1LL*p*dp[n][i]%kcz*tmp%kcz),tmp=1LL*tmp*(x-i)%kcz*qpow(x-i-1,kcz-2)%kcz*(n-i)%kcz*qpow(i+1,kcz-2)%kcz;
return ret;
}
```
组合数：
```
int inv[N],fac[N];
inline void pre(){
inv[0]=inv[1]=fac[0]=fac[1]=1;
for(res i=2;i<=N-10;i++)fac[i]=(LL)fac[i-1]*i%kcz,inv[i]=(LL)(kcz-kcz/i)*inv[kcz%i]%kcz;
for(res i=2;i<=N-10;i++)inv[i]=(LL)inv[i-1]*inv[i]%kcz;
}
inline int C(res x,res y){
return (LL)fac[x]*inv[y]%kcz*inv[x-y]%kcz;
}
```
虚树：
```
namespace Vir{
inline bool cmp(res x,res y){
return Tree::id[x]<Tree::id[y];
}
struct E{
int next,to;
E() {}
E(res next,res to):next(next),to(to) {}
}edge[N];
int head[N],cnt;
inline void addedge(res u,res v){
edge[++cnt]=E(head[u],v),head[u]=cnt;
}
int st[N],top,H[N],k,tot;
bool vip[N],vis[N];
inline void init(){
cnt=0;
for(res i=1;i<=tot;i++)vis[H[i]]=vip[H[i]]=0,head[H[i]]=-1;
}
inline void Read(){
init();
k=read();
for(res i=1;i<=k;i++)H[i]=read(),vis[H[i]]=vip[H[i]]=1;
}
inline void build(){
Read();
tot=k,sort(H+1,H+tot+1,cmp);
for(res i=1,x;i<tot;i++)if(!vis[x=Tree::get_lca(H[i],H[i+1])])vis[H[++k]=x]=1;
tot=k,sort(H+1,H+tot+1,cmp);
st[top=1]=H[1];
for(res i=2;i<=tot;st[++top]=H[i++]){
while(Tree::id[H[i]]<Tree::id[st[top]]||Tree::low[H[i]]>Tree::low[st[top]])top--;
addedge(st[top],H[i]);
}
}
}
```
边分治：
```
namespace Edtree{
struct E{
LL next,to;
bool tag;
E() {}
E(res next,res to,bool tag):next(next),to(to),tag(tag) {}
}edge[N<<4];
LL head[N],cnt;
inline void init(){
memset(head,-1,sizeof(head));
}
inline void addedge(res u,res v,bool tag){
edge[++cnt]=E(head[u],v,tag),head[u]=cnt;
edge[++cnt]=E(head[v],u,tag),head[v]=cnt;
}
void build(res x,res fax){
res X=x;
bool flag=0;
for(res i=Tree::head[x];~i;i=Tree::edge[i].next){
res tox=Tree::edge[i].to;
if(tox==fax)continue;
if(flag)addedge(x,++n,0),va[n]=va[x],x=n;
addedge(x,tox,1);
build(tox,X);
flag=1;
}
}
bool vis[N];
LL siz[N],rt,w;
void getroot(res x,res fax,res sum){
siz[x]=1;
for(res i=head[x];~i;i=edge[i].next){
res tox=edge[i].to;
if(tox==fax||vis[i>>1])continue;
getroot(tox,x,sum);
siz[x]+=siz[tox];
res K=_max(siz[tox],sum-siz[tox]);
if(K<w)w=K,rt=i;
}
}
```
后缀数组（SA）：
```
struct SA{
int str[N];
struct SAM{
int vis[26],par,len,pos;
bool val;
}sam[N<<1];
int cnt,rt,las;
inline void INIT(){
cnt=rt=las=1;
memset(sam,0,sizeof(sam));
}
inline void extend(const res &x,const res &id){
res p=las,np=++cnt;
las=np,sam[np].len=sam[p].len+1,sam[np].pos=id,sam[np].val=1;
for(;p&&!sam[p].vis[x];p=sam[p].par)sam[p].vis[x]=np;
if(!p)sam[np].par=rt;
else {
res q=sam[p].vis[x];
if(sam[q].len==sam[p].len+1)sam[np].par=q;
else {
res nq=++cnt;
memcpy(sam[nq].vis,sam[q].vis,sizeof(sam[nq].vis));
sam[nq].par=sam[q].par,sam[nq].len=sam[p].len+1,sam[nq].pos=sam[q].pos,sam[q].par=sam[np].par=nq;
for(;p&&sam[p].vis[x]==q;p=sam[p].par)sam[p].vis[x]=nq;
}
}
}
int rnk[N],sa[N],hei[N],tot,vis[N<<1][26];
inline void addedge(const res &u,const res &v,const res &c){
vis[u][c]=v;
}
inline void build(){
memset(vis,0,sizeof(vis)),tot=0;
for(res i=2;i<=cnt;i++)addedge(sam[i].par,i,str[sam[i].pos+sam[sam[i].par].len]);
}
void dfs(const res &x){
if(sam[x].val)sa[rnk[sam[x].pos]=++tot]=sam[x].pos;
for(res i=0;i<26;i++)if(vis[x][i])dfs(vis[x][i]);
}
inline void get_hei(){
res k=0;
for(res i=1;i<=n;i++)rnk[sa[i]]=i;
for(res i=1;i<=n;i++){
if(rnk[i]==1)continue;
if(k)k--;
res j=sa[rnk[i]-1];
while(j+k<=n&&i+k<=n&&str[i+k]==str[j+k])k++;
hei[rnk[i]]=k;
}
}
int st[N][21];
inline void ST(){
memset(st,inf,sizeof(st));
for(res i=1;i<=n;i++)st[i][0]=hei[i];
for(res j=1;j<=20;j++)
for(res i=1;i+(1<<j)-1<=n;i++)
st[i][j]=_min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
inline int query_min(const res &l,const res &r){
res k=log2(r-l+1);
return _min(st[l][k],st[r-(1<<k)+1][k]);
}
inline int LCP(const res &l,const res &r){
return query_min(_min(rnk[l],rnk[r])+1,_max(rnk[l],rnk[r]));
}
inline void pre(){
INIT();
for(res i=n;i;i--)extend(str[i],i);
build(),dfs(1),get_hei(),ST();
}
}A;
```