各类模板

树状数组

1.基本构型

树状数组是一种支持$O(logn)$修改查询的维护数列前缀和的数据结构。核心在于tree数组和位运算的结合。所有树状数组维护前缀和的部分基本都是一样的:

struct BIT
{
	long long t[N<<2];
	inline int lowbit(int &x){return x&(-x);}
	void add(int x,long long v)
	{
		while(x<=n)t[x]+=v,x+=lowbit(x);
	}
	long long sum(int x)
	{
		long long rt=0;
		while(x)
			rt+=t[x],x-=lowbit(x);
		return rt;
	}
};

2.维护区间修改+单点查询

我们从差分数组的角度观察,发现整个数列满足以下特点:$arr_i=\sum\limits_{j=1}^{j\le i} diff_j$,可以使用树状数组维护差分数组的前缀和,而区间修改操作在差分数组上就是$diff_l+=v,diff_{r+1}-=v$,因此每次修改左右端点的差分前缀和即可。单点查询只需要查pos处前缀和即可。

3.维护区间修改+区间查询

模板题

继续上面维护区间修改的思路,列出整个数列的前缀和表达式:$$\sum\limits_{i=1}^{i\le x}a_i=\sum\limits_{i=1}^{i\le x}\sum\limits_{j=1}^{j\le i}diff_j=\sum\limits_{i=1}^{i\le x}diff_j\cdot (x-i+1)$$

(好吧,其实我不会复杂和式的运算,只是方便表示,具体如何变形自己展开一下就知道了)

然后我们进一步变形为$$x\cdot\sum\limits_{i=1}^{i\le x}diff_j-\sum\limits_{i=1}^{i\le x}diff_j\cdot(i-1)$$

这样就方便使用树状数组维护了。对于前面一项延续上面区间改的方法维护差分数组前缀和,对于后面一项,我们同样使用前缀和进行维护。我们发现更改$diff_i$对整体前缀和的影响是$v\cdot(i-1)$的,因此每次更改时乘上只与位置相关的(i-1)即可。

具体说,就是将x后的元素整体加v的操作分为一下两步:

  1. 将维护式子中前一项的树状数组x后整体加$v$(对应模板写法为add(x,v))。
  2. 将维护式子中后一项的树状数组x后整体加$v\cdot(x-1)$(对应模板写法为add(x,v*(x-1)))。

查询操作参考上式,查询1到x元素和的操作对应改变为:

  1. 在维护前一项的树状数组中查询x的前缀和,记为sum0。
  2. 在维护后一项的树状数组中查询x的前缀和,记为sum1。
  3. 原数列前缀和即为sum=sum0*x-sum1。

当然,为了方便,我们可以进行适当的移项变换。最后写成的模板为:

#include<bits/stdc++.h>
using namespace std;
const int N=100020;
int n,m;
struct BIT
{
	long long t[N<<2];
	inline int lowbit(int &x){return x&(-x);}
	void add(int x,long long v)
	{
		while(x<=n)t[x]+=v,x+=lowbit(x);
	}
	long long sum(int x)
	{
		long long rt=0;
		while(x)
			rt+=t[x],x-=lowbit(x);
		return rt;
	}
}T1,T2;
void update(int l,int r,long long v)
{
	T1.add(l,v),T1.add(r+1,-v);
	T2.add(l,v*(l-1)),T2.add(r+1,-v*r);
}
long long query(int l,int r)
{
	return (T1.sum(r)*r-T1.sum(l-1)*(l-1))-(T2.sum(r)-T2.sum(l-1));
}
int main()
{
	scanf("%d%d",&n,&m);
	long long ai,ki;
	for(int i=1;i<=n;i++)
		scanf("%lld",&ai),update(i,i,ai);
	for(int i=1,op,xi,yi;i<=m;i++)
	{
		scanf("%d%d%d",&op,&xi,&yi);
		if(op==1)
		{
			scanf("%lld",&ki);
			update(xi,yi,ki);
		}
		else if(op==2)
		{
			printf("%lld\n",query(xi,yi));
		}
	}
}

虽然线段树也能实现相同功能,但树状数组常数很小,跑[LNOI2014]LCA快2倍多。

割点

模板题

给出一个nn个点,mm条边的无向图,求图的割点。

定义

(我连割点的定义都不记得了)

在无向连通图中,如果将其中一个点以及所有连接该点的边去掉,图就不再连通,那么这个点就叫做割点(cut vertex / articulation point)。

求法

割点的求法同样是Tarjan大神发明的。

核心在于,从联通块中任意一个点出发dfs遍历全图,然后对于当前点分两类考虑(自己可以结合图形想想):

若当前点是遍历的出发点,且当前点有两棵或以上的子树,则当前点是割点,因为去掉当前点子树间无法相互到达。进一步的,判断当前点子树个数的方法为:若某子节点未到达过则子树数量加1。

若当前点不是遍历的出发点,且当前点是环与链的交点(去掉环链不连通,low[x]==low[v])或在至少1条链上(去掉链的两部分不连通,low[x]<low[v])是则当前点是割点。进一步的,判断方法为比较low值。

例如下图3种情况中x皆为割点:

cut_vertex_cases

low值的更新细节要注意。模板如下:

#include<bits/stdc++.h>
#define Side(x) for(int i=p[x];i;i=nt[i])
using namespace std;
const int N=20020,M=200020;
int tot,e[M],nt[M],p[N],start;
void _add(int x,int y){e[++tot]=y,nt[tot]=p[x],p[x]=tot;}
inline void add(int x,int y){_add(x,y),_add(y,x);}
int n,m,clc,low[N],dfn[N],anss,ans[N];
void Tarjan(int x)
{
    dfn[x]=low[x]=++clc;
    int cnt=0;
    Side(x)
    {
        if(!dfn[e[i]])
        {
            Tarjan(e[i]),low[x]=min(low[x],low[e[i]]),cnt++;
            if(low[e[i]]>=dfn[x]&&x!=start)ans[++anss]=x;
        }
        low[x]=min(low[x],dfn[e[i]]);
    }
    if(cnt>1&&x==start)ans[++anss]=x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,xi,yi;i<=m;i++)
        scanf("%d%d",&xi,&yi),add(xi,yi);
    for(int i=1;i<=n;i++)
        if(!dfn[i])start=i,Tarjan(i);
    sort(ans+1,ans+1+anss);
    anss=unique(ans+1,ans+1+anss)-ans-1;
    printf("%d\n",anss);
    for(int i=1;i<=anss;i++)
        printf("%d ",ans[i]);
    return 0;
}

缩点(强连通分量)

定义

强连通分量英语:Strongly connected component)是图论中的概念。图论中,强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。意即对于此图上每一个点对(Va,Vb),皆存在路径Va→Vb以及Vb→Va。强连通分量则是指一张有向图G的极大强连通子图G'。如果将每一个强连通分量缩成一个点,则原图G将会变成一张有向无环图。一张图被称为有向无环图当且仅当此图不具有点集合数量大于一的强连通分量,因为有向环即是一个强连通分量,而且任何的强连通分量皆具有至少一个有向环。

做法

做法见代码。先找强连通分量,将一个强连通分量中的点集作为一个新图中的点(权值相加),新图中的边集为原图中强连通分量间的边。然后topsort时dp一下就好了。

注意点

Tarjan的模板中我经常性忘记维护instack标记,需要注意。

乘法逆元

定义

存在一个$inv_a$满足$$a\cdot inv_a\equiv1\pmod{p}$$则称$inv_a$为$a$在模$p$意义下的逆元。

求法

  1. 扩展欧几里得法

  2. 费马小定理法

    #include<bits/stdc++.h>
    using namespace std;
    int n,p;
    int qpow(long long x,int k)
    {
    	long long rt=1;
    	while(k)
    	{
    		if(k&1)rt=(rt*x)%p;
    		x=(x*x)%p,k>>=1;
    	}
    	return (int)rt;
    }
    int main()
    {
    	scanf("%d%d",&n,&p);
    	for(int i=1;i<=n;i++)
    		printf("%d\n",qpow(i,p-2));
    }
    
  3. 递推法

    #include<bits/stdc++.h>
    using namespace std;
    const int N=3000020;
    int n,p,inv[N];
    int main()
    {
        scanf("%d%d",&n,&p);
        inv[1]=1;putchar('1');
        for(int i=2;i<=n;i++)
            printf("\n%d",inv[i]=(int)((long long)(p-p/i)*inv[p%i]%p));
    }
    

并查集

注意点

  1. 路径压缩,查询时更新fa数组,本校几位神仙曾因此挂了NOIP2017等比赛。
  2. 初始化n(点数)个fa[i]。

代码略。

最短路

spfa

基本上已经废了,但鉴于NOIP的ccf老爷机,可能使用STL的priority_queue会比较慢,但最好还是不要用spfa,容易被卡成$O(n\cdot m)$的。

判负环还是有点用的。

dijkstra

bool operator < (const pt &x) const {return d>x.d;}
#include<bits/stdc++.h>
using namespace std;
const int N=100020,M=400020;
int tot,e[M],nt[M],w[M],p[N];
void _add(int x,int y,int z){e[++tot]=y,nt[tot]=p[x],w[tot]=z,p[x]=tot;}
inline void add(int x,int y,int z){_add(x,y,z),_add(y,x,z);}
int n,m,s,dis[N];
bool vis[N];
struct pt
{
    int u,d;
    bool operator <(const pt &x)const{return d>x.d;}
};
void dijkstra()
{
    priority_queue<pt>q;
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
    q.push((pt){s,0});
    while(!q.empty())
    {
        int fr=q.top().u;q.pop();
        if(vis[fr])continue;
        vis[fr]=true;
        for(int i=p[fr];i;i=nt[i])
        {
            if(dis[e[i]]-w[i]>dis[fr])
            {
                dis[e[i]]=dis[fr]+w[i];
                q.push((pt){e[i],dis[e[i]]});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1,xi,yi,zi;i<=m;i++)
        scanf("%d%d%d",&xi,&yi,&zi),_add(xi,yi,zi);
    dijkstra();
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}