题目大意：给定一个个区间，要求选择最少的区间覆盖所有点
首先我们考虑链上版本，，显然我们有一个贪心的做法： 从1号节点开始，每次选择能向后走的最远的区间，直到走完所有节点为止 正确性显然 但是到了环上版本我们却不能直接套用这个算法，因为环上不存在所谓的“1号节点” 因此我们这样做： 拆环后将序列倍增，把所有区间按照右端点从小到大排序 每个区间向这个区间右端点向后能走的最远的区间连一条边 这样我们会得到一棵树 从每个点可以用树上倍增求出最少向上走多少个点可以绕环走一圈 数据范围真虚，然而过了……
;int len,n,ans=0x3f3f3f3f;int fa[20][M],dpt[M];struct Interval{int x,y;friend istream& operator >> (istream &_,Interval &i){scanf(“%d%d”,&i.x,&i.y);if(i.y<i.x) i.y+=len;return _;}< (const Interval &i1,const Interval &i2){return i1.y < i2.y ;}}intervals[M];bool Compare(int x,int y){return intervals[x] < intervals[y] ;}void Get_Depth(int x){if(!fa[0][x])dpt[x]=1;if(dpt[x])return ;Get_Depth(fa[0][x]);dpt[x]=dpt[fa[0][x]]+1;}void Build_LCA(){int i,j;for(i=1;i<=n;i++)Get_Depth(i);for(j=1;j<=19;j++)for(i=1;i<=n;i++)fa[j][i]=fa[j-1][fa[j-1][i]];}int Query(int x,int limit){int j;for(j=19;~j;j–)if(fa[j][x]&&intervals[fa[j][x]].y<limit)x=fa[j][x];return intervals[x].y>=limit?x:fa[0][x];}int main(){int i,j;cin>>len>>n;for(i=1;i<=n;i++)cin>>intervals[i];sort(intervals+1,intervals+n+1);static int max_y[M];for(i=1;i<=n;i++)max_y[intervals[i].x]=max(max_y[intervals[i].x],i);int temp=0;for(j=1,i=1;i<=n;i++){for(;j<=intervals[i].y+1;j++)temp=max(temp,max_y[j],Compare);fa[0][i]=temp==i?0:temp;}Build_LCA();for(i=1;i<=n;i++){int temp=Query(i,intervals[i].x+len-1);if(temp) ans=min(ans,dpt[i]-dpt[temp]+1);}if(ans==0x3f3f3f3f)puts(“impossible”);elsecout<<ans<<endl;return 0;}
接受失败等于回归真实的自我，
