首页 > 代码库 > 【BZOJ 3772】精神污染 主席树+欧拉序
【BZOJ 3772】精神污染 主席树+欧拉序
这道题的内存…………………真·精神污染………..
这道题的思路很明了，我们就是要找每一个路径包含了多少其他路径那么就是找，有多少路径的左右端点都在这条路径上，对于每一条路径，我们随便选定一个端点作为第一关键字，另一个作为第二关键字，于是就有了两维限制，按照主席树的一般思路，我们把建树顺序作为一维，然后在里面维护另一维，那么我们在外面限制第一关键字，就是在树上建主席树，查询减LCA，在里面的话我们把每个点作为第一关键字对应的第二关键字，放入主席树，而主席树维护的是欧拉序区间，所以我们每次查询只用查询在两端点减LCA得到了一棵树里查询，其所对应的欧拉序区间里的sum，对于sum来说，一个点第一次出现的位置加+1，第二次出现的位置-1，因为我们要找的是一段连续区间里在一段路径上的sum。
欧拉序建树的内存要比直接父子关系建树大2倍左右。
#include <cstdio> #include <cstring> #include <ctime> #include <vector> #define MAXN 100001 using namespace std; inline int read(){ int sum=0;register char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)sum=(sum<<1)+(sum<<3)+ch-‘0‘,ch=getchar(); return sum; } struct Seg_Tree{ Seg_Tree *ch[2]; int size; }*root[MAXN<<1],*null; struct Via{ int to,next; }*c; int *head,t; struct Bia{ int to,next,id; }*C; int *Head,T; int *f; bool *v; vector<int> memmber[MAXN]; int Ola[MAXN<<1],One[MAXN],Two[MAXN],Time,F[MAXN]; int L[MAXN],R[MAXN],Lca[MAXN]; int n,m; //*******************Define******************* inline void add(int x,int y){ c[++t].to=y,c[t].next=head[x],head[x]=t; } inline void Add(int x,int y,int z){ C[++T].to=y,C[T].next=Head[x],Head[x]=T,C[T].id=z; } inline int find(int x){ return x==f[x]?x:(f[x]=find(f[x])); } void LCA(int x,int fa){ f[x]=x; for(int i=head[x];i;i=c[i].next) if(c[i].to!=fa)LCA(c[i].to,x),f[c[i].to]=x; v[x]=1; for(int i=Head[x];i;i=C[i].next) if(v[C[i].to])Lca[C[i].id]=find(C[i].to); } //********************Tarjan******************* void dfs(int x,int fa){ Ola[++Time]=x,One[x]=Time,F[x]=fa; for(int i=head[x];i;i=c[i].next) if(c[i].to!=fa) dfs(c[i].to,x); Ola[++Time]=-x,Two[x]=Time; } //********************Ola********************** void ins(Seg_Tree *&p,Seg_Tree *last,int key,int l,int r){ if(p==last)p=new Seg_Tree,p->ch[0]=last->ch[0],p->ch[1]=last->ch[1],p->size=last->size; p->size+=Ola[key]<0?-1:1;if(l==r)return; if(key<=((l+r)>>1))ins(p->ch[0],last->ch[0],key,l,((l+r)>>1)); else ins(p->ch[1],last->ch[1],key,((l+r)>>1)+1,r); } int query(Seg_Tree *A1,Seg_Tree *A2,Seg_Tree *B1,Seg_Tree *B2,int l,int r,int z,int y){ if(z<=l&&r<=y)return A1->size-A2->size+B1->size-B2->size;int sum=0; if(z<=((l+r)>>1)&&((l+r)>>1)<y)return query(A1->ch[0],A2->ch[0],B1->ch[0],B2->ch[0],l,((l+r)>>1),z,y)+query(A1->ch[1],A2->ch[1],B1->ch[1],B2->ch[1],((l+r)>>1)+1,r,z,y); if(z<=((l+r)>>1))return query(A1->ch[0],A2->ch[0],B1->ch[0],B2->ch[0],l,((l+r)>>1),z,y); if(((l+r)>>1)<y)return query(A1->ch[1],A2->ch[1],B1->ch[1],B2->ch[1],((l+r)>>1)+1,r,z,y); } void Del(Seg_Tree *p,Seg_Tree *last){ if(p==last)return; Del(p->ch[0],last->ch[0]),Del(p->ch[1],last->ch[1]); delete p; } void Delete(int x,int fa){ for(int i=head[x];i;i=c[i].next) if(c[i].to!=fa) Delete(c[i].to,x); Del(root[x],root[fa]); } void Dfs_Build_One(int x,int fa){ root[x]=root[fa]; for(int i=0;i<memmber[x].size();i++){ ins(root[x],root[fa],One[memmber[x][i]],1,Time); } for(int i=head[x];i;i=c[i].next) if(c[i].to!=fa) Dfs_Build_One(c[i].to,x); } void Dfs_Build_Two(int x,int fa){ root[x]=root[fa]; for(int i=0;i<memmber[x].size();i++){ ins(root[x],root[fa],Two[memmber[x][i]],1,Time); } for(int i=head[x];i;i=c[i].next) if(c[i].to!=fa) Dfs_Build_Two(c[i].to,x); } //********************Seg_Tree****************** long long GCD(long long x,long long y){ return x==0?y:GCD(y%x,x); } //********************GCD*********************** int main(){ c=new Via[MAXN<<1],C=new Bia[MAXN<<1],head=new int[MAXN],Head=new int[MAXN],f=new int[MAXN],v=new bool[MAXN]; for(int i=0;i<MAXN;i++)head[i]=Head[i]=v[i]=0; n=read(),m=read();for(int i=1,x,y;i<n;i++)x=read(),y=read(),add(x,y),add(y,x); for(int i=1;i<=m;i++)L[i]=read(),R[i]=read(),Add(L[i],R[i],i),Add(R[i],L[i],i),memmber[L[i]].push_back(R[i]); LCA(1,0),dfs(1,0),null=new Seg_Tree,null->ch[0]=null->ch[1]=null,null->size=0,root[0]=null; delete[] C,delete[] Head,delete[] f,delete[] v; Dfs_Build_One(1,0); long long ans=0; for(int i=1;i<=m;i++){ ans+=query(root[L[i]],root[Lca[i]],root[R[i]],root[F[Lca[i]]],1,Time,One[Lca[i]],One[L[i]]); if(Lca[i]!=R[i])ans+=query(root[L[i]],root[Lca[i]],root[R[i]],root[F[Lca[i]]],1,Time,One[Lca[i]]+1,One[R[i]]); } Delete(1,0),Dfs_Build_Two(1,0); for(int i=1;i<=m;i++){ ans+=query(root[L[i]],root[Lca[i]],root[R[i]],root[F[Lca[i]]],1,Time,One[Lca[i]],One[L[i]]); if(Lca[i]!=R[i])ans+=query(root[L[i]],root[Lca[i]],root[R[i]],root[F[Lca[i]]],1,Time,One[Lca[i]]+1,One[R[i]]); } ans-=m; long long x=(long long)(m-1)*m/2,y=GCD(ans,x);ans/=y,x/=y; printf("%lld/%lld",ans,x); return 0; } //*******************Main**********************
【BZOJ 3772】精神污染 主席树+欧拉序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。