Gravatar
CSU_Turkey
积分:1723
提交:614 / 1589
并没有看懂题解的复杂度证明,只好当做结论来记了

Gravatar
半汪
积分:1972
提交:508 / 1308
在要怀疑人生的时候,才发现没写return……

题目 2638 数列操作ψ
2017-03-29 07:14:58
Gravatar
小一米
积分:1050
提交:234 / 504
感谢Yveh,DaD3zZ大神提醒,该题只用一个(两个)log就可以做,两个(三个)log的标程已替换成一个(两个)log的,时限改为1s
求管理重新审核
(又一次)身败名裂.jpg

题目 2638 数列操作ψ
2017-03-28 10:04:56
Gravatar
kito
积分:2514
提交:693 / 1285
回复 @DaD3zZ :
这种使代码达到最差复杂度的数据要怎么造呀……

题目 2638 数列操作ψ
2017-03-28 07:55:58
Gravatar
DaD3zZ
积分:103
提交:16 / 68
回复 @kito :
恩,我问了一下吉老师,这种做法最差还是log2的..
不过除非构造不然很容易就全部一样了..所以效果效果比log2快很多..

题目 2638 数列操作ψ
2017-03-28 07:54:23
Gravatar
kito
积分:2514
提交:693 / 1285
回复 @DaD3zZ :
吉老师不是说随机数据下全局and 全局or很快整个序列都会变成一样的么,估计是这个原因吧。

题目 2638 数列操作ψ
2017-03-27 21:46:50
Gravatar
DaD3zZ
积分:103
提交:16 / 68
回复 @小一米 :
这样的O(1)合并的复杂度应该才是最坏log2的吧..
log合并是log3的吧..
感觉每一位都有O(N)段,一共log位,所以一共NlogN段,每一段在线段树上都是log
但是感觉随机数据表现应该非常优秀...

题目 2638 数列操作ψ
2017-03-27 21:43:46
Gravatar
DaD3zZ
积分:103
提交:16 / 68
回复 @kito :
大爷常数好小啊QwQ,压不过您QwQ

Gravatar
kito
积分:2514
提交:693 / 1285
回复 @yveh :
不胜感激。

题目 2638 数列操作ψ
2017-03-27 17:20:50
Gravatar
yveh
积分:340
提交:63 / 278
回复 @kito :
那这样常数更优越了。

题目 2638 数列操作ψ
2017-03-27 17:16:51
Gravatar
kito
积分:2514
提交:693 / 1285
回复 @yveh :
嗯,我是在合并same的时候多了一个log,这个log可以用位运算直接与掉,谢谢。
我是把与和或操作转化成了区间减值和区间加值,可以只用一个lazy标记。

题目 2638 数列操作ψ
2017-03-27 17:14:42
Gravatar
yveh
积分:340
提交:63 / 278
回复 @kito :
因为判断可以是O(1)啊,而且or和and可以O(1)合并

题目 2638 数列操作ψ
2017-03-27 17:11:14
Gravatar
kito
积分:2514
提交:693 / 1285
回复 @yveh :
愿闻大神讲解
感谢大神代码对我的提示。

题目 2638 数列操作ψ
2017-03-27 17:05:34
Gravatar
Fmuckss
积分:1327
提交:273 / 511
想建31棵线段树试试........

题目 2638 数列操作ψ
2017-03-27 17:00:28
Gravatar
沉迷学习的假的Keller
积分:1633
提交:464 / 692
哪来这么多数列操作2333333

题目 2638 数列操作ψ
2017-03-27 16:57:01
Gravatar
yveh
积分:340
提交:63 / 278
好像一个log就能做??

题目 2638 数列操作ψ
2017-03-27 16:32:26
Gravatar
小一米
积分:1050
提交:234 / 504
只加强了一组数据,所以”有理有据的底层优化“好像能拿90

题目 2638 数列操作ψ
2017-03-27 15:25:24
Gravatar
小一米
积分:1050
提交:234 / 504
回复 @‎Alboi_真神名驴蛋蛋 :
加强了一组数据,顺便扩大了一下时限,应该不卡常了= =

题目 2638 数列操作ψ
2017-03-27 15:21:55
Gravatar
YGOI_真神名曰驴蛋蛋
积分:1978
提交:671 / 1901
@张浩南 别以为我不知道你刚看完直播!
顺便这题应该念数列操作(psi),不是数列操作(phi)(手动

题目 2638 数列操作ψ
2017-03-27 15:00:41
Gravatar
AntiLeaf
积分:3393
提交:1527 / 4369
回复 @小一米 :
你这题太弱了,加上区间翻转、区间插入、区间删除和可持久化才好玩

题目 2638 数列操作ψ
2017-03-27 14:58:04