[DS记录]P7126 [Ynoi2008] rdCcot
command_block
2021-06-28 12:12:19
**题意** : 给一棵 $n$ 个点的树和常数 $C$。
每次查询给出区间 $[l,r]$，查询有多少个 C-块，定义如下：
对任意两个节点 $a,b$，定义 $a,b$ 是 C-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，满足：
1. $v_1=a$
2. $v_t=b$
3. 对任意 $1\le i\le t-1$，$dis(v_i,v_{i+1})\le C$
4. 对任意 $1\le i\le t$，$l\le v_i\le r$
定义“C-块”为一个点集 $S$，满足：
1. 对任意 $a\in S$，$b$ 属于 $S$ 的补集，$a,b$ 不 C-连通
2. 对任意 $a,b\in S$，$a$ 和 $b$ C-连通
3. 对任意 $a\in S$，有 $l\le a \le r$
$n\leq 3\times 10^5,m\leq 6\times 10^5$ ，时限 $\texttt{2s}$。
------------
- ### **Part1**
不难发现 C-块 点集是不交的，且任意两个 C-块 的虚树也是不交的。
考虑在每个 C-块 的最浅点将其统计，若同样浅，则选择编号较小的。（注意不是虚树的最浅点）
我们按照这个规则定义点的大小关系。
先考虑静态问题。给出一个点集 $S$ 求 C-块个数。
每个点向距离 $C$ 以内的最小点连边（如果这个最小点比自己小的话）。可以发现，没有出边的点就是一个 C-块 的最小点。
- **正确性说明** ： 相当于要证 ： 从点 $u$ 不断跳向距离 $C$ 以内的最小点，最终可以来到所在 C-块 的最小点。
只有距离 $C$ 以内没有更小的点才不能跳，因此上面的结论是显然的。
- ### **Part2**
接下来考虑区间询问。
我们只需要快捷地判定某个点是否存在出边。
记距点 $i$ 在 $C$ 以内的，小于点 $i$ 的，编号离 $i$ 最接近的两个点分别为 $l_i,r_i$ ，一左一右。
对于点 $i\in [l,r]$ ，若 $l_i<l$ 且 $r<r_i$ ，则 $i$ 没有出边，是某个 C-块 中的最小点。
考虑求出 $l_i,r_i$ 之后如何回答询问。
使用扫描线，增大右端点并维护每个左端点的答案。
对子 $(l_i,r_i)$ 当 $r$ 增大到 $i$ 时，开始将左端点 $(l_i,i]$ 的答案均 $+1$。当 $r$ 增大到 $r_i$ 时，取消贡献。
树状数组即可。
- ### **Part3**
考虑如何求出 $l_i,r_i$。
使用点分治。对于点 $u$ ，记到分治中心的距离为 $dis_u$ 。
每个点 $v$ 会询问来自其他分支的（这个不用管，一定更劣）， 比 $v$ 小的，满足 $dis_u+dis_v\leq C$ 的，编号最接近的 $u$。
考虑静态问题。将点按照大小排序，逐个插入以点编号为下标的线段树，线段树内维护 $dis$ 的最小值。
查询时，只能走存在 $dis_u\leq C-dis_v$ 的分支，在此基础上，尽量“向左”或“向右”走即可。
这容易用线段树维护。总复杂度 $O(n\log^2n+m\log n)$。
有点卡常，去堆栈 + 快读+ 剪枝才勉强卡过。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 300500
using namespace std;
namespace io {
char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<22)-10,stdin),p1==p2)?EOF:*p1++)
int rd() {
int x=0;char ch=getchar();
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
void putc(char ch){*O++=ch;}
void print(int x){if(x>9)print(x/10);*O++=x%10+'0';}
void flush(){fwrite(obuf,O-obuf,1,stdout);}
}
const int INF=1000000000;
struct Point{int l,r,p;}p[MaxN],p2[MaxN],b[MaxN<<1];
bool cmpP(const Point &A,const Point &B){return A.r<B.r;}
vector<int> g[MaxN];
int dep[MaxN];
bool cmpU(int A,int B)
{return dep[A]==dep[B] ? A<B : dep[A]<dep[B];}
void pfs2(int u)
{
for (int i=0,v;i<g[u].size();i++)
if (!dep[v=g[u][i]]){
dep[v]=dep[u]+1;
pfs2(v);
}
}
int e[MaxN],ef,siz[MaxN],mp[MaxN],st[MaxN],tn;
void pfs(int u)
{
e[st[++tn]=u]=ef;
siz[u]=1;mp[u]=0;
for (int i=0,v;i<g[u].size();i++)
if (e[v=g[u][i]]<ef){
pfs(v);
siz[u]+=siz[v];
mp[u]=max(mp[u],siz[v]);
}
}
int grt(int u)
{
int rt=tn=0;ef++;pfs(u);
for (int i=1;i<=tn;i++){
int u=st[i];
mp[u]=max(mp[u],tn-siz[u]);
if (mp[u]<mp[rt])rt=u;
}return rt;
}
int dis[MaxN];
void dfs(int u)
{
e[u]=ef;
for (int i=0,v;i<g[u].size();i++)
if (e[v=g[u][i]]<ef){
dis[v]=dis[u]+1;
dfs(v);
}
}
int n,a[MaxN<<2],tp[MaxN],lim;
void build(int l,int r,int u)
{
if (l==r){tp[l]=u;lim=max(lim,u);return ;}
int mid=(l+r)>>1;
build(l,mid,u<<1);build(mid+1,r,u<<1|1);
}
void add(int p,int c)
{for (int u=tp[p];u;u>>=1)a[u]=min(a[u],c);}
void clr(int u)
{
if (a[u]==INF)return ;
a[u]=INF;
if ((u<<1)>lim)return ;
clr(u<<1);clr(u<<1|1);
}
int wfl,wfr,wfc,buf;
int qry1(int l,int r,int u)
{
if (r<=buf)return buf;
if (l==r)return a[u]<=wfc&&l<=wfr ? l : 0;
int mid=(l+r)>>1;
if (wfr>mid&&a[u<<1|1]<=wfc){
int sav=qry1(mid+1,r,u<<1|1);
if (sav)return sav;
}return qry1(l,mid,u<<1);
}
int qry2(int l,int r,int u)
{
if (buf<=l)return buf;
if (l==r)return a[u]<=wfc&&wfl<=l ? l : n+1;
int mid=(l+r)>>1;
if (wfl<=mid&&a[u<<1]<=wfc){
int sav=qry2(l,mid,u<<1);
if (sav!=n+1)return sav;
}return qry2(mid+1,r,u<<1|1);
}
int C;
void solve(int u)
{
if (tn==1)return ;
ef++;dis[u]=0;dfs(u);e[u]=INF;
sort(st+1,st+tn+1,cmpU);
for (int i=1;i<=tn;i++){
int u=st[i];
if (dis[u]>C)continue;
add(u,dis[u]);
wfc=C-dis[u];
wfr=u-1;buf=p[u].l;p[u].l=max(p[u].l,qry1(1,n,1));
wfl=u+1;buf=p[u].r;p[u].r=min(p[u].r,qry2(1,n,1));
}clr(1);
for (int i=0,v;i<g[u].size();i++)
if (e[v=g[u][i]]!=INF)solve(grt(v));
}
#define lbit(p) (p&-p)
struct SumDS
{
int t[MaxN];
void add(int p,int c)
{while(p<=n+2){t[p]+=c;p+=lbit(p);}}
int qry(int p){
int ret=0;
while(p){ret+=t[p];p^=lbit(p);}
return ret;
}
}T;
int m,ans[MaxN<<1];
int main()
{
n=io::rd();m=io::rd();C=io::rd();
for (int i=2,fa;i<=n;i++){
fa=io::rd();
g[fa].pb(i);g[i].pb(fa);
}
dep[1]=1;pfs2(1);
for (int i=1;i<=n;i++){p[i].r=n+1;p[i].p=i;}
build(1,n,1);clr(1);
mp[0]=n;solve(grt(1));
for (int i=1;i<=m;i++)
{b[i].l=io::rd();b[i].r=io::rd();b[i].p=i;}
for (int i=1;i<=n;i++)p2[i]=p[i];
sort(p+1,p+n+1,cmpP);
sort(b+1,b+m+1,cmpP);
for (int i=1,j=1,k=1;i<=m;i++){
while(k<=b[i].r){
T.add(p2[k].l+1,1);
T.add(k+1,-1);
k++;
}
while(j<=n&&p[j].r<=b[i].r){
T.add(p[j].l+1,-1);
T.add(p[j].p+1,1);
j++;
}
ans[b[i].p]=T.qry(b[i].l);
}
for (int i=1;i<=m;i++)
{io::print(ans[i]);io::putc('\n');}
io::flush();
return 0;
}
```