#include<bits/stdc++.h>
using namespace std;
int main()
{
    /*
    数据结构

    定义：数据存储的格式。

    1.数组

    2.栈（括号序列，匹配问题）
    遇到左括号，入栈；反之，查询有没有左括号。

    3.队列（BFS，迷宫）

    4.链表（数组是放在一起，链表用指针，不放在一起）
    特点：比较方便，动态的新增一个节点
    邻接链表--储存图
    双向链表--O(1)去插入删除(知道位置)

    --------以上都是线性--------

    --------树---------
    有一些节点，有一些边。
    满足：任何两个点只有唯一的一条边，否则就是图。

    V{1，2，3}；
    E{(1,2),(1,3)};
    树：n个节点，n-1边的无向连通图；（任意两个点，有且仅有一条路径）

    5.堆(优先队列)：二叉树，只能去堆顶拿，堆顶是最值。(排序，对顶堆)
    对顶堆：1.添加i 2.查询中位数
    (用到两个堆，左边查询最大，右边查询最小)

    区间数据结构 
        1.修改某个数 
        2.求整体和(维护sum) 
        3.求区间和 
        4.修改整个区间

    6.线段树(求区间和，修改区间，求最值)
    12345678
    1234|5678
    12|34|56|78
    1|2|3|4|5|6|7|8

    1到7
    从上到下搜索，遇到包含，return 值，不包含，return 0
    1234567=1234|56|7  log2n O(n)

    修改7
    7+3，包含7的集合都加上3(1.查找到数 2.重新计算一下)

    lazy(无法整个区间修改)
    1234567+2；
    1234|+2*4
    56|+2*2
    7|+2*1
    lazy表示子树还没有被更新
    询问到时，取消标记，下放给子树

    其他线段树：重新计算，下放(重写)

    7.树状数组(可以做和，但不能查最值，可以查前缀最大值)
    sum[l,r]=sum[1,r]-sum[1,l-1];
    修改区间和

    lowbit
    6=01(1)0 lowbit=x&~x+1(负数的补码)
    1 2 3 4 5 6 7 8
    1 0001 [1]
    2 0010 [1,2]
    3 0011 [3]
    4 0100 [1,4]
    5 0101 [5]
    6 0110 [5,6]
    7 0111 [7]
    8 1000 [1,8]

    1 2 3 4 5 6 7 8
    1 2 3 4
    1 2     5 6
    1   3   5   7
    1 2 3 4 5 6 7 8

    8.st表(可以查询最值)
    st[i][j]，i向后，pow(2,j)位[i,i+2^j];
    max[1,7]=max(max[1,5],max[3,7]);
    找到2^j接近len max=max(st[i][j],st[][j]);
    st[i][j] st[i+2^j][j]
    st[i][j+1]
    缺点：只能离线，构建好了就不能再修改

    ------单调-------
    9.单调栈
    (1.栈顶是空就入栈
     2.栈顶元素大于当前元素，栈顶出栈
     3.栈顶元素小于等于当前元素，入栈)
     3 1 4 5 3 2 7 1

     [3

     [1

     [1 4

     [1 4 5

     [1 3

     [1 2

     [1 2 7

     [1 1 
     性质（右边是栈顶）
     1.操作完后，栈顶元素=当前元素
     2.如果有第二个元素，是当前元素之前最后一个小于它的元素
     3.栈底是前缀的最小值，求子区间的最小值。

     洛谷P4147 玉蟾宫
     R，F
     全是F的子矩阵，面积最大

    10.单调队列
    队首-队尾
    可以求一个定长的区间最值，dp优化
    (滑动窗口)

    ---------------------------
    树
    遍历dfs,bfs
    规定根节点，父节点，子节点，祖先
    1.求u,v路径
      向上找到lca最近公共祖先
      求lca方法(倍增)
      pre[i][j]：i向上跳2^j步到达的节点
      pre[i][j]=pre[pre[i][j-1]][j-1];
      定义深度：到达根节点需要跳多少步
      1.将u,v移到相同的深度
      2.向上枚举(二分，找到深度相同if d[x]>=d[u],v=x)
      3.找到lca u-x,v-y;
        if(x==y)不跳；
        else 跳，u=x,v=y;
      这两个点的父亲刚好是lca return pre[u][v];
     2.树的直径：树上最远的两点的路径
       1.树形dp
       2.两遍dfs
         1.随便选一个点做根
         2.找到深度最深的点v1;
         3.把v1作为根，从v1出发
         4.找到深度最深的点v2;
     3.（无根树）树的重心：mx最小的节点,mx=儿子的子树中最大的节点数
    */
    return 0;
}