x坐标排序，y坐标当权值，同一个x坐标的，y从大到小排。
求f(i)表示以i结尾的LIS以后，从后向前枚举，不断更新一个max数组，max(i)代表最长上升子序列为i时，当前的 结尾的最大值是多少。
一个元素可能在LIS里面，则说明存在一个j>i，f（j）=f（i）+1，且a（j）>a（i），就查询一下max(f(i)+1)是否大于a(i)即可。如果可行的话，再用该值更新max数组。
一定在LIS里面的就是i可能在LIS里面，并且f(i)只出现了一次的。
队友的代码(↓)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&-(x))
using namespace std;
struct node{
int x,y,id;
}a[100005];
bool cmp(node a,node b)
{
return a.x==b.x?a.y>b.y:a.x<b.x;
}
int Ans1[100005],Ans2[100005],f[100005],g[100005],vis[100005],n,ans1num,ans2num,s[100005],ans,ls[100005];
bool cmp2(int a,int b)
{
return f[a]<f[b];
}
bool ans1[100005];
void add(int p,int x)
{
p=lower_bound(ls+1,ls+n+1,p)-ls;
for(;p<=n;p+=lowbit(p))
{
s[p]=max(s[p],x);
}
}
int get(int p)
{
p=lower_bound(ls+1,ls+n+1,p)-ls-1;
int nowans=0;
for(;p;p-=lowbit(p))
{
nowans=max(nowans,s[p]);
}
return nowans;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id=i;
ls[i]=a[i].y;
}
sort(ls+1,ls+n+1);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
{
f[i]=get(a[i].y)+1;
add(a[i].y,f[i]);
ans=max(ans,f[i]);
}
for(int i=n;i;--i)
{
if(f[i]==ans||(vis[f[i]+1]&&a[i].y<g[f[i]+1]))
{
ans1[i]=1;
if(vis[f[i]]==0)
{
g[f[i]]=a[i].y;
vis[f[i]]=1;
}
else
{
g[f[i]]=max(g[f[i]],a[i].y);
}
}
}
for(int i=1;i<=n;++i)
if(ans1[i])
{
Ans1[++ans1num]=i;
}
sort(Ans1+1,Ans1+ans1num,cmp2);
for(int i=1;i<=ans1num;++i)
{
if(f[Ans1[i]]!=f[Ans1[i-1]]&&f[Ans1[i]]!=f[Ans1[i+1]])
{
Ans2[++ans2num]=a[Ans1[i]].id;
}
}
for(int i=1;i<=ans1num;++i)
Ans1[i]=a[Ans1[i]].id;
sort(Ans1+1,Ans1+ans1num+1);
sort(Ans2+1,Ans2+ans2num+1);
printf("%d ",ans1num);
for(int i=1;i<ans1num;++i)
printf("%d ",Ans1[i]);
if(ans1num) printf("%d
",Ans1[ans1num]);
printf("%d ",ans2num);
for(int i=1;i<ans2num;++i)
printf("%d ",Ans2[i]);
if(ans2num)printf("%d
",Ans2[ans2num]);
return 0;
}