BZOJ3435[Wc2014]紫荆花之恋——动态点分治(替罪羊式点分树套替罪羊树)

时间:2023-01-29 16:58:08

题目描述

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点。每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 i 都有一个感受能力值Ri ,小精灵 i, j 成为朋友当且仅当在树上 i 和 j 的距离 dist(i,j) ≤ Ri + R! ,其中 dist(i, j)表示在这个树上从 i 到 j 的唯一路径上所有边的边权和。强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。  
我们假定这个树一开始为空,节点按照加入的顺序从 1开始编号。由于强强非常好奇, 你必须在他每次出现新节点后马上给出总共的朋友对数,不能拖延哦。

输入

共有 n + 2 行。 
第一行包含一个正整数,表示测试点编号。 
第二行包含一个正整数 n ,表示总共要加入的节点数。 
我们令加入节点前的总共朋友对数是 last_ans,在一开始时它的值为0。 
接下来 n 行中第 i 行有三个数 ai, bi, ri,表示节点  i  的父节点的编号为 ai xor (last_ans mod 10^9)   (其中xor 表示异或,mod  表示取余,数据保证这样操作后得到的结果介于 1到i  –  1之间),与父节点之间的边权为 ci,节点 i 上小精灵的感受能力值为r!。 
注意 a1 = c1 = 0,表示 1 号点是根节点,对于 i > 1,父节点的编号至少为1。

输出

包含 n 行,每行输出1 个整数, 表示加入第 i 个点之后,树上有几对朋友。

样例输入

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

样例输出

0
1
2
4
7

提示

1<=Ci<=10000
Ai<=2*10^9
Ri<=10^9
N<=100000

经过一天的卡常+优化,经过从非旋转treap到旋转treap到替罪羊树的改进,终于过掉了这个传说中的神仙题!

因为这道题比较繁琐,我们分块讲解。

点分治

按照动态点分治的常规套路,我们考虑对于一棵给定的树,单次询问如何用点分治处理。

当以x为分治中心时,如果联通块中i,j两个点满足条件,假设i,j距离分治中心距离分别为di,dj,那么di+dj<=ri+rj,即di-ri<=rj-dj。

那么遍历分治中心的每个子树,记录每个点的ri-di,对于每个点x找到有多少个点的ri-di>=dx-rx,同样容斥去掉两点位于同一棵子树中的答案。

对于维护每个点的ri-di只要开一棵平衡树即可(因为本题强制在线不能离散化,所以不能使用权值线段树)。

平衡树

因为本题用到的平衡树功能单一,所以建议使用高速平衡树(除非旋转treap和splay之外的其他平衡树)。

当然如果你有高超的卡常技巧也可以用splay或非旋转treap。

对于高速平衡树的选择,个人建议选择插入时间复杂度较优的SBT或替罪羊树(原因后面会说)。

对于替罪羊树,经过不懈尝试,我发现重构因子为0.86时的时间复杂度比较优秀。

动态点分治&点分树

多次询问显然要用点分树来解决,通过上面对单次查询点分治的处理方法,我们可以知道点分树上每个点需要维护的信息:

1、每个点开一棵平衡树维护以它为分治中心时联通块内所有点的ri-di(di为联通块内点为到它的距离)。

2、每个点开一棵平衡树维护以它为分治中心时联通块内所有点的ri-di(di为联通块内点到它在点分树上父节点的距离)。

那么显然对于静态的树,单次修改和查询只要从操作点往点分树的根爬并对沿途点进行修改或统计信息即可。

替罪羊式重构

本题的重点是边加点边询问,那么问题来了:如何构建外层点分树?

显然不能加一个点重构一次点分树,而点分树也不具有treap等平衡树的可旋性,但是我们可以像替罪羊树一样重构!

我们知道点分树要求每个点的子树中所有点都是以它为分治中心时能遍历到的点,那么在新加一个点时我们不妨直接将这个点加到它原树的父节点下面。

与替罪羊树相同,我们同样需要一个重构因子,这里因为重构时间复杂度较高,所以重构因子建议设成0.9.

在往根方向修改沿途信息时我们记录距离根最近的一个需要重构的点,然后将这个子树重构。

因为这棵子树在原树上一定是一个联通块,所以直接对这个联通块进行一遍点分治建出这个联通块真正的点分树即可。

因为需要将联通块内所有点的vis标记都清空,所以还需要每个点开一个vector存一下这个点在点分树上的子树中都有哪些点。

当重构外层点分树时,因为点分树上的父子关系改变,所以内层平衡树的信息也要发生相应的变化。

因为外层不是平衡树,我们无法像平衡树一样通过上传来重新改变内层信息,所以只能暴力删除平衡树并暴力重新插入信息。

这也是为什么要用插入时间复杂度较优的平衡树的原因。

LCA

同样因为动态加点,无法用RMQ或者树链剖分等方法求两点在原树的LCA,对于新加入的每个点,只能用倍增来求LCA。

时间复杂度

本题的时间复杂度主要在外层重构及内层平衡树的重建上。

对于外层点分树,重构的时间复杂度每次均摊O(logn)。

对于内层平衡树的重建,因为每个平衡树平均logn个节点,每次插入时间复杂度O(logn),所以重建一棵平衡树时间复杂度O(logn^2)。

一次内层重建logn棵平衡树时间复杂度是O(logn^3)。

同样对于一次查询或修改需要遍历logn个节点,每次求LCA+平衡树上查找时间复杂度O(logn),单次查询或修改时间复杂度O(logn^2)。

注意在点分治递归求重心时每层要dfs一遍整个联通块使当前层的分治中心获得真正的联通块大小,否则会影响重构时的判断。

综上所述,总时间复杂度O(nlogn^3)。

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
inline char _read()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int x=0,f=1;char ch=_read();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=_read();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=_read();}
return x*f;
}
int n;
ll ans;
int rot;
int num;
int tot;
int cnt;
int top;
int type;
int point;
int x,y,z;
int a,b,c;
int r[100010];
int d[100010];
int f[100010];
int lg[100010];
int to[200010];
int mx[100010];
int dep[100010];
int vis[100010];
int root[100010];
int size[100010];
int head[100010];
int next[200010];
int st[4000010];
int froot[100010];
int g[100010][18];
vector<int>q[100010];
const int mod=1000000000;
struct balance_tree
{
int cot;
int *flag;
int q[4000010];
int v[4000010];
int ls[4000010];
int rs[4000010];
int sum[4000010];
inline bool bad(int rt)
{
if(sum[rt]*86<=100*max(sum[ls[rt]],sum[rs[rt]]))
{
return true;
}
return false;
}
inline void dfs(int rt)
{
if(!rt)
{
return ;
}
dfs(ls[rt]);
q[++cot]=rt;
dfs(rs[rt]);
}
inline void build(int &rt,int l,int r)
{
int mid=(l+r)>>1;
rt=q[mid];
if(l==r)
{
ls[rt]=rs[rt]=0;
sum[rt]=1;
return ;
}
if(l<mid)
{
build(ls[rt],l,mid-1);
}
else
{
ls[rt]=0;
}
build(rs[rt],mid+1,r);
sum[rt]=sum[ls[rt]]+sum[rs[rt]]+1;
}
inline void rebuild(int &rt)
{
cot=0;
dfs(rt);
if(cot)
{
build(rt,1,cot);
}
else
{
rt=0;
}
}
inline void insert(int &rt,int k)
{
if(!rt)
{
if(top)
{
rt=st[top--];
}
else
{
rt=++cnt;
}
v[rt]=k;
sum[rt]=1;
return ;
}
sum[rt]++;
if(v[rt]>=k)
{
insert(ls[rt],k);
}
else
{
insert(rs[rt],k);
}
if(bad(rt))
{
flag=&rt;
}
}
inline void ins(int &rt,int val)
{
flag=0;
insert(rt,val);
if(flag)
{
rebuild(*flag);
}
}
inline void del(int &rt)
{
if(!rt)
{
return ;
}
del(ls[rt]);
del(rs[rt]);
v[rt]=sum[rt]=0;
st[++top]=rt;
rt=0;
}
inline int query(int root,int k)
{
int rt=root;
int ans=0;
while(rt)
{
if(v[rt]>=k)
{
rt=ls[rt];
}
else
{
ans+=sum[ls[rt]]+1;
rt=rs[rt];
}
}
return sum[root]-ans;
}
}tr;
inline void add(int x,int y)
{
next[++tot]=head[x];
head[x]=tot;
to[tot]=y;
}
inline int lca(int x,int y)
{
if(d[x]<d[y])
{
swap(x,y);
}
int deep=d[x]-d[y];
for(int i=0;i<=lg[deep];i++)
{
if((deep&(1<<i)))
{
x=g[x][i];
}
}
if(x==y)
{
return x;
}
for(int i=lg[d[x]];i>=0;i--)
{
if(g[x][i]!=g[y][i])
{
x=g[x][i];
y=g[y][i];
}
}
return g[x][0];
}
inline int dis(int x,int y)
{
return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
inline void getroot(int x,int fa)
{
size[x]=1;
mx[x]=0;
for(int i=head[x];i;i=next[i])
{
if(!vis[to[i]]&&to[i]!=fa)
{
getroot(to[i],x);
size[x]+=size[to[i]];
mx[x]=max(mx[x],size[to[i]]);
}
}
mx[x]=max(mx[x],num-size[x]);
if(mx[x]<mx[rot])
{
rot=x;
}
}
inline void dfs(int x,int fa,int rt)
{
size[x]=1;
q[rt].push_back(x);
tr.ins(root[rt],r[x]-dis(x,rt));
if(f[rt])
{
tr.ins(froot[rt],r[x]-dis(x,f[rt]));
}
for(int i=head[x];i;i=next[i])
{
if(!vis[to[i]]&&to[i]!=fa)
{
dfs(to[i],x,rt);
size[x]+=size[to[i]];
}
}
}
inline void partation(int x,int fa)
{
getroot(x,0);
tr.del(root[x]);
tr.del(froot[x]);
q[x].clear();
f[x]=fa;
vis[x]=1;
dfs(x,0,x);
for(int i=head[x];i;i=next[i])
{
if(!vis[to[i]])
{
num=size[to[i]];
rot=0;
getroot(to[i],0);
partation(rot,x);
}
}
}
inline void insert(int x)
{
point=-1;
for(int i=x;i;i=f[i])
{
q[i].push_back(x);
tr.ins(root[i],r[x]-dis(x,i));
if(f[i])
{
tr.ins(froot[i],r[x]-dis(x,f[i]));
}
size[i]++;
if(f[i]&&size[i]*100>(size[f[i]]+1)*90)
{
point=f[i];
}
}
if(point!=-1)
{
int len=q[point].size();
for(int i=0;i<len;i++)
{
vis[q[point][i]]=0;
}
num=size[point];
rot=0;
getroot(point,0);
partation(rot,f[point]);
}
}
inline int query(int x)
{
int res=0;
for(int i=x;i;i=f[i])
{
res+=tr.query(root[i],dis(x,i)-r[x]);
}
for(int i=x;f[i];i=f[i])
{
res-=tr.query(froot[i],dis(x,f[i])-r[x]);
}
return res;
}
int main()
{
type=read();n=read();
x=read();y=read();z=read();
printf("0\n");
r[1]=z;
tr.ins(root[1],r[1]);
q[1].push_back(1);
mx[0]=1<<30;
size[1]=vis[1]=1;
for(int i=2;i<=n;i++)
{
lg[i]=lg[i>>1]+1;
x=read();y=read();z=read();
x^=(ans%mod);
r[i]=z;
add(i,x);
add(x,i);
g[i][0]=f[i]=x;
d[i]=d[x]+1;
dep[i]=dep[x]+y;
vis[i]=1;
for(int j=1;(1<<j)<=d[i];j++)
{
g[i][j]=g[g[i][j-1]][j-1];
}
ans+=query(i);
printf("%lld\n",ans);
insert(i);
}
}

BZOJ3435[Wc2014]紫荆花之恋——动态点分治(替罪羊式点分树套替罪羊树)的更多相关文章

  1. luoguP3920 &lbrack;WC2014&rsqb;紫荆花之恋 动态点分治 &plus; 替罪羊树

    意外的好写..... 考虑点分 \(dis(i, j) \leq r_i + r_j\) 对于过分治中心一点\(u\),有 \(dis(i, u) - r_i = dis(j, u) + r_j\) ...

  2. &lbrack;WC2014&rsqb;紫荆花之恋&lpar;动态点分治&plus;替罪羊思想&rpar;

    题目描述 强强和萌萌是一对好朋友.有一天他们在外面闲逛,突然看到前方有一棵紫荆树.这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来.仔细看看的话,这个大树实际上是一个带权树.每 ...

  3. bzoj3435 &lbrack;Wc2014&rsqb;紫荆花之恋(动态点分治&plus;替罪羊树)

    传送门(权限) 传送门(非权限) 题解 我终终终终终终于做出来啦!!! 作为一个没有学过替罪羊树的蒟蒻现场学了一下替罪羊树,作为一个平衡树都写数组版本的看着大佬的指针题解无语只能硬去理解然后照着抄了一 ...

  4. uoj 55 紫荆花之恋 动态点分治&plus;替罪羊式重构&plus;treap

    每插入一个点,直接把它当做重心插入原树,当做是动态点分树一样维护 但这样深度会越来越大,所以我们用类似替罪羊的方法 当树失去平衡时,对子树进行一次点分,保证复杂度 #include <cstdi ...

  5. BZOJ3435&colon; &lbrack;Wc2014&rsqb;紫荆花之恋&lpar;替罪羊树,Treap&rpar;

    Description 强强和萌萌是一对好朋友.有一天他们在外面闲逛,突然看到前方有一棵紫荆树.这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来.仔细看看的话,这个大树实际上是 ...

  6. bzoj3435 &lbrack;Wc2014&rsqb;紫荆花之恋

    如果这棵树不变的话,就是一个裸的点分树套平衡树,式子也很好推$di+dj<=ri+rj$,$ri-di>=dj-rj$ 平衡树维护$dj-rj$,然后查$ri-di$的$rank$即可. ...

  7. UOJ &num;55 &amp&semi; 洛谷 P3920 紫荆花之恋 —— 动态点分治&plus;替罪羊树

    题目:http://uoj.ac/problem/55 https://www.luogu.org/problemnew/show/P3920 参考博客:https://www.cnblogs.com ...

  8. 【BZOJ3435】&lbrack;Wc2014&rsqb;紫荆花之恋 替罪点分树&plus;SBT

    [BZOJ3435][Wc2014]紫荆花之恋 Description 强强和萌萌是一对好朋友.有一天他们在外面闲逛,突然看到前方有一棵紫荆树.这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从 ...

  9. bzoj 3435&colon; &lbrack;Wc2014&rsqb;紫荆花之恋 替罪羊树维护点分治 &amp&semi;&amp&semi; AC400

    3435: [Wc2014]紫荆花之恋 Time Limit: 240 Sec  Memory Limit: 512 MBSubmit: 159  Solved: 40[Submit][Status] ...

随机推荐

  1. Spring中Bean的作用域、生命周期

                                   Bean的作用域.生命周期 Bean的作用域 Spring 3中为Bean定义了5中作用域,分别为singleton(单例).protot ...

  2. vmware 安装 macos

    http://jingyan.baidu.com/article/ff411625b9011212e48237b4.html

  3. &num;import 跟 &num;include、&commat;class 之间的区别

    #include 是 C/C++ 导入头文件的关键字  是完整的包含某个文件的内容(包括该文件中被导入的文件) #import 是 OC 导入头文件的关键字 #import 指令是 OC 针对 #in ...

  4. IT公司100题-9-判断整数序列是不是二元查找树的后序遍历结果

    问题描述: 输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果. 如果是返回true,否则返回false. 例如输入4, 8, 6, 12, 16, 14, 10,由于这一整数序列是如下树 ...

  5. WinAPI你知道多少?!(上千个,好多都没见过)

    http://www.cnblogs.com/vanver/archive/2013/06/13/NO-2013_06_13pm.html 播客开篇,讲讲废话:本篇播客只是推荐给热与钻研的同学们... ...

  6. &lbrack;Git&rsqb; git log命令

    这是git的新系列,不常用的命令和其参数比较容易记不住,干脆将常用的记录下来,日后查查方便也是好的,一篇文章一个git命令,长短根据命令有所不同. git log命令主要用于查看提交历史,同时根据添加 ...

  7. 《Redis 使用规范》

    一:Redis 概述 - Redis 是内存级别的数据库,在一台普通电脑上,Redis 3.X 便可以读取 10 万个键值对(现在的Redis官方版本已经更新到了5.X,性能会更好). 二:关于Red ...

  8. 面试题&lowbar;默认传参list

    # ###2.值是多少 def extendList(val, list=[]): list.append(val) return list 如果默认形参是列表,会提前在内存中开辟一个空间存储列表 如 ...

  9. 2019&period;03&period;25 git

    Git简介: Git是一个分布式版本控制软件. 背景故事: Linus在1991年创建了开源的Linux. 在2002年以前:世界各地的志愿者把源代码文件通过diff的方式发给Linus,然后Linu ...

  10. C&plus;&plus;学习(二十三)(C语言部分)之 指针4

    指针 指针 存放地址 只能存放地址 使用 &取地址运算符 *取值 解引用运算符 malloc 申请堆内存 free释放堆内存 1.1 指针 存放的地址(变量地址 常量区的地址 堆区内存首地址 ...