P3180 [HAOI2016]地图

显然，这是一个仙人掌图

inline void tarjan(LL u,LL fa){

    low[u]=dfn[u]=++tot,

    pre[tot]=u;

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!dfn[v])

            tarjan(v,u),

            low[u]=min(low[u],low[v]);

        else

            low[u]=min(low[u],dfn[v]);

    }

}

void Dfs(LL u){

    xu[u]=++tot,

    size[u]=1,

    b[tot]=a[u];//拍扁莫队

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!xu[v]&&low[v]>=dfn[u])

            Dfs(v),

            size[u]+=size[v];

    }

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!xu[v]&&low[v]<dfn[u])

            Dfs(v),

            size[pre[low[v]]]+=size[v];//返回割点那里

    }

}

只有割点能造成贡献，要统计的就是割点的子树，dfs序拍扁莫队离线处理，分块优化

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stack>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL maxn=2000000;

inline LL Read(){

    LL x=0,f=1; char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-') f=-1; c=getchar();

    }

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*f;

}

struct node{

    LL to,next;

}dis[maxn];

LL num,tot,n,m,m_val,Size,pieces,sum,l=1,r=0;

LL a[maxn],head[maxn],b[maxn],visit[maxn],fk[maxn][2];

LL low[maxn],dfn[maxn],size[maxn],pre[maxn],xu[maxn];

LL belong[maxn],bl[maxn],br[maxn],ans[maxn];

inline void Add(LL u,LL v){

    dis[++num]=(node){v,head[u]},head[u]=num;

}

inline void tarjan(LL u,LL fa){

    low[u]=dfn[u]=++tot,

    pre[tot]=u;

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!dfn[v])

            tarjan(v,u),

            low[u]=min(low[u],low[v]);

        else

            low[u]=min(low[u],dfn[v]);

    }

}

void Dfs(LL u){

    xu[u]=++tot,

    size[u]=1,

    b[tot]=a[u];//拍扁莫队

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!xu[v]&&low[v]>=dfn[u])

            Dfs(v),

            size[u]+=size[v];

    }

    for(LL i=head[u];i;i=dis[i].next){

        LL v=dis[i].to;

        if(!xu[v]&&low[v]<dfn[u])

            Dfs(v),

            size[pre[low[v]]]+=size[v];//返回割点那里

    }

}

struct code{

    LL l,r,op,val,id;

}q[maxn];

inline bool cmp(code x,code y){

    return (belong[x.l]^belong[y.l])?

            belong[x.l]<belong[y.l]:

            	(belong[x.l]&1)?x.r<y.r:x.r>y.r;

}

inline void Inc(LL c){

    LL now=belong[c];

    if(visit[c]&1)//奇数

        --fk[now][1],

        ++fk[now][0];

    else if(visit[c])//偶数出现过

        ++fk[now][1],

        --fk[now][0];

    else

        ++fk[now][1];

    ++visit[c];

}

inline void Del(LL c){

    LL now=belong[c];

    if(!(visit[c]&1))//偶数

        ++fk[now][1],

        --fk[now][0];

    else if(visit[c]^1)//

        --fk[now][1],

        ++fk[now][0];

    else

        --fk[now][1];

    --visit[c];

}

int main(){

    n=Read(),m=Read();

    for(LL i=1;i<=n;++i)

        a[i]=Read();

    for(LL i=1;i<=m;++i){

        LL u,v;

        Add(u=Read(),v=Read()),Add(v,u);

    }

    tot=0, tarjan(1,0),

    tot=0, Dfs(1),

    m=Read();

    for(LL i=1;i<=m;++i){

    	LL ty=Read(),x=Read(),val=Read();

    	q[i]=(code){dfn[x],dfn[x]+size[x]-1,ty,val,i};

    	m_val=max(m_val,val);

    }

    Size=sqrt(n),

    pieces=ceil((double)n/Size);//莫队分块

    for(LL i=1;i<=pieces;++i)

        for(LL j=(i-1)*pieces+1;j<=i*pieces;++j)

            belong[j]=i;

    sort(q+1,q+1+m,cmp),

    Size=sqrt(m_val),//清空实行真正的分块

    pieces=ceil((double)m_val/Size);

    for(LL i=1;i<=pieces;++i){

        bl[i]=(i-1)*pieces+1,br[i]=i*pieces;

        for(LL j=bl[i];j<=br[i];++j)

            belong[j]=i;//每种拉面属于的块

    }

    for(LL i=1;i<=m;++i){

        LL ql=q[i].l,qr=q[i].r,now=q[i].val;

        while(l<ql)

            Del(b[l++]);

        while(l>ql)

            Inc(b[--l]);

        while(r<qr)

            Inc(b[++r]);

        while(r>qr)

            Del(b[r--]);

        sum=0;

        LL pos=belong[now];//拉面所在块

        for(LL j=1;j<pos;++j)

            sum+=fk[j][q[i].op];

        for(LL j=bl[pos];j<=q[i].val;++j)

            if(visit[j])

                sum+=(visit[j]&1)==q[i].op;

        ans[q[i].id]=sum;

    }

    for(LL i=1;i<=m;++i)

        printf("%lld\n",ans[i]);

    return 0;

}/*

*/

巴特西

P3180 [HAOI2016]地图

最新文章

热门文章