前言
再过两天就\(NOIP2018\)了。
于是，我决定不做其他题目，开始一心一意刷板子了。
这篇博客记录的就是我的刷板子计划。
【洛谷3383】【模板】线性筛素数
这种普及-的题目我还写挂了两次（感觉自己废掉了）。
好吧，第一次写挂是因为数组开小了，第二次写挂是因为没有特判\(1\)不是质数... ...
class Class_LineSiever
{
private:
#define PrimeSize 1000000
bool IsNot[PrimeSize+5];
public:
int Prime_cnt,Prime[PrimeSize+5];
inline void Sieve(int Size)
{
register int i,j;
for(IsNot[1]=true,i=2;i<=Size;++i)
{
if(!IsNot[i]) Prime[++Prime_cnt]=i;
for(j=1;j<=Prime_cnt&&1LL*i*Prime[j]<=Size;++j) if(IsNot[i*Prime[j]]=true,!(i%Prime[j])) break;
}
}
inline bool IsPrime(int x) {return !IsNot[x];}
};
【洛谷3370】【模板】字符串哈希
这真的是比较基础的题目。（看以前的提交记录发现我之前是用\(map\)过的... ...）
class Class_StringHasher
{
private:
#define ull unsigned long long
struct Hash
{
ull fir,sec;
Hash(ull x=0,ull y=0):fir(x),sec(y){}
inline friend Hash operator + (Hash x,Hash y) {return Hash(x.fir+y.fir,x.sec+y.sec);}
inline friend Hash operator - (Hash x,Hash y) {return Hash(x.fir-y.fir,x.sec-y.sec);}
inline friend Hash operator * (Hash x,Hash y) {return Hash(x.fir*y.fir,x.sec*y.sec);}
inline friend bool operator < (Hash x,Hash y) {return x.fir^y.fir?x.fir<y.fir:x.sec<y.sec;}
}base;
set<Hash> vis;
inline Hash GetHash(string x)
{
register int i,len=x.length();register Hash res=0;
for(i=0;i<len;++i) res=res*base+Hash(x[i],x[i]);
return res;
}
public:
Class_StringHasher() {base=Hash(119,127);}
inline bool Exist(string x) {return vis.find(GetHash(x))!=vis.end();}
inline void Add(string x) {vis.insert(GetHash(x));}
};
【洛谷3366】【模板】最小生成树
分别使用\(Prim\)和\(Kruskal\)各写了一遍。
发现自己对\(Prim\)已经有一些陌生了，直至看到代码才想起来它可以用堆优化... ...（感觉自己好菜）
class Class_PrimSpanner
{
private:
int dis[N+5],vis[N+5];typedef pair<int,int> Status;priority_queue<Status,vector<Status>,greater<Status> > q;
public:
inline int GetAns()
{
register int i,ans=0;register Status k;
for(i=2;i<=n;++i) dis[i]=INF;q.push(make_pair(dis[1]=0,1));
while(!q.empty())
{
while(!q.empty()&&vis[q.top().second]) q.pop();
if(q.empty()) break;
for(k=q.top(),q.pop(),ans+=k.first,vis[k.second]=1,i=lnk[k.second];i;i=e[i].nxt)
if(!vis[e[i].to]&&e[i].val<dis[e[i].to]) q.push(make_pair(dis[e[i].to]=e[i].val,e[i].to));
}
return ans;
}
};
class Class_KruskalSpanner
{
private:
class Class_UnionFindSet
{
private:
int fa[N+5],level[N+5];
inline int getfa(int x) {return fa[x]^x?fa[x]=getfa(fa[x]):x;}
public:
inline void Init() {for(register int i=1;i<=n;++i) fa[i]=i;}
inline bool Identify(int x,int y) {return !(getfa(x)^getfa(y));}
inline void Union(int x,int y) {((x=getfa(x))^(y=getfa(y)))&&(level[x]<level[y]&&swap(x,y),fa[y]=x,!(level[x]^level[y])&&++level[x]);}
}U;
public:
inline int GetAns()
{
register int i,ans=0;
for(U.Init(),sort(e+1,e+m+1),i=1;i<=m;++i) !U.Identify(e[i].from,e[i].to)&&(U.Union(e[i].from,e[i].to),ans+=e[i].val);
return ans;
}
};
【洛谷3369】【模板】普通平衡树
这是我比较担心的一块。
分别用替罪羊树、\(Treap\)和\(Splay\)三种平衡树各码了一遍板子。
码板子的过程中还是发现了一些细节问题，所以有点怕即使\(NOIP\)考了平衡树我都不一定敢写。
class Class_ScapegoatTree
{
private:
#define Alpha 0.75
#define NewNode() (VoidSize?Void[VoidSize--]:++tot)
#define Init(x) (node[x].Exist=node[x].Size=node[x].Fac=1,node[x].Son[0]=node[x].Son[1]=0)
#define Balance(x) (Alpha*node[x].Fac>1.0*max(node[node[x].Son[0]].Fac,node[node[x].Son[1]].Fac))
#define PushUp(x) (void)(node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+1,node[x].Fac=node[node[x].Son[0]].Fac+node[node[x].Son[1]].Fac+node[x].Exist)
#define ReBuild(x) (void)(cnt=0,Traversal(x),cnt?(SetUp(x,1,cnt),0):x=0)
int rt,tot,cnt,cur[N+5],VoidSize,Void[N+5];
struct Tree
{
int Val,Exist,Size,Fac,Son[2];
Tree(int x=0):Val(x){Exist=Size=Fac=Son[0]=Son[1]=0;}
}node[N+5];
inline void Traversal(int x) {x&&(Traversal(node[x].Son[0]),(node[x].Exist?cur[++cnt]=x:Void[++VoidSize]=x),Traversal(node[x].Son[1]),0);}
inline void SetUp(int &x,int l,int r) {register int mid=l+r>>1;Init(x=cur[mid]),l<mid&&(SetUp(node[x].Son[0],l,mid-1),0),r>mid&&(SetUp(node[x].Son[1],mid+1,r),0),PushUp(x);}
inline void ins(int &x,int val) {if(!x) return (void)(node[x=NewNode()]=Tree(val),Init(x));++node[x].Size,++node[x].Fac,ins(node[x].Son[node[x].Val<val],val);}
inline void del(int &x,int rk) {register int t=node[node[x].Son[0]].Fac+node[x].Exist;if(--node[x].Fac,t^rk||!node[x].Exist) t<rk?del(node[x].Son[1],rk-t):del(node[x].Son[0],rk);else node[x].Exist=0;}
inline void chk(int &x,int val) {if(!x) return;if(!Balance(x)) return ReBuild(x);chk(node[x].Son[node[x].Val<val],val);}
public:
inline void Insert(int val) {ins(rt,val),chk(rt,val);}
inline int get_rank(int val) {register int x=rt,rk=1;while(x) node[x].Val<val?(rk+=node[node[x].Son[0]].Fac+node[x].Exist,x=node[x].Son[1]):x=node[x].Son[0];return rk;}
inline void Delete(int val) {del(rt,get_rank(val)),Alpha*node[rt].Size>1.0*node[rt].Fac&&(ReBuild(rt),0);}
inline int get_val(int rk) {register int x=rt,t;while(x) if((t=node[node[x].Son[0]].Fac+node[x].Exist)==rk&&node[x].Exist) return node[x].Val;else t<rk?(rk-=t,x=node[x].Son[1]):x=node[x].Son[0];}
inline int get_pre(int val) {return get_val(get_rank(val)-1);}
inline int get_nxt(int val) {return get_val(get_rank(val+1));}
};
class Class_Treap
{
private:
#define ull unsigned long long
#define NewNode() (VoidSize?Void[VoidSize--]:++tot)
#define Init(x) (node[x].Size=node[x].Cnt=1,node[x].Data=1ull*rand()*rand()*rand()*rand()*rand())
#define PushUp(x) (node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+node[x].Cnt)
int rt,tot,VoidSize,Void[N+5];
struct Tree
{
int Val,Size,Cnt,Son[2];ull Data;
Tree(int x=0):Val(x){Size=Cnt=Data=Son[0]=Son[1]=0;}
}node[N+5];
inline void Rotate(int &x,int d) {register int k=node[x].Son[d^1];node[x].Son[d^1]=node[k].Son[d],node[k].Son[d]=x,PushUp(x),PushUp(k),x=k;}
inline void ins(int &x,int val)
{
if(!x) return (void)(node[x=NewNode()]=Tree(val),Init(x));
if(++node[x].Size,!(node[x].Val^val)) return (void)(++node[x].Cnt);
register int d=node[x].Val<val;
ins(node[x].Son[d],val),node[x].Data<node[node[x].Son[d]].Data&&(Rotate(x,d^1),0),PushUp(x);
}
inline void del(int &x,int val)
{
if(!x) return;
if(!(node[x].Val^val))
{
if(node[x].Cnt>1) return (void)(--node[x].Cnt,--node[x].Size);
if(!node[x].Son[0]||!node[x].Son[1]) return (void)(x=node[x].Son[0]+node[x].Son[1]);
register int d=node[node[x].Son[0]].Data<node[node[x].Son[1]].Data;
return (void)(Rotate(x,d^1),del(node[x].Son[d^1],val),PushUp(x));
}
del(node[x].Son[node[x].Val<val],val),PushUp(x);
}
public:
Class_Treap() {srand(20050521);}
inline void Insert(int val) {ins(rt,val);}
inline void Delete(int val) {del(rt,val);}
inline int get_rank(int val)
{
register int x=rt,rk=1;
while(x) node[x].Val<val?(rk+=node[node[x].Son[0]].Size+node[x].Cnt,x=node[x].Son[1]):x=node[x].Son[0];
return rk;
}
inline int get_val(int rk)
{
register int x=rt;
while(x)
{
if(node[node[x].Son[0]].Size>=rk) x=node[x].Son[0];
else if(rk-=node[node[x].Son[0]].Size,node[x].Cnt>=rk) return node[x].Val;
else rk-=node[x].Cnt,x=node[x].Son[1];
}
}
inline int get_pre(int val)
{
register int x=rt,pre=-INF;
while(x) node[x].Val<val?(pre=node[x].Val,x=node[x].Son[1]):x=node[x].Son[0];
return pre;
}
inline int get_nxt(int val)
{
register int x=rt,nxt=INF;
while(x) node[x].Val>val?(nxt=node[x].Val,x=node[x].Son[0]):x=node[x].Son[1];
return nxt;
}
};
class Class_Splay
{
private:
#define NewNode() (VoidSize?Void[VoidSize--]:++tot)
#define Init(x) (node[x].Size=node[x].Cnt=1,node[x].Son[0]=node[x].Son[1]=0)
#define Which(x) (node[node[x].Father].Son[1]==x)
#define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)
#define PushUp(x) (node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+node[x].Cnt)
int rt,tot,VoidSize,Void[N+5];
struct Tree
{
int Val,Size,Cnt,Father,Son[2];
Tree(int x=0,int y=0):Val(x),Father(y){Size=Cnt=Son[0]=Son[1]=0;}
}node[N+5];
inline void Rotate(int x,int &k)
{
register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);
(fa^k?node[pa].Son[Which(fa)]=x:k=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1),PushUp(fa),PushUp(x);
}
inline void Splay(int x,int &k)
{
register int fa=node[x].Father;
while(x^k) fa^k&&(Rotate(Which(x)^Which(fa)?x:fa,k),0),Rotate(x,k),fa=node[x].Father;
PushUp(x);
}
inline void ins(int &x,int val,int lst)
{
if(!x) return (void)(node[x=NewNode()]=Tree(val,lst),Init(x),Splay(x,rt));
if(++node[x].Size,!(node[x].Val^val)) return (void)(++node[x].Cnt,Splay(x,rt));
ins(node[x].Son[node[x].Val<val],val,x);
}
public:
inline void Insert(int val) {ins(rt,val,0);}
inline int get_rank(int val)
{
register int x=rt,rk=1;
while(x)
{
if(!(node[x].Val^val)) return rk+=node[node[x].Son[0]].Size,Splay(x,rt),rk;
node[x].Val<val?(rk+=node[node[x].Son[0]].Size+node[x].Cnt,x=node[x].Son[1]):x=node[x].Son[0];
}
}
inline int get_val(int rk)
{
register int x=rt;
while(x)
{
if(node[node[x].Son[0]].Size>=rk) x=node[x].Son[0];
else if(rk-=node[node[x].Son[0]].Size,node[x].Cnt>=rk) return Splay(x,rt),node[x].Val;
else rk-=node[x].Cnt,x=node[x].Son[1];
}
}
inline void Delete(int val)
{
if(get_rank(val),--node[rt].Cnt) return;
if(!node[rt].Son[0]||!node[rt].Son[1]) return (void)(node[rt=node[rt].Son[0]+node[rt].Son[1]].Father=0);
register int k=node[rt].Son[0];
while(node[k].Son[1]) k=node[k].Son[1];
Connect(node[rt].Son[1],k,1),node[rt=node[rt].Son[0]].Father=0;
}
inline int get_pre(int val)
{
register int x=rt,pre=-INF;
while(x) node[x].Val<val?(pre=node[x].Val,x=node[x].Son[1]):x=node[x].Son[0];
return pre;
}
inline int get_nxt(int val)
{
register int x=rt,nxt=INF;
while(x) node[x].Val>val?(nxt=node[x].Val,x=node[x].Son[0]):x=node[x].Son[1];
return nxt;
}
};
【洛谷3391】【模板】文艺平衡树
\(Splay\)维护数列的最经典例题（也是最水例题）。
这题也花了挺多时间在调试上，结果果真发现犯了一个智障的错误... ...
class Class_Splay
{
private:
#define Which(x) (node[node[x].Father].Son[1]==x)
#define PushUp(x) (node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+1)
#define PushDown(x) (node[x].Rev&&(swap(node[x].Son[0],node[x].Son[1]),node[node[x].Son[0]].Rev^=1,node[node[x].Son[1]].Rev^=1,node[x].Rev=0))
#define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)
#define Split(x,y) (Splay(get_pos(x),rt),Splay(get_pos((y)+2),node[rt].Son[1]),node[node[rt].Son[1]].Son[0])
int rt,tot,data[N+5];
struct node
{
int Val,Size,Father,Rev,Son[2];
}node[N+5];
inline void bld(int l,int r,int &rt)
{
register int mid=l+r>>1;rt=++tot,
l<mid&&(bld(l,mid-1,node[rt].Son[0]),node[node[rt].Son[0]].Father=rt),r>mid&&(bld(mid+1,r,node[rt].Son[1]),node[node[rt].Son[1]].Father=rt),
node[rt].Val=data[mid],PushUp(rt);
}
inline void Rotate(int x,int &k)
{
register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);
(fa^k?node[pa].Son[Which(fa)]=x:k=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1),PushUp(fa),PushUp(x);
}
inline void Splay(int x,int &k)
{
register int fa=node[x].Father;
while(x^k) fa^k&&(Rotate(Which(x)^Which(fa)?x:fa,k),0),Rotate(x,k),fa=node[x].Father;
PushUp(x);
}
inline int get_pos(int rk)
{
register int x=rt;
while(x)
{
if(PushDown(x),node[node[x].Son[0]].Size>=rk) x=node[x].Son[0];
else if(rk-=node[node[x].Son[0]].Size,!(rk^1)) return x;
else --rk,x=node[x].Son[1];
}
}
public:
inline void Build(int n) {for(register int i=2;i<=n+1;++i) data[i]=i-1;data[1]=-INF,data[n+2]=INF,bld(1,n+2,rt);}
inline void Rever(int l,int r) {register int k=Split(l,r);node[k].Rev^=1;}
inline int get_num(int x) {return node[get_pos(x+1)].Val;}
};
【洛谷4779】【模板】单源最短路径（标准版）
第一次知道\(Dijkstra\)可以用线段树优化。
\(WA\)了好几发，原因是没有看到题目中的边是有向边，感觉自己像个智障。
我没有写\(SPFA\)板子，毕竟它已经死了。
class Class_Dijkstra
{
private:
class Class_SegmentTree
{
private:
#define Left l,mid,rt<<1
#define Right mid+1,r,rt<<1|1
#define PushUp(x) (node[x]=min(node[x<<1],node[x<<1|1]))
pair<int,int> node[N<<2];
inline void upt(int l,int r,int rt,int pos,int val) {if(l==r) return (void)(node[rt]=make_pair(val,l));register int mid=l+r>>1;(pos<=mid?upt(Left,pos,val):upt(Right,pos,val)),PushUp(rt);}
public:
inline void Build(int l=1,int r=n,int rt=1) {if(l==r) return (void)(node[rt]=make_pair(INF,l));register int mid=l+r>>1;Build(Left),Build(Right),PushUp(rt);}
inline void Update(int pos,int val) {upt(1,n,1,pos,val);}
inline pair<int,int> Query() {return node[1];}
}S;
public:
int dis[N+5];
inline void Solve(int s)
{
register int i,Time;register pair<int,int> k;
for(S.Build(),i=1;i<=n;++i) dis[i]=INF;
for(S.Update(s,dis[s]=0),Time=1;Time<=n;++Time)
{
for(k=S.Query(),S.Update(k.second,INF),i=lnk[k.second];i;i=e[i].nxt)
dis[e[i].to]>k.first+e[i].val&&(S.Update(e[i].to,dis[e[i].to]=k.first+e[i].val),0);
}
}
};
【洛谷3374】【模板】树状数组1&&【洛谷3368】【模板】树状数组2
对于树状数组我真的是完全不懂啊。
今天好好学了一下，貌似有点理解了它的大致思想。
我相信考到树状数组题我肯定会去写线段树，即使它常数比较大。
class Class_TreeArray
{
private:
#define lowbit(x) ((x)&-(x))
int data[N+5];
inline int qry(int x) {register int res=0;while(x) res+=data[x],x-=lowbit(x);return res;}
public:
inline void Add(int x,int val) {while(x<=n) data[x]+=val,x+=lowbit(x);}
inline int Query(int l,int r) {return qry(r)-qry(l-1);}
};
class Class_TreeArray
{
private:
#define lowbit(x) ((x)&-(x))
int val[N+5],data[N+5];
public:
inline int Init(int len,int *num) {for(register int i=1;i<=len;++i) val[i]=num[i];}
inline void Add(int x,int val) {while(x<=n) data[x]+=val,x+=lowbit(x);}
inline int Query(int x) {register int res=val[x];while(x) res+=data[x],x-=lowbit(x);return res;}
};
【洛谷3884】【模板】可持久化线段树1（主席树）
最近写了挺多主席树题，因此还算是比较熟练的吧。
但样例依然调了很久。
最后发现问题竟错在我最相信不会错的离散化上... ...
class Class_ChairmanTree
{
private:
int tot,Root[N+5];
struct Tree
{
int Size,Son[2];
}node[N*LogN+5];
class Class_Discretization
{
private:
int data[N+5];
public:
int cnt;
inline void Init(int n,int *num) {for(register int i=1;i<=n;++i) data[i]=num[i];sort(data+1,data+n+1),cnt=unique(data+1,data+n+1)-data-1;}
inline int get_val(int x) {register int l=1,r=cnt,mid;while(l<=r) data[mid=l+r>>1]<x?l=mid+1:r=mid-1;return l;}
inline int get_fac(int x) {return data[x];}
}D;
inline void ins(int l,int r,int &rt,int lst,int val)
{
if(node[rt=++tot]=node[lst],++node[rt].Size,!(l^r)) return;
register int mid=l+r>>1;
val<=mid?ins(l,mid,node[rt].Son[0],node[lst].Son[0],val):ins(mid+1,r,node[rt].Son[1],node[lst].Son[1],val);
}
inline int qry(int l,int r,int rt1,int rt2,int k)
{
if(!(l^r)) return l;
register int mid=l+r>>1,t=node[node[rt2].Son[0]].Size-node[node[rt1].Son[0]].Size;
return t>=k?qry(l,mid,node[rt1].Son[0],node[rt2].Son[0],k):qry(mid+1,r,node[rt1].Son[1],node[rt2].Son[1],k-t);
}
public:
inline void Init(int len,int *num) {D.Init(len,num);for(register int i=1;i<=n;++i) ins(1,D.cnt,Root[i],Root[i-1],D.get_val(num[i]));}
inline int Query(int l,int r,int k) {return D.get_fac(qry(1,D.cnt,Root[l-1],Root[r],k));}
};
【洛谷3865】【模板】ST表
练了一下\(RMQ\)，毕竟这个算法我经常写炸。
class Class_RMQ
{
private:
int Log[N+5],Max[N+5][LogN+5];
public:
inline void Init(int *data)
{
register int i,j;
for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
for(i=1;i<=n;++i) Max[i][0]=data[i];
for(j=1;(1<<j-1)<=n;++j) for(i=1;i+(1<<j-1)<=n;++i) Max[i][j]=max(Max[i][j-1],Max[i+(1<<j-1)][j-1]);
}
inline int get_max(int x,int y)
{
register int k=Log[y-x+1];
return max(Max[x][k],Max[y-(1<<k)+1][k]);
}
};
【洛谷3390】【模板】矩阵快速幂
对于矩阵乘法及矩阵快速幂我之前学过，但现在已经忘得差不多了... ...
所以相当于又重学了一遍吧。
class Class_Matrix
{
private:
int n,m;
public:
int num[N+5][N+5];
Class_Matrix(int x=0,int y=0):n(x),m(y){memset(num,0,sizeof(num));}
inline friend Class_Matrix operator * (Class_Matrix x,Class_Matrix y)
{
register int i,j,k;register Class_Matrix res(x.n,y.m);
for(i=1;i<=x.n;++i) for(j=1;j<=y.m;++j) for(k=1;k<=x.m;++k) (res.num[i][j]+=1LL*x.num[i][k]*y.num[k][j]%XRY)%=XRY;
return res;
}
inline friend Class_Matrix operator ^ (Class_Matrix x,LL y)
{
register Class_Matrix res(x.n,x.n);
for(register int i=1;i<=x.n;++i) res.num[i][i]=1;
while(y) (y&1)&&(res=res*x,0),x=x*x,y>>=1;
return res;
}
};
【洛谷3375】【模板】KMP字符串匹配
对\(KMP\)这个东西我真的是一脸懵逼。
勉勉强强莫名其妙过了样例，一交结果只有\(80\)分。
仔细一检查+调试，总算发现自己少写了一个\(=\)。
好不容易过了。
class Class_KMP
{
private:
int Next[N+5];
inline void GetNext(string s1,string s2)
{
register int i,j=Next[0]=-1,len1=s1.length(),len2=s2.length();
for(i=1;i<=len2;++i)
{
while(~j&&s2[i-1]^s2[j]) j=Next[j];
Next[i]=++j;
}
}
public:
inline void Solve(string s1,string s2)
{
int i,j=-1,len1=s1.length(),len2=s2.length();
for(GetNext(s1,s2),i=0;i<=len1;++i)
{
while(~j&&s1[i-1]^s2[j]) j=Next[j];
if(++j==len2) F.write(i-len2+1),j=Next[j],F.writec('\n');
}
for(i=1;i<=len2;++i) F.write(Next[i]),F.writec(' ');
}
};
【洛谷3811】【模板】线性求逆元
线性求逆元我现在是真的不会了。
重新看了一下以前写过的博客：浅谈乘法逆元的三种解法，才弄懂了逆元应该怎么求。
class Class_InvIniter
{
public:
int Inv[N+5];Class_InvIniter() {Inv[1]=1;}
inline void Init(int x,int XRY) {for(register int i=2;i<=x;++i) Inv[i]=(-1LL*(XRY/i)*Inv[XRY%i]%XRY+XRY)%XRY;}
}InvIniter;
【洛谷3372】【模板】线段树1&&【洛谷3373】【模板】线段树2
线段树应该还是比较简单的一种数据结构吧。
但是，一题因为没开\(long\ long\)，一题因为没取模，都尴尬地\(WA\)了好几发。
class Class_SegmentTree
{
private:
#define Left l,mid,rt<<1
#define Right mid+1,r,rt<<1|1
#define PushUp(x) (node[x]=node[x<<1]+node[x<<1|1])
#define PushDown(x) (node[x].flag&&(node[x<<1].F5(node[x].flag,mid-l+1),node[x<<1|1].F5(node[x].flag,r-mid),node[x].flag=0))
int n;LL data[N+5];
struct Tree
{
LL Sum,flag;
Tree(LL x=0,LL f=0):Sum(x),flag(f){}
inline friend Tree operator + (Tree x,Tree y) {return Tree(x.Sum+y.Sum);}
inline void F5(LL x,int len) {Sum+=x*len,flag+=x;}
}node[N<<2];
inline void bld(int l,int r,int rt)
{
if(!(l^r)) return (void)(node[rt]=Tree(data[l]));
register int mid=l+r>>1;
bld(Left),bld(Right),PushUp(rt);
}
inline void upt(int l,int r,int rt,int ul,int ur,LL val)
{
if(ul<=l&&r<=ur) return (void)(node[rt].F5(val,r-l+1));
register int mid=l+r>>1;
PushDown(rt),ul<=mid&&(upt(Left,ul,ur,val),0),ur>mid&&(upt(Right,ul,ur,val),0),PushUp(rt);
}
inline LL qry(int l,int r,int rt,int ql,int qr)
{
if(ql<=l&&r<=qr) return node[rt].Sum;
register int mid=l+r>>1;register LL res=0;
return PushDown(rt),ql<=mid&&(res+=qry(Left,ql,qr)),qr>mid&&(res+=qry(Right,ql,qr)),res;
}
public:
inline void Build(int len,LL *num) {n=len;for(register int i=1;i<=n;++i) data[i]=num[i];bld(1,n,1);}
inline void Update(int l,int r,LL val) {upt(1,n,1,l,r,val);}
inline LL Query(int l,int r) {return qry(1,n,1,l,r);}
};
class Class_SegmentTree
{
private:
#define Left l,mid,rt<<1
#define Right mid+1,r,rt<<1|1
#define PushUp(x) (node[x]=node[x<<1]+node[x<<1|1])
#define PushDown(x) ((node[x].flag1^1||node[x].flag2)&&(node[x<<1].F5(node[x].flag1,node[x].flag2,mid-l+1),node[x<<1|1].F5(node[x].flag1,node[x].flag2,r-mid),node[x].flag1=1,node[x].flag2=0))
int n;int data[N+5];
struct Tree
{
int Sum,flag1,flag2;
Tree(int x=0,int f1=1,int f2=0):Sum(x),flag1(f1),flag2(f2){}
inline friend Tree operator + (Tree x,Tree y) {return Tree(GetSum(x.Sum,y.Sum));}
inline void F5(int x,int y,int len) {Sum=GetSum(1LL*Sum*x%XRY,1LL*y*len%XRY),flag1=1LL*flag1*x%XRY,flag2=GetSum(1LL*flag2*x%XRY,y);}
}node[N<<2];
inline void bld(int l,int r,int rt)
{
if(!(l^r)) return (void)(node[rt]=Tree(data[l]));
register int mid=l+r>>1;
bld(Left),bld(Right),PushUp(rt);
}
inline void mul(int l,int r,int rt,int ul,int ur,int val)
{
if(ul<=l&&r<=ur) return (void)(node[rt].F5(val,0,r-l+1));
register int mid=l+r>>1;
PushDown(rt),ul<=mid&&(mul(Left,ul,ur,val),0),ur>mid&&(mul(Right,ul,ur,val),0),PushUp(rt);
}
inline void add(int l,int r,int rt,int ul,int ur,int val)
{
if(ul<=l&&r<=ur) return (void)(node[rt].F5(1,val,r-l+1));
register int mid=l+r>>1;
PushDown(rt),ul<=mid&&(add(Left,ul,ur,val),0),ur>mid&&(add(Right,ul,ur,val),0),PushUp(rt);
}
inline int qry(int l,int r,int rt,int ql,int qr)
{
if(ql<=l&&r<=qr) return node[rt].Sum;
register int mid=l+r>>1,res=0;
return PushDown(rt),ql<=mid&&Inc(res,qry(Left,ql,qr)),qr>mid&&Inc(res,qry(Right,ql,qr)),res;
}
public:
inline void Build(int len,int *num) {n=len;for(register int i=1;i<=n;++i) data[i]=num[i];bld(1,n,1);}
inline void Mul(int l,int r,int val) {mul(1,n,1,l,r,val);}
inline void Add(int l,int r,int val) {add(1,n,1,l,r,val);}
inline int Query(int l,int r) {return qry(1,n,1,l,r);}
};
【洛谷1939】【模板】矩阵加速（数列）
这题其实就是前面矩阵快速幂的应用。
因此代码省略了。
【洛谷3379】【模板】最近公共祖先（LCA）
\(LCA\)可谓是一个比较常用的技巧吧。
常见的\(LCA\)据说有\(4\)中：倍增\(LCA\)、树剖\(LCA\)、\(Tarjan\ LCA\)和\(RMQ\ LCA\)。
但我只会第一种。
class Class_LCA
{
private:
int Depth[N+5],fa[N+5][LogN+5];
public:
inline void Init(int x=0)
{
register int i;
for(i=1;i<=LogN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(i=lnk[x];i;i=e[i].nxt) e[i].to^fa[x][0]&&(Depth[e[i].to]=Depth[fa[e[i].to][0]=x]+1,Init(e[i].to),0);
}
inline int Query(int x,int y)
{
register int i;
if(Depth[x]<Depth[y]) swap(x,y);
for(i=0;Depth[x]^Depth[y];++i) ((Depth[x]^Depth[y])&(1<<i))&&(x=fa[x][i]);
if(!(x^y)) return x;
for(i=LogN;~i;--i) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);
return fa[x][0];
}
};
【洛谷3807】【模板】卢卡斯定理
这题数据真的很水，貌似暴力也可以过... ...
class Class_Lucas
{
private:
#define GetC(x,y) (x<y?0:(1LL*Fac[x]*Inv[y]%XRY*Inv[x-y]%XRY))
int Fac[N+5],Inv[N+5];
inline int quick_pow(int x,int y)
{
register int res=1;
while(y) (y&1)&&(res=1LL*res*x%XRY),x=1LL*x*x%XRY,y>>=1;
return res;
}
public:
inline void Init()
{
register int i;
for(i=1,Fac[0]=1;i<XRY;++i) Fac[i]=1LL*Fac[i-1]*i%XRY;
for(i=XRY-2,Inv[XRY-1]=quick_pow(Fac[XRY-1],XRY-2);~i;--i) Inv[i]=1LL*Inv[i+1]*(i+1)%XRY;
}
inline int C(int x,int y)
{
if(x<y) return 0;if(!y) return 1;
return 1LL*GetC(x%XRY,y%XRY)*C(x/XRY,y/XRY)%XRY;
}
};
【洛谷2197】【模板】nim游戏
这种博弈论题还是比较简单的。
只要求出异或和，异或和为\(0\)输出\(No\)，不为\(0\)输出\(Yes\)。
代码略。
【洛谷1439】【模板】最长公共子序列
\(O(n^2)\)的最长公共子序列是很好求的。
但观察数据，显然\(O(n^2)\)会被卡。
考虑两个序列分别是\(1\sim n\)的排列，就不难想到将其转化成最长上升子序列来实现\(O(nlogn)\)求解。
代码略。
【洛谷3386】【模板】二分图匹配
自然，这道题可以用网络流来做。
但我写的是匈牙利算法。
class Class_Hungarian
{
private:
int s[N+5],vis[N+5];
public:
inline bool Match(int x,int Time)
{
for(register int i=lnk[x];i;i=e[i].nxt)
{
if(!(vis[e[i].to]^Time)) continue;
if(vis[e[i].to]=Time,!s[e[i].to]||Match(s[e[i].to],Time)) return s[e[i].to]=x,true;
}
return false;
}
};
【洛谷2613】【模板】有理数取余
这应该是比较裸的乘法逆元。
唯一要注意的是，为了避免高精度，我们可以一边读入一边取模。
代码略。
【洛谷3805】【模板】manacher算法
\(Manacher\)算法是比较常见的回文算法。
我个人认为它还是比较重要的吧。
class Class_Manacher
{
private:
int len,p[(N<<1)+5];char ns[(N<<1)+5];
public:
inline void Init(char *s)
{
register int i,l=strlen(s);
for(ns[i=0]='!',ns[len=1]='%';i<l;++i) ns[++len]=s[i],ns[++len]='%';
ns[++len]='?';
}
inline int GetAns()
{
register int i,Max=0,id,ans=0;
for(i=1;i<len;++i)
{
p[i]=i<=Max?min(p[(id<<1)-i],p[id]+id-i):0;
while(!(ns[i-p[i]]^ns[i+p[i]])) ++p[i];
i+p[i]>Max&&(Max=i+p[id=i]),Gmax(ans,p[i]-1);
}
return ans;
}
};
【洛谷3389】【模板】高斯消元法
高斯消元真的是一个比较有趣的数学算法。
判断变量是否为\(0\)时写了一个\(v<eps\)，忘记了还有负数... ...
class Class_Gauss
{
private:
#define eps 1e-15
#define Exit() (puts("No Solution"),exit(0),0)
double v[N+5][N+5],res[N+5];
inline void swap(double x,double y) {double t=x;x=y,y=t;}
inline void FindLine(int x)
{
register int i,p=x;
while(fabs(v[p][x])<eps&&p<=n) ++p;
if(!(p^x)) return;
for(p>n&&Exit(),i=1;i<=n;++i) swap(v[x][i],v[p][i]);
}
public:
inline void GetData(int x,int y,double t) {v[x][y]=t;}
inline void GetRes(int x,int t) {res[x]=t;}
inline void Solve()
{
register int i,j,k;register double delta;
for(i=1;i<=n;++i) for(FindLine(i),j=i+1;j<=n;++j) for(res[j]+=res[i]*(delta=-v[j][i]/v[i][i]),k=i;k<=n;++k) v[j][k]+=v[i][k]*delta;
for(i=n;i;--i) for(fabs(v[i][i])<eps&&Exit(),res[i]/=v[i][i],j=i-1;j;--j) res[j]-=v[j][i]*res[i];
}
inline void PrintAns() {for(register int i=1;i<=n;++i) printf("%.2lf\n",res[i]);}
};
【洛谷3388】【模板】割点（割顶）
好吧，对于割点与桥，我真的是忘得一干二净。
重新去学习了一遍... ...
class Class_CutPointFinder
{
private:
int d,low[N+5];
public:
int dfn[N+5],IsCut[N+5];
inline void Solve(int x,int lst=0)
{
register int i,tot=0;
for(dfn[x]=low[x]=++d,i=lnk[x];i;i=e[i].nxt)
{
if(!(e[i].to^lst)) continue;
if(!dfn[e[i].to])
{
Solve(e[i].to,x),Gmin(low[x],low[e[i].to]),++tot;
if(lst&&low[e[i].to]>=dfn[x]) IsCut[x]=1;
}
else Gmin(low[x],dfn[e[i].to]);
}
if(!lst&&tot>1) IsCut[x]=1;
}
};
【洛谷3385】【模板】负环
这题看起来只是一道简单的板子题，以为很快就能过的。
没想到的是，先是看错了题目，好不容易才调过样例，一交\(WA\)了，手玩感觉没问题，才发现题目中说大于等于\(0\)的边是双向边... ...
接下来更是尴尬，第\(9\)个点一直在\(WA\)与\(TLE\)中徘徊。
听说用\(STL\)队列会超时，因此我一直是手写循环队列的。没想到把手写队列改成了\(STL\)队列之后，原来\(TLE\)的点竟\(50ms\)出答案了！
真香。
class Class_NegativeRingFinder
{
private:
int dis[N+5],Inqueue[N+5];queue<int> q;
public:
int vis[N+5];
inline bool Exist(int s)
{
register int i,k;
for(i=1;i<=n;++i) dis[i]=INF,Inqueue[i]=vis[i]=0;
while(!q.empty()) q.pop();q.push(1);
dis[s]=0,Inqueue[s]=1;
while(!q.empty())
{
for(Inqueue[k=q.front()]=0,q.pop(),i=lnk[k];i;i=e[i].nxt)
{
if(dis[e[i].to]>dis[k]+e[i].val)
{
if((vis[e[i].to]=vis[k]+1)>=n) return true;
if(dis[e[i].to]=dis[k]+e[i].val,!Inqueue[e[i].to]) Inqueue[e[i].to]=1,q.push(e[i].to);
}
else if(dis[e[i].to]==dis[k]+e[i].val&&e[i].val>0&&(vis[e[i].to]+=vis[k])>=n) return true;
}
}
return false;
}
};
【洛谷3387】【模板】缩点
这题可不是一道单纯的缩点题，还要在\(DAG\)上跑\(DP\)。
实际上还是蛮简单的。
突然发现我最近用了大约\(1\)个月的一个\(\#define\)出锅了，莫名慌了。
或许我在\(NOIP\)期间是不会用\(\#define\)了，即使它比函数的常数要小得多。
代码我还是单纯贴一下缩点的代码吧：
class Class_Tarjan
{
private:
int d,Top,low[N+5],InStack[N+5],Stack[N+5];
public:
int cnt,dfn[N+5],col[N+5],sum[N+5];
inline void Solve(int x,int lst=0)
{
register int i;
for(dfn[x]=low[x]=++d,InStack[Stack[++Top]=x]=1,i=lnk[x];i;i=e[i].nxt)
{
if(!dfn[e[i].to]) Solve(e[i].to,x),Gmin(low[x],low[e[i].to]);
else if(InStack[e[i].to]) Gmin(low[x],dfn[e[i].to]);
}
if(low[x]^dfn[x]) return;
sum[col[x]=++cnt]=val[x],InStack[x]=0;
while(Stack[Top]^x) sum[col[Stack[Top]]=cnt]+=val[Stack[Top]],InStack[Stack[Top--]]=0;
--Top;
}
};
【洛谷3376】【模板】网络最大流
这应该不是提高组范围内的吧。
依然智障地将一个\(t\)写成了\(T\)，又是一波调试。
class Class_Dinic
{
private:
int FlowTotal,q[N+5],cur[N+5],Depth[N+5];
inline bool BFS()
{
register int i,k,H=1,T=1;
for(i=1;i<=n;++i) Depth[i]=0;Depth[q[1]=s]=1;
while(H<=T&&!Depth[t]) for(i=lnk[k=q[H++]];i;i=e[i].nxt) !Depth[e[i].to]&&e[i].Cap>e[i].Flow&&(Depth[q[++T]=e[i].to]=Depth[k]+1);
return Depth[t];
}
inline int DFS(int x,int f=INF)
{
if(!(x^t)||!f) return f;
register int i,res=0,NowFlow;
for(i=lnk[x];i;i=e[i].nxt)
{
if(Depth[e[i].to]^(Depth[x]+1)||e[i].Cap<=e[i].Flow||!(NowFlow=DFS(e[i].to,min(f,e[i].Cap-e[i].Flow)))) continue;
if(e[i].Flow+=NowFlow,e[((i-1)^1)+1].Flow-=NowFlow,res+=NowFlow,!(f-=NowFlow)) return res;
}
return res;
}
public:
inline void Solve()
{
register int i;
while(BFS())
{
for(i=1;i<=n;++i) cur[i]=lnk[i];
FlowTotal+=DFS(s);
}
F.write(FlowTotal);
}
};
【洛谷3808】【模板】AC自动机（简单版）&&【洛谷3796】【模板】AC自动机（加强版）
\(AC\)自动机是一个比较神奇的字符串算法，当时学的时候也花了挺多时间去理解，今天又用了一个多小时才做掉了简单版的板子题。
错误原因很尴尬，题目中文本串是在最后一行读入的，结果我以为是在第一行读入的... ...结果莫名\(RE\)调试到心态爆炸... ...
加强版的板子我炸得更惨，我现在才知道连续开多个字符数组要稍微开大一点，不然会把你一次性全部输出... ...
代码就贴一下简单版的吧：
class Class_AC_Automation
{
private:
#define Size 1000000
int rt,tot,q[Size+5];
struct Trie
{
int Sum,Next,Son[27];
}node[Size+5];
public:
Class_AC_Automation() {rt=tot=1;}
inline void Insert(char *s,int len)
{
register int i,x=rt,nxt;
for(i=0;i<len;++i)
{
if(!node[x].Son[nxt=s[i]&31]) node[x].Son[nxt]=++tot;
x=node[x].Son[nxt];
}
++node[x].Sum;
}
inline void GetNext()
{
register int i,k,H=1,T=0;
for(i=1;i<=26;++i) node[rt].Son[i]?node[q[++T]=node[rt].Son[i]].Next=rt:node[rt].Son[i]=rt;
while(H<=T) for(k=q[H++],i=1;i<=26;++i) node[k].Son[i]?node[q[++T]=node[k].Son[i]].Next=node[node[k].Next].Son[i]:node[k].Son[i]=node[node[k].Next].Son[i];
}
inline int GetAns(char *s,int len)
{
register int i,x=rt,p,res=0;
for(i=0;i<len;++i)
{
p=x=node[x].Son[s[i]&31];
while(p^rt)
{
if(~node[p].Sum) res+=node[p].Sum,node[p].Sum=-1;else break;
p=node[p].Next;
}
}
return res;
}
};
后记
虽然还有很多板子没做，但\(NOIP2018\)还是很快到来了，而直至\(NOIP\)结束，我也没能成功把板子刷完。
关于\(NOIP2018\)，可以看这篇博客：NOIP2018学军中学游记。
不得不承认，我刷的这些板子，在此次比赛中没有发挥任何作用。
但是我想，复习算法总是有一定意义的吧。（自我安慰）