板子——2019 summer
[TOC]
树论&图论
网络流
使用范围：主要解决的问题就是最大流（从源点到汇点的总量最大）和最小割（断掉最小权值的边使得源点不能到达汇点），似乎还能解决二分图的问题
思想：利用BFS判断每个点的深度，然后利用DFS算出每条链上的最小权值，每次修改的时候更新路上的所有边。使用的时候记得考虑建图。
代码板子：
struct Edge{
int to;
LL val;
Edge(int _to,int _val){to=_to;val=_val;}
Edge(){}
}edge[maxn*2];
LL dis[maxn];
vector<int> flow[maxn];
int deep[maxn];
void addedge(int x,int y,LL c){
edge[coun].to=y,edge[coun].val=c;
flow[x].push_back(coun++);
edge[coun].to=x,edge[coun].val=0;
flow[y].push_back(coun++);
}
void init(){
for(int i=0;i<maxn;++i){
ori[i].clear();
flow[i].clear();
coun=0;
}
}
bool bfs_divide(int s,int t){
memset(deep,-1,sizeof(deep));
deep[s]=0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<flow[u].size();++i){
int tmp=flow[u][i];
int v=edge[tmp].to;
LL val=edge[tmp].val;
if(val&&deep[v]==-1){
deep[v]=deep[u]+1;
q.push(v);
}
}
}
return deep[t]!=-1;
}
LL dfs_cut(int u,LL val){
if(u==n) return val;
LL res=0;
for(int i=0;i<flow[u].size();++i){
int tmp=flow[u][i];
if(edge[tmp].val&&deep[u]+1==deep[edge[tmp].to]){
LL mid=dfs_cut(edge[tmp].to,min(val,edge[tmp].val));
val-=mid;
res+=mid;
edge[tmp].val-=mid;
edge[tmp^1].val+=mid;
if(val==0) break;
}
}
return res;
}
LL maxflow(int s,int t){
LL res=0;
while(bfs_divide(int s,int t)){
res+=dfs_cut(s,INFL);
}
return res;
}
Dijkstra最短路
使用范围：无负环的图
思想：每次优先选择的点都是离自己最近的点，由此得到的路径一定是最短的。
模板代码：
struct Edge{
int to;
LL val;
Edge(int _to,int _val){to=_to;val=_val;}
Edge(){}
}edge[maxn*2];
LL dis[maxn];
vector<Edge> ori[maxn];
struct Node{
int num;
LL dis;
Node(int n,LL d):num(n),dis(d){}
Node(){}
bool operator <(const Node& b)const{
return dis>b.dis;
}
};
void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
priority_queue<Node> q;
q.push(Node(1,0));
while(!q.empty()){
int u=q.top().num;
LL tmp=q.top().dis;
q.pop();
if(dis[u]!=tmp) continue;
int sz=ori[u].size();
for(int i=0;i<sz;i++){
int v=ori[u][i].to;
LL val=ori[u][i].val;
if(dis[u]+val<dis[v]){
dis[v]=dis[u]+val;
q.push(Node(v,dis[v]));
}
}
}
}
SPFA
适用范围：带负权圈的图，用dijkstra会死循环。spfa原理是记录每个点的入队次数来规避负权圈。
思想：反正就是那么回事自己理解一下
模板代码：
bool SPFA(int s){
queue<int>q;
q.push(s);vis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=0;i<G[u].size();++i){
int v=G[u][i].to,val=G[u][i].val;
if(dis[u]<INF&&dis[v]>dis[u]+val){
dis[v]=dis[u]+val;
if(!vis[v]){
q.push(v);vis[v]=1;
if(++cnt[v]>n) return false;
}
}
}
}
return true;
}
树链剖分
使用范围：对树结构进行区间序列操作的时候用。目前看起来是要对点权树使用，不过边权可以转换一下变成点权嘛……应该可以吧？
思想：每次找到子树多的儿子作为重儿子，然后把重儿子组成的链称为重链，对其他的轻儿子肯定也能组成以自己为根的重链的。然后利用优先遍历重链的方式决定树变成区间时的DFS序，让重链在区间上连续。对树的路径查找利用LCA实现(但实际上跟LCA是有区别的，由于进行了树链剖分，每次只要先处理更轻的链，然后往上走走，进一条链就好处理了)，之后结合线段树实现对区间求和、区间最值什么的。
模板代码：
struct Node{
int son,siz;//重儿子和子树大小，工具人变量，剖分完了就不需要了
int fa,deep,top，pos;//跳转时候用来定位比较什么的变量
int val;//工具人变量2组，给主席树/树状数组赋值用的玩意，赋完了就可以舍弃了呢，实际上可以开数组存不用放在结构体里吧
}node[maxn];
vector<int> tree[maxn];//反正边的信息在转换成区间后就不需要了
//随便拿个vector存一下吧
int dfsarray[maxn],tot;
void dfs1(int u,int fa){//第一个DFS用来处理出重儿子，并且从vector中得到树的父亲与深度信息
node[u].fa=fa;
node[u].son=0;
node[u].siz=1;
node[u].deep=node[fa].deep+1;
for(int i=0;i<tree[u].size();++i){
int v=tree[u][i];
if(v!=f) {dfs1(v);
node[u].siz+=node[v].siz;
if(node[node[u].son].siz<node[v].siz){
node[u].son=v;
}
}
}
void dfs2(int u,int ancient){//第二个dfs就是用来求dfs序的了
node[u].top=ancient;
node[u].pos=++tot;
dfsarray[tot]=node[u].val;
//dfs2(node[u].son,u,ancient);//自己真是个铁憨憨，要先判断有没有儿子
if(node[u].son)
dfs2(node[u].son,ancient);
for(int i=0;i<tree[u].size();++i){
int v=tree[u][i];
if(v!=node[u].fa&&v!=node[u].son){
dfs2(v,v);
}
}
}
线段树部分略，稍微贴一点跳的部分：
int sum_skip(int a,int b){
int res=0;
while(node[a].top!=node[b].top){
int aa=node[a].top,bb=node[b].top;
if(node[aa].deep<node[bb].deep) swap(a,b);
res+=qsum(1,node[aa].pos,node[a].pos);
a=node[a].top;
}
if(node[a].deep<node[b].deep) swap(a,b);
res+=qsum(1,node[b].pos,node[a].pos);
return res;
}
LCA
适用范围：树上a 到b 之间的路径之类的问题吧
思路：说白了就是二进制嘛，只要我预先处理出树上每个节点的往上走1、 2、 4、……2n层的点，然后让询问的两个点都往上跳，直到深度相同，两点再同时往上跳，此时的点就是要求的公共祖先点了嘛。预处理时间复杂度O(nlog(n))，每次询问的时间复杂度是O(log(n))。同样用DFS，遍历到每个点时，都处理出每个点往上走那么多层的距离。询问时再利用二进制让a b两点跳到同一深度，如果此时父节点不同则继续往上跳，直到父节点相同为止。
模板代码：
int vis[maxn];
LL dis[maxn],dep[maxn];
struct Edge{
int to,dis;
}
vector<Edge> tree[maxn];
int par[maxn][maxm];//最大为2^maxm的深度
void pre_dfs(int fa,int u,int depth,int dist){
dis[u]=dist;
dep[u]=depth;//更新点u的深度和到根节点的距离
if(u==1){
for(int i=0;i<maxm;i++)par[u][i]=u;//定1为根节点，则往上跳多少都是自身
}
else{
par[u][0]=fa;
for(int i=1;i<maxm;i++){
par[u][i]=par[par[u][i-1]][i-1];//2^i层的节点=u往上跳2^i-1层的点再往上跳2^i-1层
}
}
//处理完u之后再进行常规的DFS
int len=tree[u].size();
for(int i=0;i<len;i++){
int v=tree[u][i].to,d=tree[u][i].dis;
if(v!=fa) pre_dfs(u,v,depth+1,d+dist);
}
}
int skip(int a,int level){
for(int i=maxm-1;i>=0;i--){
if((1<<i)&level){//二进制的思想
a=par[a][i];
}
}
return a;
}
int lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);//保证a比较深
a=skip(a,dep[a]-dep[b]);
if(a==b) return a;
for(int i=maxm-1;i>=0;i--){//也是利用二进制思想从高位往低位逼近的思想
if(par[a][i]!=par[b][i]){
a=par[a][i];
b=par[b][i];
}
}
return par[a][0];
}
强连通分量缩点
使用范围：基本上是基础中的基础。缩点之后要为了目的服务才是关键。最常见的缩点就是为了应对某些情况下的单向性。比如poj-2186奶牛崇拜和hdu-5934炸弹连环引爆都具有单向的传递性。就需要缩点来减少问题规模。
思想：tarjan算法，使用DFS进行搜索。如果子树没有连到父节点以上的点，证明没有往回走的通路，则应该从这里断开，该点及其子树就是一个单独的强连通分量了。并且由于DFS是优先处理子树的，所以当你用栈来维护的时候如果栈顶不是目前节点，则说明他们都是构成强连通分量的你的翅膀。
vector<int> path[maxn];
int dfn[maxn],low[maxn],tot;//用于tarjan中维护。判断强连通的变量
bool in[maxn];//同上
stack<int> ss;//强连通分量栈不能少啊，当然你要是闲可以自己写
int block[maxn],ff;//退栈时将元素分到相应的块中，标记每个元素属于哪一块
void tarjan(int u){
low[u]=dfn[u]=++tot;
ss.push(u);
in[u]=true;
int v;
for(int i=0;i<path[u].size();++i){
v=path[u][i];
if(!dfn[v]){
tarjan(v);
if(low[v]<low[u]) low[u]=low[v];
}
else if(in[v]&&dfn[v]<low[u])
low[u]=dfn[v];
}
if(low[u]==dfn[u]){
++ff;
do{
v=ss.top();
ss.pop();
block[v]=ff;
in[v]=false;
}while(u!=v);
}
}
强连通分量求割点
使用范围：无向图中去掉点破坏其他点连通性的点称为割点
思想：若一个点在进行tarjan的DFS时其子节点们的low[v]<=dfn[u],意味着这个点不能在不经过u的情况下去到更高的点。（注意是无向图所以路不考虑方向）只要存在这样的子节点即说明该点是割点。根节点由于没有比它标号小的点所以需要特判，至少要有两个儿子节点满足上述关系。
void tarjan(int u,int fa){
dfn[u]=++tot;low[u]=tot;//这个就是DFS序
int son=0;
for(int i=0;i<path[u].size();++i){
int v=path[u][i];
if(v==fa) continue;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);//注意跟下面那个不同
if(low[v]>=dfn[u]){
son++;
if(u!=root || son>1){
cutpoint[u]= true;
}
}
}
else
low[u]=min(dfn[v],low[u]);//就是说要能够直接到达的点小而不能是间接到达的点小
}
}
针对两个low的不同考虑如下情况：
graph LR
a(1)---b(3)
c(2)---b
a---c
b---d(4)
b---e(5)
d---e
这个情况关系到上面的low判断的不同，目前先放在这里，晚上整理一下。结果晚上也没整理，自己感受一下吧。
欧拉回路 欧拉路径
适用范围：总之就是一笔画问题，如何不重复地走过所有的边。欧拉路是有两个度为奇数的点，从一点出发走到另一点，欧拉回路是度全为偶数，随便选个点走回来就完事了。
思想：重点是存边，然后需要移动点指向的边来使得不重复访问已经访问过的点。如果是来回都只算一遍还要用编号去掉相应的反向边。另外如果题目没保证存在，则需要判断欧拉回路是否存在。
模板代码：
void eular(){
ss.push(1);
while(!ss.empty()){
int u=ss.top(),i=head[u];
while(i&&vis[i]) i=Edge[i].nxt;
if(i){
ss.push(Edge[i].to);
vis[i]=true;//每条边只走一遍就是vis[i]=vis[i^1]=true;
head[u]=Edge[i].nxt;
}
else{
ss.pop();
res[++tot]=u;
}
}
}
以下模板没用过，这里先放在这里看一下
求桥
这里更新为了lyd《算法竞赛进阶指南》上求桥的板子
如果搜索树上某个点u的子节点v,dfn[u]<low[v]。那么u-v这条边是割边。
理性分析一下，这样说明v无法通过一条路径到达u本身和之前访问到的点，那么u,v这条边一旦断开，那么v和u就将不连通
注意重边的情况，我们再前向星数组中存双向边是(2,3)(4,5)一对一对的，那么在更新low的时候，要判断上一条到达u点的边是否跟当前枚举的边在本质上是一条边，如果是，那么就不能用来更新low。
inline void tarjan(int u,int in_edge)
{
int v;
bool flag=0;
dfn[u]=low[u]=++ind;
for(int i=ehead3[u];i;i=e3[i].nxt)
{
v=e3[i].to;
if(!dfn[v])
{
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
cut[e3[i].id]=cut[e3[i^1].id]=true;
}
else if(i!=(in_edge^1))
low[u]=min(low[u],dfn[v]);
}
}
双联通分量缩点
边双联通分量
求出桥以后去掉桥，剩下的连通块就是边双联通分量
inline void tarjan(int u,int last)
{
dfn[u]=low[u]=++ind;
int v;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(!dfn[v])
{
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
cut[e[i].id]=cut[e[i^1].id]=true;
}
else if(i!=(last^1))
low[u]=min(low[u],dfn[v]);
}
}
inline void dfs(int u)
{
int v;
c[u]=dcc;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(c[v] || cut[e[i].id]) continue;
dfs(v);
}
}
inline void addc(int u,int v)
{
ce[++ccnt].to=v;ce[ccnt].nxt=cehead[u];
cehead[u]=ccnt;
}
inline void cdfs(int u,int last)
{
int v;
for(int i=cehead[u];i;i=ce[i].nxt)
{
v=ce[i].to;
if(v==last) continue;
dep[v]=dep[u]+1;fa[v]=u;
cdfs(v,u);
}
}
inline void prework()
{
for(int i=1;i<=n;i++)
ehead[i]=0,f[i]=0;
int u,v;cnt=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v,i);add(v,u,i);
cut[i]=false;
}
ind=0;
for(int i=1;i<=n;i++)
dfn[i]=0,low[i]=0,c[i]=0;
tarjan(1,0);
dcc=0;
for(int i=1;i<=n;i++)
if(!c[i])
{
++dcc;f[dcc]=dcc;
dfs(i);
cehead[dcc]=0;dep[dcc]=0;fa[dcc]=0;
}
ccnt=1;
for(int i=2;i<=cnt;i+=2)
{
u=e[i].to;v=e[i^1].to;
if(c[u]==c[v]) continue;
addc(c[u],c[v]);addc(c[v],c[u]);
}
fa[1]=1;
cdfs(1,0);
}
点双联通分量
inline void tarjan(int u)
{
dfn[u]=low[u]=++ind;s[++top]=u;
if(u==rt && ehead[u]==0)
{
dcc[++dcccnt].push_back(u);
return;
}
int son=0,v;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
son++;
if(u!=rt || son>1)
cut[u]=true;
dcccnt++;
int d;
do
{
d=s[top--];
dcc[dcccnt].push_back(d);
}while(d!=v);
dcc[dcccnt].push_back(u);
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
inline void mainwork()
{
for(int i=1;i<=n;i++)
if(!dfn[i])
{
rt=i;top=0;
tarjan(i);
}
}
区间数
数位DP
使用范围：一段区间上满足条件的数的个数
思想：实际上也是先暴力模拟然后记忆化搜索
代码板子：
LL posi[10][2];
LL dig[20];
LL dfs(int p,bool bef,bool edge){
if(p==0) return 1;
LL sz= edge? dig[p]: 9;
if(posi[p][bef]!=-1&&!edge) return posi[p][bef];//边界特判
LL ans=0;
for(int i=0;i<=sz;++i){
if(i==4) continue;
if(i==2&&bef) continue;
ans+=dfs(p-1,i==6,edge&&(i==sz));
}
if(!edge) posi[p][bef]=ans;//边界特判
return ans;
}
LL init(int a){
int i=0;
memset(dig,0,sizeof(dig));
while(a){
dig[++i]=a%10;
a/=10;
}
LL res= dfs(i,false,true);
return res;
}
线段树
使用范围：对区间内点的修改与区间修改，复杂度可以降低到 log(n) 级别。不过目前自己还是只会区间加乘与单点加乘
思想：二进制思想，分别记录区间1-n、 1-n/2、n/2+1-n等等，区间修改就往下找到区间，单点修改就找到点。并且区间的修改需要使用lazy标记，在下次遍历到更下面的区间时进行更新。
模板代码：(进行区间加法的)
struct node{
int l,r,sum,tag;
}tree[maxn<<2];
void build(int k,int l,int r){
tree[k].l=l,tree[k].r=r;
if(l==r){
tree[k].sum=a[l];
return ;
}
int mid=(tree[k].l+tree[k].r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void change_tag(int k){
if(tree[k].l==tree[k].r){
tree[k].sum+=tree[k].tag;
}
else{
tree[k].sum+=(tree[k].r-tree[k].l+1)*tree[k].sum;
tree[k<<1].tag+=tree[k].tag;
tree[k<<1|1].tag+=tree[k].tag;
}
tree[k].tag=0;
}
void add(int k,int l,int r,int x){
if(tree[k].l==l&&tree[k].r==r) {
tree[k].tag+=x;
return;
}
if(tree[k].tag) change_tag(k);
tree[k].sum+=(r-l+1)*x;
int mid=(tree[k].l+tree[k].r)>>1;
if(r<=mid){ add(k<<1,l,r,x);}
else if(l>mid){add(k<<1|1,l,r,x)}
else {add(k<<1,l,mid,x);
add(k<<1|1,mid+1,r,x);
}
}
int query(int k,int l,int r){
if(tree[k].tag) change(k);
if(tree[k].l==l&&tree[k].r==r) return tree[k].sum;
int mid=(tree[k].l+tree[k].r)>>1;
if(r>=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
主席树
使用范围：需要知道过去状态的线段树
思想：可持久化线段树，存储每个修改前的线段树，因此一开始不能直接建树，一开始只能建一个空节点然后渐渐按照线段树的思想对其进行扩充。建议开到20*maxn。未被修改的子树会直接接到新的线段树的原位上，所以整体结构不如线段树那样整洁优美，导致不能通过下标确定子树位置，需要在节点信息中额外保存。另外进行区间修改的时候是不清空lazy的，通过累加路径上的lazy带来的影响，来修正结果，这样就可以减少往下递归的次数，生成更少的点，从而降低空间复杂度。
struct node{
LL lazy,sum;
int ls,rs;
}tree[maxn*20];
int root[maxn],tot,timestamp;
//kl kr用来标记区间
LL ori[maxn], sum[maxn];;
void pre_build(int k,int l,int r){
tree[k].lazy=0;
tree[k].sum=sum[r]-sum[l-1];
if(l==r) return;
tree[k].ls=++tot;//常规线段树的预先建树时会导致产生几个空点
tree[k].rs=++tot;//毕竟都保存了左右儿子了就前序遍历建的紧凑一点吧，不然tot值会出错
int mid=(l+r)>>1;
pre_build(tree[k].ls,l,mid);
pre_build(tree[k].rs,mid+1,r);
}
void tree_insert(int kl,int kr,int l,int r,int &k,LL val){
tree[++tot]=tree[k];
k=tot;//修改K值以符合实际的新情况，连带修改K原来的位置
if(l==kl&&r==kr) {
tree[k].lazy+=val;//正好是区间的情况下只改lazy的值
return;
}
else tree[k].sum+=val*(r-l+1);//包含关系就要清楚的加上
int mid=(kl+kr)>>1;
if(r<=mid) tree_insert(kl,mid,l,r,tree[k].ls,val);
else if(l>mid) tree_insert(mid+1,kr,l,r,tree[k].rs,val);
else {
tree_insert(kl,mid,l,mid,tree[k].ls,val);
tree_insert(mid+1,kr,mid+1,r,tree[k].rs,val);
}
}
LL query(int kl,int kr,int l,int r,int k){
LL res=tree[k].lazy*(r-l+1);//有lazy表示后面都被修改了，所以加上一个值
int mid=(kl+kr)>>1;
if(kl==l&&kr==r) return res+tree[k].sum;
if(r<=mid) res+=query(kl,mid,l,r,tree[k].ls);
else if(l>mid) res+=query(mid+1,kr,l,r,tree[k].rs);
else res+=query(kl,mid,l,mid,tree[k].ls)+query(mid+1,kr,mid+1,r,tree[k].rs);
return res;
}
//同时还要在root数组中存储每个树的头，在生成新的树时root[i]=root[i-1]继承上个树的结果
//对root[i]的值的修改则是交给tree_insert函数进行的
还可以处理区间第k大问题，将最初的建树变成插入的过程，使得每加入一个值就生成新的树，每次记录节点下的叶子数。如果要求[l,r]区间上的第k大，则计算左右子树增加的值，与K进行比较来快速确定。时间复杂度大概是log(n)，空间复杂度挺大的，nlog(n)+mlog(n)?大概吧。在处理区间第k大的时候，实际上是建了一个1 ~ INF的线段树，此时区间[ l, r ]中的和就意味着值为 [ l,r ]的点有多少。
代码板子：
const int maxn=100005;
struct Node{
int ls,rs,sum;
//求第k大的时候不需要区间信息就不存左右节点了
//正常情况下还是要像正常线段树一样存的
Node(int l,int r):ls(l),rs(r){}
Node(){}
}tree[maxn*20];
int coun,root[maxn];
void tree_insert(int num,int &k,int l,int r){
tree[++coun]=tree[k];//先新建点继承原先的数据
k=coun;//主要是为了修改父节点的左右儿子的值
tree[k].sum++;//更新一下数据，如果有别的也要更新别的
if(l==r) return ;//到叶子节点了
int mid=(l+r)>>1;
if(num<=mid)
tree_insert(num,tree[k].ls,l,mid);
else tree_insert(num,tree[k].rs,mid+1,r);
}
int query(int before,int after,int k,int l,int r){
//before 与after 存储的是前后两个线段树的头节点
if(l==r) return l;
int leftadd=tree[tree[after].ls].sum-tree[tree[before].ls].sum;
//这个求出来是第k小，如果要求第k大要考虑右侧增加的数
int mid=(l+r)>>1;
if(k<=leftadd)
query(tree[before].ls,tree[after].ls,k,l,mid);
else query(tree[before].rs,tree[after].rs,k-leftadd,mid+1,r);
}
还会用到一个离散化操作：
for(int i=1;i<=n;++i){
scanf("%d",&ori[i]);
discrete[i]=ori[i];
}
coun=0;
sort(discrete+1,discrete+n+1);
int newn=unique(discrete+1,discrete+n+1)-discrete-1;
for(int i=1;i<=n;++i)
ori[i]=lower_bound(discrete+1,discrete+newn+1,ori[i])-discrete;
树状数组
适用范围：前缀和、单点修改、区间加法等等,复杂度O(log2n)，好处就是写起来方便，对单点修改比较好使。
思想：二进制的思想，对一个数k，其最低二进制位x存储有1-x的信息，这样就可以将n的数值修改或查询变成只取logn个数的算法。
模板代码：
LL sumarray[maxn];//普通的求和,别的情况就改后头的函数吧
int n;
inline int lowbit(int x){return x&-x;}
void change_node(int u,int val){
for(;u<=n;u+=lowbit(u))
sumarray[u]+=val;
}
int query(int l,int r){
}
线性基
适用范围：区间异或相关的各种问题。
思想：实际上利用的是异或的性质，在数字最大为64位的情况下，64个最高位不同的二进制数从中随意选数来异或，能表示264个数，如果一个数在与现有数字异或的过程中变成0了，说明这个数可以由现有的数进行异或得到（毕竟异或运算的逆运算就是异或）。然而如果这个数字没有被消掉，那肯定会有某个高位是0，让你可以把数插进去。同时由于异或同一个数两次等于没异或，让你可以在遍历线性基一遍的时间内得到你想要的异或结果。
模板代码：(异或第k小)
bool build(LL x){
for(int i=62;i>=0;--i){
if(x&(1ll<<i)){
if(lis[i]) x^=lis[i];
else {
lis[i]=x;
return true;
}
}
}
havezero=true;
return false;
}
bool rebuild(){
coun=0;
for(int i=62;i>=1;--i){//i=0的时候必定为1，不用往下异或了
if(lis[i]){
for(int j=i-1;j>=0;--j){
if(lis[i]&(1ll<<j)){//保证有减小
lis[i]^=lis[j];
}
}
}
}//由于线性基性质+每次只改变后面j位,所以扫一遍就够了
for(int i=0;i<=62;++i){
if(lis[i])
sml[coun++]=lis[i];
}
}
LL ksmall(int k){
if(havezero) --k;
LL res=0;
if(k>=(1ll<<coun)) return -1;
for(int i=coun;i>=0;--i){
if(k&(1ll<<i))
res^=sml[i];
}
return res;
}
如果是区间异或的板子：
void insert(int num,int k){
int nown=num,nowv=k;
for(int i=0;i<=30;++i){
xmxyji[num][i]=xmxyji[num-1][i];
posi[num][i]=posi[num-1][i];
}
for(int i=30;i>=0;--i){
if((1<<i)&k){
if(!xmxyji[num][i]){
xmxyji[num][i]=k;
posi[num][i]=nown;
return;
}
else{
if(nown>posi[num][i]){
swap(k,xmxyji[num][i]);
swap(nown,posi[num][i]);
}
k^=xmxyji[num][i];
}
}
}
return ;
}
int query(int l,int r){
int res=0;
if(l>r) swap(l,r);
for(int i=30;i>=0;--i){
if(posi[r][i]>=l){
if(res<(res^xmxyji[r][i]))
res^=xmxyji[r][i];
}
}
return res;
}
我tm竟然到线性基就没更新了吗……也太怠惰了吧
单调队列
适用范围：在数组里面移动的过程中的区间最值问题。
思想：需要维护的一方面是维护队首是最值，队尾是新插入的值。当队首已经过期的时候删去队首。每次插入新的元素就与队尾元素进行比较，比如维护的是最小值，如果新元素比队尾元素小，就删掉队尾，再跟新的队尾判断，直到队空或者新元素比队尾大，就将新元素加入队尾。最大值就是反过来的。可以用stl里面的deque来实现，不过挺容易的，实际上手写也很方便。维护单调队列复杂度整体是o(n),单次询问是o(1)，可以拿来做dp优化。
模板代码：
void max_insert(){//最开始写了一个纯数组存编号，但是找值太反人类，还是一并存值好理解
for(int i=1;i<=n;++i){
if(maxl!=maxr&&maxque[maxl].num<=i-k){
maxl=(maxl+1)%maxn;//队首退栈警告
}
//栈中的比要插入的值小的就没必要留在里面了
while(maxque[maxr-1].val<ori[i]&&maxl<maxr)
maxr=(maxr-1+maxn)%maxn;
maxque[maxr]=mq(ori[i],i);//单调队列是不存在插不进去的情况的
maxr=(maxr+1)%maxn;
resmax[i]=maxque[maxl].val;
}
}
数学问题
扩展欧几里得
适用范围：原本还拿来求求逆元什么的……结果发现快速幂用费马小定理速度差不多的情况下还更好写……但是还是记一下吧……万一用到了呢。
思想：欧几里得就完事了，然后从终态往前面算可能的值。总之就是ax+by=res这样子。关于y的计算可以稍微推一下式子。
模板代码：
int ex_gcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return b;
}
int res=ex_gcd(b,a%b,x,y);
int tmp=y;
y=x-y*(a/b);
x=tmp;
return res;
}
拉格朗日插值法
适用范围：n次多项式求值，包括自然数的幂和。
思路：拉格朗日插值法告诉我们，一个n次的多项式可以由n+1个点值来进行确定，而自然数的幂和，即1k+2k+…+nk 必定存在一个最高项为k+1次的通项公式，故我们只要选择k+2个点就可以求出任意的k值。注意当n<k时直接返回值，否则按照模的逆运算你可能得不到结果。给出拉格朗日插值的一般形式：
这里面前只给出幂和的代码：
LL jxig[maxn],ffzi,y[maxn];//y值怎么求也不用放了吧，反正递推求就完事了
void init(){//由于选取的是连续的点，所以每一项的分母必定是阶乘的形式
jxig[0]=jxig[1]=1;
for(int i=2;i<=1000002;++i)
jxig[i]=(jxig[i-1]*i)%mod;
}
void qqffzi(){//预处理出分子，针对每一项再做除法即可。
ffzi=1;
for(int i=1;i<=k+2;++i) ffzi=ffzi*(n-i)%mod;
}
LL qpow(LL x,int m){//快速幂的代码没有放出来的必要吧
}
LL lagelhri(){
LL res=0;
for(int i=1;i<=k+2;++i){
LL ig=y[i],iu=(jxig[i-1]*jxig[k+2-i])%mod;
if((k+2-i)&1) iu=mod-iu;//判断除数的正负
ig=(ig*ffzi)%mod*qpow(n-i,mod-2)%mod;
res+=ig*qpow(iu,mod-2)%mod;
res%=mod;
}
return res;
}
FFT
适用范围：大数乘法，或者是HDU-4609这样的有很多的加法运算，并且要算概率的一揽子问题。不然常规的三角形问题可以通过贪心解决，因为不能组成三角形的边是满足斐波那契数列递增规律的，1e9数量级内不会超过44次
思路：别问，问就我也不会。大致思路似乎是将系数表示变成点值表示，同时点值表示选取的是单位元的上的点，从而根据复数平面的对称性使得你实际上只需要求上半部分的值就能得出下半部分，再进行分治后就将时间复杂度从O(n2)变成了 O(nlogn)了。中间还有一些优化什么的……但是太复杂了不会用。另外核心思想就在于F(x)=f(x) * g(x),则F(x0)=f(x0)*g(x0)。而复数的点积就是一个因式分解？非常好算。
代码模板：
struct complex
{
double re,im;
complex (double r=0.0,double i=0.0){re=r;im=i;}
}a[maxl*2],b[maxl*2],w[2][maxl*2];
complex operator +(const complex&x,const complex&y)
{
return complex(x.re+y.re,x.im+y.im);
}
complex operator -(const complex&x,const complex&y)
{
return complex(x.re-y.re,x.im-y.im);
}
complex operator *(const complex&x,const complex&y)
{
return complex(x.re*y.re-x.im*y.im,x.im*y.re+x.re*y.im);
}
int n,na,nb,rev[maxl*2],res[maxl*2];
char oria[maxl],orib[maxl];
void init()
{
for(int i=0;i<n;++i){rev[i]=(rev[i>>1]>>1)|(i&1)<<(len-1);}//求出编号的翻转值，用来在分治时缩小常数
for(int i=0;i<n;i++)//求单位元上的点
{
w[0][i]=w[1][i]=complex(cos(2*pi*i/n),sin(2*pi*i/n));
w[1][i].im=-w[0][i].im;
}
}
void FFT(complex *a,int order)
{
complex x,y;
for(int i=0;i<n;i++)
{
if(i<rev[i])swap(a[i],a[rev[i]]);
}
for(int i=1;i<n;i<<=1)
{
for(int j=0,t=n/(i<<1);j<n;j+=i<<1)
for(int k=0,l=0;k<i;k++,l+=t)
{
x=w[order][l]*a[j+k+i];
y=a[j+k];
a[j+k]=y+x;
a[j+k+i]=y-x;
}
}
if(order)for(int i=0;i<n;i++) a[i].re/=n;
}
//主函数中需要处理出来最高位len和最高位的数字n
//然后主函数中需要进行的操作就是fft(a,0);fft(b,0);循环a[i]=a[i]*b[i];fft(a,1);然后实部四舍五入加起来。