题解 P5267 【美好的每一天~不连续的存在~】

思路（对我来说）好毒瘤的一道题啊…… %%%lxl %%%比赛时AC的大佬 （以下是我对于正解的理解） 大概来说，是有两次的问题转化的过程： **第一步** 建出点分树，这样对于询问(l,r,x)中x所在的一个连通块，必定完全包含在[l,r]区间内某一个节点（在点分树上）的子树里面，在点分树上暴力跳父亲即可找到这个节点，然后把这个询问"送"给这个节点，接下来我们一个节点一个节点地处理这些询问。 这样转化之后，问题就变成了：在一棵树中，从根节点出发，只经过[l,r]范围内的点，可以到达的颜色数。 **第二步** 我们记录一下每一个节点到（点分树上的）每个祖先的路径上的编号最大的点和编号最小的点，分别设成L和R 我们发现，只有对于x节点拥有的一个询问(l,r)，只有L>=l且R<=r的节点才能对答案有贡献 于是，这就是一个二维偏序问题了……将询问离线一波，第一维排序第二维树状数组维护即可解决。 丑陋的不行的代码： ```cpp #include<cstdio> #include<vector> #include<algorithm> using namespace std; int n,m,xi,yi,zi; int col[100010],ans[100010],cx[100010]; int nxt[200010],to[200010],head[100010],gs; int size[100010],used[100010],d[100010]; int rt,srt,tot; struct node{ int l,r,id;node(int a=0,int b=0,int c=0){l=a;r=b;id=c;} bool operator <(const node d)const{return l==d.l?id>d.id:l>d.l;} }; vector<node> v[100010],q[100010]; inline void lb(int x,int y){ nxt[++gs]=head[x];head[x]=gs;to[gs]=y; } void frt(int x,int fa){ int mn=size[x]=1;for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa && !used[to[i]])frt(to[i],x),size[x]+=size[to[i]],mn=max(mn,size[to[i]]); mn=max(mn,tot-size[x]);if(mn<srt)srt=mn,rt=x; } void dfs(int x,int fa,int mx,int mn){ size[x]=1;v[x].push_back(node(mn,mx,rt)),q[rt].push_back(node(mn,mx,col[x]));for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa && !used[to[i]])dfs(to[i],x,max(mx,to[i]),min(to[i],mn)),size[x]+=size[to[i]]; } void vp(int x){ tot=size[x];srt=0x3f3f3f3f;frt(x,-1);used[rt]=1;dfs(x=rt,-1,rt,rt); for(int i=head[x];i;i=nxt[i])if(!used[to[i]])vp(to[i]); } //以上为蒟蒻的点分树 void update(int x,int v){for(;x<=n;x+=x&-x)d[x]+=v;} int query(int x,int ans=0){for(;x;x-=x&-x)ans+=d[x];return ans;} //以上为蒟蒻的树状数组 int main(){ scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&col[i]); for(int i=1;i<n;i++)scanf("%d %d",&xi,&yi),lb(xi,yi),lb(yi,xi); size[1]=n;vp(1);for(int i=1;i<=m;i++){ scanf("%d %d %d",&xi,&yi,&zi); for(vector<node>::iterator id=v[zi].begin();id!=v[zi].end();id++){ node j=*id;if(j.l>=xi && j.r<=yi){q[j.id].push_back(node(xi,yi,-i));break;} }//id为负表示是一个询问 }for(int i=1;i<=n;i++){ sort(q[i].begin(),q[i].end()); for(vector<node>::iterator id=q[i].begin();id!=q[i].end();id++){ node j=*id; if(j.id<0)ans[-j.id]=query(j.r); else{ if(cx[j.id]>j.r)update(cx[j.id],-1),cx[j.id]=0; if(!cx[j.id])update(j.r,1),cx[j.id]=j.r; } } for(vector<node>::iterator id=q[i].begin();id!=q[i].end();id++){ node j=*id; if(j.id>0 && cx[j.id]==j.r)update(j.r,-1),cx[j.id]=0; } }for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return lxl毒瘤; } ```