整理的各种模板 （随时弃坑emmmmm）

线段树：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define lson rt<<1
#define rson rt<<1|1
#define ll long long
using namespace std;
inline ll read()
{
    char c=getchar();ll num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
const ll N=1e5+5;
ll n,m;
ll a[N];
struct Tree
{
    ll len;                   //记录掌管的区间的长度数(元素个数 
    ll maxn,minn,sum;         //最大最小值、区间和 
    ll lazy;                  //lazy标记 
}tree[N<<2];
inline void pushup(ll rt)     //用儿子更新当前节点 
{
    tree[rt].maxn=max(tree[lson].maxn,tree[rson].maxn);
    tree[rt].minn=min(tree[lson].minn,tree[rson].minn);
    tree[rt].sum=tree[lson].sum+tree[rson].sum;
    return;
}
void build(ll rt,ll l,ll r)    //rt为当前的树根，l,r为rt对应的区间 
{
    tree[rt].len=r-l+1;        //当前节点掌管的区间长度(元素个数 
    if(l==r)                   //建到叶子节点了 
    {
        tree[rt].maxn=a[l];    //rt就是位置l对应的节点 
        tree[rt].minn=a[l];
        tree[rt].sum=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lson,l,mid);          //建左儿子rt*2，对应区间[l,mid] 
    build(rson,mid+1,r);        //建右儿子rt*2+1，对应区间[mid+1,r] 
    pushup(rt);                 //更新当前区间 
}
inline void pushdown(ll rt)     //下传lazy标记 
{
    if(tree[rt].lazy)
    {
        //更新孩子的lazy标记 
        tree[lson].lazy+=tree[rt].lazy;
        tree[rson].lazy+=tree[rt].lazy;
        //更新孩子的最大值 
        tree[lson].maxn+=tree[rt].lazy;
        tree[rson].maxn+=tree[rt].lazy;
        //更新孩子的最小值 
        tree[lson].minn+=tree[rt].lazy;
        tree[rson].minn+=tree[rt].lazy;
        //更新孩子的区间和 
        tree[lson].sum+=tree[rt].lazy*tree[lson].len;
        tree[rson].sum+=tree[rt].lazy*tree[rson].len;
        //lazy重置 
        tree[rt].lazy=0;
    }
    return;
}
void modify(ll rt,ll l,ll r,ll pos,ll val)  //单点修改 
{
    if(l==r)    //找到pos对应的叶子节点了 
    {
        tree[rt].maxn+=val;
        tree[rt].minn+=val;
        tree[rt].sum+=val;
        return;
    }
    pushdown(rt);                 //下放当前区间lazy标记
    ll mid=(l+r)>>1;
    if(pos<=mid)                  //pos在左儿子里 
        modify(lson,l,mid,pos,val);
    else                       //在右儿子里 
        modify(rson,mid+1,r,pos,val); 
    pushup(rt);                 //更新当前区间 
}
void Modify(ll rt,ll l,ll r,ll L,ll R,ll val)   //区间修改 
{
    if(l==L&&r==R)  //找到一个合法区间 
    {
        tree[rt].sum+=tree[rt].len*val;
        tree[rt].maxn+=val;
        tree[rt].minn+=val;
        tree[rt].lazy+=val;
        return;
    }
    pushdown(rt);
    ll mid=(l+r)>>1;
    if(R<=mid)
        Modify(lson,l,mid,L,R,val);
    else if(L>mid)
        Modify(rson,mid+1,r,L,R,val);
    else
        Modify(lson,l,mid,L,mid,val),Modify(rson,mid+1,r,mid+1,R,val);
    pushup(rt);                               //不要忘了pushup 
}
ll query_sum(ll rt,ll l,ll r,ll L,ll R)         //查询区间和 
{
    if(l==L&&r==R)                           //找到了一个合法区间，返回区间和 
        return tree[rt].sum;
    pushdown(rt);
    ll mid=(l+r)>>1;
    if(R<=mid)                              //查询区间全在左子树 
        return query_sum(lson,l,mid,L,R);
    else if(L>mid)                          //查询区间全在右子树 
        return query_sum(rson,mid+1,r,L,R);
    else                                     //一块在左子树，一块在右子树 
        return query_sum(lson,l,mid,L,mid)+query_sum(rson,mid+1,r,mid+1,R);
}
ll query_max(ll rt,ll l,ll r,ll L,ll R)
{
    if(l==L&&r==R)
        return tree[rt].maxn;
    pushdown(rt);
    ll mid=(l+r)>>1;
    if(R<=mid)
        return query_max(lson,l,mid,L,R);
    else if(L>mid)
        return query_max(rson,mid+1,r,L,R);
    else
        return max(query_max(lson,l,mid,L,mid),query_max(rson,mid+1,r,L,R));
}
ll query_min(ll rt,ll l,ll r,ll L,ll R)
{
    if(l==L&&r==R)
        return tree[rt].minn;
    pushdown(rt);
    ll mid=(l+r)>>1;
    if(R<=mid)
        return query_min(lson,l,mid,L,R);
    else if(L>mid)
        return query_min(rson,mid+1,r,L,R);
    else
        return min(query_min(lson,l,mid,L,mid),query_min(rson,mid+1,r,L,R));
};
ll opt;
ll x,l,r,val;
int main()
{
    n=read(),m=read();
    for(ll i=1;i<=n;++i)
        a[i]=read();
    build(1,1,n);
    while(m--)
    {
        opt=read();
        if(opt==2)
        {
            l=read(),r=read();
            cout<<query_sum(1,1,n,l,r)<<'\n';
        }
        else if(opt==1)
        {
            l=read(),r=read(),val=read();
            Modify(1,1,n,l,r,val);
        }
    }
    return 0;
}

st表：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,f[100005][33],lg[100005];
int main()
{
    scanf("%d%d",&n,&m);
    lg[0]=-1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&f[i][0]);
        lg[i]=lg[i>>1]+1;
    }
    for(int j=1;j<=19;++j)
    {
        for(int i=1;i+(1<<j)-1<=n;++i)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1,l,r;i<=m;++i)
    {
        scanf("%d%d",&l,&r);
        int k=lg[r-l+1];
        cout<<max(f[l][k],f[r-(1<<k)+1][k])<<"\n";
    }
    return 0;
}

dijkstra(O(n²))：

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio> 
#define maxn 500000+1
#define maxn1 10000+1
using namespace std;
inline int qread()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
struct Edge
{
    int v,w,nxt;
}edge[maxn];
int head[maxn],num;
void ct(int u,int v,int w)
{
    edge[++num].v=v;
    edge[num].w=w;
    edge[num].nxt=head[u];
    head[u]=num;
}
int n,m,s;
int dis[maxn1],vis[maxn1];
void dijkstra()
{
    dis[s]=0;
    for(int i=1;i<=n;++i)
    {
        int minn=0x7fffffff,u=-1;
        for(int j=1;j<=n;++j)
        {
            if(!vis[j]&&dis[j]<minn)
              minn=dis[j],u=j;
        }
        if(u==-1) break;
        vis[u]=1;
        for(int j=head[u];j;j=edge[j].nxt)
        {
            int v=edge[j].v;
            if(!vis[v]&&dis[v]>dis[u]+edge[j].w)
              dis[v]=dis[u]+edge[j].w;
        }
    }
}
int main()
{
    n=qread(),m=qread(),s=qread();
    for(int i=1;i<=n;++i)
    dis[i]=0x7fffffff;
    for(int i=1,u,v,w;i<=m;++i)
    {
        u=qread(),v=qread(),w=qread();
        ct(u,v,w);
    }
    dijkstra();
    for(int i=1;i<=n;++i)
    printf("%d ",dis[i]);
    return 0;
}

堆优化dijkstra(O(nlogn))：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 200000+1
#define maxn1 100000+1
using namespace std;
struct Edge
{
    int v,nxt,w;
}edge[maxn];
int num,head[maxn],n,m,s,dis[maxn1];
struct node
{
    int x,y;
    bool operator < (const node &a) const
    {
        return y>a.y;
    } 
};
inline void ct(int u,int v,int w)
{
    edge[++num].v=v;
    edge[num].w=w;
    edge[num].nxt=head[u];
    head[u]=num;
}
inline int qread()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
inline void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<node>q;
    q.push((node){s,0});
    while(!q.empty())
    {
        int u=q.top().x,d=q.top().y;
        q.pop();
        if(d!=dis[u]) continue;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w)
            {
                dis[v]=dis[u]+edge[i].w;
                q.push((node){v,dis[v]});   
            }   
        }   
    } 
}
int main()
{
    n=qread(),m=qread(),s=qread();
    for(int i=1,u,v,w;i<=m;++i)
    {
        u=qread(),v=qread(),w=qread();
        ct(u,v,w);
    }
    dijkstra();
    for(int i=1;i<=n;++i)
        cout<<dis[i]<<" ";
    return 0;
}

堆：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n;
int main()
{
    priority_queue<int ,vector<int> ,greater<int > >q;
    scanf("%d",&n);
    while(n--)
    {
        int k;
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d",&k);
            q.push(k);
        }
        else
          if(k==2)
            printf("%d\n",q.top());
        else
          q.pop();
    }
    return 0;
}

并查集：

#include<iostream>
#include<cstdio>
#define X 10000+10
using namespace std;
int fa[X];
int find(int x)
{
    if(fa[x]!=x) return fa[x]=find(fa[x]);
    return x;
}
void fac(int x,int y)
{
    x=find(x),y=find(y);
    fa[x]=y;
}
bool pd(int x,int y)
{
    if(find(x)==find(y)) return 1;
    return 0;
}
int main()
{
    int n,m,a,b,z;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    fa[i]=i;
    while(m--)
    {
        cin>>z>>a>>b;
        if(z==1) 
        {
            if(find(a)!=find(b)) 
            fac(a,b);
        } 
        if(z==2)
        {
            if(pd(a,b)==1) cout<<"Y"<<endl;
            else
            cout<<"N"<<endl;
        }
    }
    return 0;
} 

乘法逆元：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=3e6+1;
ll inv[maxn],n,p;
int main()
{
    scanf("%lld%lld",&n,&p);
    inv[1]=1;
    for(int i=2;i<=n;++i)
    {
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    }
    for(int i=1;i<=n;++i)
    {
        cout<<inv[i]<<'\n';
    }
    return 0;
}

LCA：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define maxn 500001
using namespace std;
int n,m,s,num,d[maxn],head[maxn],f[maxn][21];
inline int qread()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
struct node
{
    int v,nxt;
}e[maxn<<1];
inline void ct(int u,int v)
{
    e[++num].v=v;
    e[num].nxt=head[u];
    head[u]=num;
}
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v!=fa)
        {
            d[v]=d[u]+1;
            f[v][0]=u;
            dfs(v,u);
        }
    }
}
inline int lca(int a,int b)
{
    if(d[a]>d[b]) swap(a,b);
    for(int i=20;i>=0;--i)
    if(d[a]<=d[b]-(1<<i)) b=f[b][i];
    if(a==b) return a;
    for(int i=20;i>=0;--i)
    if(f[a][i]!=f[b][i])
      a=f[a][i],b=f[b][i];
    return f[a][0];
}
int main()
{
    n=qread();m=qread();s=qread();
    for(int i=1,u,v;i<n;++i)
    {
        u=qread(),v=qread();
        ct(u,v);ct(v,u);
    }
    dfs(s,0);
    for(int j=1;j<=20;++j)
    for(int i=1;i<=n;++i)
    f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1,u,v;i<=m;++i)
    {
        u=qread(),v=qread();
        cout<<lca(u,v)<<'\n';
    }
    return 0;
}

缩点：

#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
#define maxn 10001
using namespace std;
bool vis[maxn];
int n,m,head[maxn],block[maxn],bel[maxn],size[maxn],js,cnt,num,dfn[maxn],low[maxn];
int f[maxn],zrj,w[maxn];
struct node {
  int u,v,nxt;
}e[100001];
inline void ct(int u, int v) {
  e[++num].u=u;
  e[num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
stack<int>q;
void tarjan(int u) {
  dfn[u]=low[u]=++cnt;
  q.push(u),vis[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    else if(vis[v]) low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]) {
    int x;js++;
    while(x!=u) {
      x=q.top(),q.pop();
      size[js]++,bel[x]=js;
      block[js]+=w[x];
      vis[x]=0;
    }
  }
}
void dfs(int u) {
  int maxx=0;
  if(f[u]) return;
  f[u]=block[u];
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!f[v]) dfs(v);
    maxx=max(maxx,f[v]);
  }
  f[u]+=maxx;
}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i) scanf("%d",&w[i]);
  for(int i=1,u,v;i<=m;++i) {
    scanf("%d%d",&u,&v);
    ct(u,v);
  }
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  memset(head,0,sizeof(head));num=0;
  for(int i=1;i<=m;++i) if(bel[e[i].u]!=bel[e[i].v]) ct(bel[e[i].u],bel[e[i].v]);
  for(int i=1;i<=js;++i) {
    if(!f[i]) dfs(i);
    zrj=max(zrj,f[i]);
  }
  printf("%d\n",zrj);
  return 0;
}

割点：

#include<cstdio>
#include<algorithm>
#define maxn 20007
using namespace std;
int n,m,head[maxn],dfn[maxn],low[maxn],bel[maxn],size[maxn],num,cnt,js,zrj;
bool vis[maxn],bj[maxn];
struct node {
  int v,nxt;
}e[200007];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void tarjan(int u, int fa) {
  int child=0;
  dfn[u]=low[u]=++cnt;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(!dfn[v]) {
      tarjan(v, fa);
      low[u]=min(low[u],low[v]);
      if(u!=fa&&low[v]>=dfn[u]) bj[u]=1;
      if(u==fa) child++;
    }
    low[u]=min(low[u],dfn[v]);
  }
  if(u==fa&&child>=2) bj[u]=1;
}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1,u,v;i<=m;++i) {
    scanf("%d%d",&u,&v);
    ct(u,v),ct(v,u);
  }
  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);
  for(int i=1;i<=n;++i) if(bj[i]) zrj++;  
  printf("%d\n",zrj);
  for(int i=1;i<=n;++i) if(bj[i]) printf("%d ",i);
  printf("\n");
  return 0;
}