会议中心[APIO2009]

会议中心

思路

 #include<bits/stdc++.h>

 #define ll long long

 #define FOR(i,a,b) for(register int i=a;i<=b;i++)

 #define ROF(i,a,b) for(register int i=a;i>=b;i--)

 using namespace std;

 const int N=+;

 int n;

 int p[N],pr[N],s[N];

 int q[N];

 struct s1

 {

     int l,r,id;

 }a[N];

 bool cmp(s1 x,s1 y)

 {

     return x.r<y.r;

 }

 int scan()

 {

     int as=,f=;

     char c=getchar();

     while(c>''||c<''){if(c=='-') f=-;c=getchar();}

     while(c>=''&&c<=''){as=(as<<)+(as<<)+c-'';c=getchar();}

     return as*f;

 }

 int main()

 {

     n=scan();

     FOR(i,,n)

     {

         a[i].l=scan();a[i].r=scan();a[i].id=i;

     }

     sort(a+,a+n+,cmp);

     FOR(i,,n)

     {

         int l=,r=i-,m=;

         while(l<=r)

         {

             int mid=(l+r)>>;

             if(a[mid].r<a[i].l) m=mid,l=mid+;

             else r=mid-;

         }

         //现在我们找到了最近的一个区间

         int f=s[m]+;

         pr[i]=p[m];

         if(f>s[i-]) s[i]=f,p[i]=i;

         else if(s[i-]>f) s[i]=s[i-],p[i]=p[i-];

         else

         {

             int p1=p[i-],p2=i,min1=1e9,min2=1e9;

             while(pr[p1]!=pr[p2])

             {

                 if(a[p1].id<min1) min1=a[p1].id;

                 if(a[p2].id<min2) min2=a[p2].id;

                 p1=pr[p1];p2=pr[p2];

             }

             if(a[p1].id<min1)min1=a[p1].id;//处理"祖先"相同但当前结点不同

             if(a[p2].id<min2) min2=a[p2].id;

             if(min1<min2) s[i]=s[i-],p[i]=p[i-];

             else s[i]=f,p[i]=i,pr[i]=p[m];

         }

     }

     int now=p[n],top=;

     cout<<s[n]<<endl;

     while(now)

     {

         q[++top]=a[now].id;now=pr[now];

     }

     sort(q+,q+top+);

     FOR(i,,top) cout<<q[i]<<" ";

     return ;

 }