题解 P5311 【[Ynoi2012]D1T3】

cosmicAC

2019-05-16 08:04:01

Solution

觉得其他大佬的题解写的太过简略了,我理解了好久。所以我会写的尽量详细一些。 这道题首先一个巧妙的地方是建点分树。可以证明,树上的任意一个联通块中,存在一个在点分树上深度最小的节点,并且整个联通块都在这个节点的子树中。 为什么这个一定成立呢?我想了好久发现这个可以反证法。假设点分树上最浅的节点叫做$p$,联通块中有一个点$q$不在$p$的子树内。由于点分树上$p$的子树也是原树中的一个联通块,并且**所有$p$子树之外的点到达$p$都必须经过一个比$p$更浅的节点**,所以$q$到$p$的路径上最浅的点一定比$p$浅,而同时这个点一定也在联通块内,这违反了“$p$是最浅的节点”。 所以我们可以把每一个询问$l,r,x$,归在和$x$在同一个联通块中的点分树上最浅的节点。然后就只需要对点分树上每个点遍历一遍子树,分开来处理。 下面假设当前扫描到的点叫做$p$,$q$是$p$点分树上子树中的任意一个节点。容易发现选中$q$的条件是$p$到$q$路径上的所有点都在$[l,r]$之中。所以把一个$q$写成二维平面中的一个点$(mn,mx)$,其中的$mn,mx$就是$p$到$q$路径中的最小值和最大值。于是一个询问就变成了一个二维数颜色,查询所有$mn\ge l,mx\le r$点的颜色数。这东西乍一看不太可做,我一开始的想法是把所有的点排列成$mn,mx$都单调递增的序列,其他点都没有意义,然后就可以记录一个$pre$,化成三维数点。可惜这样算上点分治一共是三个log,肯定是过不去的。 然后我仔细研究了其他题解的代码,终于领悟了正确的做法。我们可以把所有点和询问按照第一维从大到小排序。然后只需要一边扫描线,一边记录**每种颜色$mx$最小的一次出现**。这样可以巧妙的保证每种颜色只被算到了最多一次,并且原来算得到的颜色现在还是算得到。然后就树状数组维护即可。 时间复杂度$O(n\log^2{n})$,空间复杂度$O(n)$或$O(n\log n)$。 代码如下: ```cpp // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; int n,m,cl[1<<17],rt,mn,S,siz[1<<17],vis[1<<17],mv[1<<17],ans[1<<17],c[1<<17]; basic_string<int> v[1<<17]; struct ev{int x,y,z,tp;};basic_string<ev>q[1<<17],fa[1<<17]; void getrt(int p,int f=0){ siz[p]=1;int mx=0; for(int i:v[p])if(!vis[i] && i!=f) getrt(i,p),siz[p]+=siz[i],mx=max(mx,siz[i]); if((mx=max(mx,S-siz[p]))<mn)mn=mx,rt=p; } void dfs(int p,int f=0,int mn=1e9,int mx=-1e9){ mn=min(mn,p),mx=max(mx,p);fa[p]+={mn,mx,rt}; siz[p]=1;q[rt]+={mn,mx,cl[p],0}; for(int i:v[p])if(i!=f && !vis[i])dfs(i,p,mn,mx),siz[p]+=siz[i]; } void work(int p){ vis[p]=1;dfs(p); for(int i:v[p])if(!vis[i]) S=siz[i],mn=1e9,getrt(i),work(rt); } void ins(int p,int v){for(;p<=n;p+=p&-p)c[p]+=v;} int qry(int p){int r=0;for(;p;p&=p-1)r+=c[p];return r;} int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",cl+i); for(int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); v[x]+=y,v[y]+=x; } S=n,mn=1e9;getrt(1);work(rt); for(int i=1;i<=m;i++){ int x,y,z;scanf("%d%d%d",&x,&y,&z); for(ev&j:fa[z])if(j.x>=x && j.y<=y) {q[j.z]+={x,y,i,1};break;} } memset(mv,0x3f,sizeof mv); for(int i=1;i<=n;i++){ sort(q[i].begin(),q[i].end(),[](ev x,ev y){ return x.x>y.x || x.x==y.x&&x.tp<y.tp; }); for(ev&E:q[i])if(E.tp)ans[E.z]=qry(E.y);else if(E.y<mv[E.z]){if(mv[E.z]<1e9)ins(mv[E.z],-1);ins(mv[E.z]=E.y,1);} for(ev&E:q[i])if(!E.tp){ mv[E.z]=1e9;for(int p=E.y;p<=n;p+=p&-p)c[p]=0; } } for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; } ```