题目名称	2215. [HNOI 2016] 网络
输入输出	`network_tenderRun.in/out`
难度等级	★★★☆
时间限制	2000 ms (2 s)
内存限制	128 MiB
测试数据	10
题目来源	mikumikumi 于2016-04-18加入
开放分组	全部用户
提交状态
分类标签	树状数组整体分治树链剖分
	分享题解

通过：40，提交：122，通过率：32.79%
该用户不存在	100	2.186 s	9.66 MiB	C++
Link	100	2.391 s	15.56 MiB	C++
Steven	100	2.493 s	23.20 MiB	C++
Steven	100	2.541 s	23.19 MiB	C++
Samle	100	2.788 s	27.19 MiB	C++
op_组撒头屯	100	2.889 s	0.00 MiB	C++
Candy？	100	2.894 s	44.57 MiB	C++
pretend_fal	100	2.941 s	81.10 MiB	C++
Kirin	100	3.002 s	15.95 MiB	C++
liaoy	100	3.017 s	29.07 MiB	C++

本题关联比赛
20160407

关于网络的近10条评论(全部评论)
我怎么就没有想到用树状数组，而去线段树TTT了呢。。。。药丸再见 2017-06-21 20:14 10楼
样例好评 Cydiater 2017-03-31 14:07 9楼
我表示不能理解，明明树剖用堆线段树维护(id=299174)是O(nlon^3)而整体二分(id=376787)是O(nlogn^2)的，为什么反而整体二分慢？ _Itachi 2017-02-28 09:01 8楼
回复 @riteme : 虽说ST可以做到O(nlongn)预处理，O(1)查lca，但是你整体二分肯定要配合树状数组或者线段树之类的吧，那样整体二分的复杂度就是O(nlongn^2)了，你的整体复杂度还是O(nlongn^2)的，而且你用的是树剖求lca，每次是O(logn)的，不过因为是离线，所以求出所有lca的复杂度还是O(nlongn)的。这道题应该没有时间渐进复杂度低于O(nlongn^2)的做法了，（还是我太弱不会？）如果有，还请大神讲解。 _Itachi 2017-02-28 07:24 7楼
回复 @riteme : 感谢神犇的知道，NOIP后我才知道树上的链修改点求值可以变成点修改子树求和。 FoolMike 2017-01-03 10:45 6楼
回复 @Mike is Fool : 使用线段树分治 + $O(1)$的LCA查询可以做到二分过程$O(n \log n)$ riteme 2016-10-13 16:00 5楼
有人用整体二分写吗，整体二分带树剖好像是O(nlog^3n)，显然会挂。总不是要带LCT吧 FoolMike 2016-09-30 20:52 4楼
%%% AntiLeaf 2016-08-23 17:05 3楼
用堆来维护线段树，再用这棵线段树来维护树剖，这考试时就算想到也不敢写啊！ _Itachi 2016-08-16 14:24 2楼
树剖加堆，送分题啊，考场上没写出来 TenderRun 2016-05-07 09:30 1楼