beautiful people(dp o(nlogn)).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
#define NMAX 100100 
int p,n;
struct node {
	int s,b;
	int num;
	bool operator < (const node & t) const {
		if(s != t.s) {
			return s < t.s;//non-decreasing order
		}
		return b > t.b;//non-increasing order
	}
}pepo[NMAX];
node len[NMAX];
int dp[NMAX];

int main()
{
	int i,j,t;
	pepo[0].s = -1;
	scanf("%d", &t);
	while (t --) {
		scanf("%d", &n);
		for (i=1;i<=n;i++) {
			scanf("%d %d", &pepo[i].s, &pepo[i].b);
			pepo[i].num = i;
		}
		sort(pepo,pepo+n+1);
		dp[0] = 0;
		dp[1] = 1;
		len[1] = pepo[1];
		int mmax = 1;
		for (i=2;i<=n;i++) {//DP, Longest non-decreasing Sequence
			dp[i] = 1;
			len[i].s = len[i].b = INT_MAX;
			int left = 1, right = mmax;
			while (right >= left) {
				int mid = (left + right) / 2;
				if (pepo[i].s > len[mid].s && pepo[i].b > len[mid].b) {
					left = mid+1;
				}
				else {
					right = mid-1;
				}
			}
			dp[i] = left;
			if (pepo[i].b < len[ dp[i] ].b) {
				len[ dp[i] ] = pepo[i];
			}
			mmax = mmax > dp[i] ? mmax : dp[i];
		}//for i
		printf("%d\n", mmax);
		int pre ;
		for (i=n;i>=1;i--) {
			if (mmax == dp[i]) {
				mmax --;
				printf("%d", pepo[i].num);
				pre = i;
				break;
			}
		}
		for ( ;i>=1;i--) {
			if (mmax == dp[i] && pepo[i].s < pepo[pre].s && pepo[i].b < pepo[pre].b) {
				mmax --;
				printf(" %d", pepo[i].num);
				pre = i;
			}
			if (mmax == 0) {
				break ;
			}
		}

		printf("\n");
	}
}