线段树的概念 线段树是一种用于区间处理的数据结构，用二叉树来构造线段树是二叉树，一个区间每次被折一半往下分，所有最多分 次就能找到。这就是线段树效率高的原因，使用了二叉树折半查找的方法。 线段树的基本操作 单点修改，区间查询 【max】给定一个n（n <= 100000）个元素的数组A，有m（m <= 100000）个操作，共两种操作： 单点修改：（C a c）表示将第a个元素变成c； 区间查询：（Q a b）表示询问区间[a, b]的最大值； const int maxn = 2e5+1; int p[maxn]; struct node { int l, r...

强连通分量（SCC） 如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任意点强连通，称这样的一个“极大强连通”子图是G的一个强连通分量。 Kosaraju算法 时间复杂度 O(N+E) Kosaraju 算法用到了“反图”的技术，基于下面两个原理：（1）一个有向图G，把G所有的边反向，建立反图rG，反图rG不会改变原图G的强连通行。也就是说，图G的SCC数量与rG的SCC数量相同。（2）对原图G和反图rG各做一次DFS，可以确定SCC的数量。 算法步骤： 在G上做一次DFS，标记点的先后顺序。在DFS的过程...

凸包问题 给定义一些点，求能把所有这些点包含在内的面积最小的多边形，可以想象有一个很大橡皮箍，它把所有的点都箍在里面，在橡皮箍收紧之后，绕着最外围的点形成的多边形就是凸包。如下图： Graham扫描法 时间复杂度：O(n㏒n)思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，但它不是利用夹角。步骤： 把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。 把所有点的坐标平移一下，使 P0 作为原点，如上图。 计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离...

https://blog.nowcoder.net/n/3335cd0b10cd4615812a77c127dac707

#include<iostream> const int N=1005; using namespace std; int p[N]; int main() {     int n,k,t,m=0;     cin>>n;     for(int i=1;i<=n;i++){         cin>>k;p[k]++;         if(p[k]>m){             m=p[k];t=k;         }     }     cout<<t<<endl;     return 0; } 

#include<iostream> #include<vector> using namespace std; int main() {     vector<int>table;                                     //建立一个数组table     int i,n,k,m,pos;     cin>>n>>k>>m;     pos=k;     for(i=0;i<n;i++){         table.pus...