SPOJ - COT2 : Count on a tree II (树上莫队)

题目链接：http://www.spoj.com/problems/COT2/en/

题目大意：

题意很简单，就是问你一棵树上任意两点间都多少不同的点。

解题思路：

这道题用到了传说中的树上莫队，其实还是很懵逼的，还不是很了解树上莫队的转换。树上莫队的详细解析可以看这篇博客http://blog.csdn.net/discreeter/article/details/52372689，自己讲是真的很难讲清楚，最后其实就是根据点的出现次数决定是否计算该点对答案的贡献。

自己代码也是照着大佬的来写的，主要根据代码来讲吧。

Ac代码：

#include
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int INF=1e9+7;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,a[N];   
int si,tag,pos[N];      //分块
int dep[N],par[N][21];      //dfs和求lca
int tmp,vis[N],tot[N],res[N];   //莫队算法
struct node     //储存询问
{int l,r;int id;
}qu[N];
stack s;     //建立一个栈用于树分块
vector v;    //离散化
vector vk[N];//建图
int getid(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
bool cmp(const node &p,const node &q)     //根据点所在块进行排序
{if(pos[p.l]==pos[q.l])return pos[p.r]=si){while(num--){pos[s.top()]=tag;s.pop();}tag++;}}}s.push(k);return num+1;
}
int lca(int vv,int uu)      //求lca
{if(dep[vv]>i)!=0;i++)if((d>>i)&1) vv=par[vv][i];if(vv==uu)return vv;for(int i=20;i>=0;i--){if(par[vv][i]!=par[uu][i]){vv=par[vv][i];uu=par[uu][i];}}return par[vv][0];
} 
void slove(int &v)      //莫队转移
{if(vis[v])      //如果该点之前出现过{if(--tot[a[v]]==0)  //出现次数-1 并判断-1后是否为0tmp--;          //为0则去掉对答案的贡献}else if(++tot[a[v]]==1) //判断出现次数+1后是否为1tmp++;              //增加对答案的贡献vis[v]^=1;              //取反v=par[v][0];
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);    //离散化 跟qsc大佬学的 感觉挺方便的sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++)a[i]=getid(a[i]);for(int i=1;ipos[qu[i].r])   //保持pos小的在前swap(qu[i].l,qu[i].r);qu[i].id=i;}sort(qu+1,qu+1+m,cmp);  //对询问进行离线排序tmp=0;int cv=1,cu=1;for(int i=1;i<=m;i++)   //进行树上莫队的转移{int nv=qu[i].l,nu=qu[i].r;int la=lca(cv,nv);while(cv!=la) slove(cv);while(nv!=la) slove(nv);la=lca(cu,nu);while(cu!=la) slove(cu);while(nu!=la) slove(nu);cv=qu[i].l,cu=qu[i].r;la=lca(cv,cu);res[qu[i].id]=tmp+(!tot[a[la]]);}for(int i=1;i<=m;i++)printf("%d\n",res[i]);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！