傳送門

題意：

一棵樹，詢問一個子樹內(nèi)出現(xiàn)次數(shù)$\ge k$的顏色有幾種，Candy?這個沙茶自帶強制在線

---

?

吐槽：

本來一道可以離散的莫隊我非要強制在線用分塊做；上午就開始寫了然后發(fā)現(xiàn)思路錯了...；改 下午繼續(xù)寫....然后發(fā)現(xiàn)看大了數(shù)據(jù)范圍卡空間了...；改 然后又發(fā)現(xiàn)好多bug...；再改 然后發(fā)現(xiàn)TLE了... ；改塊的大小....可惡又卡空間了.... ；改short...可惡溢出了；改unsigned short....可惡n總共才1e5怎么練unsigned short也溢出了.....; 開O2...還不行....;然后發(fā)現(xiàn)之前把塊的大小和數(shù)量搞反了....;繼續(xù)改塊的大小再加上有理有據(jù)對本題特性的vector優(yōu)化.....終于A了.................

?

題解：

一開始想成已經(jīng)知道k預(yù)處理f不用第三維了(md那還用分塊干什么)

對出現(xiàn)次數(shù)$>S$和$\le S$的分開討論

預(yù)處理$f[i][j][k]$為塊i到塊j出現(xiàn)次數(shù)$[k,S]$的有幾種

$s[i][j]$為前i塊顏色j出現(xiàn)了幾次

詢問的時候

兩邊不完整的塊暴力枚舉

$>S$的部分不超過$\frac{N}{S}$種，單獨暴力枚舉(注意如果兩邊枚舉過了就不能重復(fù)枚舉了)

$[k,S]$的部分直接用預(yù)處理的f

?

?

#pragma GCC optimize ("O2") #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int N=1e5+5, M=245, S=425; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }int n,Q,col,a[N],u,v,k; int cou[N], big[N], tot, mark[N];bool biiig[N]; struct edge{int v,ne;}e[N<<1]; int cnt,h[N]; inline void ins(int u,int v){e[++cnt]=(edge){v,h[u]}; h[u]=cnt;e[++cnt]=(edge){u,h[v]}; h[v]=cnt; } int dfc,L[N],R[N]; int t[N]; void dfs(int u,int fa){L[u]=++dfc; a[dfc]=t[u];for(int i=h[u];i;i=e[i].ne)if(e[i].v!=fa) dfs(e[i].v, u);R[u]=dfc; }int block,m,pos[N]; struct _blo{int l,r;}b[M]; void ini(){//block=sqrt(n); block=420;m=(n-1)/block+1;for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;for(int i=1;i<=m;i++) b[i].l=(i-1)*block+1, b[i].r=i*block;b[m].r=n; }struct Block{int f[M][M][S], c[N], s[M][N];void Set0(int x){for(int i=1;i<=col;i++) s[x][i]=s[x-1][i];for(int i=b[x].l; i<=b[x].r; i++) s[x][a[i]]++;}void Set1(int x){for(int t=x;t<=m;t++){for(int i=b[t].l; i<=b[t].r; i++) if(!biiig[ a[i] ]) c[a[i]]++;for(int i=b[t].l; i<=b[t].r; i++) if(!biiig[ a[i] ] && c[a[i]]>0){ int _=s[t-1][a[i]] - s[x-1][a[i]];f[x][t][ _+c[a[i]] ]++;f[x][t][ _ ]--;c[a[i]]=0;}for(int i=block; i>=1; i--) f[x][t][i]+=f[x][t][i+1];for(int i=1; i<=block; i++) f[x][t][i]+=f[x][t-1][i];}}int Que(int l,int r,int k){ int pl=pos[l], pr=pos[r];int ans=0;if(pl==pr){for(int i=l; i<=r; i++) c[a[i]]++;for(int i=l; i<=r; i++) if(c[a[i]]>0) ans+= c[a[i]]>=k, c[a[i]]=0;}else{for(int i=1; i<=tot; i++) mark[ big[i] ]=0;vector<int> v;int *rr=s[pr], *ll=s[pl-1];for(int i=l; i<=b[pl].r; i++){ mark[ a[i] ]=1;if(rr[a[i]] - ll[a[i]]>=k)c[a[i]]++, v.push_back(a[i]); }for(int i=b[pr].l; i<=r; i++){mark[ a[i] ]=1;if(rr[a[i]] - ll[a[i]]>=k)c[a[i]]++, v.push_back(a[i]); }for(int i=0; i<(int)v.size(); i++) if(c[v[i]]>0){int _=s[pr-1][v[i]] - s[pl][v[i]];if(biiig[ v[i] ]) ans+= _+c[v[i]]>=k;else ans+= (_<k && _+c[v[i]]>=k);c[v[i]]=0;}if(k<=block) ans+=f[pl+1][pr-1][k]; for(int i=1;i<=tot;i++) if(!mark[ big[i] ])ans+= s[pr-1][big[i]] - s[pl][big[i]] >= k;}return ans;} }B;int main(){ // freopen("in","r",stdin);n=read(); Q=read(); ini();for(int i=1;i<=n;i++) a[i]=t[i]=read(), col=max(col, a[i]), cou[a[i]]++;for(int i=1;i<n;i++) ins(read(), read());dfs(1,0);for(int i=1;i<=col;i++) if(cou[i]>block) big[++tot]=i, biiig[i]=1;for(int i=1;i<=m;i++) B.Set0(i);for(int i=1;i<=m;i++) B.Set1(i);while(Q--){u=read(); k=read();printf("%d\n", B.Que(L[u], R[u], k) );} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/candy99/p/6567213.html

總結(jié)

以上是生活随笔為你收集整理的CF 375D. Tree and Queries加强版!!!【dfs序分块 大小分类讨论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。