Vector

因为vector是可以和数组一样操作的，所以很多用法都几乎用不到；

比如insert用法，很少用到，但是还是要复习一下；

vector<int>ve;
ve.insert(ve.begin(),1);//表示在第一个位置插入1 
ve.insert(ve.end(),10);//表示在末尾位置追加10 

最变态的是vector还可以和二分结合起来用；
例题：洛谷·P1168 中位数
这题是给你n个数字，然后让你求出前1,3,5,…个数的中位数。

一般的思路是开一个multiset，自动排序，然后找出中间位置即可，但是multiset返回的迭代器，并且这个迭代器不能加减，无法O(1)找到中间位置；

这个时候可以用 vector 了，每次把输入的 a[i] 插入到 vector 中大于 a[i] 的位置上，这样等于是排好序了，直接输出 vector 的中间位置即可；

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=100100;
const int M=2000000;
const LL mod=1e9+7;
vector<int>ve;
int main(){
    int n,a;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        ve.insert(upper_bound(ve.begin(),ve.end(),a),a);
        if(i&1) printf("%d\n",ve[(i-1)/2]); 
    }
    return 0;
}