本文共 3569 字，大约阅读时间需要 11 分钟。
10 10 10 0 0 7 2 1 4 7 7 7 9 1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 8 9 8 2 8 0 9 3 1 8 0 8 4 2 7 9 7 3 4 7 0 2 2 7 3 2 1 2 3 4
1603 957 7161 9466 3232 5223 1879 1669 1282 0
这道题和ZJOI那题点剖比较像。
可以用相似的方法做，先建出一棵重心树。每个点维护一棵动态开节点的线段树，维护重心管辖区域内的点到重心/(重心树上父亲的距离之和），查询的时候沿着重心树跳即可，复杂度O(Nlog2N)。
但是直接做是会爆空间的！！！！
我们需要压缩空间。首先年龄可以离散化，
然后由于每个点最多只有3个儿子，所以重心管辖区域内的点到重心/(重心树上父亲的距离之和）只记录一个即可，成功将空间压至460MB.
#include #include #include #include #include #include using namespace std;typedef long long ll;map H;struct Tree{ int size,ls,rs; ll sf;}tr[22000011];int ds[19][150011];int G[150011],Next[150011],Y[150011],fs[150011];int g[150011],num[300011],next[300011],y[300011],len[300011];int dep[150011],d[150011],fa[18][150011],que[150011];int size[150011],F[150011],val[150011],root[150011];int tt,n,m,lim,l,r,a,b,rs,i,x,z,q,j,u,dd,tl,tc,df,tot,yr,T;bool p[150011];ll ans;void st(int i,int j){ T++; Next[T]=G[i]; G[i]=T; Y[T]=j;}void star(int i,int j,int k){ tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j; len[tt]=k;}int bfs(int st){ tl++; int i,ff,l,r,x,j,k,sum,mx; l=r=1; fs[st]=0; que[l]=st; while(l<=r){ x=que[l]; j=g[x]; while(j!=0){ k=y[j]; if(k!=fs[x]&&p[k]){ r++; que[r]=k; fs[k]=x; if(tl==1){ fa[0][k]=x; dep[k]=dep[x]+len[j]; d[k]=d[x]+1; } } j=next[j]; } l++; } for(i=1;i<=r;i++)size[que[i]]=0; for(i=r;i>=2;i--){ x=que[i];ff=fs[x]; size[x]++; size[ff]+=size[x]; } size[que[1]]++; sum=size[que[1]]; mx=0; for(i=1;i<=r;i++){ x=que[i]; j=g[x]; mx=0; while(j!=0){ k=y[j]; if(fs[k]==x&&p[k]){ if(size[k]>mx)mx=size[k]; } j=next[j]; } if(sum-size[x]>mx)mx=sum-size[x]; if(mx<=sum/2)return x; }}int dfs(int x){ int j,k,ls,vs; ls=bfs(x); p[ls]=false; j=g[ls]; while(j!=0){ k=y[j]; if(p[k]){ vs=dfs(k); F[vs]=ls; st(ls,vs); } j=next[j]; } return ls;}int get(int x,int z){ int i,l,e; if(d[x] =0;i--)if(fa[i][x]!=fa[i][z]){ x=fa[i][x]; z=fa[i][z]; } return fa[0][x];}int dis(int x,int z){ return dep[x]+dep[z]-2*dep[get(x,z)];}void insert(int &t,int l,int r,int x,int nf){ if(t==0)t=++tc; if(l==r){ tr[t].size++; tr[t].sf+=nf; return; } int mid; mid=(l+r)/2; if(x<=mid)insert(tr[t].ls,l,mid,x,nf); if(x>mid)insert(tr[t].rs,mid+1,r,x,nf); tr[t].sf=tr[tr[t].ls].sf+tr[tr[t].rs].sf; tr[t].size=tr[tr[t].ls].size+tr[tr[t].rs].size;}Tree Merge(Tree a,Tree b){ Tree c; c.size=a.size+b.size; c.sf=a.sf+b.sf; return c;}Tree ask(int t,int l,int r,int x,int y){ if(t==0)return tr[t]; if(l==x&&r==y)return tr[t]; int mid; mid=(l+r)/2; if(y<=mid)return ask(tr[t].ls,l,mid,x,y); if(x>mid)return ask(tr[t].rs,mid+1,r,x,y); if(x<=mid&&y>mid)return Merge(ask(tr[t].ls,l,mid,x,mid),ask(tr[t].rs,mid+1,r,mid+1,y));}void Find(int x,int l,int r){ int dx,rl,nxt,j,k,st; nxt=0; Tree ts; rl=x; st=0; while(x){ dx=ds[st][rl]; j=G[x]; while(j!=0){ k=Y[j]; if(k!=nxt){ ts=ask(root[k],1,tot,l,r); ans+=ts.sf+(ll)ts.size*dx; } j=Next[j]; } if(val[x]>=l&&val[x]<=r)ans+=dx; nxt=x; x=F[x]; st++; }}int GG(int x){ int l,r,mid; l=1; r=tot; while(l<=r){ mid=(l+r)/2; if(num[mid]>=x)r=mid-1; else l=mid+1; } return l;}int main(){ memset(p,true,sizeof(p)); scanf("%d%d%d",&n,&m,&lim); for(i=1;i<=n;i++){ scanf("%d",&val[i]); val[i]++; if(!H[val[i]]){ H[val[i]]=1; num[++tot]=val[i]; } } sort(num+1,num+1+tot); for(i=1;i<=tot;i++)H[num[i]]=i; for(i=1;i<=n;i++)val[i]=H[val[i]]; for(i=1;i tot||num[r]>yr)r--; ans=0; if(l<=r)Find(u,l,r); printf("%lld\n",ans); }}
转载于:https://www.cnblogs.com/applejxt/p/4461590.html
