所谓倍增，就是按2的倍数来增大，也就是跳 1,2,4,8,16,32…… 不过在这我们不是按从小到大跳，而是从大向小跳，即按……32,16,8,4,2,1来跳，如果大的跳不过去，再把它调小。这是因为从小开始跳，可能会出现“悔棋”的现象。拿 5 为例，从小向大跳，5≠1+2+4,所以我们还要回溯一步，然后才能得出5=1+4；而从大向小跳，直接可以得出5=4+1。这也可以拿二进制为例，5(101)，从高位向低位填很简单，如果填了这位之后比原数大了，那我就不填，这个过程是很好操作的。

具体操作看代码吧：

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,s,cnt;
int head[500010],fa[500010][25],dep[500010];//head数组建图用，fa[a][b]数组表示a的2^b祖先，dep[a]表示第a个点的深度
struct Edge
{
	int nst,to;
}edge[1000010];
void add(int a,int b)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	head[a]=cnt;
}
void dfs(int x,int y)//预处理出祖先节点
{//x是当前节点，y是x的祖先节点
	dep[x]=dep[y]+1;//深度++
	fa[x][0]=y;//x的2^0祖先是y
	for(int i=0;i<=20;i++)
	{
		fa[x][i+1]=fa[fa[x][i]][i];//x的2^（i+1）祖先等于x的2^i祖先的2^i祖先，这是倍增求lca里的重要转移
	}
	for(int i=head[x];i;i=edge[i].nst)//遍历与当前节点相连的边
	{
		int v=edge[i].to;
		if(v!=y)//如果这条边不是他的祖先节点，那一定是他的子节点
		{
			dfs(v,x);//递归
		}
	}
}
int lca(int x,int y)//求x和y的最小公共祖先
{
	if(dep[x]<dep[y])swap(x,y);//保证x的深度大于y
	for(int i=20;i>=0;i--)//必须倒序遍历，这样就相当于从树根往上找
	{//这个循环处理x和y在一条树枝上的情况
		if(dep[y]<=dep[fa[x][i]])x=fa[x][i];//如果x的祖先节点的深度仍然大于y的深度，就更新x
		if(x==y)return x;//如果x与y相等了，就说明x和y在一条树枝上，直接return
	}
	for(int i=20;i>=0;i--)
	{//如果不在一条树枝上
		if(fa[x][i]!=fa[y][i])//当他们的祖先节点不同时，同时更新x和y，让他们同步上升
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];//最后输出当前x的2^0祖先
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	int a,b;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(s,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}

接下来介绍另一种求LCA的方式：树剖求LCA

两篇详解：树链剖分求LCA 和树链剖分求LCA（最近公共祖先）

树剖求LCA的速度很快， $O(n)$ 预处理， $O(log(n))$ 查询，相较于倍增LCA更快，而且求LCA那部分更好写，但是dfs部分比较难写.

整个算法流程就是先两个dfs预处理，然后一个判断u与v是否在同一条重链，不在就往上跳，最后得到LCA.

至于为什么查询是 $O(log(n))$ 的，因为我们可以证明重链只有 $log(n)$ 条，所以是 $O(n)$ 的.

找重链的方法：取每个节点u的所有子节点中，子树最大的子节点v，然后将边(u,v)作为重边，其余边作为轻边，重边构成的链就是重链

具体过程是两遍深搜，第一遍建树，第二遍构造重链：

#include<cstdio>
#include<iostream>
#define maxn 500010
using namespace std;
inline int read()
{
    int x=0,fu=1;char o=getchar();
    while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();}
    while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+(o^48);o=getchar();}
    return x*fu;
}
struct Edge
{
	int to,dis,nst;
}edge[maxn<<1];
int cnt,head[maxn],fa[maxn],top[maxn];//fa存i的父节点，top存i在的重链的链顶 
int dep[maxn],siz[maxn],son[maxn],val[maxn];//dep存深度，siz存子树大小，son存以i为链首的重链的另一端点，val存边权值 
inline void add(int a,int b,int c)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	edge[cnt].dis=c;
	head[a]=cnt;
}
void dfs1(int x)//建树 
{
	dep[x]=dep[fa[x]]+1;//深度比父节点大1 
	siz[x]=1;//至少有一个节点 
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(fa[x]!=v&&!fa[v])//如果v不是x的父亲且v的父亲还没有找到 
		{
			val[v]=edge[i].dis;//记录边权(虽然只求LCA用不到)
			fa[v]=x;//更新v的父节点 
			dfs1(v);
			siz[x]+=siz[v];//更新x的子树大小 
			if(siz[son[x]]<siz[v])son[x]=v;//更新以x为链首的重链 
		}
	}
}
void dfs2(int x)//构造重链 
{
	if(x==son[fa[x]])top[x]=top[fa[x]];//更新重链链顶，方便查询时使用 
	else top[x]=x;
	for(int i=head[x];i;i=edge[i].nst)
	if(fa[edge[i].to]==x)dfs2(edge[i].to);//从树根向下遍历 
}
int query(int x,int y)//查询LCA 
{
	while(top[x]!=top[y])
	{  
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];//当x、y不在一条链上时，将深度较大的点调到其重链链顶的父节点上
    }
    if(dep[x]>dep[y])swap(x,y);//当在一条链上时，挑深度小的输出 
    return x;
}
int n,m,s,x,y,v;
int main()
{
	n=read();m=read();s=read();
	for(int i=1;i<n;i++)
	{
        x=read();y=read();
        add(x,y,0);add(y,x,0);
    }
    dfs1(s);dfs2(s); 
    for(int i=1;i<=m;i++)
    {
        x=read();y=read();
        printf("%d\n",query(x,y));
    }
    return 0;
}

第二题：P3386 【模板】二分图匹配

题解思路1：匈牙利算法

我也不想细讲思路了，去看这篇博客和这篇博客吧

以下是我的代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,e,ans,match[1001];//match[i]=j代表右侧的i号点与左侧的j号点匹配。
bool a[1001][1001],vis[1001];
bool dfs(int x)//查找匹配 
{
	for(int i=1;i<=m;i++)//遍历右侧点集里的点 
	if(!vis[i]&&a[x][i])//如果x和i之间存在一条边且没有被访问过 
	{
		vis[i]=1;//将i点标记为访问过 
		if(!match[i]||dfs(match[i]))//如果这是增广路的终点或还能从这个点找到增广路 
		{
			match[i]=x;
			return 1;
		}
	}
	return 0;//如果扫描了每一个点都无法找到增广路就说明找不到增广路了 
}
int main()
{
	scanf("%d%d%d",&n,&m,&e);
	for(int i=1;i<=e;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(v<=m)a[u][v]=1;//邻接矩阵存图 
	}
	for(int i=1;i<=n;i++)
	{
		ans+=dfs(i);
		memset(vis,0,sizeof(vis));
	}
	printf("%d",ans);
	return 0;
}

题解思路2：网络最大流Dinic

去看我的这篇博客，当然上文的第一篇博客里也讲了Dinic，比较着看看吧

代码……就不放了（~~反正NOIP不考网络流~~）

第三题：P3387 【模板】缩点

题解思路：tarjan缩点+拓扑排序+DP

安利一下这两篇博客，把tarjan的思路讲得很详细：原理解析，模板详解

（update on 2019/9/22）对于无向图的tarjan，我们需要在dfs函数上多加一个记录父节点的参数来保证不会再双向边上打转，具体做法看代码里的注释部分

那么具体思路我就不赘述了（~~我可真懒~~），详解看代码：

#include<queue>
#include<stack>
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=10015;
int n,m,p[maxn];//数据记录层 
int tim,sd[maxn],dfn[maxn],low[maxn],vis[maxn];//tarjan使用层
//tim是时间，sd[i]是i点属于哪个强联通分量，dfn[i]是遍历到点i的时间
//low[i]是 以i点为根的子树里的点 能连接到点中最小的dfn值
//vis[i]表示i点在不在栈里 
int in[maxn],dist[maxn];//DP使用层
//in[i]表示i点的入度，dist[i]表示i点的从入度为零的点到i的最大点权和 
int head[maxn],h[maxn],cnt,num;//建图层 
struct Edge
{
	int to,from,nst;
}edge[maxn*10],e[maxn*10];
void add(int a,int b)
{
	edge[++cnt].nst=head[a];
	edge[cnt].from=a;
	edge[cnt].to=b;
	head[a]=cnt;
}
stack <int> s;//貌似用数组模拟栈更快…… 
void tarjan(int x)//喜闻乐见的缩点 
{
	low[x]=dfn[x]=++tim;//先增加一下时间 
	s.push(x); 
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(!dfn[v])//如果v点还没被遍历到 
		{
			tarjan(v);//就继续DFS 
			low[x]=min(low[x],low[v]);//更新x的low值 
		}
		else if(vis[v])//如果v点在栈里 
		{//就说明找到了一个环 
			low[x]=min(low[x],dfn[v]);//更新x的low值 
		}
	}
	if(dfn[x]==low[x])//以x为根的搜索子树上所有节点是一个强连通分量。(实质上就是这个点的整个子树回溯完了，并且下面都是死路)
	{
		int u;
		while(u=s.top())//退栈 
		{
			s.pop();
			sd[u]=x;//记录一下栈顶的点在哪个环上 
			vis[u]=0; 
            p[x]+=p[u];//缩点自然要把点权也加和 
			if(u==x)break;
		}
	}
}
/*这个是无向图tarjan的写法
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++tim;
	stack[++top]=x;
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(fa==v)continue;
		if(!dfn[v])
		{
			tarjan(v,x);
			low[x]=min(low[x],low[v]);
		}
		if(vis[v])
		{
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(dfn[x]==low[x])
	{
		int u;
		num++;
		while(u=stack[top--])
		{
			vis[u]=0;
			sd[u]=num;
			if(u==x)return;
		}
	}
}
*/
int dp()//利用拓扑排序保证DP的无后效性 
{
	queue <int> q;
	int tot=0;
	for(int i=1;i<=n;i++)
	if(sd[i]==i&&!in[i])
	{
		q.push(i);
		dist[i]=p[i];
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].nst)
		{
			int v=e[i].to;
			dist[v]=max(dist[v],dist[u]+p[v]);
			in[v]--;
			if(!in[v])q.push(v);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	ans=max(ans,dist[i]);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&p[i]);
	int a,b;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i);//防止原图不连通 
	for(int i=1;i<=m;i++)//建立新图 
	{
		a=sd[edge[i].from];
		b=sd[edge[i].to];
		if(a!=b)
		{
			e[++num].nst=h[a];
			e[num].to=b;
			e[num].from=a;
			h[a]=num;
			in[b]++;
		}
	}
	printf("%d",dp());
	return 0;
}

第四题：P3388 【模板】割点

题解思路：tarjan割点

~~为什么又是tarjan~~

tarjan割点算法与tarjan缩点算法有相似之处，这篇博客详细的讲述了这个算法，我就不赘述了……（~~我又懒了~~）

以下是AC代码：

#include<cstdio>
#include<iostream>
using namespace std;
struct Edge
{
	int nst,to;
}edge[200010];
int n,m,cnt,tot,tim;
int head[100010],dfn[100010],low[100010];
bool vis[100010];
void add(int a,int b)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	head[a]=cnt;
}
void tarjan(int x,int fa)//x是当前节点，fa是父节点
{
	dfn[x]=low[x]=++tim;//时间戳
	int child=0;
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(!dfn[v])
		{
			tarjan(v,fa);
			low[x]=min(low[x],low[v]);
			if(low[v]>=dfn[x]&&x!=fa)vis[x]=1;
			if(x==fa)child++;
		}
		low[x]=min(low[x],dfn[v]);
	}
	if(child>=2&&x==fa)
	vis[x]=1;
}
/*
int dfs(int u,int fa)//这是另一个版本的割点
{
	int ans=pre[u]=++tim;
	int child=0;
	for(int i=head[u];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(v==fa)continue;
		if(pre[v])ans=min(ans,pre[v]);
		else
		{
			child++;
			int tmp=dfs(v,u);
			ans=min(ans,tmp);
			if(tmp>=pre[v])iscut[u]=1;
		}
	}
	if(fa==0&&child==1)iscut[u]=0;//如果该节点是根节点且只有一个儿子，那么它一定不是割点
	return ans;
}
*/
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i,i);
	for(int i=1;i<=n;i++)
	if(vis[i])tot++;
	printf("%d\n",tot);
	for(int i=1;i<=n;i++)
	if(vis[i])printf("%d ",i);
	return 0;
}

第五题：P4782 【模板】2-SAT问题

题解思路：位运算建图+tarjan缩点

2-SAT问题其实是SAT问题的特例，所以它并非NP问题，是可以用巧妙的方法求解的。

再次安利：算法详解（~~笔者的懒癌已经病入骨膏了……~~）

但是有一点需要说明：笔者代码里的建图方向与博客里相反，顾笔者使用的是 $col[i]>col[i+n]$

而且博客里有一点没有说明：为什么拓扑序大的应为真呢？因为若 $x_0→x_1$ ，那么 $x_0$ 的拓扑序显然比 $x_1$ 小，如果使 $x_0$ 为真，则 $x_1$ 里的值也必须全选，这样会造成矛盾，故我们拓扑序大的为真。因为tarjan求出来的点都是按拓扑逆序排列的，所以若 $sd[i]<sd[i+n]$ ，则应选i，又因为i代表x为真，故输出1。

以下是源代码:

#include<queue>
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=2000005;
struct Edge
{
	int nst,to,from;
}edge[2*maxn];
int dfn[maxn],vis[maxn],stack[maxn],low[maxn],sd[maxn],top,tim,num;
int n,m,head[maxn],cnt;
inline void add(int a,int b)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	edge[cnt].from=a;
	head[a]=cnt;
}
void tarjan(int x)
{
	low[x]=dfn[x]=++tim;
	stack[++top]=x;
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(vis[v])
		{
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(dfn[x]==low[x])
	{
		int u;
		num++;
		while(u=stack[top--])
		{
			sd[u]=num;
			vis[u]=0;
			if(u==x)break;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,a,y,b;
	for(register int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&x,&a,&y,&b);
		add(x+!a*n,y+b*n);
		add(y+!b*n,x+a*n);
	}
	for(register int i=1;i<=2*n;i++)
	if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
	if(sd[i]==sd[i+n]){printf("IMPOSSIBLE\n");return 0;}
	printf("POSSIBLE\n");
	for(int i=1;i<=n;i++)
	printf("%d ",sd[i]>sd[i+n]);
	return 0;
}

第六题：P1939 【模板】矩阵加速（数列）

题解思路：矩阵快速幂

安利：矩阵快速幂

以下是代码君：

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int p=1e9+7;
struct mat
{
	ll m[5][5];
}ans,base;
inline void init()//初始化
{
	memset(ans.m,0,sizeof(ans.m));
	for(int i=1;i<=3;i++)
	ans.m[i][i]=1;
	memset(base.m,0,sizeof(base.m));
	base.m[1][1]=base.m[1][3]=base.m[2][1]=base.m[3][2]=1;
}
inline mat mul(mat a,mat b)//普通的矩阵乘法
{
	mat res;
	memset(res.m,0,sizeof(res.m));
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			for(int k=1;k<=3;k++){
				res.m[i][j]+=(a.m[i][k]%p)*(b.m[k][j]%p);
				res.m[i][j]%=p;
			}
		}
	}
	return res;
}
inline void qmat_pow(int p)//矩阵快速幂的精髓
{
	while(p)
	{
		if(p&1)ans=mul(ans,base);
		base=mul(base,base);
		p>>=1;
	}
}
int t,n;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		if(n<=3)
		{
			printf("1\n");
			continue;
		}
		init();
		qmat_pow(n);
		printf("%lld\n",ans.m[2][1]);
	}
	return 0;
}

第七题：P1082 同余方程

这就是个用拓展欧几里得算法求解同余方程的模板题

（一般来说exgcd背背代码就可以了，但是如果想要详细了解可以看这篇题解）

以下是代码

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll a,b,x,y;
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,x,y);
	ll tmp=x;
	x=y;
	y=tmp-a/b*y;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	exgcd(a,b,x,y);
	x=(x+b)%b;
	printf("%lld",x);
	return 0;
}

第八题：P2613 【模板】有理数取余

用拓欧求逆元，进而求有理数取余，详细过程可以看这篇题解

以下是代码：

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll a,b,x,y;
const int p=19260817;
inline int read()
{
	int x=0,fu=1;char o=getchar();
	while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();}
	while(o>='0'&&o<='9'){x=((x<<3)+(x<<1)+(o^48))%p;o=getchar();}
	return x*fu;
}
void exgcd(ll a,ll b)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b);
	ll tmp=x;
	x=y;
	y=tmp-a/b*y;
}
int main()
{
	a=read();b=read();
	if(b==0){printf("Angry!\n");return 0;}
	exgcd(b,p);
	x=(x%p+p)%p;
	printf("%lld",a*x%p);
	return 0;
}

第九题：需要求树的直径（或重心）的一类问题

题解思路：树上DP

部分援引：树的直径和重心

我们设 $d[x]$ 代表从x开始走能到达在以x为根的子树里的最远的点的距离，那么就有DP方程： $d[x]=max(d[x],d[v]+dis(x,v))$

我们设 $f[x]$ 代表经过x点的最长链的长度，树的直径就是最大的 $f[x]$

我们知道，对于任意两个节点u、v，经过x的最长链由四部分构成： $d[u],d[v]$ ，u到x的距离，v到x的距离

那我们就能得到DP方程： $f[x]=max(f[x],f[u]+f[v]+dis(u,x)+dis(v,x)$

以下是参考代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100010;
inline int read()
{
    int x=0,fu=1;char o=getchar();
    while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();}
    while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+(o^48);o=getchar();}
    return x*fu;
}
struct Edge
{
	int nst,to,dis;
}edge[maxn<<1];
int n,head[maxn],dis[maxn],ans;
int vis[maxn];
inline void add(int a,int b,int c)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	edge[cnt].dis=c;
	head[a]=cnt;
}
void dp(int x)
{
	vis[x]=1;
	for(register int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(vis[v])continue;
		dp(v);
		ans=max(ans,dis[x]+dis[v]+edge[i].dis);
		dis[x]=max(dis[x],dis[v]+edge[i].dis);
	}
}
int main()
{
	n=read();
    int x,y;
	for(int i=1;i<n;i++)
	{
        x=read();y=read();
        add(x,y,1);add(y,x,1);
    }
    dp(1);
    printf("%d",ans);
    return 0;
}

第十题：P2731 骑马修栅栏(欧拉回路类问题)

夹议：一些定义

一、基本概念：

欧拉路：欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次。

欧拉回路：欧拉回路是指起点和终点相同的欧拉路。

二、存在欧拉路的条件:

1.无向连通图存在欧拉路的条件：

所有点度都是偶数，或者恰好有两个点度是奇数，则有欧拉路。若有奇数点度，则奇数点度点一定是欧拉路的起点和终点，否则可取任意一点作为起点。

2.有向连通图存在欧拉路的条件：

每个点的入度等于出度，则存在欧拉回路（任意一点有度的点都可以作为起点）
除两点外，所有入度等于出度。这两点中一点的出度比入度大，另一点的出度比入度小，则存在欧拉路。取出度大者为起点，入度大者为终点。

题解思路：Hierholzer算法求欧拉回路

Hierholzer算法，又称逐步插入回路法，可以求无向图中的欧拉回路

所谓逐步插入回路，就是从入度为奇数的点开始找回路，找到以后就回溯，走其他没有走过的路径，直至找不到回路（貌似并不是很清晰，这篇博客里有图示说明，可以自行理解）

以下是参考代码：

#include<stack>
#include<cstdio>
#include<cstring> 
#include<iostream>
using namespace std;
const int maxn=1005;
int a[maxn][maxn],rudu[maxn],n,m;
stack <int> s;
void dfs(int u)
{
	for(int v=1;v<=n;v++)
	if(a[u][v])
	{
		a[u][v]-=1;
		a[v][u]-=1;
		dfs(v);
	}
	s.push(u);
}
inline void print()
{
	if(!s.empty())
	{
		printf("%d",s.top());
		s.pop();
	}
	printf("\n");
}
inline void init()
{
	memset(rudu,0,sizeof(rudu));
	memset(a,0,sizeof(a));
}
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		init();
		int u,v;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			a[u][v]+=1;a[v][u]+=1;
			rudu[u]^=1;rudu[v]^=1;//利用异或运算，0表示入度为偶数 
		}
		for(u=1;u<=n;u++)if(rudu[u])break;//找入度为奇数的点 
		if(u==n+1)dfs(1);//如果入度都为偶数，随便找一个点开始 
		else dfs(u);//不然就从入度为奇数的点开始找 
		print();
	}
	return 0;
}

第十一题：P3128 最大流Max Flow(树上差分类问题)

题解思路：树上点差分

有一类题，它会给你在一棵树，让你把树上两点 $u,v$ 间的所有边都加一个值 $x$ 。对于这种题目，显然，暴力做法是不可取的，于是就有了树上差分。

差分，顾名思义（~~这名字好像也看不出啥~~），就是把对一个区间的操作转化成对一个点的操作，在点上记录变化量。区间差分的常规做法就是：对于“将区间 $[x,y]$ 间的每一个数都加上 $u$ ”，我们使“ $val[x]+=u$ ， $val[v+1]-=u$ ”，最后用前缀和扫一遍即可。

树上差分与其类似，对于第一段说的那种题目，我们只需将" $val[u]+=x$ ， $val[v]+=x$ ， $val[lca(u,v)]-=2*x$ "，然后就可以从树根开始前缀和了。这就叫树上边差分

但是这个题是树上点差分。我们只需要将" $val[lca(u,v)]-=x$ ， $val[fa[lca(u,v)]]-=x$ "即可

原理其实很简单：我们在该路径上每个点都加x时，分别从u和v给lca加了两个x，所以我们对lca-=x，保证lca只比原来大x；为了把影响只限制在u到v的路径，我们对lca的父节点减x即可

树上差分适用于修改多而询问少的情况。

（参考了Sagittarius大佬的这篇博客）

#include<cstdio>
#include<iostream>
#define maxn 50010
using namespace std;
inline int read()
{
	int x=0,fu=1;char o=getchar();
	while(o>'9'||o<'0'){if(o=='-')fu=-1;o=getchar();}
	while(o>='0'&&o<='9'){x=(x<<3)+(x<<1)+(o^48);o=getchar();}
	return x*fu;
}
struct Edge
{
	int to,dis,nst;
}edge[maxn<<1];
int n,m,x,y;
int ans,cnt,head[maxn],fa[maxn],top[maxn];
int dep[maxn],siz[maxn],son[maxn],val[maxn];
inline void add(int a,int b,int c)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	edge[cnt].dis=c;
	head[a]=cnt;
}
void dfs1(int x)
{
	dep[x]=dep[fa[x]]+1;
	siz[x]=1;
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(fa[x]!=v&&!fa[v])
		{
			val[v]=edge[i].dis;
			fa[v]=x;
			dfs1(v);
			siz[x]+=siz[v];
			if(siz[son[x]]<siz[v])son[x]=v;
		}
	}
}
void dfs2(int x)
{
	if(x==son[fa[x]])top[x]=top[fa[x]];
	else top[x]=x;
	for(int i=head[x];i;i=edge[i].nst)
	if(fa[edge[i].to]==x)dfs2(edge[i].to);
}
int query(int x,int y)
{
	while(top[x]!=top[y])
	{
		dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
	}
	return dep[x]<dep[y]?x:y;
}
void getans(int x,int fa)
{
	for(int i=head[x];i;i=edge[i].nst)
	{
		int v=edge[i].to;
		if(v==fa)continue;
		getans(v,x);
		val[x]+=val[v];
	}
	ans=max(val[x],ans);
}
int main()
{
	n=read();m=read();
    for(int i=1;i<n;i++)
    {
        x=read();y=read();
        add(x,y,0);add(y,x,0);
    }
    dfs1(1);dfs2(1);
    for(int i=1;i<=m;i++)
    {
        x=read();y=read();
        int lca=query(x,y);
        val[x]++;val[y]++;val[lca]--;val[fa[lca]]--;
    }
    getans(1,0);
    printf("%d",ans);
    return 0;
}

第十二题：SP116 Intervals（差分约束类问题）

题解思路：差分约束系统

做了这几道差分约束系统的题（P3275 SP116 UVA1723）以后，我觉得差分约束系统是利用题面中给出的约束条件，和题干中隐藏的约束条件建图，之后求解最短（长）路的过程。但是我们在建图的过程中要关注具体问题，若求的是两个变量差的最大值，那么将所有不等式转变成"<="的形式并且在建图后求最短路；反之则转换成">="的形式，并且求最长路

辣么，对于这个题，我们设 $d[i]$ 代表在区间 $[0,i]$ 上取 $d[i]$ 个数，则根据题意，就有 $d[b_i]-d[a_i-1]>=c_i$

但是只有这一个约束条件还不够，所以我们还要去挖掘题目中的隐含条件。首先，显然， $d[i]$ 肯定大于等于 $d[i-1]$ ，所以我们有 $d[i]-d[i-1]>=0$ 。然后我们发现，题目中有一句话很关键：每个数只能取一次，所以我们可以得到另一个约束条件： $d[i]-d[i-1]$ 只能等于0或1，因此就得到了差分约束方程组：

$d[i]-d[i-1]>=0$

$d[i-1]-d[i]>=-1$

$d[b_i]-d[a_i-1]>=c_i$

所以，我们在建图时要做到这三步：

在 $a_i-1$ 和 $b_i$ 间连一条边权为 $c_i$ 有向边
在i和i-1之间连一条边权为0的有向边
在i-1和i之间连一条边权为-1的有向边

然后以0为起点，用spfa跑最长路，输出 $d[maxx]$ 即可

以下是AC代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,t,cnt,maxx;
struct Edge
{
	int nst,to,dis;
}edge[500010];
int head[50010],dis[50010],vis[50010];
void add(int a,int b,int c)
{
	edge[++cnt].nst=head[a];
	edge[cnt].to=b;
	edge[cnt].dis=c;
	head[a]=cnt;
}
void spfa()
{
	queue <int> q;
	for(int i=1;i<=maxx+1;i++)
	{
		dis[i]=-1e9;
		vis[i]=0;
	}
	dis[0]=0;
	vis[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nst)
		{
			int v=edge[i].to;
			if(dis[v]<dis[u]+edge[i].dis)
			{
				dis[v]=dis[u]+edge[i].dis;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		maxx=-1;
		cnt=0;
		memset(edge,0,sizeof(edge));
		memset(head,0,sizeof(head));
		scanf("%d",&n);
		int a,b,c;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a-1,b,c);
			maxx=max(maxx,b);
		}
		for(int i=1;i<=maxx+1;i++)
		{
			add(i-1,i,0);
			add(i,i-1,-1);
		}
		spfa();
		printf("%d\n",dis[maxx+1]);
	}
	return 0;
}

第十三题：P2580 于是他错误的点名开始了（Trie树）

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#define maxn 1000010
using namespace std;
struct Trie
{
	int ch[maxn][26],val[maxn],mark[26],sz;
	//val为附加信息
    //这里的ch数组，第二维的大小为26是因为字符串只由小写字母构成，第二维的大小一般是由字符串的组成决定
    //sz即为节点编号 
	Trie()
	{
		sz=1;//一开始的时候只有根节点这一个节点 
		memset(ch[0],0,sizeof(ch[0]));
		memset(val,0,sizeof(val));
	}//这里是初始化 ,自动初始化
	int idx(char c){return c-'a';}//返回字符c的编号 
	void insert(char s[],int v)
	{//插入操作 ,这里是整份代码中唯一用到指针的地方，因为函数是放在结构体里面 ，所以最好用个指针，其实等价于char s[] 
    //s代表要插入的字符串，v为附加信息 
		int u=0,len=strlen(s);
		for(int i=0;i<len;i++)
		{
			int c=idx(s[i]);
			if(!ch[u][c])//如果节点不存在就插入，不然就继续往下遍历 
			{
				memset(ch[sz],0,sizeof(ch[sz]));
				val[sz]=0;//中间的节点是没有附加信息的 
				ch[u][c]=sz++;//新建节点 
			}
			u=ch[u][c];//往下遍历 
		}
		val[u]=v;//插入附加信息，注意，我们一般只在叶子节点插入附加信息，中间的节点一般是没有附加信息的，因为一个非叶子结点，在Trie中一般都会被不同的单词使用到（定义） 
	}
	int search(char s[])
	{
    //对于这一个查找操作，我们就以最简单的操作来展开：
    //查找这个字符串是否在Trie中出现过，如果出现过，返回它的附加信息 
		int u=0,len=strlen(s);
		for(int i=0;i<len;i++)
		{
			int c=idx(s[i]);
			if(!ch[u][c])return -1;
			//没有这个节点，返回-1，即代表这个字符串没有在Trie中出现过
            //这个返回值得看题目所需要的附加信息来决定，因为这里是不可以与附加信息冲突的，在这里我们假定附加信息为0或正数 
			u=ch[u][c];//继续向下遍历 
		}
		return val[u];//这个节点存在，返回它的附加信息 
	}
}tree;
int n,m;
char o[50];
char s[maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		cin>>o;
		tree.insert(o,1);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		printf("%d\n",tree.search(s));
	}
	return 0;
}

第十四题：P3796 【模板】AC自动机（加强版）

一篇优秀的算法讲解：AC自动机

求Fail（以下援引自 hyfhaha 奆佬的博客）

首先我们可以确定，每一个点i的Fail指针指向的点的深度一定是比i小的。（Fail指的是后缀啊）

第一层的Fail一定指的是root。（比深度1还浅的只有root了）

点i的父亲fa的Fail指针指的是fafail，那么如果fafail有和i值相同的儿子j，那么i的Fail就指向j。这里可能比较难理解一点，不过等会转换成代码就很好理解了。

由于我们在处理i的情况必须要先处理好fa的情况，所以求Fail我们使用BFS来实现。

实现的一些细节：

刚开始我们不是要初始化第一层的fail指针为root，其实我们可以建一个虚节点0号节点，将0的所有儿子指向root（编号为1)，然后root的fail指向0就OK了。效果是一样的。
如果不存在一个节点i，那么我们可以将那个节点设为fafail的值和i相同的儿子。保证存在性，就算是0也可以成功返回到根，因为0的所有儿子都是根。
无论fafail存不存在和i值相同的儿子j，我们都可以将i的fail指向j。因为在处理i的时候j已经处理好了，如果出现这种情况，j的值是第2种情况，也是有实际值的，所以没有问题。
实现时不记父亲，我们直接让父亲更新儿子

struct AC_Auto_Machine
{
	void init()
	{
		for(int i=1;i<=n;i++)vis[i]=0;
		for(int i=0;i<=cnt;i++)t[i].clear();
		cnt=1;ans=0;
	}
	void insert(char *s,int num)
	{
		int u=1,len=strlen(s);
		for(int i=0;i<len;i++)
		{
			int v=s[i]-'a';
			if(!t[u].son[v])t[u].son[v]=++cnt;
			u=t[u].son[v];
		}
//		t[u].flag++;
//		t[u].flag=num;  //变化：标记为第num个出现的字符串
		if(!t[u].flag)t[u].flag=num;//防止有重复模式串 
		map[num]=t[u].flag;
	}
	void getfail()
	{
		for(int i=0;i<26;i++)t[0].son[i]=1;//初始化0的所有儿子都是1
		q.push(1);//将根压入队列
		t[1].fail=0;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			int fail=t[u].fail;//就是fafail，trie[fail].son[i]就是和v值相同的点
			for(int i=0;i<26;i++)//遍历所有儿子
			{
				int v=t[u].son[i];//处理u的i儿子的fail，这样就可以不用记父亲了
				if(!v){t[u].son[i]=t[fail].son[i];continue;}//不存在该节点，第二种情况
				t[v].fail=t[fail].son[i];//第三种情况，直接指就可以了
				q.push(v);//存在实节点才压入队列
			}
		}
	}
	int query2(char *s)//输出一共出现了几种模式串
	{
		int u=1,len=strlen(s);
		for(int i=0;i<len;i++)
		{
			int v=s[i]-'a';
			int k=t[u].son[v];//跳Fail
			while(k>1&&t[k].flag!=-1)//经过就不统计了
			{
				ans+=t[k].flag;//累加上这个位置的模式串个数，标记已经过
				t[k].flag=-1;
				k=t[k].fail;//继续跳Fail
			}
			u=t[u].son[v];//到儿子那,存在性看上面的第二种情况
		}
		return ans;
	}
	void query1(char *ss)//输出所有模式串中出现次数最多的模式串和其数量
	{
		int u=1,len=strlen(ss);
		for(int i=0;i<len;i++)
		{
			int v=ss[i]-'a';
			int k=t[u].son[v];
			while(k>1)
			{
				if(t[k].flag)vis[t[k].flag]++; //如果有模式串标记，更新出现次数
				k=t[k].fail;
			}
			u=t[u].son[v];
		}
		for(int i=1;i<=n;i++)
		ans=max(ans,vis[i]);
		printf("%d\n",ans);
		for(int i=1;i<=n;i++)
		if(vis[i]==ans) printf("%s\n",s[i]);
	}
	void query(char *ss)//输出所有模式串的出现次数
	{
		int u=1,len=strlen(ss);
		for(int i=0;i<len;i++)
		{
			int v=ss[i]-'a';
			int k=t[u].son[v];
			while(k>1)
			{
				if(t[k].flag)vis[t[k].flag]++;
				k=t[k].fail;
			}
			u=t[u].son[v];
		}
		for(int i=1;i<=n;i++)
		printf("%d\n",vis[map[i]]);
	}
};

第十五题：STL的妙用

1.upper_bound()和lower_bound()

两个二分函数，用法：

1 2	upper_bound(a+1,a+1+n,k)-a; lower_bound(a+1,a+1+n,k)-a;

前者返回序列中第一个大于k的数的下标（不减数组名的话会返回一个指针）

后者返回序列中第一个不大于k的数的下标

2.nth_element和stable_sort

两个排序函数，用法：

1 2	nth_element(a+1,a+1+k,a+1+n); stable_sort(a+1,a+1+n);

前者使无重复元素的序列的第k个位置上保存序列中第k小的数

后者是一个稳定的sort函数（和sort用法基本一样，不过复杂度稳定在 $O(nlog_2 n)$ ，实现本质是归并排序）

3.unique()

一个去重函数，用法：

1 2	unique(a+1,a+1+n); unique(a+1,a+1+n)-a-1;

前者是一般用法，后者是返回去重后的数组大小

如何用unique函数和sort函数进行快速的离散化

sort(a+1,a+1+n)//要离散化的数组
int m=unique(a+1,a+1+n)-a-1;//去重

//以下为函数部分
int q(int x)
{
	return lower_bound(a+1,a+1+m,x)-m;
}
//这样q(x)就是x离散化之后的数了

当然这样离散化查询时会有 $O(logm)$ 的小常数，~~不过它好写且方便啊！！！~~

4.random_shuffle()

随机化排列函数，用法：

1	random_shuffle(a+1,a+1+n);

对指定范围内的数随机排列

5.vector

STL自带链表，本机亲测1s内可插入 $10^5$ 个点，可删除 $3*10^5$ 个点，可以水过平衡树

6.map

7.set

8.next_permutation()

枚举下一个全排列的函数，工作原理似乎是交换末尾的几个数，所以最好在序列有序的情况下用，用法：

1	next_permutation(a+1,a+1+n);

9.clock()

ctime库的函数，系统不同返回值的类型不同，用法：

int tim=CLOCKS_PER_SEC;
tim=tim*0.95;//这里的0.95是要卡进0.95秒
if(clock()>tim)break;
if(!(i&2047))if(clock()>tim)break;//当然如果不想调用太多次clock函数，可以这样写

10.cstring库内的函数：

strstr 寻找字符子串的首次出现
strlen 返回给定字符串的长度
strcmp 比较两个字符串
strcat 连接两个字符串
strchr 寻找字符的首次出现
strrchr 寻找字符的最后一次出现
strcpy 复制一个字符串给另一个

具体用法:

char s[1001],o[1001];
int len=strlen(s);
strcpy(o,s);//复制s到o
strcat(o,s);//复制s到o的结尾
strcmp(o,s);//若o的字典序小于s则返回负数，相等返回0，否则返回正数
char* t=strstr(s,o);//o是模式串，s是文本串，返回一个指针指向从找到的第一个子串的首个字符开始的剩下的文本串
printf("%s",t);
t=strchr(s,'o');//返回一个指针指向从找到的第一个指定的字符开始的剩下的文本串
printf("%s",t);

第十六题：常用板子

（~~先咕一会，下次再补完~~）

Prim

#include<cstdio>
#include<iostream>
using namespace std;
inline int read()
{
    int fu=1,x=0;char o=getchar();
    while(o<'0'||o>'9'){if(o=='-')fu=-1;o=getchar();}
    while(o>='0'&&o<='9'){x=(x<<1)+(x<<3)+(o^48);o=getchar();}
    return x*fu;
}
const int maxn=1000;
const int inf=0x7f7f7f7f;
int n,m,ans=inf,map[maxn][maxn];
int low[maxn];//表示以i为终点的最小边权值 
int mst[maxn];//表示low对应的边的起点 
void prim(int u)
{
	int tot=0;//最小生成树权值
	for(int i=1;i<=n;i++)//初始化两个数组
	{
		low[i]=map[u][i];
		mst[i]=u;
	}
	mst[u]=-1;//设置成-1表示已经加入mst
	for(int i=1;i<n;i++)//只需要加n-1条边 
	{
		int minn=inf,v=-1;
		for(int j=1;j<=n;j++)//在lowcost数组中寻找未加入mst的最小值
		{
			if(mst[j]!=-1&&low[j]<minn)
			{
				v=j;
				minn=low[j];
			}	
		}
		if(v)//v=-1表示未找到最小的边,
		{//v表示当前距离mst最短的点
			mst[v]=-1;
			tot+=low[v];
			for(int j=1;j<=n;j++)//更新最短边
			{
				if(mst[j]!=-1&&low[j]>map[v][j])
				{
					low[j]=map[v][j];
					mst[j]=v;
				}
			}
		}
	}
	ans=min(ans,tot);
}
int main()
{
	m=read();n=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			map[i][j]=read();
			if(!map[i][j])map[i][j]=m;//这两行因题而异 
			if(map[i][j]>m)map[i][j]=m;
		}
	}
	prim(1);
	printf("%d",ans+m);
	return 0;
}

Prim的随机化改进

struct Edge
{
	int u,v;
}past[1000],e,e2;
bool operator < (struct edge a, struct edge b) 
{
    return map[a.u][a.v]>map[b.u][b.v];
}
int cnt=0,vis[1000]={0};
void random_prim(int u)
{
	priority_queue <Edge> q;
	vis[u]=1;
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		if(map[u][i]<inf)
		{
			e.u=u;e.v=i;
			q.push(e);
		}
	}
	for(int i=1;i<n;i++)
	{
		e=q.top();q.pop();
		while(q.size()&&(vis[e.v]||rand()%(n)<1))
		{//注意这里的判断条件rand()%n<1,即对于一个当前最近点，不选择的几率随着n的增大而减小
			if(!vis[e.v])past[++cnt]=e;//对于跳过了的边，以后还用得上，等待选择结束后再压回优先队列中
			e=q.top();q.pop();
		}
		vis[e.v]=1;
		if(cnt)//压回优先队列
		{
			for(;cnt>=1;cnt--)
			{
				q.push(past[cnt]);
			}
		}cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(map[e.v][i]<inf&&!vis[i])
			{
				e2.u=e.v;e2.v=i;
				q.push(e2);
			}
		}
		cost+=map[e.u][e.v];
	}
}

Kruscal

void kruscal()
{
	tot=0;num=0;
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u=edge[i].from,v=edge[i].to;
		u=find(u);v=find(v);
		if(u!=v)
		{
			fa[u]=v;
			num++;
			tot+=edge[i].dis;
		}
		if(num>=n-1)break;
	}
}

LCA

struct Tree_Chain_Partition
{
Edge edge[maxn];
int cnt,head[maxn];
int dep[maxn],siz[maxn],son[maxn],fa[maxn],top[maxn];
inline void add(int a,int b)
{
    edge[++cnt].nst=head[a];
    edge[cnt].to=b;
    head[a]=cnt;
}
void dfs1(int x)
{
    dep[x]=dep[fa[x]]+1;
    siz[x]=1;
    for(int i=head[x];i;i=edge[i].nst)
    {
        int v=edge[i].to;
        if(fa[x]!=v&&!fa[v])
        {
            fa[v]=x;
            dfs1(v);
            siz[x]+=siz[v];
            if(siz[son[x]]<siz[v])son[x]=v;
        }
    }
}
void dfs2(int x)
{
    if(x==son[fa[x]])top[x]=top[fa[x]];
    else top[x]=x;
    for(int i=head[x];i;i=edge[i].nst)
    if(fa[edge[i].to]==x)dfs2(edge[i].to);
}
int query(int x,int y)
{
    while(top[x]!=top[y])
    {  
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
};

Spfa & Dijkstra

struct Spfa_Dijkstra
{
Edge edge[maxn];
int cnt,head[maxn];
int dis[maxn],vis[maxn];
inline void add(int a,int b)
{
    edge[++cnt].nst=head[a];
    edge[cnt].to=b;
    head[a]=cnt;
}
void spfa(int s)
{
	queue <int> q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	q.push(s);
	vis[s]=1;dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nst)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].dis)
			{
				dis[v]=dis[u]+edge[i].dis;
				if(!vis[v]){q.push(v);vis[v]=1;}
			}
		}
	}
}
void dijkstra(int s)
{
	priority_queue <pair <int,int> > q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	q.push(make_pair(0,s));
	dis[s]=0;
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nst)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].dis)
			{
				dis[v]=dis[u]+edge[i].dis;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}
};

树状数组

struct Tree_Array
{
	int t[maxn<<1];
	int lowbit(int x){return x&(-x);}
	void add(int x,int y){for(x;x<=n;x+=x&-x)t[x]+=y;}
	int sum(int x)
	{
		int ans=0;
		for(x;x;x-=x&-x)ans+=t[x];
		return ans;
	}
	int query(int x,int y)
	{
		return sum(y)-sum(x-1);
	}
};

线段树

struct Section_Tree
{
	int t[maxn<<2],add[maxn];
	void build(int k,int l,int r)
	{
		if(l==r){t[k]=a[l];return;}
		int mid=l+r>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		t[k]=t[k<<1]+t[k<<1|1];
	}
	void Add(int k,int l,int r,int v)
	{
		add[k]+=v;
		t[k]+=v*(r-l+1);
	}
	void pushdown(int k,int l,int r)
	{
		if(!add[k])return;
		int mid=l+r>>1;
		Add(k<<1,l,mid,add[k]);
		Add(k<<1|1,mid+1,r,add[k]);
		add[k]=0;
	}
	void query(int k,int l,int r,int x,int y)
	{
		if(l>=x&&r<=y)return t[k];
		int mid=l+r>>1;
		int ans=0;
		pushdown(k,l,r);
		if(x<=mid)ans+=query(k<<1,l,mid,x,y);
		if(y>mid)ans+=query(k<<1|1,mid+1,r,x,y);
		return ans;
	}
	void modify(int k,int l,int r,int x,int y,int v)
	{
		if(l>=x&&r<=y)return Add(k,l,r,v);
		int mid=l+r>>1;
		pushdown(k,l,r);
		if(x<=mid)modify(k<<1,l,mid,x,y,v);
		if(y>mid)modify(k<<1|1,mid+1,r,x,y,v);
		t[k]=t[k<<1]+t[k<<1|1];
	}
};

OI基础数学合集

struct Math
{
	int oula(int x)//欧拉函数,查找小于x的与x互质的数的个数 
	{
		int res=x;
		for(int i=2;i*i<=x;i++)
		if(!(x%i))
		{
			res=res-res/i;
			x/=i;
			while(!(x%i)) x/=i;
		}
		if(x>1)res=res-res/x;
		return res;
	}
	int count(int x)//查询一个数中二进制1的个数 
	{
		int cnt=0;
		while(x)
		{
			cnt++;
			x=x&(x-1);
		}
		return cnt;
	}
	int p[maxn],cnt;
	bool m[maxn];
	void prime()//线性筛 
	{
		cnt=0;
		for(int i=2;i<=n;i++)
		{
			if(!m[i])p[++cnt]=i;
			for(int j=1;j<=cnt&&i*p[j]<=n;j++)
			{
				m[i*p[j]]=1;
				if(i%p[j]==0)break;
			}
		}
	}
	int gcd(int a,int b)//最大公因数 
	{
		return b==0?a:gcd(b,a%b);
	}
	int lcm(int a,int b)//最小公倍数 
	{
		int c=gcd(a,b);
		a=a/c;b=b/c;
		return a*b*c;
	}
	int qpow(int a,int b,int p)//快速幂 
	{
		int res=1%p;
		while(b)
		{
			if(b&1)res=res*a%p;
			b>>=1;
			a=a*a%p;
		}
		return res;
	}
	int exgcd(int a,int b,int &x,int &y)//拓展欧几里得算法 
	{
		int t;
		if(b==0){x=1;y=0;return a;}
		t=x;x=y;y=t-(a/b)*y;
		return exgcd(b,a%b,x,y);
	}
};

高精度

struct High_Precision
{
	void read(int* a)
	{
		int cnt=0;char b[10010];
		scanf("%s",b);
		for(int i=strlen(b)-1;i>=0;i--)
		a[++cnt]=b[i]-'0';
		a[0]=cnt;
	}
	void write(int* a)
	{
		for(int i=a[0];i>=1;i--)
		printf("%d",a[i]);
		printf("\n");
	}
	void add(int* a,int* b,int* c)
	{
		int k=0;
		c[0]=max(a[0],b[0]);
		for(int i=1;i<=c[0];i++)
		{
			c[i]=a[i]+b[i]+k;
			k=c[i]/10;
			c[i]%=10;
		}
		if(k){c[0]++;c[c[0]]+=k;}
	}
	void subtract(int* a,int* b,int* c)
	{
		int k=0;
		if(b[0]>a[0])swap(a,b); 
		c[0]=a[0];
		for(int i=1;i<=c[0];i++)
		{
			c[i]=a[i]-b[i]-k;
			k=0;
			if(c[i]<0)c[i]+=10,k++;
		}
		while(!c[c[0]])c[0]--;
	}
	void multiply(int* a,int b,int* c)
	{
		int k=0;
		c[0]=a[0];
		for(int i=1;i<=c[0];i++)
		{
			c[i]=a[i]*b+k;
			k=c[i]/10;
			c[i]%=10;
		}
		while(k){c[0]++;c[c[0]]+=(k%10);k/=10;}
	}
	void divide(int* a,int b,int* c)
	{
		int k=0;
		memcpy(c,a,sizeof(a)*10010);
		for(int i=c[0];i>=1;i--)
		{
			k*=10;k+=c[i];c[i]=0;
			if(k>=b)
			{
				c[i]=k/b;
				k=k%b;
			}
		}
		while(!c[c[0]])c[0]--;
	}
};