贡献最大的元素放在队头，直至失效出队，队中所有比即将入队元素贡献值小的元素出队，因其无论如何不会比选即将入队元素更优，即将入队元素必定入队，因其时间上有优势，直至其后出现贡献值比他大的元素。
并查集的作用是快速的查询两个元素是否属于同一个集合。将除根节点外所有元素作为根节点的子节点(树的高度为2)即可得到O(1)的查询复杂度，这即是路径压缩。fa[i]即是i的父节点编号。如果两个节点有公共祖先，那么两节点在同一集合内。
先占个坑，以后再补(挠头)
我们以查询静态区间最大值为例，f[i][j]中的i表示区间起始点为i、j表示区间长度为2^j，f[i][j]的值即为i~i+2^j-1的区间最大值。由比较f[l][lg[r-l+1]]与f[r-lg[r-l+1]+1][lg[r-l+1]]大小(lg[r-l+1]会向下取整)即可得到区间[l,r]最大值。
这里是用一个结构体将堆封装起来，达到类似STL的效果。这是一个小根堆，即保证堆顶的值最小，相对较大的值尽量向下沉。插入一个值即将其放在叶子结点上，不断上浮，直至比其子结点小、比其父节点大。弹出堆顶值即将堆底值与其交换，不断下沉，直至比其子结点小、比其父节点大。
有n个结点和与之互联的若干条边，选取其中n-1条边使每个结点相互联通，这n-1条边的边权之和最小，这样生成的树叫做最小生成树。我们可以先对边权进行排序，从边权小的开始加边，如果该边联通两点在同一并查集里，则忽略该边，如果不在，则加入该边，并将这两点所属并查集合并，当加入边数=n-1时，所选边与其所连结点即构成最小生成树。
线段树主要应用于区间修改、区间查询，相对于遍历数组查询有着较好的时间复杂度，相对于二维数组预处理有着较好的空间复杂度，相对于RMQ增添了修改功能，有时可以与树状数组互换。线段树的原理以其原数为叶子结点，其区间所需操作为父结点(如求最大值时，其区间最大值即为其父结点的值)。举个例子，以1、2、3、4求最大值建树，[1]、[2]的父结点是[1,2]，其值为2，[1,2]、[3,4]的父结点是[1,4]，其值为4。线段树查询的优越性在于已经预处理了所需区间而空间复杂度比二维数组更优，其修改的优越性在于添加了Lazy Tag，可以将修改延后到查询时，从而降低了时间复杂度，即只修改我们要查询的。修...
