最近点 - 可持久化点分树 - 主席树

2019-04-14 18:27发布

站内文章 / 模拟电子
16040 0 1200
题目大意：给一棵树，点有黑白，每次形如翻转一个点颜 {MOD}，询问到某个点的最近黑 {MOD}点距离，以及返回之前某个版本。n,q<=1e5.
题解：显然将点分树可持久化一下，然后用一个可持久化堆（虽然写了个可持久化线段树）维护一下即可。点分树可持久化可以暴力拿个主席树维护点分树的点到堆的编号的映射，也可以将原树三度化之后直接可持久化，后者这部分复杂度一个log（但是并不很快）。 #include #define rep(i,a,b) for(int i=a;i<=b;i++) #define Rep(i,v) rep(i,0,(int)v.size()-1) #define lint long long #define ull unsigned lint #define db long double #define pb push_back #define mp make_pair #define fir first #define sec second #define debug(x) cerr<<#x<<"="< #define sp <<" " #define ln < using namespace std; typedef pair<int,int> pii; typedef set<int>::iterator sit; namespace INPUT_SPACE{ const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;inline int gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; } inline int inn() { int x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');return x; } }using INPUT_SPACE::inn; namespace OUTPUT_SPACE{ char ss[100000*15],tt[20];int ssl,ttl;inline int Flush() { return fwrite(ss+1,sizeof(char),ssl,stdout),ssl=0,0; } inline int print(int x) { if(!x) ss[++ssl]='0';for(ttl=0;x;x/=10) tt[++ttl]=char(x%10+'0');for(;ttl;ttl--) ss[++ssl]=tt[ttl];return ss[++ssl]=' '; } }using OUTPUT_SPACE::print;using OUTPUT_SPACE::Flush; const int N=200010,LOG=20,INF=1e9;struct edges{ int to,pre,w; }e[N<<1];int h[N],etop;vector<int> g[N]; inline int add_edge(int u,int v,int w) { return e[++etop].to=v,e[etop].w=w,e[etop].pre=h[u],h[u]=etop; } inline int build_edge(int u,int v,int w) { return add_edge(u,v,w),add_edge(v,u,w); } namespace SDH_space{ int son[N],wf[N]; inline int sdh(int x,int fa,int &nc) { int cnt=0,c;Rep(i,g[x]) if(g[x][i]^fa) sdh(g[x][i],x,nc); Rep(i,g[x]) if(g[x][i]^fa) son[++cnt]=g[x][i],wf[cnt]=1; while(cnt>2) { rep(i,(c=0)+1,cnt/2) nc++,build_edge(nc,son[i*2-1],wf[i*2-1]), build_edge(nc,son[i<<1],wf[i<<1]),son[++c]=nc,wf[c]=0; if(cnt&1) son[++c]=son[cnt],wf[c]=wf[cnt];cnt=c; } rep(i,1,cnt) build_edge(x,son[i],wf[i]);return 0; } } namespace MyHeap_space{ const int T=3e7,max_range=1e5;int lc[T],rc[T],val[T],s[T],heap_node_cnt; inline int init() { return val[0]=INF; } inline int update(int &x,int y,int p,int v,int l=0,int r=max_range) { x=++heap_node_cnt,lc[x]=lc[y],rc[x]=rc[y],s[x]=s[y]; int mid=(l+r)>>1;if(l==r) return s[x]+=v,val[x]=(s[x]?l:INF); if(p<=mid) update(lc[x],lc[y],p,v,l,mid);else update(rc[x],rc[y],p,v,mid+1,r); return val[x]=min(val[lc[x]],val[rc[x]]); } inline int query(int x) { return val[x]; } }using MyHeap_space::update;using MyHeap_space::query; namespace NODE_space{ struct node{ int g[3],rt[3],c,ans0;node() { g[0]=g[1]=g[2]=rt[0]=rt[1]=rt[2]=c=ans0=0; } inline int upd_from(const node &t,int dir,int dis,int sgn) { c=t.c;rep(i,0,c-1) g[i]=t.g[i],rt[i]=t.rt[i]; return ans0=t.ans0,update(rt[dir],t.rt[dir],dis,sgn); } inline int ans(int k)const { int ans=INF;if(ans0) return 0; rep(i,0,c-1) if(i^k) ans=min(ans,query(rt[i])); return ans; } }; }using NODE_space::node; namespace DFZ_space{ const int T=3e6;node t[T]; int sz[N],Lst[N],Lcnt,dir[N],d[N],vis[N]; int dis[LOG][N],fr[LOG][N],rt[N],dfz_node_cnt; inline int getsz(int x,int fa=0) { sz[x]=1,Lst[++Lcnt]=x; for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to]&&e[i].to!=fa) sz[x]+=getsz(y,x); return sz[x]; } inline int getrt(int &x) { for(int i=1,fsz=sz[x],tsz=fsz;i<=Lcnt;i++) { int y=Lst[i],ysz=fsz-sz[y]; for(int j=h[y],z;j;j=e[j].pre) if(!vis[z=e[j].to]&&sz[e[j].to]<sz[y]) ysz=max(ysz,sz[z]); if(ysz<tsz) tsz=ysz,x=y; } return 0; } inline int getmsg(int x,int fa,int c,int d,int *dis,int *fr) { dis[x]=d,fr[x]=c; for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to]&&e[i].to!=fa) getmsg(y,x,c,d+e[i].w,dis,fr); return 0; } inline int dfz(int x,int dpt=0) { Lcnt=0,getsz(x),getrt(x),vis[x]=1,d[x]=dpt;int cnt=0; for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to]) getmsg(y,x,cnt++,e[i].w,dis[dpt],fr[dpt]); for(int i=h[x],y;i;i=e[i].pre) if(!vis[y=e[i].to]) t[x].g[t[x].c++]=dfz(y,dpt+1); return x; } inline int getdir(int x) { for(int i=d[x]-1;i>=0;i--) dir[i]=fr[i][x];return d[x]; } inline int upd(int x,int las,int cur,int sgn) { int r=rt[las],len=getdir(x),p=rt[cur]=++dfz_node_cnt; rep(i,0,len-1) t[p].upd_from(t[r],dir[i],dis[i][x],sgn), r=t[r].g[dir[i]],p=t[p].g[dir[i]]=++dfz_node_cnt; return t[p]=t[r],t[p].ans0^=1; } inline int qry(int x,int cur) { int ans=INF,p=rt[cur],len=getdir(x); rep(i,0,len-1) ans=min(ans,dis[i][x]+t[p].ans(fr[i][x])),p=t[p].g[dir[i]]; return min(ans,t[p].ans(-1)); } }using DFZ_space::upd;using DFZ_space::qry;using DFZ_space::dfz; namespace STA_space{ const int T=3e6; int lc[T],rc[T],v[T],n,rt[N],sta_node_cnt; inline int build(int &x,int l,int r) { x=++sta_node_cnt;int mid=(l+r)>>1;if(l==r) return v[x]=-1; return build(lc[x],l,mid),build(rc[x],mid+1,r); } inline int build(int _n) { return n=_n,build(rt[0],1,n); } inline int update(

热门文章