# [WC2014] Bauhinia love [scapegoat thought], [dynamic point tree], [scapegoat tree]

Portal

Meaning: there is a tree without nodes at the beginning, nnn times of query, each time add a new point and give the parent node, the distance to the father, the parameter rir_iri, and query the logarithm of point pair (u,v)(u,v)(u,v) (U, V) satisfying dist(u,v) < ru + R vdist (U, V) < ru + rv.

n ≤ 105n\leq 10^5n ≤ 105, forced Online

It's a good question. It's not as terrible as the rumours in the Jianghu. I only wrote it for two days

Obviously, we only need to consider the contribution of the newly added points and the previous sum

Set the current added point as uuu

Look at this formula:

dist(u,v)≤ru+rvdist(u,v)\leq r_u+r_vdist(u,v)≤ru​+rv​

If we find any ppp on the path from uuu to vvv, it can be divided into

dist(u,p)+dist(v,p)≤ru+rvdist(u,p)+dist(v,p)\leq r_u+r_vdist(u,p)+dist(v,p)≤ru​+rv​

What we want is to meet

dist(v,p)−rv≤ru−dist(u,p)dist(v,p)-r_v\leq r_u-dist(u,p)dist(v,p)−rv​≤ru​−dist(u,p)

The number of vvv s of

If the ppp is fixed, you can use the balance tree to maintain it

Then we can enumerate the ancestors of uuu as the ppp statistical answer

But apparently a chain is up

Note that the complexity of doing this is O (depth of U) O (depth of U) O (depth of U). You can try to split the tree

If the shape of a tree is fixed, because of the nature of point trees

Lcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalcalca

And what we need above is just on the path, so we can count in the same way on the point tree

In the specific implementation, each node u u u on the point tree opens a balanced tree to record the dist(v,u) - R vdist (V, U) - R vdist (V, U) - rv of all points in the subtree

Then, set the newly added point as x x x, and jump up from xxx. When you jump to u u u, ask the number of points in the balance tree of uuu ≤ rx − dist(x,u)\leq r_x-dist(x,u) ≤ rx − dist(x,u)

But this is not a simple path, so it is necessary to record the information of dist(v,u) - R vdist (V, U) - R vdist (V, U) - rv in the subtree of a son of uuu

Specifically, each node u u u opens another balance tree to record the dist(v,fau) - R vdist (V, fa_) - R vdist (V, Fau) - rv of each node vvv in the subtree

But this tree still moves

Using black technology and the idea of scapegoat tree, if there are too serious points in jumping points and dividing trees, the whole subtree will be reconstructed

It's easy to say, but there are many details

Because the constant is surprisingly large, the internal balance tree uses a scapegoat tree

True, righteous, scapegoat set

Complexity O (yes) O (yes) O (yes)

Error prone details of this question:

1. Empty chchch array when internal scapegoat refactoring
2. When the point tree is used to reconstruct the subtree, it is only a connected block on the original tree. It needs dfs to make a mark again and then only access the marked points
3. Clearing a pile of information of all nodes when reconstructing subtree from point tree
4. In order to calculate distdistdist distdistdist, the father of the root of the new subtree (that is, the center of gravity of the whole connected block) should be connected before the reconstruction of the point tree
5. To record that each point on the tree is the father's son and pass on the reference
6. In the reconstruction of point tree, two vector s are needed to be opened and sorted respectively to build the balance tree violently
7. Point tree reconstruction can not modify the information of fa,disfa,disfa,dis, etc
8. When judging reconstruction, it is necessary to judge specifically the root of the whole point tree
9. To write a memory reclaim pool
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <algorithm>
#include <cassert>
#define MAXN 100005
#define MAXM 200005
using namespace std;
const int MOD=1e9;
const double alpha=0.8;
typedef long long ll;
struct edge{int u,v,w;}e[MAXM];
inline void addnode(int u,int v,int w)
{
e[++cnt]=(edge){u,v,w};
}
{
int ans=0;
char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
int dis[MAXN],dep[MAXN],up[MAXN][20];
inline int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for (int i=0;(1<<i)<=t;i++) if (t&(1<<i)) x=up[x][i];
if (x==y) return x;
for (int i=19;i>=0;i--)	if (up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
return up[x][0];
}
inline int dist(const int& x,const int& y){return dis[x]+dis[y]-2*dis[lca(x,y)];}
namespace SGT
{
int *pos;
const int N=MAXN<<6;
int bin[N],lis[N];
int ch[N][2],siz[N],val[N],tot;
inline int newnode(const int& v){int x=(bin[0]? bin[bin[0]--]:++tot);return ch[x][0]=ch[x][1]=0,siz[x]=1,val[x]=v,x;}
inline void update(const int& x){siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];}
void insert(int& x,int v){if (!x) return (void)(x=newnode(v));insert(ch[x][v>val[x]],v);update(x);if (siz[ch[x][0]]>siz[x]*alpha||siz[ch[x][1]]>siz[x]*alpha) pos=&x;}
void build(int& x,int l=1,int r=lis[0]){if (l>r) return (void)(x=0);int mid=(l+r)>>1;x=newnode(lis[mid]),build(ch[x][0],l,mid-1),build(ch[x][1],mid+1,r),update(x);}
void dfs(int& x){if (!x) return;dfs(ch[x][0]);bin[++bin[0]]=x,lis[++lis[0]]=val[x];dfs(ch[x][1]);x=0;}
inline void rebuild(){if (pos==NULL) return;lis[0]=0,dfs(*pos),build(*pos),pos=NULL;}
inline void modify(int& x,int v){insert(x,v),rebuild();}
int query(int x,int v){if (!x) return 0;if (v<val[x]) return query(ch[x][0],v);return siz[ch[x][0]]+1+query(ch[x][1],v);}
inline void getbuf(const vector<int>& v){lis[0]=0;for (int i=0;i<(int)v.size();i++) lis[++lis[0]]=v[i];}
}
using SGT::modify;
using SGT::query;
using SGT::getbuf;
int fa[MAXN],idx[MAXN],rt[MAXN],prt[MAXN],r[MAXN],*pos;
int Rt=1;
vector<int> son[MAXN],sub[MAXN];
inline int insert(int x)
{
int ans=0;
for (int u=x,v=0;u;v=u,u=fa[u])
{
int val=r[x]-dist(x,u);
ans+=query(rt[u],val)-query(prt[v],val);
modify(rt[u],-val);
if (v) modify(prt[v],-val);
if (SGT::siz[rt[v]]>SGT::siz[rt[u]]*alpha) pos=(fa[u]? &son[fa[u]][idx[u]]:&Rt);
}
return ans;
}
bool vis[MAXN];
vector<int> block;
void dfs(int u){vis[u]=1,block.push_back(u);for (int i=0;i<(int)son[u].size();i++) dfs(son[u][i]);}
int siz[MAXN],maxp[MAXN]={0x7fffffff},root;
void findrt(int u,int f,int sum)
{
siz[u]=1,maxp[u]=0;
if (vis[e[i].v]&&e[i].v!=f)
{
findrt(e[i].v,u,sum);
siz[u]+=siz[e[i].v],maxp[u]=max(maxp[u],siz[e[i].v]);
}
if (sum-siz[u]>maxp[u]) maxp[u]=sum-siz[u];
if (maxp[u]<maxp[root]) root=u;
}
int getsiz(int u,int f)
{
int ans=1;
if (vis[e[i].v]&&e[i].v!=f)
ans+=getsiz(e[i].v,u);
return ans;
}
void build()
{
vis[root]=0;
int u=root;
sub[u].push_back(u);
if (vis[e[i].v])
{
root=0;
findrt(e[i].v,0,getsiz(e[i].v,0));
int v=root;
build();
for (vector<int>::iterator it=sub[v].begin();it!=sub[v].end();++it) sub[u].push_back(*it);
}
vector<int> tmp1,tmp2;
for (int i=0;i<(int)sub[u].size();i++)
{
int v=sub[u][i];
tmp1.push_back(dist(v,u)-r[v]);
tmp2.push_back(dist(v,fa[u])-r[v]);
}
sort(tmp1.begin(),tmp1.end());
getbuf(tmp1),SGT::build(rt[u]);
if (fa[u])
{
sort(tmp2.begin(),tmp2.end());
getbuf(tmp2),SGT::build(prt[u]);
}
}
int main()
{
ll lans=0;
for (int u=1;u<=n;u++)
{
int a,c;
up[u][0]=a;
for (int i=1;i<20;i++) up[u][i]=up[up[u][i-1]][i-1];
dis[u]=dis[up[u][0]]+c,dep[u]=dep[up[u][0]]+1;
printf("%lld\n",lans+=insert(u));
if (pos==NULL) continue;
//		cerr<<"rebuild "<<*pos<<'\n';
int f=fa[*pos],id=idx[*pos];
dfs(*pos),root=0,findrt(*pos,0,SGT::siz[rt[*pos]]);
int RT=root;
//		cerr<<*pos<<' '<<RT<<'\n';
for (int i=0;i<(int)block.size();i++)
{
int v=block[i];
SGT::dfs(rt[v]),SGT::dfs(prt[v]);
fa[v]=idx[v]=rt[v]=prt[v]=0;
son[v].clear(),sub[v].clear();
}
fa[RT]=f,idx[RT]=id,*pos=RT;
build();
block.clear();
pos=NULL;
}
return 0;
}

70 original articles published, praised, 6 visits 6265

Posted on Tue, 03 Mar 2020 19:03:02 -0800 by lc21