板子合集

头文件

//5oiR5piv6YKj57u06I6x54m555qE54uX
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=-1;
constexpr int inf=20241218;
stack<char> t;
int main()
{
//	freopen("neuvillette.in","r",stdin);
//	freopen("neuvillette.out","w",stdout);

	return 0;
}

IO

template <typename T>
inline void read(T &x){x=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(f)x=-x;}
template <typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
template <typename T,typename ...Args>
inline void readn(T a[],int _){for(int i=1;i<=_;i++) read(a[i]);}
template <typename T>
inline void write(T x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+48);}
template <typename T,typename ...Args>
inline void write(T tmp,Args ...tmps){write(tmp);putchar(' ');write(tmps...);}
template <typename ...Args>
inline void writeln(Args ...tmps){write(tmps...);putchar('\n');}

gcd（得特判 $0$）

inline int gcd(int a,int b)
{
	while(b^=a^=b^=a%=b);
	return a;
}

质数筛

bool vis[N];
vector<int> p;
inline void sieve(int n)
{
	int cnt=1;
	vis[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			cnt++;
			p.push_back(i);
		}
		for(int j=0;j<cnt;j++)
		{
			if(1ll*i*p[j]>n) break;
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}

最小生成树

int p[N];
int find(int u){return p[u]==u?u:p[u]=find(p[u]);}
vector<edge> e;
int kruskal()
{
    sort(e.begin(),e.end(),[&](edge A,edge B){return A.w<B.w;});
    int ans=0,cnt=0;
    for(edge E:e)
    {
        int pu=find(E.u),pv=find(E.v);
        if(pu!=pv) p[pu]=pv,ans+=E.w,cnt++;
    }
    return cnt==n-1?ans:-1;
}

Dijkstra

typedef pair<int,int> pii;
inline void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    priority_queue<pii> q;
    q.push({0,s});
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=h[u];i;i=e[i].nxt)
            {
                int v=e[i].to,w=e[i].w;
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    q.push({-dis[v],v});
                }
            }
        }
    }
}

线段树

#define ls (u<<1)
#define rs (u<<1|1)
struct node{int l,r;ll sum,lazy;}tr[N<<2];
int n,m;
int a[N];
inline void up(int u)
{
    tr[u].sum=tr[ls].sum+tr[rs].sum;
}
inline void down(int u)
{
    if(tr[u].lazy)
    {
        tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[u].lazy;
        tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[u].lazy;
        tr[ls].lazy+=tr[u].lazy;
        tr[rs].lazy+=tr[u].lazy;
        tr[u].lazy=0;
    }
}
void B(int u,int l,int r)
{
    tr[u]={l,r,a[l],0};
    if(l==r) return;
    int mid=(l+r)>>1;
    B(ls,l,mid);
    B(rs,mid+1,r);
    up(u);
}
void M(int u,int l,int r,ll k)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].sum+=(tr[u].r-tr[u].l+1)*k;
        tr[u].lazy+=k;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    down(u);
    if(l<=mid) M(ls,l,r,k);
    if(r>mid) M(rs,l,r,k);
    up(u);
}
ll Q(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
    int mid=tr[u].l+tr[u].r>>1;
    down(u);
    ll s=0;
    if(l<=mid) s=Q(ls,l,r);
    if(r>mid) s+=Q(rs,l,r);
    return s;
}

LCA

int dep[N],fa[N][20];
void dfs(int u,int p)
{
	dep[u]=dep[p]+1;
	fa[u][0]=p;
	for(int i=1;i<19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=h[u];i;i=e[i].nxt) if(e[i].to!=p) dfs(e[i].to,u);
}
int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	if(u==v) return v;
	for(int i=19;i>=0;i--)
	if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}