SGU199 就是二维的LIS，要输出路径。 所以第一维进行排序，第二维用树状数组去找最大值。
199. Beautiful People
time limit per test: 0.25 sec. memory limit per test: 65536 KB
input: standard output: standard
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 2003 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 presti≥ 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.
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 test(s)
Input
4 1 1 1 2 2 1 2 2
Output
2 1 4
/* ***
Author :kuangbin
Created Time :2014/11/4 11:37:23
File Name :E:\2014ACM\SGU\SGU199.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN = 100010;
int dp[MAXN];
int c[MAXN];
int cnt;
int lowbit(int x){
return x&(-x);
}
void add(int x,int id){
int i = x;
while(i <= cnt){
if(dp[id] > dp[c[i]])
c[i] = id;
i += lowbit(i);
}
}
int query(int i){
int ret = 0;
while(i > 0){
if(dp[c[i]] > dp[ret])ret = c[i];
i -=lowbit(i);
}
return ret;
}
struct Node{
int x,y;
int index;
bool operator <(const Node &b)const{
return x < b.x || (x == b.x && y < b.y);
}
}node[MAXN];
int yy[MAXN];
int pre[MAXN];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1){
cnt = 0;
for(int i = 1;i <= n;i++){
scanf(“%d%d”,&node[i].x,&node[i].y);
node[i].index = i;
yy[++cnt] = node[i].y;
}
sort(node+1,node+n+1);
sort(yy+1,yy+cnt+1);
cnt = unique(yy+1,yy+cnt+1) - yy - 1;
map<int,int>mp;
for(int i = 1;i <= cnt;i++)mp[yy[i]] = i;
for(int i = 1;i <= n;i++)
node[i].y = mp[node[i].y];
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
int id = 1;
for(int i = 1;i <= n;i++){
while(node[id].x != node[i].x){
add(node[id].y,id);
id++;
}
int tmp = query(node[i].y-1);
dp[i] = dp[tmp] + 1;
pre[i] = tmp;
}
int now = 0;
for(int i = 1;i <= n;i++)
if(dp[i] > dp[now])
now = i;
vector
while(now){
ans.push_back(node[now].index);
now = pre[now];
}
reverse(ans.begin(),ans.end());
int sz = ans.size();
printf(“%d\n”,sz);
for(int i = 0;i < sz;i++){
printf(“%d”,ans[i]);
if(i < sz-1)printf(“ “);
else printf(“\n”);
}
}
return 0;
}
