# bzoj4444: [Scoi2015]国旗计划

2020-12-07 15:21:32

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int L[210000],R[210000],l[210000],r[210000],A[410000];
bool cmp(int a,int b) {

return a<b;}int n,m,len;
int pos(int x) {
int l=1,r=len,mid,ans=0;
while(l<=r) {
mid=(l+r)/2;
if(A[mid]>=x) {
if(A[mid]==x)ans=mid;
r=mid-1;
}else l=mid+1;
}return ans;
}
struct node {

int l,r;}s[410000];int mx[21][1100000],bin[21];
bool cmp1(node n1,node n2) {

return n1.l<n2.l;}
int jump(int x,int k) {

for(int i=20;i>=0;i--)if((k&bin[i]))x=mx[i][x];return x;}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {scanf("%d%d",&L[i],&R[i]);A[++len]=L[i];A[++len]=R[i];}
sort(A+1,A+1+len,cmp);int mmax=0;
for(int i=1;i<=n;i++) {l[i]=pos(L[i]);r[i]=pos(R[i]);mmax=max(mmax,max(l[i],r[i]));}
len=0;
for(int i=1;i<=n;i++) {
if(l[i]>r[i])r[i]+=mmax;
s[++len].l=l[i];s[len].r=r[i];
s[++len].l=l[i]+mmax;s[len].r=min(r[i]+mmax,2*mmax);
}sort(s+1,s+1+len,cmp1);
int t=1,F=0;memset(mx,0,sizeof(mx));
for(int i=1;i<=2*mmax;i++) {
while(s[t].l<=i&&t<=2*n) {F=s[t].r;t++;}
mx[0][i]=F;
}
bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]*2;
for(int j=1;j<=20;j++)for(int i=1;i<=2*mmax;i++)mx[j][i]=mx[j-1][mx[j-1][i]];
int ans;
for(ans=0;ans<n;ans++)if(jump(r[1],ans)>=l[1]+mmax) break;
printf("%d",ans+1);
for(int i=2;i<=n;i++) {
if(jump(r[i],ans-1)>=l[i]+mmax)printf(" %d",ans);
else if(jump(r[i],ans)>=l[i]+mmax)printf(" %d",ans+1);
else printf(" %d",ans+2);
}
return 0;
}``````

https://my.oschina.net/u/4377109/blog/4778673