P5311 [Ynoi2011] 成都七中

题目描述

给你一棵 $n$ 个节点的树，每个节点有一种颜色，有 $m$ 次查询操作。

查询操作给定参数 $lrx$，需输出：

将树中编号在 $[l,r]$ 内的所有节点保留，$x$ 所在连通块中颜色种类数。

每次查询操作独立。

对于 $100\%$ 的数据，所有出现过的数在 $[1,10^5]$ 之间，保证每次输入的 $l\le x\le r$。

题解

建出点分树，可以发现这样一个性质，对于树上任意一个连通块，一定有一个连通块上的点，在点分树该点的子树中包含连通块的所有点
那么对于每个询问中的$x$，我们找到它在点分树上一个深度最低的祖先$v$，满足$v$与$x$可以通过$[l,r]$之间的点连通，那么问题就变成了求$v$所在连通块中颜色种类数，连通块只会在$v$的点分树子树内，这就变得很好做，一个点和$v$是否连通可以求出它到$v$的编号最小值$\min$和最大值$\max$，它与$v$连通当且仅当$l\le \min ,\max \le r$，二维数点即可

$\text{code}$

#include<cstdio>
#include<algorithm>
using namespace std;
void read(int &res)
{res=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=2e5+100;
int n,q,a[N+10],st[N+10],tot;
struct edge
{int to,last;
}e[N<<1|1];
void add(int a,int b)
{e[++tot].to=b;e[tot].last=st[a];st[a]=tot;
}
struct node
{int l,r,id;
};
vector<node> p[N+10];
int rt,siz[N+10],sum,ans[N+10];
bool vis[N+10];
void getrt(int u,int fa)
{siz[u]=1;int maxn=0;for(int i=st[u],v;i!=0;i=e[i].last){v=e[i].to;if(v==fa||vis[v]) continue;getrt(v,u),siz[u]+=siz[v],maxn=max(maxn,siz[v]);}maxn=max(maxn,sum-siz[u]);if((maxn<<1)<=sum) rt=u;
}
int cnt;
struct qst
{int id,l,r,co;
}g[N+10];
bool cmp(qst a,qst b){return a.l>b.l||(a.l==b.l&&a.r<b.r||a.l==b.l&&a.r==b.r&&a.id<b.id);}
int pre[N+10];
void dfs(int u,int minn,int maxn,int fa)
{minn=min(minn,u),maxn=max(maxn,u);g[++cnt]=(qst){0,minn,maxn,a[u]};for(auto v:p[u])if(v.l<=minn&&maxn<=v.r&&!ans[v.id])g[++cnt]=(qst){v.id,v.l,v.r,0};for(int i=st[u],v;i!=0;i=e[i].last){v=e[i].to;if(v==fa||vis[v]) continue;dfs(v,minn,maxn,u);}
}
struct Tree
{int t[N+10];int lowbit(int x){return x&-x;}void update(int x,int k){for(;x<=N;x+=lowbit(x))t[x]+=k;}int query(int x){int res=0;for(;x;x-=lowbit(x)) res+=t[x];return res;}
}t;
void solve(int u)
{getrt(u,0),sum=siz[u],getrt(u,0),u=rt;cnt=0;dfs(u,N,0,0);sort(g+1,g+1+cnt,cmp);for(int i=1;i<=cnt;i++){if(g[i].id==0){if(!pre[g[i].co]) t.update(g[i].r,1),pre[g[i].co]=g[i].r;else{if(g[i].r<pre[g[i].co])t.update(pre[g[i].co],-1),t.update(g[i].r,1),pre[g[i].co]=g[i].r;}}else ans[g[i].id]=t.query(g[i].r);}for(int i=1;i<=cnt;i++)if(g[i].id==0&&pre[g[i].co])t.update(pre[g[i].co],-1),pre[g[i].co]=0;vis[u]=true;for(int i=st[u],v;i!=0;i=e[i].last){v=e[i].to;if(vis[v]) continue;solve(v);}
}
int main()
{
//	freopen("a.in","r",stdin);read(n),read(q);for(int i=1;i<=n;i++) read(a[i]);for(int i=1,a,b;i<n;i++) read(a),read(b),add(a,b),add(b,a);for(int i=1,l,r,x;i<=q;i++) read(l),read(r),read(x),p[x].push_back({l,r,i});solve(1);for(int i=1;i<=q;i++) printf("%d\n",ans[i]);return 0;
}