![2019.03.26 bzoj4444: [Scoi2015]国旗计划(线段树+倍增) 2019.03.26 bzoj4444: [Scoi2015]国旗计划(线段树+倍增)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
传送门
题意简述:现在给你一个长度为mmm的环,有nnn条互不包含的线段,问如果强制选第iii条线段至少需要用几条线段覆盖这个环,注意用来的覆盖的线段应该相交,即[1,3],[4,5][1,3],[4,5][1,3],[4,5]不合法[1,4],[4,5][1,4],[4,5][1,4],[4,5]合法。
思路:把坐标先离散化,然后破环为链,接着用线段树维护每个点向左走一步最多走到哪个点,然后就可以用ststst表维护每个点向左走2k2^k2k步最多走到哪个点,最后对于每条线段倍增求答案即可。
代码:
#include<bits/stdc++.h>
#define fi first
#define se second
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef pair<int,int> pii;
const int N=8e5+5;
int n,m,val[N],sig=0,st[N][20],vl[2][N],vr[2][N];
pii a[N];
namespace sgt{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
int mx[N<<2];
inline void pushnow(int p,int v){mx[p]=max(mx[p],v);}
inline void pushdown(int p){pushnow(lc,mx[p]),pushnow(rc,mx[p]);}
inline void update(int p,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr)return pushnow(p,v);
pushdown(p);
if(qr<=mid)update(lc,l,mid,ql,qr,v);
else if(ql>mid)update(rc,mid+1,r,ql,qr,v);
else update(lc,l,mid,ql,mid,v),update(rc,mid+1,r,mid+1,r,v);
}
inline void query(int p,int l,int r){
if(l==r){st[l][0]=mx[p];return;}
pushdown(p);
query(lc,l,mid),query(rc,mid+1,r);
}
#undef lc
#undef rc
#undef mid
}
inline int find(const int&x){return lower_bound(val+1,val+sig+1,x)-val;}
inline int query(int s,int t){
int ret=0;
for(ri i=19;~i;--i){
if(!st[s][i]||st[s][i]>=t)continue;
s=st[s][i];
ret|=1<<i;
}
return ret+1;
}
int main(){
n=read(),m=read();
val[++sig]=1,val[++sig]=m,val[++sig]=m+1,val[++sig]=m<<1;
for(ri i=1;i<=n;++i)val[++sig]=a[i].fi=read(),val[++sig]=a[i].se=read(),val[++sig]=a[i].fi+m,val[++sig]=a[i].se+m;
sort(val+1,val+sig+1),sig=unique(val+1,val+sig+1)-val-1;
for(ri i=1;i<=n;++i)vl[0][i]=find(a[i].fi),vl[1][i]=find(a[i].fi+m),vr[0][i]=find(a[i].se),vr[1][i]=find(a[i].se+m);
for(ri i=1;i<=n;++i){
if(a[i].fi<=a[i].se){
sgt::update(1,1,sig,vl[0][i],vr[0][i],vr[0][i]);
sgt::update(1,1,sig,vl[1][i],vr[1][i],vr[1][i]);
}
else{
sgt::update(1,1,sig,1,vr[0][i],vr[0][i]);
sgt::update(1,1,sig,vl[0][i],vr[1][i],vr[1][i]);
sgt::update(1,1,sig,vl[1][i],sig,sig);
}
}
sgt::query(1,1,sig);
for(ri j=1;j<20;++j)for(ri i=1;i<=sig;++i)st[i][j]=st[st[i][j-1]][j-1];
for(ri i=1;i<=n;++i)cout<<1+query(a[i].se<a[i].fi?vr[1][i]:vr[0][i],vl[1][i])<<' ';
return 0;
}