题解 P4155 【[SCOI2015]国旗计划】
FlashHu
·
·
题解
复杂度优化的思路是建立在倍增思路的基础上的，看看楼上几位巨佬的描述吧。
首先数组倍长是一样的。倍增法对于快速找到$j$满足$l_j+m\le r_i$进行了优化。然后菊开队长说可以建个树优化，可是他没讲清楚就把这个神仙东西扔给了我这个蒟蒻。。。一个晚上终于把这个模性建出来了。
在倍长的序列上，我们对于每一个$i$找到最小的$j$满足$r_j\ge l_i$并连一条$i$到$j$的边，于是就成了一个森林。贪心地想，我们要求的东西就变成了：对于每个点，找到与它最近的祖先$j$满足$l_j+m\le r_i$，$j$到$i$间的总点数就是答案。下面称$j$为$i$的决策点。
还是要树上倍增么？不不不，我们来注意一个性质：设不强制选某个战士的最优答案是$ans$，那么如果强制选某一个，答案要么是$ans$要么是$ans+1$。显然如果一个战士能够被一个最优方案包含的话就是$ans$，如果不能，任选一个最优方案再选他自己就可以了。
于是，假设$x$的决策点为$y$，那么$x$的一个儿子$x_1$的决策点，要么还是$y$，要么是$y$往$x$方向上的儿子。直接从上往下dfs并维护每个点的决策点就好啦！实现中，找到“$y$往$x$方向上的儿子”可以用类似Dinic当前弧的方法维护。
时间复杂度$O(n)$，常数较大，欢迎超越。为了理论上的严格线性，蒟蒻研究了下松爷基排，还写了个template，好不麻烦。template的食用方法可以去[蒟蒻的blog](https://www.cnblogs.com/flashhu/p/9751909.html)上看。
注意开unsigned int，没开的话蒟蒻不知道能不能过。
```cpp
#include<bits/stdc++.h>
#define UI unsigned int
#define RG register
#define R RG UI
#define G if(++ip==ie)fread(ip=buf,1,N,stdin)
using namespace std;
const UI N=4e5+9;
struct Data{UI l,r,id;}a[N],b[N];
UI m,he[N],ne[N],at[N],d[N];
char buf[N],*ie=buf+N,*ip=ie-1;
inline UI in(){
G;while(*ip<'-')G;
R x=*ip&15;G;
while(*ip>'-'){x*=10;x+=*ip&15;G;}
return x;
}
template<typename T>//基数排序
inline void Radixsort(RG T*fst,RG T*lst,RG T*buf,RG int*op){
static int b[0x100];
RG UI Len=lst-fst,Sz=sizeof(T),i,j;
RG unsigned char*bgn,*end,*it;
for(i=0;i<Sz;++i){
if(op[i]==-1)continue;
bgn=(unsigned char*)fst+i;end=(unsigned char*)lst+i;
memset(b,0,sizeof(b));
for(it=bgn;it!=end;it+=Sz)++b[*it];
for(j=1;j<=0xff;++j)b[j]+=b[j-1];
for(it=end;it!=bgn;)buf[--b[*(it-=Sz)]]=*--lst;
lst=buf+Len;swap(fst,buf);
}
}
void dfs(R x,R y){
if(a[he[y]].l+m<=a[x].r)
y=he[y],--d[x];//决策点偏移
for(R&i=he[x];i;i=ne[i])
d[i]=d[x]+1,dfs(i,y);
}
int main(){
R n=in(),i,p;m=in();
for(i=1;i<=n;++i){
a[i].l=in();a[i].r=in();a[i].id=i;
if(a[i].l>a[i].r)a[i].r+=m;//环状数据处理成链意义下的
}
Radixsort(a+1,a+n+1,b+1,new int[12]{0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1});
memcpy(a+n+1,a+1,12*n);
for(i=n+1;i<=2*n;++i)//倍长处理
at[a[i-n].id]=i,a[i].l+=m,a[i].r+=m;
for(p=1,i=2;i<=2*n;++i){//建树，贪心思想
while(a[p].r<a[i].l)++p;
ne[i]=he[p];he[p]=i;
}
for(i=1;i<=n;++i)
if(!d[i])d[i]=1,dfs(i,i);
for(i=1;i<=n;++i)
printf("%d ",d[at[i]]);
puts("");
return 0;
}
```