分类: 数据结构

6 篇文章

P3979 遥远的国度:换根树剖
遥远的国度 题目描述 zcwwzdjn 在追杀 zhx ,而 zhx 逃入了一个遥远的国度。当 zcwwzdjn 准备进入遥远的国度继续追杀时,守护神 RapiD 阻拦了 zcwwzdjn 的去路,他需要 zcwwzdjn 完成任务后才能进入遥远的国度继续追杀。 问题是这样的:遥远的国度有 $n$ 个城市,这些城市之间由一些路连接且这些城市构成了一…
简单点分治
Tree 题目描述 给定一棵 $n$ 个节点的树,每条边有边权,求出树上两点距离小于等于 $k$ 的点对数量。 输入格式 第一行输入一个整数 $n$,表示节点个数。 第二行到第 $n$ 行每行输入三个整数 $u,v,w$ ,表示 $u$ 与 $v$ 有一条边,边权是 $w$。 第 $n+1$ 行一个整数 $k$ 。 输出格式 一行一个整数,表示答案…
模拟赛日寄
T3 #include<bits/stdc++.h> #define cint const int& #define lowbit(x) (x & -x) using namespace std; const int maxn = 5e5+10; int n, a, b; struct { int nxt, v; }ed…
Tip
凡是O(log)转O(1),本质都是ST表与单调性 笛卡尔树 #define EL #include<bits/stdc++.h> #define int unsigned long long EL using namespace std; EL #define FIO 0 #define ten(x) (((x)<<1)+…
Tip
目前的状态是动态开点呢已经学的还不错了主要就是先申请内存然后呢再拿一个cnt技术 可持久化也很简单一般来说Try树线段树和树状数组都能够直接使用如果说能够可持久化或者说不区间待修的话就不要用树套树树套树实在是太占空间了模拟赛MLE 树桃树目前的状态就是把树状数组或者是线状树上的每一个节点当成一棵线段树来考虑并且在插入的时候在参数插入