BZOJ 4564: [Haoi2016]地图

题目大意

原题链接

给一个仙人掌，每个结点有一个权值，查询每个仙人掌的子树（算本身）（子树结点满足：必须经过该点才能到达跟，即该点是子树的割点）有多少种小于y的权值个数为奇数（或偶数）。y是每次询问时候给。
可离线，1e5个点和询问

算法分析

如果在树上那就需要用DFS序，仙人掌也有DFS序，叫做仙人掌序列嘛。
实际上就是需要先预处理出一个结点在环上的相邻结点（有一个一定是DFS的父亲结点），最后走环上的那个结点并且不算当前结点的子树。

查询就变成了区间查询，用3809的那种莫队+分块。

注意

1、我这个SB每次块都忘了初始化，所以一定要测试极限数据啊。
2、注意考虑0结点，数据中y和w都有=0的情况。
3、为了在第二次DFS的时候用vis数组记录即可，当做图的便利，否则判断挺麻烦的。

/*
维护部分：
一个支持初始化，修改，奇偶查询的分块
一段莫队算法 
根据仙人掌序列得到需要被维护的序列
根据询问进行转换 

仙人掌部分：
第一次DFS得到fa和son
第二次DFS得到仙人掌序列 
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+105,maxm=15e4+105,maxs=1e6+105;
int tl[maxn],tr[maxn],a[maxn];
namespace Captain_Mo
{
    static const int Tim=500,n=1e6;
    int N,Q,ans[maxn],belong[maxs];
    struct data{
        int l,r,b,op,id;
        friend bool operator<(data a,data b)
        {
            return belong[a.l]!=belong[b.l]?belong[a.l]<belong[b.l]:a.r<b.r;
        }
    }q[maxn];
    struct block
    {
        int num,L[maxs/Tim+5],R[maxs/Tim+5],vis[maxs],ji[maxs/Tim+5],ou[maxs/Tim+5];
        void Build()
        {
            L[0]=R[0]=0;
            belong[0]=1;
            for(num=1;num*Tim<n;num++)
            {
                L[num]=R[num-1]+1,R[num]=L[num]+Tim-1;
                for(int i=L[num];i<=R[num];i++)belong[i]=num;
            }
            L[num]=R[num-1]+1,R[num]=n;
            for(int i=L[num];i<=R[num];i++)belong[i]=num;
        }
        void add(int v)
        {
            if(vis[v]==0)
                ji[belong[v]]++;
            else if(vis[v]&1)
                ji[belong[v]]--,ou[belong[v]]++;
            else
                ji[belong[v]]++,ou[belong[v]]--;
            vis[v]++;
        }
        void del(int v)
        {
            if(vis[v]==1)
                ji[belong[v]]--;
            else if(vis[v]&1)
                ji[belong[v]]--,ou[belong[v]]++;
            else
                ji[belong[v]]++,ou[belong[v]]--;
            vis[v]--;
        }
        int query_0(int l,int r)
        {
            int ret=0;
            if(belong[l]==belong[r])
            {
                for(int i=l;i<=r;i++)if(vis[i] && ~vis[i]&1)ret++;
                return ret;
            }
            for(int i=l;i<=R[belong[l]];i++)if(vis[i] && ~vis[i]&1)ret++;
            for(int i=belong[l]+1;R[i]<r;i++)ret+=ou[i];
            for(int i=L[belong[r]];i<=r;i++)if(vis[i] && ~vis[i]&1)ret++;
            return ret;
        }
        int query_1(int l,int r)
        {
            int ret=0;
            if(belong[l]==belong[r])
            {
                for(int i=l;i<=r;i++)if(vis[i]&1)ret++;
                return ret;
            }
            for(int i=l;i<=R[belong[l]];i++)if(vis[i]&1)ret++;
            for(int i=belong[l]+1;R[i]<r;i++)ret+=ji[i];
            for(int i=L[belong[r]];i<=r;i++)if(vis[i]&1)ret++;
            return ret;
        }
    }blo;
    void Init()
    {
        int x;
        scanf("%d",&Q);
        for(int i=1;i<=Q;i++)
        {
            scanf("%d%d%d",&q[i].op,&x,&q[i].b);
            q[i].id=i,q[i].l=tl[x],q[i].r=tr[x];
        }
        sort(q+1,q+Q+1);
    }
    void modui()
    {
        int L=1,R=0;
        for(int i=1;i<=Q;i++)
        {
            while(L>q[i].l)blo.add(a[--L]);
            while(R<q[i].r)blo.add(a[++R]);
            while(L<q[i].l)blo.del(a[L++]);
            while(R>q[i].r)blo.del(a[R--]);
            ans[q[i].id]=(!q[i].op)?blo.query_0(1,q[i].b):blo.query_1(1,q[i].b);
        }
    }
    void work()
    {
        blo.Build();
        Init();
        modui();
        for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
    }
}
namespace Cactus
{
    int np,first[maxn];
    struct edge{
        int to,next;
    }E[maxm<<1];
    void add(int u,int v)
    {
        E[++np]=(edge){v,first[u]};
        first[u]=np;
    }
    int n,m,cnt;
    int co[maxn];
    int dfs_clock,dfn[maxn],low[maxn],fa[maxn],son[maxn],vis[maxn];
    void Init()
    {
        int u,v;
        scanf("%d%d",&n,&m);
        Captain_Mo::N=n;
        for(int i=1;i<=n;i++)scanf("%d",&co[i]);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
    }
    void DFS(int i,int f)
    {
        fa[i]=f;
        dfn[i]=low[i]=++dfs_clock;
        for(int p=first[i];p;p=E[p].next)
        {
            int j=E[p].to;
            if(j==f)continue;
            if(dfn[j])
            {
                if(dfn[j]<dfn[i])low[i]=min(low[i],dfn[j]);
                continue;
            }
            DFS(j,i);
            low[i]=min(low[i],low[j]);
            if(low[j]<dfn[i])son[i]=j;
        }
    }
    void DFS(int i)
    {
        vis[i]=1;
        tl[i]=++cnt;a[cnt]=co[i];
        for(int p=first[i];p;p=E[p].next)
        {
            int j=E[p].to;
            if(vis[j] || j==son[i])continue;
            DFS(j);
        }
        tr[i]=cnt;
        if(son[i])DFS(son[i]);
    }
    void work()
    {
        Init();
        DFS(1,0); 
        DFS(1);
    }
}
int main()
{
    Cactus::work();
    Captain_Mo::work();
    return 0;
}