[BZOJ3648]寢室管理（點分治+bit）

2019-11-08 19:47:25

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

Sunshine學長去年的互測題orz 然而他給的solution除了點分和bit什么都沒說啊。。。硬著頭皮想吧，反正我知道要用bit了。。

如果是樹的話點分治+二分或者bit就能搞定如果是環套樹的話怎么辦捏首先考慮不經過環的答案，直接在外向樹上點分就行了然后考慮經過環的答案假設當前外向樹上深度為h的有x個點，那么上一棵外向樹的貢獻就是x*深度>=k-1-h的點的個數假設上一個外向樹深度為1,2,..的點的個數都加入到bit里，那么就直接在bit里查詢就可以了從這里可以想到用bit來維護然后查詢，也就是將當前外向樹之前的點都加進去，暴力枚舉當前外向樹的深度，然后查詢當然兩棵外向樹的距離是不一樣的，所以在加入的過程中還需要根據距離進行相應的差分，實際上就是后一個加入的深度相比實際深度要比前一個小還有就是因為是一個環，需要展環成鏈然后做n次細節比較多。。。時間復雜度O(nlogn?一坨常數) $O(nlogn*一坨常數)$

有一個讓我掛挺了的地方，，就是點分治必須每一次更新size，否則找到的重心是不準確的

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>using namespace std;#define LL long long#define N 200005#define base 200000int n,m,k,x,y;int tot,point[N],nxt[N*2],v[N*2];void addedge(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}namespace tree{ int sum,root; int big[N],size[N],d[N],deep[N]; bool vis[N]; LL ans; void getroot(int x,int fa) { size[x]=1;big[x]=0; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { getroot(v[i],x); size[x]+=size[v[i]]; big[x]=max(big[x],size[v[i]]); } big[x]=max(big[x],sum-size[x]); if (big[x]<big[root]) root=x; } void getdeep(int x,int fa) { deep[++deep[0]]=d[x]; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { d[v[i]]=d[x]+1; getdeep(v[i],x); } } int find(int l,int r,int x) { int mid,ans=deep[0]+1; while (l<=r) { mid=(l+r)>>1; if (deep[mid]+x>=k) ans=mid,r=mid-1; else l=mid+1; } return ans; } LL calc(int x,int now) { d[x]=now;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); LL t=0LL; for (int i=1;i<=deep[0];++i) { int pos=find(i+1,deep[0],deep[i]); t+=(LL)(deep[0]-pos+1); } return t; } void dfs(int x) { ans+=calc(x,0); vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { ans-=calc(v[i],1); sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); } } void solve() { big[0]=N; sum=n;root=0; getroot(1,0); dfs(root);