P3180 [HAOI2016] 地图
对原仙人掌建出圆方树，从市中心到 \(x\) 的路全被堵死意味着圆方树上 \(x\) 到它父亲的边断开。
这说明每次询问中能到达的点是 \(x\) 的子树中的圆点，通过 dfs 序将子树转为区间查询。
可以将询问离线下来，使用莫队解决：
按出现次数的奇偶分别维护值域分块，块内维护一个块中出现次数的为奇/偶的数的个数。
移动指针时可以 \(\mathcal O(1)\) 维护，查询时需要 \(\mathcal O(\sqrt V)\) 扫一遍。
总时间复杂度 \(\mathcal O(n(\sqrt n+\sqrt V))\)。
#include<bits/stdc++.h>
#define N 200005
#define V 1000005
using namespace std;
constexpr int B=2000;
vector<int>stk,G[N],s[N];
int tot,dfn[N],low[N],siz[N];
int n,m,q,idx,a[N],v[N],ord[N],ans[N];
struct Query{int op,x,l,r,id;}b[N];
void tarjan(int x){dfn[x]=low[x]=++tot;stk.emplace_back(x);for(auto p:G[x]) if(!dfn[p]){tarjan(p),low[x]=min(low[x],low[p]);if(low[p]>=dfn[x]){a[++idx]=1e6+1;s[x].emplace_back(idx);s[idx].emplace_back(x);for(int v=0;v^p;)v=stk.back(),stk.pop_back(),s[v].emplace_back(idx),s[idx].emplace_back(v);}}else low[x]=min(low[x],dfn[p]);
}
int dfs(int x,int fa){dfn[x]=++idx,ord[idx]=x;for(auto p:s[x])if(p^fa) siz[x]+=dfs(p,x);return ++siz[x];
}
class Blocks{private:int c[V],sum[V/B+5][2];public:void add(int x){sum[x/B][c[x]&1]-=!!c[x];sum[x/B][++c[x]&1]++;}void del(int x){sum[x/B][c[x]--&1]--;sum[x/B][c[x]&1]+=!!c[x];}int query(int x,bool op){int res=0,bx=x/B;for(int i=0;i<bx;i++) res+=sum[i][op];for(int i=bx*B;i<=x;i++) res+=c[i]&&c[i]&1^op^1;return res;}
}T;
int main(){scanf("%d%d",&n,&m),idx=n;for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),G[u].emplace_back(v),G[v].emplace_back(u);tarjan(1),idx=0;dfs(1,0),scanf("%d",&q);for(int i=1,x;i<=q;i++)scanf("%d%d%d",&b[i].op,&x,&b[i].x),b[i].id=i,b[i].l=dfn[x],b[i].r=dfn[x]+siz[x]-1;sort(b+1,b+q+1,[&](Query x,Query y){if(x.l/B^y.l/B) return x.l/B<y.l/B;return x.l/B&1?x.r>y.r:x.r<y.r;});for(int i=1;i<=idx;i++) v[i]=a[ord[i]];for(int i=1,l=1,r=0;i<=q;i++){auto t=b[i];for(;l>t.l;T.add(v[--l]));for(;r<t.r;T.add(v[++r]));for(;l<t.l;T.del(v[l++]));for(;r>t.r;T.del(v[r--]));ans[t.id]=T.query(t.x,t.op);}for(int i=1;i<=q;i++) printf("%d\n",ans[i]);return 0;
}