algorithm 库中函数

algorithm 库中函数

reverse(v.begin(),v.end())

翻转 O（n/2）

sort(v.begin(),v.end())

默认是从小到大排序

unique(a+1,a+1+n)

去重,使用前先sort

此处的删除，并不是真的删除，而是指重复的元素被移到了后面

应用（离散化）

int m=unique(a+1,a+1+n)-a-1;

m是没重的序列末位置

lower_bound

查找第一个大于等于它的位置 O(log n)

　　（1）查找第一个大于x的元素的位置：upper_bound()。代码例如：
　　　　　　　　pos = upper_bound(a, a+n, test) - a;
　　（2）查找第一个等于或者大于x的元素：lower_bound()。
　　（3）查找第一个与x相等的元素：lower_bound()且 = x。
　　（4）查找最后一个与x相等的元素：upper_bound()的前一个且 = x。
　　（5）查找最后一个等于或者小于x的元素：upper_bound()的前一个。
　　（6）查找最后一个小于x的元素：lower_bound()的前一个。
　　（7）单调序列中数x的个数：upper_bound() - lower_bound()。

手写二分：

while (l <= r) {
    mid = (l + r) >> 1;
    if (a[mid] < k) {
        l = mid + 1;
    } else {
        ans = mid;
        r = mid - 1;
    }
}
printf("%d
", ans);

upper_bound

查找第一个大于它的位置 O(log n)

用于求最长（不）上升/（不）下降子序列

下面的例子是不上升、不下降

#include<bits/stdc++.h>
using namespace std;
int a[300000],f[300000],g[300000];
struct cmp{
	bool operator()(int a,int b){
	    return a>b;
	}
};
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int con=1,now=1;
    g[1]=f[1]=a[1];
    for(int i=2;i<=n;i++){
        if(g[now]>=a[i]) g[++now]=a[i];
        else g[upper_bound(g+1,g+now+1,a[i],cmp())-g]=a[i];
        if(f[con]<=a[i])f[++con]=a[i];
        else f[upper_bound(f+1,f+con+1,a[i])-f]=a[i];
    }
    printf("%d
",n-max(now,con));
    return 0;
}

表示b为a数组中k（本身或后继）的排名；

next_permutation(start,end)

下一个排列

如果数组一开始是[1,n]递增的那么就可以生成全排列

sort(a,a+n);
do{
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    puts("");
}next_permutation(a,a+n);

prev_permutation(start,end)

上一个排列