传送门：点击打开链接
题意：告诉你n个人，每个人有个s和b连个值，要求从n个人中选出数量最多的人，使任意两个人(i,j)都有si<sj且bi<bj或者sj<si且bj<bi，要求输出选出数量最多的人，且输出是哪一些人，其中题目是spj。
思路：首先很容易想到DAG模型，但是这题的n<=100000,所以用DAG模型复杂度太高了。然后会想到LIS，可能就会想到用二维线段树去做。
其实仔细想想这道题，和普通的LIS还是有不一样的地方的。那就是他的顺序并不是给定的！！什么意思呢，虽说是二维LIS,但是他给出的n个人，并不是必须要递增，而是只要选出一部分，然后排序一下，让他们递增就可以了，其实这就是在提示你，可以稍微处理一下输入，比如排序什么的，这是普通的LIS不能做的。这里排序也非常的巧妙
按照s从小到大排序，s相同时按照b从大到小排序，那么这样排序有什么好处呢。我们可以看下排序以后的样例
1 2,1 1,2 2,2 1
可以发现，s总是增大的(废话)，那么如果我们按照b去做LIS会怎样呢？
首先，1 2和1 1绝对不会出现在同一个LIS中，因为b是从大到小排序的，如果是s相同的时候，b在LIS中最多只会被取一次，因为本身b是递减的，但是在LIS中是递增的，所以只会存在一个。所以排序后对b做LIS就是答案了，然而另外一个问题在于如何打印答案。
有两种方法用O(nlogn)的复杂度去处理LIS，一种是线段树，可以做到打印路径且字典序最小，一种是二分查找，但是不好处理字典最小，好在题目是spj，所以我们同样可以采用二分的方法。
直接标记某个位置结尾的LIS的大小，然后从后往前扫，从最大的LIS往1去找对应的输出，一定不能从前向后扫，因为答案会不对，只有从后向前扫，此时才是一个完整的LIS路径
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;struct Node {int x, y, id;bool operator<(const Node &b)const {if(x == b.x) return y > b.y;return x < b.x;}
} A[MX];int d[MX], mark[MX];int main() {int n; //FIN;while(~scanf("%d", &n)) {memset(d, INF, sizeof(d));memset(mark, 0, sizeof(mark));for(int i = 1; i <= n; i++) {A[i].id = i;scanf("%d%d", &A[i].x, &A[i].y);}sort(A + 1, A + 1 + n);int ans = 0;for(int i = 1; i <= n; i++) {int p = lower_bound(d + 1, d + 1 + n, A[i].y) - d;mark[i] = p;ans = max(ans, p);d[p] = A[i].y;}printf("%d\n", ans);for(int i = n, j = ans; i >= 1; i--) {if(mark[i] == j) {printf("%d%c", A[i].id, j == 1 ? '\n' : ' ');j--;}}}return 0;
}