题意：

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

 

---

 

强制在线见上一道

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

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

[update 2017-03-22]还可以用dsu on tree做，并不想再写了...

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N=1e5+5, M=320;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,a[N],u,k;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);    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 sum[M],a[N];    void add(int x,int v) {sum[pos[x]]+=v; a[x]+=v;}    int suf(int x){        if(x>n) return 0;        int p=pos[x], ans=0;        if(p==m) for(int i=x;i<=n;i++) ans+=a[i];        else{            for(int i=x; i<=b[p].r; i++) ans+=a[i];            for(int i=p+1; i<=m; i++) ans+=sum[i];        }        return ans;    }}B;struct meow{    int l,r,k,id;    bool operator <(const meow &x) const {
   return pos[l]
          
           q[i].r) del(a[r]), r--; while(l
           
            q[i].l) l--, add(a[l]); ans[ q[i].id ]=B.suf( q[i].k ); }}int main(){// freopen("in","r",stdin); n=read(); Q=read(); ini(); for(int i=1;i<=n;i++) a[i]=t[i]=read(); for(int i=1;i