SPOJ10707 COT2 - Count on a tree II 【树上莫队】 - Java

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目分析：

考虑欧拉序，这里的欧拉序与ETT欧拉序的定义相同而与倍增LCA不同。然后不妨对于询问$u$与$v$让$dfsin[u] \leq dfsin[v]$，这样对于u和v不在一条路径上，它们可以改成询问$dfsin[u]$到$dfsin[v]$。否则改成$dfsout[u]$到$dfsin[v]$，并加上LCA上的影响，如果在询问过程中没有加入就加入，否则删除。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int maxm = ;

 const int srt = ;

 int n,m;

 int a[maxn],tb[maxn],arr[maxn],fa[maxn],pm[maxm],ans[maxm];

 int dfsin[maxn],dfsout[maxn],Num,pre[maxn];

 vector <int> g[maxn];

 vector <pair<int,int> > Qy[maxn];

 struct query{int l,r,bel,rem;}Q[maxm];

 int found(int x){

     int rx = x; while(pre[rx] != rx) rx = pre[rx];

     while(pre[x] != rx){int tmp = pre[x]; pre[x] = rx; x = tmp;}

     return rx;

 }

 void dfs(int now,int ff){

     arr[now] = ;pm[++Num] = now;fa[now] = ff;

     dfsin[now] = Num;

     for(int i=;i<Qy[now].size();i++){

     if(!arr[Qy[now][i].first])continue;

     Q[Qy[now][i].second].bel=found(Qy[now][i].first);

     }

     for(int i=;i<g[now].size();i++){

     if(g[now][i]==fa[now])continue;

     dfs(g[now][i],now);

     }

     pre[now] = fa[now];

     pm[++Num] = now; dfsout[now] = Num;

 }

 void read(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d",&a[i]),tb[i] = a[i];

     sort(tb+,tb+n+);  int num=unique(tb+,tb+n+)-tb-;

     for(int i=;i<=n;i++) a[i]=lower_bound(tb+,tb+num+,a[i])-tb;

     memset(tb,,sizeof(tb));

     for(int i=;i<n;i++){

     int u,v; scanf("%d%d",&u,&v);

     g[u].push_back(v); g[v].push_back(u);

     }

     for(int i=;i<=m;i++) scanf("%d%d",&Q[i].l,&Q[i].r);

 }

 int cmp(query alpha,query beta){

     if(alpha.l/srt == beta.l/srt) return alpha.r < beta.r;

     else return alpha.l/srt < beta.l/srt;

 }

 void init(){

     for(int i=;i<=m;i++){

     Qy[Q[i].l].push_back(make_pair(Q[i].r,i));

     Qy[Q[i].r].push_back(make_pair(Q[i].l,i));

     }

     for(int i=;i<=n;i++) pre[i] = i;

     dfs(,);

     for(int i=;i<=m;i++){

     if(dfsin[Q[i].l] > dfsin[Q[i].r]) swap(Q[i].l,Q[i].r);

     if(Q[i].bel == Q[i].l || Q[i].bel == Q[i].r){

         Q[i].l = dfsin[Q[i].l]; Q[i].r = dfsin[Q[i].r];

         Q[i].bel = i; Q[i].rem = ;

     }else{

         Q[i].l = dfsout[Q[i].l]; Q[i].r = dfsin[Q[i].r];

         Q[i].rem = Q[i].bel; Q[i].bel = i;

     }

     }

     sort(Q+,Q+m+,cmp);

 }

 void work(){

     int L = ,R = ,as=; tb[a[]]++;

     for(int i=;i<=m;i++){

     int nowl = Q[i].l,nowr = Q[i].r;

     while(R < nowr){

         R++;

         if(dfsin[pm[R]]==R||dfsin[pm[R]]<L){

         if(!tb[a[pm[R]]])as++;

         tb[a[pm[R]]]++;

         }else{

         if(tb[a[pm[R]]] == ) as--;

         tb[a[pm[R]]]--;

         }

     }

     while(L > nowl){

         L--;

         if(dfsout[pm[L]]==L||dfsout[pm[L]]>R){

         if(!tb[a[pm[L]]])as++;

         tb[a[pm[L]]]++;

         }else{

         if(tb[a[pm[L]]] == ) as--;

         tb[a[pm[L]]]--;

         }

     }

     while(R > nowr){

         if(dfsin[pm[R]]==R||dfsin[pm[R]]<L){

         if(tb[a[pm[R]]] == ) as--;

         tb[a[pm[R]]]--;

         }else{

         if(!tb[a[pm[R]]])as++;

         tb[a[pm[R]]]++;

         }

         R--;

     }

     while(L < nowl){

         if(dfsout[pm[L]]==L||dfsout[pm[L]]>R){

         if(tb[a[pm[L]]] == ) as--;

         tb[a[pm[L]]]--;

         }else{

         if(!tb[a[pm[L]]])as++;

         tb[a[pm[L]]]++;

         }

         L++;

     }

     if(Q[i].rem && !tb[a[Q[i].rem]])ans[Q[i].bel]=as+;

     else ans[Q[i].bel] = as;

     }

     for(int i=;i<=m;i++) printf("%d\n",ans[i]);

 }

 int main(){

     read();

     init();

     work();

     return ;

 }