bzoj1178

题目：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，但不适用于pojusing 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-9;
inline int sgn(DB x){if(abs(x)<EPS)return 0;return(x>0)?1:-1;}
const DB Pi=acos(-1.0);inline int gint(){int res=0;bool neg=0;char z;for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());if(z==EOF)return 0;if(z=='-'){neg=1;z=getchar();}for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());return (neg)?-res:res; }
inline LL gll(){LL res=0;bool neg=0;char z;for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());if(z==EOF)return 0;if(z=='-'){neg=1;z=getchar();}for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar());return (neg)?-res:res; }const int maxN=200000;
const int maxcnt=2*maxN;
const int INF=2147483647;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=0,int _r=0,int _id=0){l=_l;r=_r;id=_id;}}a[maxN+100],temp[maxN+100];int flag[maxN+100];
int ans;
PII fin[maxN+100];int tol;int cnt,bak[maxcnt+100];inline bool cmpr(Ta x,Ta y){return x.r<y.r;}int tree[maxcnt+100];int next[maxN+100];
int jump[maxN+100][31];#define lowbit(a) (a&(-a))
inline int ask(int p){p=cnt-p+1;int res=INF;for(;p>=1;p-=lowbit(p))upmin(res,tree[p]);return res;}
inline void update(int p,int v){p=cnt-p+1;for(;p<=cnt;p+=lowbit(p))upmin(tree[p],v);}PII tr[4*maxcnt+1000];
inline void down(int root,int l,int r,int mid){if(tr[root]!=PII(0,0)){tr[root*2]=tr[root*2+1]=tr[root];tr[root]=PII(0,0);}}
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)/2;down(root,l,r,mid);if(p<=mid) askf(root*2,l,mid,p,x,y); else askf(root*2+1,mid+1,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)/2;down(root,l,r,mid);updatef(root*2,l,mid,x,y,val);updatef(root*2+1,mid+1,r,x,y,val);}inline int solve(int x,int y){if(x>y)return 0;int res=0,i,p=lower_bound(a+1,a+N+1,Ta(x,0,0))-a;if(p>N)return 0;red(i,30,0)if(jump[p][i]!=0 && 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-1);int t3=solve(r+1,y);return solve(x,y)==solve(x,l-1)+1+solve(r+1,y);}int main(){freopen("bzoj1178.in","r",stdin);freopen("bzoj1178.out","w",stdout);int i,j;N=gint();re(i,1,N)a[i].l=gint(),a[i].r=gint(),a[i].id=i;re(i,1,N)bak[++cnt]=a[i].l,bak[++cnt]=a[i].r;sort(bak+1,bak+cnt+1);cnt=unique(bak+1,bak+cnt+1)-bak-1;re(i,1,N)a[i].l=lower_bound(bak+1,bak+cnt+1,a[i].l)-bak,a[i].r=lower_bound(bak+1,bak+cnt+1,a[i].r)-bak;re(i,1,N)fin[a[i].id]=PII(a[i].l,a[i].r);tol=N;sort(a+1,a+N+1,cmpr);int t=0;re(i,1,N){if(a[i].l<=t)flag[i]=1;upmax(t,a[i].l);}int ge=0;re(i,1,N)if(!flag[i])temp[++ge]=a[i];N=ge;re(i,1,N)a[i]=temp[i];t=0;re(i,1,N)if(t<a[i].l){ans++;t=a[i].r;}cout<<ans<<endl;re(i,1,cnt)tree[i]=INF;red(i,N,1){next[i]=ask(a[i].r+1);if(next[i]==INF) next[i]=0;update(a[i].l,i);}red(i,N,1){jump[i][0]=next[i];re(j,1,30)jump[i][j]=jump[jump[i][j-1]][j-1];}re(i,1,4*maxcnt+1000-1)tr[i]=PII(1,cnt);re(i,1,tol){int l=fin[i].fi,r=fin[i].se,x,y;askf(1,1,cnt,l,x,y);if(x==-1 && y==-1)continue;if(!(x<=l && r<=y))continue;if(check(x,y,l,r)){printf("%d ",i);ans--;if(ans==0)break;updatef(1,1,cnt,l,r,PII(-1,-1));updatef(1,1,cnt,x,l-1,PII(x,l-1));updatef(1,1,cnt,r+1,y,PII(r+1,y));}}printf("\n");return 0;}