[HAOI2016] 地图 - 仙人掌,莫队,分块

给定一个仙人掌，每个点有一家拉面店，售卖油腻程度为 \(a_i\) 的拉面，油腻程度相同的拉面称作同一种拉面。有 \(q\) 个询问，每次问从点 \(x\) 开始，不经过所有从 \(x\) 到 \(1\) 号点简单路径上的边，能够访问到的所有点中，油腻程度 \(\leq y\) 且品尝次数为奇数或偶数的拉面有多少种。

Solution

建圆方树，则问题转化为查询某点为根的子树内，出现次数为奇数或偶数，且颜色编号不大于给定值的颜色总数

在圆方树上对所有圆点跑出 DFS 序，则子树统计转化为区间统计

考虑莫队套值域分块，用 \(cnt[i]\) 记录离散化后值为 \(i\) 的颜色的出现次数，同时维护 \(sum[i][0/1]\) 表示编号为 \(i\) 的块中出现次数为偶数或奇数的颜色的种类数，注意把 \(0\) 特判掉

#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
map<int,int> mp;
int n,m,q,lim,val[N],ind,limv;
int getbel(int x) {
    return x/lim + 1;
}
int getbelv(int x) {
    return x/limv + 1;
}

struct query {
    int l,r,ty,y,id;
    bool operator < (const query &b) {
        if(getbel(l)==getbel(b.l)) return r<b.r;
        else return getbel(l)<getbel(b.l);
    }
};

namespace solver {
    int a[N],cnt[N],sum[N][2],ans[N];
    query s[N];
    void add(int x) {
        if(cnt[x]==0) sum[getbelv(x)][1]++;
        else if(cnt[x]&1) sum[getbelv(x)][1]--, sum[getbelv(x)][0]++;
        else sum[getbelv(x)][1]++, sum[getbelv(x)][0]--;
        cnt[x]++;
    }
    void dec(int x) {
        cnt[x]--;
        if(cnt[x]==0) sum[getbelv(x)][1]--;
        else if(cnt[x]&1) sum[getbelv(x)][1]++, sum[getbelv(x)][0]--;
        else sum[getbelv(x)][1]--, sum[getbelv(x)][0]++;
    }
    int getans(int x,int ty) {
        int ans=0;
        for(int i=1;i<getbelv(x);i++) ans+=sum[i][ty];
        for(int i=getbelv(x)*limv-limv;i<=x;i++) if(cnt[i]%2==ty&&cnt[i]) ans++;//!
        return ans;
    }
    void solve() {
        for(int i=1;i<=n;i++) mp[a[i]]++;
        for(auto i=mp.begin();i!=mp.end();i++) i->second=++ind, val[ind]=i->first;
        for(int i=1;i<=n;i++) a[i]=mp[a[i]];
        lim=sqrt(n);
        limv=sqrt(ind);
        sort(s+1,s+q+1);
        int l=1,r=0;
        for(int i=1;i<=q;i++) {
            while(r<s[i].r) add(a[++r]);
            while(l>s[i].l) add(a[--l]);
            while(r>s[i].r) dec(a[r--]);
            while(l<s[i].l) dec(a[l++]);
            auto it=mp.upper_bound(s[i].y);
            --it;
            ans[s[i].id]=getans(it->second,s[i].ty);
        }
        for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
    }
}

namespace cactus {
    int cnt;
    vector<int> G[N], g[N * 2];
    int dfn[N], low[N], dfc, s[N], t[N], ind, stk[N], tp, a[N];

    void Tarjan(int u) {
        low[u] = dfn[u] = ++dfc;
        stk[++tp] = u;
        for (auto v : G[u]) {
            if (!dfn[v]) {
                Tarjan(v);
                low[u] = min(low[u], low[v]);
                if (low[v] == dfn[u]) {
                    ++cnt;
                    for (int x = 0; x != v; --tp) {
                        x = stk[tp];
                        g[cnt].push_back(x);
                        g[x].push_back(cnt);
                    }
                    g[cnt].push_back(u);
                    g[u].push_back(cnt);
                }
            }
            else low[u] = min(low[u], dfn[v]);
        }
    }

    void dfs(int p) {
        if(p<=n) s[p]=++ind; else s[p]=-1;//!
        for(int q:g[p]) if(s[q]==0) dfs(q);
        if(p<=n) t[p]=ind;
    }

    void solve() {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++) {
            int t1,t2;
            cin>>t1>>t2;
            G[t1].push_back(t2);
            G[t2].push_back(t1);
        }
        cnt = n;
        for (int u = 1; u <= n; ++u)
            if (!dfn[u]) Tarjan(u), --tp;
        dfs(1);
        cin>>q;
        for(int i=1;i<=n;i++) solver::a[s[i]]=a[i];
        for(int i=1;i<=q;i++) {
            int ty,x,y;
            cin>>ty>>x>>y;
            solver::s[i]={s[x],t[x],ty,y,i};
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cactus::solve();
    solver::solve();
}

[HAOI2016] 地图 - 仙人掌,莫队,分块

原文：https://www.cnblogs.com/mollnn/p/12404084.html