import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++){
            arr[i] = in.nextInt();
        }
        quickSort(arr, 0, n - 1);
        System.out.print(arr[k - 1] + " ");
    }

    private static void quickSort(int[] arr, int left, int right){
        if(left >= right) return;
        int x = arr[left + right >> 1], i = left - 1, j = right + 1;
        while(i < j){
            do{
                i ++;
            }while(arr[i] < x);
            do{
                j --;
            }while(arr[j] > x);
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        quickSort(arr, left, j);
        quickSort(arr, j + 1, right);
    }
}

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int h[N], f[N], q[N];

int main()
{
    while (cin >> h[n]) n ++ ;

    int res = 0, cnt = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (h[i] <= h[j])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);

        int k = 0;
        while (k < cnt && q[k] < h[i]) k ++ ;
        if (k == cnt) q[cnt ++ ] = h[i];
        else q[k] = h[i];
    }

    printf("%d\n", res);
    printf("%d\n", cnt);
    return 0;
}

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int q[N],temp[N];
int n;

void merge_sort(int q[],int l,int r)
{
    if(l>=r) return ;
    int mid=l+r>>1;
    //左右两边排序
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    //合并
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else temp[k++]=q[j++];
    }
    //处理边界查看两边那边先遍历结束
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];

    //将temp数组的值重新赋值给q数组
    for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}

int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", &q[i]);
    merge_sort(q,0,n-1);
    for (int i = 0; i < n; i ++ ) printf("%d ",q[i]);
    return 0;
}

本题只要将南北岸同时根据任一端从小到大排序，就会发现如果想要不交叉的最多配对线段，
另一端就必然是一个最长上升子序列。
所以复杂度就是排序的$O(nlogn)$ 和 求最长上升子序列的复杂度

算法1

(暴力dp) $O(n^2)$

朴素版dp求最长上升子序列，dp复杂度$O(n^2)$

python 代码

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
a.sort(key = lambda x : x[1])
dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[i][0] > a[j][0]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
const int N = 5010;
PII a[N];
int dp[N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &a[i].first, &a[i].second);
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; ++i){
        dp[i] = 1;
        for (int j = 0; j <= i; ++j)
            if (a[i].second > a[j].second)
                dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }

    cout << res << endl;
    return 0;
}

算法2

(dp + 贪心二分) $O(nlogn)$

最长上升子序列的二分版本

python 代码

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
a.sort(key = lambda x : x[1])
q = [0] * (n + 10)
length = 0
for i in range(n):
    l, r = 0, length
    while l < r:
        mid = l + r + 1 >> 1
        if a[i][0] > q[mid]: l = mid
        else: r = mid - 1
    if r == length: length += 1
    q[r + 1] = a[i][0]
print(length)

C++ 代码（可过洛谷上同名题）

#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
const int N = 200010;
PII a[N];
int q[N];
int len, n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &a[i].first, &a[i].second);
    sort(a, a + n);
    for (int i = 0; i < n; ++i){
        int l = 0, r = len;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (a[i].second > q[mid]) l = mid;
            else r = mid - 1;
        }
        if (r >= len) ++len;
        q[r + 1] = a[i].second;
    }

    printf("%d\n", len);    
    return 0;
}

题目描述

click the link below

https://www.acwing.com/problem/content/description/1628/

    题目的意思是首先如果这个节点值是一个负数 那么按照原来给出的顺序放在正数的前面
    如果是一个正数 那么再来一条分割线K 
    如果小于等于K就按照它们在链表中原来的位置排在负数的后面 
    如果是大于K就排在小于等于K的节点后面
    好勒 学完困觉（gao）吧~~

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int e[N], ne[N];

int main()
{
    int n, m, head;
    vector<PII> res;
    cin >> head >> n >> m;

    for(int i = 0; i < n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[a] = b;
        ne[a] = c;
    }

    for(int i = head; i != -1; i = ne[i])
        if(e[i] < 0) res.push_back({e[i], i});

    for(int i = head; i != -1; i = ne[i])
        if(e[i] >= 0 && e[i] <= m) res.push_back({e[i], i});

    for(int i = head; i != -1; i = ne[i])
        if(e[i] > m) res.push_back({e[i], i});

    for(int i = 0; i < res.size(); i ++)
        if(i < res.size() - 1)
            printf("%05d %d %05d\n", res[i].second, res[i].first, res[i + 1].second);
        else printf("%05d %d -1", res[i].second, res[i].first);

    return 0;
}

数的三次方根

浮点数二分

浮点数二分与整数二分相比，边界条件问题没有了，但是二分循环结束条件不同，由于浮点数存储是不精确的，所以判断左右边界相等就是作差小于一个非常小的数字
一般是在要求输出的小数点位数下，多处理2位，确保答案准确

浮点数二分模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

本题目分析

这是一道很标准的模板题，套模板就够了

初始边界是 l = -100, r = 100
因为-100 和 100 的三次方都在要求边界外，(反着说就是边界的三次方根都在-100 ~ 100之间)，所以这样肯定能够二分出范围内的所有答案而不存在遗漏

时间复杂度

O($\log n$)

代码

#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;//使所有答案都落在区间范围内
    while (r - l > 1e-8)//为了答案精确，往后多计算两位，防止四舍五入出现最后一位差1的尴尬
    {
        double mid = (l + r) / 2;//取中点
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%.6lf\n", l);
    return 0;
}

import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++){
            arr[i] = in.nextInt();
        }
        int result = quickSort(arr, 0, n - 1, k);
        System.out.print(result);
    }

    private static int quickSort(int[] arr, int left, int right, int k){
        while(left >= right) return arr[left];
        int x = arr[left + right >> 1], i = left - 1, j = right + 1;
        while(i < j){
            do{
                i ++;
            }while(arr[i] < x);
            do{
                j --;
            }while(arr[j] > x);
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int length = j - left + 1;
        if(k <= length) return quickSort(arr, left, j, k);
        else return quickSort(arr, j + 1, right, k - length);
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     char val[10];
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX 1010
char s[MAX];

void dfs(struct TreeNode *root) {
    if(!root)  return;
    else if(!root -> left && !root -> right)  strcat(s, root -> val);
    else {
        strcat(s, "(");
        dfs(root -> left);
        strcat(s, root -> val);
        dfs(root -> right);
        strcat(s, ")");
    }
}

char* expressionTree(struct TreeNode *root) {
    dfs(root -> left);
    strcat(s, root -> val);
    dfs(root -> right);

    return s;
}

主席树(可持久化线段树) 模板题

优秀题解 【学习笔记】主席树

标准的线段树模板题请参考 AcWing 1275. 最大数

 "可持久化线段树" 在本题目的作用实际上是指"使用多个入口指针保存多个不同版本的线段树", 
 类似Git, 每个版本包含当前版本和之前的所有内容: 每新增一个点都建一颗新树,
 复制前一棵树并插入新元素所造成的修改. 
 实现上, 是在build的时候只建立树的骨架而不保存元素, 而对每一个点都做一次insert, 
 在插入新点的同时, 复制上一棵树, 再插入新点

主席数的整体定义

与线段树不同的是，树节点维护的$l$,$r$值从区间的端点值变成左右子节点(标志值)，那么我们下面用几张图来说明主席数的执行流程。

首先先初始化一棵空的树

注意这里区间的定义不用真的在主席数的树节点结构上表现出来，
而是在递归的时候规定递归哪个区间，然后用树节点的标志值来表示他这个节点所代表的区间是什么。
用cnt来表示它这个区间插入了多少个数

下面用加入一段序列来进行举例：序列4 3 2 3 6 1

区间[1,1]的线段树（蓝色节点为新节点）

当我们插入一个元素的时候，我们其实只需要修改其中一条链的数据，对于其他剩余的节点我们就直接复制，同时复制旧版本的节点到新的树上，复制完后新版本的节点加上新的版本号

下面的执行步骤同理

区间[1,2]的线段树（橙色节点为新节点）

区间[1,3]的线段树（紫色节点为新节点）

int insert(int p, int l, int r, int x)
{
    // 假设现在是从外界第一次执行insert, 那么调用的时候, p必定是根节点,
    // 那么q就相当于复制了一个根节点, 从节点q进入这棵树的时候, 也能得到之前的所有内容.
    // 同理, 再往下二分递归的时候, insert会继续复制根节点的左(右)子树, 一直递归直到l==r之前,
    // q和原来的p都是一毛一样. 直到l==r才真正插入了新点, 每次插入的时间空间复杂度都是lgk,
    // 总加起来就是lg1+lg2+...+lgn = lg(n!), 根据stirling公式, 结果为nlgn   (大O)
    int q = ++idx;
    tr[q] = tr[p]; 
    if (l == r)  // 如果区间长度为1, 说明就是放这里了
    {
        // tr[q].cnt++是表示插在这个叶节点上
        // 这个线段树只是保存的每个区间里面的元素个数
        // 每次插入都只是覆盖到的那堆区间里面的cnt发生+1
        tr[q].cnt++;
        return q;
    }

    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid+1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;  // 相当于pushup了
    return q;
}

回到本题，

我们发现需要进行离散化，因为此时建树的依据是数值的大小，左子树存放的数比右子数的存放的数要小，而不是下标，又因为原本的数据取值太大，因此需要通过离散化将所有数据离散为一个较小范围，离散后我们并不在意它们的真实值，只需要某个数在所有数中的位置，通过位置可以找到在原数据中的真实值。

离散化的模板可以参考 AcWing 802. 区间和

主席树

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
const int N = 100010;
using namespace std;


struct Node{
    int l,r; //分别表示左右节点
    int cnt; //表示当前树节点插入了多少个数
}tr[N * 4 + N * 17];  //初始骨架N * 4 再加上最多M次插入一共修改MlogM个节点
vector<int> nums; //用于离散化的数组,由于数的范围很大，但是不能开那么大的空间，所以需要离散化
int root[N],idx; //root记录根节点的版本号【root[r]表示插入了第r个数版本的线段树】, idx记录树节点的版本号
int a[N];  //原始数组
int n,m;  


int find(int x){
    int idx = lower_bound(nums.begin(),nums.end(),x) - nums.begin();
    return idx;
}


int build(int l,int r){  //返回标志值
    int p = idx++;
    if(l == r){   //到叶子节点了
        return p;
    }
    int mid = l + r >> 1;
    //递归到最底层之后向上给父节点的属性赋值
    tr[p].l = build(l,mid);  tr[p].r = build(mid + 1,r);
    return p;
}

// l, r是要放入的坐标范围, x是要插入的数离散化后的位置
int insert(int p,int l,int r,int x){    //返回值是新版本树节点的标志值

    int q = idx++;
    tr[q] = tr[p];  //先将上一个版本信息复制过来
    if(l == r){  //遍历到叶子节点，同时找到了要插入的位置，cnt++
        tr[q].cnt++; 
        return q;
    }

    //接着找要插入的位置
    int mid = l + r >> 1;

    //这里也是新版本树节点直接复制旧版本树的信息，同时返回一个新的版本号
    //下表小于mid放左区间，反之放右区间
    if(x <= mid) tr[q].l = insert(tr[p].l,l,mid,x);
    else tr[q].r = insert(tr[p].r,mid + 1, r ,x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;  // 相当于pushup了
    return q;

}


// l ,r是检索范围, q是当前第r个节点root[r]能包含1~r之间所有
// q的输入是root[r],p的输入是root[l-1], 作用是剔除这个根节点所包含数据的影响(前缀和的思想)
int query(int q, int p, int l, int r, int k){

    //遍历到了叶子节点的位置，说明找到了所需要的位置
    if(l == r) return r;

    // 目标是求l r之间的第k小
    // tr[tr[q].l].cnt - tr[tr[p].l].cnt的结果是求出在p之后插入到q这些数之后,
    // 有多少个数(cnt)插入了p的左子树, 由于p的内容肯定不能出现在l r之间(p根节点就是root[l-1]), 
    // 所以cnt就是相当于"存在于r版本左子树中的数但不存在于l - 1版本左子树中的数的个数"
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; 
    int mid = l + r >> 1;
    // k <= cnt说明要找的元素在q的左子树里面, 同时这里面也要剔除掉包含在p左子树的内容
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid+1, r, k - cnt);  // 类似同上
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i){
        scanf("%d",&a[i]);
        nums.push_back(a[i]);
    }

    //离散化
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    root[0] = build(0,nums.size() - 1);  //初始时，建立一个空的骨架，不同版本的线段树的结构都是一样的


    for(int i = 1;i <= n;++i){
        //初始
        root[i] = insert(root[i - 1],0,nums.size() - 1,find((a[i])));
    }

    while(m--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);

        //查询[l,r]区间中的第k大数，利用前缀和的思想,从[l ~ r]中的数据剔除掉[1 ~ l-1]的数据,
        //不同版本的线段树的结构都是一样的，所以初始都是从0到nums.size()这个范围当中找
        printf("%d\n",nums[query(root[r],root[l - 1],0,nums.size() - 1,k)]);
    }
    return 0;
}