题目：
给出一个由n个数组成的序列x[1..n]，找出它的最长单调上升子序列。即求最大的m和a1,
a2……,am，使得a1<a2<……<am且x[a1]<x[a2]<……<x[am]。要求时间复杂度O(nlgn)
这也是一道动态规划的经典应用。一种动态规划的状态表示描述为：m[i]，1≤i≤n，表示以x[i]结尾的最长上升子序列的长度，则问题的解为 max{m[i],1≤i≤n}，状态转移方程和边界条件为：
m[i]=1+max{0, m[k]|x[k]<x[i] , 1≤k<i }同时当m[i]>1时，令p[i]=k，表示最优决策，
以便在计算出最优值后构造最长单调上升子序列。
上述算法的状态总数为O(n)，每个状态转移的状态数最多为O(n)，每次状态转移的时间为
O(1)，所以算法总的时间复杂度为O(n2)。
我们先来考虑以下两种情况：
1、若x[i]<x[j]，m[i]=m[j]，则m[j]这个状态不必保留。因为，可以由状态m[j]转移得到
的状态m[k] (k>j，k>i)，必有x[k]>x[j]>x[i]，则m[k]也能由m[i]转移得到；另一方面，
可以由状态m[i]转移得到的状态m[k] (k>j，k>i)，当x[j]>x[k]>x[i]时，m[k]就无法由m
[j]转移得到。
由此可见，在所有状态值相同的状态中，只需保留最后一个元素值最小的那个状态即可。
2、若x[i]<x[j]，m[i]>m[j]，则m[j]这个状态不必保留。因为，可以由状态m[j]转移得到的状态m[k] (k>j，k>i)，必有x[k]>x[j]>x[i]，则m[k]也能由m[i]转移得到，而且m[i]>m[j]，所以m[k]≥m[i]+1>m[j]+1，则m[j]的状态转移是没有意义的。
综合上述两点，我们得出了状态m[k]需要保留的必要条件：不存在i使得：x[i]<x[k]且m[i]≥m[k]。
于是，我们保留的状态中不存在相同的状态值，且随着状态值的增加，最后一个元素的值
也是单调递增的。
也就是说，设当前保留的状态集合为S，则S具有以下性质D：
对于任意i∈S, j∈S, i≠j有：m[i]≠m[j]，且若m[i]<m[j]，则x[i]<x[j]，否则x[i]>x[j]。
下面我们来考虑状态转移：假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计
算m[i]。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨
设m[i]=m[j]+1，则x[j]<x[i]=x[k]，j∈S，j≠k，所以m[j]<m[k]，则m[i]=m[j]+1≤m[k]，所以状态m[i]不需保留。
2、否则，m[i]=1+max{m[j]| x[j]<x[i], j∈S}。我们注意到满足条件的j也满足x[j]=max{x[k]|x[k]<x[i], k∈S}。同时我们把状态i加入到S中。
3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存
在状态k∈S，使得m[i]=m[k]，则我们有x[i]<x[k]，且x[k]=min{x[j]|x[j]>x[i], j∈S}。于是状态k应从S中删去。
于是，我们得到了改进后的算法：
For i:=1 to n do
{
找出集合S中的x值不超过x[i]的最大元素k；
if x[k]<x[i] then
{
m[i]:=m[k]+1;
将状态i插入集合S；
找出集合S中的x值大于x[i]的最小元素j；
if m[j]=m[i] then 将状态j从S中删去；
}
}
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集
合。
若使用平衡树实现有序集合S，则该算法的时间复杂度为O(n*log2n)。（每个状态转移的状
态数仅为O(1)，
而每次状态转移的时间变为O(log2n)）
题目
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2319
Memory Limit: 32768 KB Special Judge
The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength Si
and beauty Bi. Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates
j-th member of the club Mr Y if Si <= Sj and Bi >= Bj or if Si
>= Sj and Bi <= Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn��t even
notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).
To celebrate a new 2005 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people
who hate each other should be invited. On the other hand, to keep the club prestige at the apropriate level, administration wants to invite as many people as possible.
Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Input
The first line of the input file contains integer N - the number of members of the club. (2 <= N <= 100 000). Next N lines contain two numbers each - Si and Bi
respectively (1 <= Si, Bi <= 109).
Output
On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers - numbers of members to be invited in arbitrary order. If several solutions exist, output any one.
Sample Input
1
4
1 1
1 2
2 1
2 2
Sample Output
2
1 4
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2319
AC代码
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
int x,y,id;
};
struct node2
{
int v,id;
};
bool cmp (node a1,node a2)
{
if(a1.x!=a2.x)
return a1.x<a2.x;
else
return a1.y>a2.y;
}
int p[100100];
node a[100100];
node2 c[100100];
int search(int l,int r,int x)
{
while(l<=r)
{
int mid=(l+r)/2;
if(c[mid].v==x) return mid;
else if(c[mid].v>x)
r=mid-1;
else
l=mid+1;
}
return l;
}
int main ()
{
int t,n,i,j,k,len,ans;
scanf("%d",&t);
while( t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id=i;
}
sort(a,a+n,cmp);
c[0].v=-1;
c[0].id=-1;
len=0;
for(i=0;i<n;i++)
{
j=search(0,len,a[i].y);
c[j].v=a[i].y;
c[j].id=a[i].id;
//printf("%d/////\n",j);
if(j>0)
{
p[a[i].id]=c[j-1].id;
}
else
p[a[i].id]=-1;
if(j>len)
len=j;
}
//for(i=0;i<n;i++)
//printf("%d....\n",p[i]);
printf("%d\n",len);
for(i=c[len].id;i>=0;i=p[i])
{
if(i!=c[len].id)
putchar(' ');
printf("%d",i+1);
}
printf("\n");
}
return 0;
}