一、基本数据结构
1.并查集
 （1）作用 将两个集合合并，询问两个数据是否在一个集合当中；
 （2）模版
 //朴素版模版
    int find(int x)
   { 
       if(p[x]!=x) p[x]=find(p[x]);
       return p[x];
   }
  //带权重边并查集
  int find(int x)
  {
      if(p[x]!=x)
      {
          int temp=find(p[x]);
          d[x]+=d[p[x]];
          p[x]=temp;
      }
      return p[x];
  }

2.单调队列
  充分利用单调性来解决类似单调栈、求滑动窗口里面的最大值、最小值的问题
可以先去暴力枚举，然后思考该题的性质，结合单调性和栈的性质来进行优化
需要思考清楚，什么时候队首出去，什么时候弹出队尾元素，以及当前的队列里面存储的值是序号还是当前值，这是非常重要的
对于普通队列来讲，可以用数组模拟队列
「
    //hh 表示队头，tt表示队尾
    int q[N],hh=0,tt=-1;
    //向队尾插入一个数
    q[++tt]=x;
    //从队头弹出一个元素
    hh++；
    //队头取值
    q[hh];
    //如果hh<=tt,则表示档当前队列不为空
」
3.trie树
用来快速存储来查找字符串集合的数据结构

int son[N][26],cnt[N],idx;
// 0号点即是根节点，又是空节点
//son[][]存储树中每个节点的子节点
//cnt[]存储以每个节点结尾的单词数量

//插入一个字符串
void insert(char *str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
//查询字符串出现的次数
int query(char *str)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
4.堆 下标从1开始比较方便
**堆是一颗完全二叉树**
以小根堆为例：每个点都是小于等于它的左右儿子的
堆的存储（一维数组）：
（1）节点x的左儿子是2*x，右儿子是2*x+1；
（2）

堆所支持的操作：
（1）插入一个数 
    heap[++size]=x;up(size);
（2）求集合当中的最小值
    heap[1];
（3）删除最小值
    heap[1]=heap[size];size--; down[1]
（4）删除任意一个元素//stl中的堆（优先队列）不可以直接实现
    heap[k]=heap[size];size--;down(k),up(k);
（5）修改任意一个元素//stl中的堆不可以直接实现
    heap[k]=x,down(k),up(k);

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
int h[N], ph[N], hp[N], size;
void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}


// O(n)建堆


> for (int i = n / 2; i; i -- ) down(i);

二、数论
1、筛质数
  int primes[N],cnt;
  bool st[N];
  void get_primes(int n)
  {
      for(int i=2;i<=n;i++)
      {
          if(!st[i]) primes[cnt++]=i;
          for(int j=0;primes[j]<=n/i;j++)
          {
              st[primes[j]*i]=true;
              if(i%primes[j]==0) break;
          }
      }
  }

2、最大公约数
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
3、快速幂
LL qmi(int a, int b, int p)
{
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
三、图论
1.拓扑排序（图的宽度优先遍历的应用）
***有向图才会有拓扑序列
时间复杂度O(n+m)
bool topsort()
{
    int hh=0,tt=-1;
    //d[i]存储点i的入度
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
            q[++tt]=i;
        }
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for (int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)
            {
                q[++tt]=j
            }
        }
    }
    return tt==n-1;
}
2、朴素dijkstra求最短路
int g[N][N];//存储每条边
int dist [N];//存储1号点到每个点的最短位置
bool st[N];存储每个节点的最短路径是否已经确定

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<n-1;i++)
    {
        int t=-1;//在为确定最短路中的点中，寻找距离最短的点
        for(int j=1;j<=n;j++)
        {
            if(!st[j] &&n(t==-1 || dist[t]>dist[j])
            {
                t=j;
            }
        }
        //用t更新其他点的距离
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        st[t]=true;
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}
3.堆优化版dijkstra()
typedef pair<int,int>PII;
int n;//点的数量
int h[N],w[N],e[N],ne[N],idx;邻接表存储所有边
int dist[N];//存储所有点到1号点的距离
bool st[N];//存储每个点的最短距离是否确定
int dijkstar()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,1});
    while(heap.size()
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance =t.first;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]>distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}
4.spfa求最短路
int h[N],e[N],ne[N],w[N],idx;
bool state[N];
int dist[N];
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    state[1]=true;

    queue<int>q;
    q.push(1);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        state[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!state[j])
                {
                    q.push(j);
                    state[j]=true;
                }
            }
        }
    }
}
  spfa判断负环
  int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}