首页 > 代码库 > CF 375D. Tree and Queries【莫队】

CF 375D. Tree and Queries【莫队】

题意:

一棵树,询问一个子树内出现次数k≥k的颜色有几种


 

强制在线见上一道

用莫队不知道比分块高到哪里去了,超好写不用调7倍速度!!!

可以用分块维护出现次数这个权值,实现$O(1)-O(\sqrt{N})$修改查询

#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();        if(k>n) puts("0");        else printf("%d\n", B.Que(L[u], R[u], k) );    }}

 

CF 375D. Tree and Queries【莫队】