博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
loj 558 我们的 CPU 遭到攻击
阅读量:4983 次
发布时间:2019-06-12

本文共 783 字,大约阅读时间需要 2 分钟。

这题很明显是lct,我们只要可以维护黑色点深度和即可。

但是lct维护子树信息好难写啊。

首先边权比较难处理,所以偷懒加虚点表示边。

然后考虑维护子树距离和,需要维护splay上的边权和。

为了可以reverse,还必须维护一个反的距离和。
虚子树的答案更新在access和link连虚边的时候。
好烦啊。

千万不要把splay之前的下传标记写挂,记得只下传本splay的标记。

#include 
using namespace std;typedef long long ll;const int N=200005;struct node{ int blcnt;//black cnt int non_cnt;//xzs ll non_dis; ll sumval;//bian quan he int val;//bian quan ll disl,disr;//disl disr bool fl,bl; int fa,ch[2]; void clear(){ memset(this,0,sizeof(*this)); } void print(){ cout<<"blcnt: "<
<
s;map
mp[N>>1];void link(int u,int v,int w){ //cerr<<"link"<
<<" "<
<<" "<
<
n; --i) s.push(i); for (int i=1; i<=m; ++i){ //cerr<<"DOD"<
<

差点就是最长代码了,足以看出调试的艰辛。

转载于:https://www.cnblogs.com/Yuhuger/p/10560697.html

你可能感兴趣的文章
Tomcat启动Creation of SecureRandom instance卡住解决办法
查看>>
poj 2000 Gold Coins
查看>>
开通博客了
查看>>
BZOJ 1863: [Zjoi2006]trouble 皇帝的烦恼( 二分答案 )
查看>>
try catch
查看>>
slf4j
查看>>
C#语言和SQL Server数据库技术_程序数据集散地:数据库
查看>>
ES6学习之变量的解构赋值
查看>>
PHP 生成图片缩略图函数
查看>>
Boost Bimap示例
查看>>
ESLint 使用入门
查看>>
流水作业调度
查看>>
涨姿势系列之——内核环境下内存映射函数
查看>>
遍历数组批量更新数组里元素的某一项属性
查看>>
github 收藏项目的方法
查看>>
九的余数
查看>>
北京师范大学第十五届ACM决赛-重现赛K Keep In Line ( 字符串模拟实现)
查看>>
(转)C# — WinForm 消息框的使用
查看>>
时间管理(转)
查看>>
Future FutrueTask Callable类源码说明以及原理使用
查看>>