题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1178
看ppt
http://wenku.baidu.com/link?url=dJv6LNme7syiLGM-TzbEEKXwx36JWEnI5HFrIlzfmzUXXg4HG8FDggj5WQS3EKL3k3p-sUYeJ268jCvN4t_kq2YPo3I4GXvaGulQjXrO3d7
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ,但不适用于poj using namespace std; typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define re(i,a,b) for(i=a;i<=b;i++)
#define red(i,a,b) for(i=a;i>=b;i--)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define SF scanf
#define PF printf
#define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0); inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
} const int maxN=;
const int maxcnt=*maxN;
const int INF=; int N;
struct Ta
{
int l,r,id;
inline friend bool operator < (Ta x,Ta y){return x.l<y.l;}
inline Ta(int _l=,int _r=,int _id=){l=_l;r=_r;id=_id;}
}a[maxN+],temp[maxN+]; int flag[maxN+];
int ans;
PII fin[maxN+];int tol; int cnt,bak[maxcnt+]; inline bool cmpr(Ta x,Ta y){return x.r<y.r;} int tree[maxcnt+]; int next[maxN+];
int jump[maxN+][]; #define lowbit(a) (a&(-a))
inline int ask(int p)
{
p=cnt-p+;
int res=INF;
for(;p>=;p-=lowbit(p))upmin(res,tree[p]);
return res;
}
inline void update(int p,int v)
{
p=cnt-p+;
for(;p<=cnt;p+=lowbit(p))upmin(tree[p],v);
} PII tr[*maxcnt+];
inline void down(int root,int l,int r,int mid)
{
if(tr[root]!=PII(,))
{
tr[root*]=tr[root*+]=tr[root];
tr[root]=PII(,);
}
}
inline void askf(int root,int l,int r,int p,int &x,int &y)
{
if(l>r || p<l || r<p) return;
if(p<=l && r<=p) {x=tr[root].fi;y=tr[root].se;return;}
int mid=(l+r)/;
down(root,l,r,mid);
if(p<=mid) askf(root*,l,mid,p,x,y); else askf(root*+,mid+,r,p,x,y);
}
inline void updatef(int root,int l,int r,int x,int y,PII val)
{
if(l>r || x>y || r<x || y<l)return;
if(x<=l && r<=y){tr[root]=val;return;}
int mid=(l+r)/;
down(root,l,r,mid);
updatef(root*,l,mid,x,y,val);
updatef(root*+,mid+,r,x,y,val);
} inline int solve(int x,int y)
{
if(x>y)return ;
int res=,i,p=lower_bound(a+,a+N+,Ta(x,,))-a;
if(p>N)return ;
red(i,,)
if(jump[p][i]!= && a[jump[p][i]].r<=y)
{
res+=two(i);
p=jump[p][i];
}
if(a[p].r<=y)res++;
return res;
}
inline int check(int x,int y,int l,int r)
{
int t1=solve(x,y);
int t2=solve(x,l-);
int t3=solve(r+,y);
return solve(x,y)==solve(x,l-)++solve(r+,y);
} int main()
{
freopen("bzoj1178.in","r",stdin);
freopen("bzoj1178.out","w",stdout);
int i,j;
N=gint();
re(i,,N)a[i].l=gint(),a[i].r=gint(),a[i].id=i;
re(i,,N)bak[++cnt]=a[i].l,bak[++cnt]=a[i].r;
sort(bak+,bak+cnt+);
cnt=unique(bak+,bak+cnt+)-bak-;
re(i,,N)a[i].l=lower_bound(bak+,bak+cnt+,a[i].l)-bak,a[i].r=lower_bound(bak+,bak+cnt+,a[i].r)-bak;
re(i,,N)fin[a[i].id]=PII(a[i].l,a[i].r);
tol=N;
sort(a+,a+N+,cmpr);
int t=;
re(i,,N){if(a[i].l<=t)flag[i]=;upmax(t,a[i].l);}
int ge=;
re(i,,N)if(!flag[i])temp[++ge]=a[i];
N=ge;
re(i,,N)a[i]=temp[i];
t=;
re(i,,N)if(t<a[i].l){ans++;t=a[i].r;}
cout<<ans<<endl;
re(i,,cnt)tree[i]=INF;
red(i,N,)
{
next[i]=ask(a[i].r+);if(next[i]==INF) next[i]=;
update(a[i].l,i);
}
red(i,N,)
{
jump[i][]=next[i];
re(j,,)jump[i][j]=jump[jump[i][j-]][j-];
}
re(i,,*maxcnt+-)tr[i]=PII(,cnt);
re(i,,tol)
{
int l=fin[i].fi,r=fin[i].se,x,y;
askf(,,cnt,l,x,y);
if(x==- && y==-)continue;
if(!(x<=l && r<=y))continue;
if(check(x,y,l,r))
{
printf("%d ",i);
ans--;if(ans==)break;
updatef(,,cnt,l,r,PII(-,-));
updatef(,,cnt,x,l-,PII(x,l-));
updatef(,,cnt,r+,y,PII(r+,y));
}
}
printf("\n");
return ;
}