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

· · 题解

思路（对我来说）好毒瘤的一道题啊…… %%%lxl %%%比赛时AC的大佬

（以下是我对于正解的理解） 大概来说，是有两次的问题转化的过程：

第一步

建出点分树，这样对于询问(l,r,x)中x所在的一个连通块，必定完全包含在[l,r]区间内某一个节点（在点分树上）的子树里面，在点分树上暴力跳父亲即可找到这个节点，然后把这个询问"送"给这个节点，接下来我们一个节点一个节点地处理这些询问。

这样转化之后，问题就变成了：在一棵树中，从根节点出发，只经过[l,r]范围内的点，可以到达的颜色数。

第二步

我们记录一下每一个节点到（点分树上的）每个祖先的路径上的编号最大的点和编号最小的点，分别设成L和R

我们发现，只有对于x节点拥有的一个询问(l,r)，只有L>=l且R<=r的节点才能对答案有贡献

于是，这就是一个二维偏序问题了……将询问离线一波，第一维排序第二维树状数组维护即可解决。

丑陋的不行的代码：

#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毒瘤;
}