给定一个仙人掌, 每个点有一家拉面店, 售卖油腻程度为 \(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] 地图 - 仙人掌, 莫队, 分块
来源: http://www.bubuko.com/infodetail-3445812.html