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

题目分析:

考虑欧拉序,这里的欧拉序与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 ;
}
上一篇:(转)Java API设计清单


下一篇:mysql_pconnect 问题