| 题目名称 | 2638. 数列操作ψ |
|---|---|
| 输入输出 | series_wei.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 小一米
于2017-03-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：51， 提交：104， 通过率：49.04% | ||||
 Sky_miner |
100 | 0.999 s | 5.35 MiB | C++ |
|
Sky_miner |
100 | 1.119 s | 5.25 MiB | C++ |
 __debug |
100 | 1.372 s | 5.27 MiB | C++ |
 Go灬Fire |
100 | 1.374 s | 7.18 MiB | C++ |
 kito |
100 | 1.413 s | 4.87 MiB | C++ |
 shallwe |
100 | 1.421 s | 6.80 MiB | C++ |
 ruoruo |
100 | 1.424 s | 5.27 MiB | C++ |
|
kito |
100 | 1.456 s | 4.87 MiB | C++ |
 L_in |
100 | 1.540 s | 4.94 MiB | C++ |
 MistyEye |
100 | 1.581 s | 4.87 MiB | C++ |
| 关于 数列操作ψ 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
并没有看懂题解的复杂度证明，只好当做结论来记了
| ||||
|
在要怀疑人生的时候，才发现没写return……
 半汪
2017-03-29 07:14
22楼
| ||||
|
感谢Yveh,DaD3zZ大神提醒，该题只用一个（两个）log就可以做，两个（三个）log的标程已替换成一个（两个）log的，时限改为1s
求管理重新审核 （又一次）身败名裂.jpg   小一米
2017-03-28 10:04
21楼
| ||||
|
回复 @DaD3zZ :
这种使代码达到最差复杂度的数据要怎么造呀…… kito
2017-03-28 07:55
20楼
| ||||
 DaD3zZ
2017-03-28 07:54
19楼
| ||||
|
回复 @DaD3zZ :
吉老师不是说随机数据下全局and 全局or很快整个序列都会变成一样的么，估计是这个原因吧。 kito
2017-03-27 21:46
18楼
| ||||
|
回复 @小一米 :
这样的O（1）合并的复杂度应该才是最坏log2的吧.. log合并是log3的吧.. 感觉每一位都有O(N)段，一共log位，所以一共NlogN段，每一段在线段树上都是log 但是感觉随机数据表现应该非常优秀... DaD3zZ
2017-03-27 21:43
17楼
| ||||
|
回复 @kito :
大爷常数好小啊QwQ，压不过您QwQ | ||||
|
回复 @yveh :
不胜感激。 kito
2017-03-27 17:20
15楼
| ||||
|
回复 @kito :
那这样常数更优越了。  yveh
2017-03-27 17:16
14楼
| ||||
CSU_Turkey【题目描述】
给定一个数列a，你需要支持的操作：区间and，区间or，询问区间最大值
【输入格式】
一行两个整数$n,m$，表示数列长度和操作个数。
接下来一行有$n$个整数，第$i$个数表示$a_i$。
接下来$m$行，每一行均为以下三种操作中的一种
$1\ l\ r\ val$：$a_i=a_i\ and\ val(l\leq i \leq r)$
$2\ l\ r\ val$：$a_i=a_i\ or\ val(l\leq i \leq r)$
$3\ l\ r$：$max\{a_i\}(l\leq i \leq r)$
【输出格式】
对于每一个3操作，输出一行整数表示对应的答案
【样例输入】
8 6 4 0 5 7 2 9 12 8 2 2 5 15 1 3 5 2 3 5 7 1 5 7 12 2 1 6 4 3 2 6
【样例输出】
12 15
【提示】
对于$20\%$数据,$n,m\leq 3000$
另有$20\%$数据，1,2操作中$l=r$
另有$20\%$数据，3操作中$l=r$
对于$100\%$数据，$1\leq n,m\leq100000,0\leq a_i,val\leq10^9$
保证所有操作中$1\leq l\leq r\leq n$
很水的随机数据
感谢Yveh大神提醒，该题只用一个log就可以做，两个log的标程已替换成一个log的，时限改为1s
【来源】
吉老师课件《小清新线段树》