-
Notifications
You must be signed in to change notification settings - Fork 670
/
Copy pathsegment_tree.go
1038 lines (936 loc) · 34.8 KB
/
segment_tree.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
package copypasta
import "math/bits"
// 线段树讲解 by 灵茶山艾府（13:30 开始）https://www.bilibili.com/video/BV15D4y1G7ms
// 可视化 https://visualgo.net/zh/segmenttree
// 推荐阅读《算法竞赛进阶指南》0x43 和 0x48 节
// https://oi-wiki.org/ds/seg/
// https://cp-algorithms.com/data_structures/segment_tree.html
// [Monoid 幺半群] Generalizing Segment Trees https://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html
// 总结得比较详细 https://www.acwing.com/blog/content/1684/
// 线段树进阶 Part 1 https://www.luogu.com.cn/blog/AlexWei/Segment-Tree-Part-1
// https://codeforces.com/blog/entry/18051
// https://codeforces.com/blog/entry/89313
// https://codeforces.com/blog/entry/15890
// todo 高效线段树 crazySegmentTree https://codeforces.com/blog/entry/89399
// https://en.algorithmica.org/hpc/data-structures/segment-trees/
// 像使用 STL 一样使用线段树 https://zhuanlan.zhihu.com/p/459679512 https://zhuanlan.zhihu.com/p/459880950
// 数组两倍空间线段树 https://www.cnblogs.com/chy-2003/p/11815396.html
// 线段树诡异题目收录 https://zhuanlan.zhihu.com/p/124181375
// Limitの线段树题单 https://www.luogu.com.cn/training/1124
// todo [题单] 线段树的进阶用法 https://www.luogu.com.cn/training/221#problems
// todo Offline Range MEX queries in O(log n) https://codeforces.com/blog/entry/117688
// 注：对于指针写法，必要时禁止 GC，能加速不少
// func init() { debug.SetGCPercent(-1) }
// 模板（单点修改、区间查询）https://www.luogu.com.cn/problem/P2068
/*
如果一个题目可以用分治解决，那么这个题目的带修改版本可以用线段树解决
带修最长连续相同子串 LC2213 https://leetcode.cn/problems/longest-substring-of-one-repeating-character/
带修最大子段和 https://www.luogu.com.cn/problem/P4513
- 代码 https://www.luogu.com.cn/record/50262292
- https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/A
- https://www.spoj.com/problems/GSS3/ 2007-08-03
- 2 个最大子段和 https://codeforces.com/problemset/problem/2042/F
- k 个最大子段和 https://codeforces.com/problemset/problem/280/D 2800 用网络流的思想「反悔」
带修最大子段和+按位或 https://www.luogu.com.cn/problem/P7492 https://www.luogu.com.cn/contest/42328
带修打家劫舍 https://www.luogu.com.cn/problem/P3097
- LC https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/
*/
// 势能线段树：区间开方、区间取模、区间 GCD 一个数，都是可以暴力更新的
// 关于线段树上的一些进阶操作 https://www.luogu.com/article/aentaeud
// 区间开方见 CF920F
// 区间取模见 CF438D
// 区间 GCD 一个数见 https://www.luogu.com.cn/problem/P9989 https://www.cnblogs.com/Athanasy/p/17940070
// https://www.luogu.com.cn/problem/P10516
// 另见吉老师线段树 Segment Tree Beats https://www.luogu.com.cn/problem/P6242 【模板】线段树 3（区间最值操作、区间历史最值）
// 另见 Kinetic Tournament 树 (KTT) https://www.luogu.com.cn/problem/P5693
// https://www.luogu.com.cn/problem/P10587
// https://www.luogu.com.cn/problem/P4588 乘法 单点修改
// https://codeforces.com/problemset/problem/2050/F 1700 GCD
// https://codeforces.com/problemset/problem/914/D 1900 GCD
// https://codeforces.com/problemset/problem/380/C 2000 区间最长括号子序列
// https://codeforces.com/contest/474/problem/E 2000 最值及其下标
// https://codeforces.com/problemset/problem/522/D 2000 区间最短线段长度
// https://codeforces.com/problemset/problem/920/F 2000 开方（也可以用并查集做）
// - https://www.luogu.com.cn/problem/P4145
// - http://acm.hdu.edu.cn/showproblem.php?pid=4027
// 区间（绝对）众数及其次数（摩尔投票算法）https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
// - LC169 https://leetcode.cn/problems/majority-element/
// - LC1157 https://leetcode.cn/problems/online-majority-element-in-subarray/
// - https://www.luogu.com.cn/problem/P3567
// - https://www.luogu.com.cn/problem/P3765
// - https://codeforces.com/contest/1514/problem/D 2000
// https://codeforces.com/problemset/problem/703/D 2100 区间元素去重后的异或和
// - 联系 https://www.luogu.com.cn/problem/P1972
// todo https://codeforces.com/problemset/problem/1567/E 2200 区间连续递增子数组个数
// https://codeforces.com/problemset/problem/1179/C 2200
// https://codeforces.com/problemset/problem/1906/F 2200 最大子数组和（非空） 离线
// https://codeforces.com/problemset/problem/438/D 2300 取模
// https://codeforces.com/problemset/problem/1093/G 2300 k 维曼哈顿（单点修改+区间最大值）
// https://codeforces.com/problemset/problem/1187/D 2400 转换的好题
// https://codeforces.com/problemset/problem/1401/F 2400 区间 swap & reverse
// - 联想 reverse bit 的递归思路
// https://codeforces.com/problemset/problem/1436/E 2400 所有子数组的 mex 的 mex
// 区间 mex https://www.luogu.com.cn/problem/P4137
// - 做法之一是离线+线段树二分 https://www.luogu.com.cn/blog/user7035/solution-p4137
// - 也可以用树状数组 https://www.luogu.com.cn/blog/Atalod/ti-xie-p4137-post
// - 反向构造题 https://www.luogu.com.cn/problem/P6852
// https://codeforces.com/problemset/problem/1609/E 2400 单点修改 + 不含子序列 abc
// https://codeforces.com/problemset/problem/1665/E 2500 区间最小的 31 个数
// https://codeforces.com/problemset/problem/2042/F 2600 两段最大子段和
// https://codeforces.com/problemset/problem/19/D 2800
// https://codeforces.com/problemset/problem/280/D 2800
// https://codeforces.com/problemset/problem/765/F 3100 最小差值
// - https://codeforces.com/problemset/problem/1793/F 2600 和 CF765F 是同一题
// - 不允许相等 https://www.luogu.com.cn/problem/P5926
// https://atcoder.jp/contests/abc285/tasks/abc285_f
// https://atcoder.jp/contests/abc339/tasks/abc339_e 值域线段树
// https://atcoder.jp/contests/abc356/tasks/abc356_f 动态图连通块大小
// https://atcoder.jp/contests/abc353/tasks/abc353_g
//
// 题目推荐 https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-12
// 力扣 https://leetcode.cn/tag/segment-tree/
// 另见 dp.go 的数据结构优化 DP
// 另见 dp.go 的动态 DP
//
// todo http://poj.org/problem?id=2991
// 变换成值域 http://poj.org/problem?id=3368
// - https://www.luogu.com.cn/problem/SP1684
// - https://www.luogu.com.cn/problem/UVA11235
// http://poj.org/problem?id=3470
// todo http://poj.org/problem?id=1201
// 线段树二分
// LC2286 https://leetcode.cn/problems/booking-concert-tickets-in-groups/
// LC2940 https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/
// EXTRA: 权值线段树
// 讲解与习题 https://www.luogu.com.cn/blog/bfqaq/qian-tan-quan-zhi-xian-duan-shu
// 浅谈权值线段树到主席树 https://www.luogu.com.cn/blog/your-alpha1022/WeightSegmentTree-ChairmanTree
// 谈树状数组套权值树 https://www.luogu.com.cn/blog/bfqaq/qian-tan-shu-zhuang-shuo-zu-quan-zhi-shu
// https://codeforces.com/problemset/problem/1042/D 1800
// todo 区间只出现一次的数的最大值 https://codeforces.com/problemset/problem/69/E
// EXTRA: 树套树
// 代码见 fenwick_tree.go
// 三维偏序：树状数组套动态开点权值线段树 https://www.luogu.com.cn/problem/P3810
// 二逼平衡树 https://www.luogu.com.cn/problem/P3380
// - 两种 O((n+q)lognlogU) 做法：
// - 树状数组套动态开点权值线段树（AC）
// - 动态开点权值线段树套下标平衡树（TLE）https://www.luogu.com.cn/record/136191286
// 二维线段树 https://www.luogu.com.cn/problem/P3437
// - LC308 https://leetcode.cn/problems/range-sum-query-2d-mutable/
// https://www.luogu.com.cn/problem/P4514
// 树套树 标记永久化 https://www.luogu.com.cn/blog/Hoshino-kaede/chao-leng-men-shuo-ju-jie-gou-er-wei-xian-duan-shu-yang-xie
// https://codeforces.com/problemset/problem/19/D 2800
// EXTRA: 线段树优化建图
// 每个位置对应着 O(logn) 个线段树上的节点，每个区间可以拆分成至多 O(logn) 个线段树上的区间
// 这个性质可以用于优化建图
// https://www.luogu.com.cn/blog/forever-captain/DS-optimize-graph
// https://codeforces.com/problemset/problem/786/B 2300
// https://codeforces.com/problemset/problem/1903/F 2500
// todo https://www.luogu.com.cn/problem/P6348
/* 一些细节
了解下列内容将有助于 Hack 代码
区间 [1,1] 对应的节点编号为 1<<bits.Len(uint(n-1)) 1e5 => 2^17 这也说明 [1,1] 对应节点编号x2 的节点是不会下标越界的
区间 [n,n] 对应的节点编号为 1<<bits.Len(uint(n))-1 1e5 => 2^17-1
当 n≠2^k 时，在内存中区间 [n,n] 的下一个就是区间 [1,1]
最下面一排的节点个数
最下面一排的节点编号之和
https://www.luogu.com.cn/problem/P9689?contestId=133572
什么时候空间最浪费？（指一般线段树的实现方式）
当 n=2^k-1 时，此时只需要 2n 的空间
什么时候空间最不浪费？（指一般线段树的实现方式）
当 n=2^k+d (d<<2^k) 时
record table
i/n n i range
1.0000 1 1 [1,1]
1.5000 2 3 [2,2]
1.6667 3 5 [2,2]
1.7500 4 7 [4,4]
1.8000 5 9 [2,2]
2.1667 6 13 [5,5]
2.5000 10 25 [7,7] **《算法竞赛进阶指南》用的例子
2.7222 18 49 [11,11]
2.8500 20 57 [17,17]
2.8529 34 97 [19,19]
3.1389 36 113 [29,29] ** 首个超过 3n 的例子
3.3088 68 225 [53,53]
3.3472 72 241 [65,65]
3.4015 132 449 [101,101]
3.5368 136 481 [121,121]
3.6402 264 961 [233,233]
3.6507 272 993 [257,257]
3.6942 520 1921 [457,457]
3.7595 528 1985 [497,497]
3.8163 1040 3969 [977,977]
3.8191 1056 4033 [1025,1025]
3.8454 2064 7937 [1937,1937]
3.8774 2080 8065 [2017,2017]
3.9072 4128 16129 [4001,4001]
3.9079 4160 16257 [4097,4097]
3.9223 8224 32257 [7969,7969]
3.9381 8256 32513 [8129,8129]
3.9534 16448 65025 [16193,16193]
3.9535 16512 65281 [16385,16385]
3.9610 32832 130049 [32321,32321]
3.9689 32896 130561 [32641,32641]
3.9766 65664 261121 [65153,65153]
3.9767 65792 261633 [65537,65537] ** 1e5 以内的最大值
3.9805 131200 522241 [130177,130177]
3.9844 131328 523265 [130817,130817]
3.9883 262400 1046529 [261377,261377]
3.9883 262656 1047553 [262145,262145]
3.9902 524544 2093057 [522497,522497]
3.9922 524800 2095105 [523777,523777]
3.9941 1049088 4190209 [1047041,1047041]
3.9941 1049600 4192257 [1048577,1048577]
*/
// 线段树有两个下标，一个是线段树节点数组的下标，另一个是线段树维护的区间的下标
// 节点数组的下标：一般是从 1 开始的。如果你想改成从 0 开始，把左右子树下标改成 o*2+1 和 o*2+2 就行
// 区间的下标：从 0 开始。如果你习惯从 1 开始的数组，也可以改成从 1 开始
// l 和 r 也可以写到方法参数上，实测二者在执行效率上无异
// 考虑到 debug 和 bug free 上的优点，写到结构体参数中
type seg []struct {
l, r int
val int // info
}
// 合并两个节点上的数据：maintain 和 query 通用
// 要求操作满足区间可加性
// 例如 + * | & ^ min max gcd mulMatrix 摩尔投票 最大子段和 ...
func (seg) mergeInfo(a, b int) int {
return max(a, b)
}
// 单点更新：见 update
func (t seg) set(o, val int) {
t[o].val = t.mergeInfo(t[o].val, val)
}
func (t seg) maintain(o int) {
t[o].val = t.mergeInfo(t[o<<1].val, t[o<<1|1].val)
}
// 下标从 0 开始
// 调用时 o=1, l=0, r=n-1
func (t seg) build(a []int, o, l, r int) {
t[o].l, t[o].r = l, r
if l == r {
t[o].val = a[l]
return
}
m := (l + r) >> 1
t.build(a, o<<1, l, m)
t.build(a, o<<1|1, m+1, r)
t.maintain(o)
}
// 调用时 o=1 0<=i<=n-1
func (t seg) update(o, i, val int) {
if t[o].l == t[o].r {
t.set(o, val)
return
}
m := (t[o].l + t[o].r) >> 1
if i <= m {
t.update(o<<1, i, val)
} else {
t.update(o<<1|1, i, val)
}
t.maintain(o)
}
// 调用时 o=1 [l,r] 0<=l<=r<=n-1
func (t seg) query(o, l, r int) int {
if l <= t[o].l && t[o].r <= r {
return t[o].val
}
m := (t[o].l + t[o].r) >> 1
if r <= m {
return t.query(o<<1, l, r)
}
if m < l {
return t.query(o<<1|1, l, r)
}
lRes := t.query(o<<1, l, r)
rRes := t.query(o<<1|1, l, r)
return t.mergeInfo(lRes, rRes)
}
func (t seg) queryAll() int { return t[1].val }
// 线段树二分：返回 [l,r] 内第一个满足 f 的下标，如果不存在，返回 -1
// 例如查询 [l,r] 内第一个大于等于 target 的元素下标，需要线段树维护区间最大值
// t.findFirst(1, l, r, func(nodeMax int) bool { return nodeMax >= target })
// 调用时 o=1
// https://leetcode.cn/problems/booking-concert-tickets-in-groups/
// - https://leetcode.cn/problems/booking-concert-tickets-in-groups/submissions/517574644/
// https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/
// - https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/submissions/517575667/
func (t seg) findFirst(o, l, r int, f func(int) bool) int {
if t[o].l > r || t[o].r < l || !f(t[o].val) {
return -1
}
if t[o].l == t[o].r {
return t[o].l
}
idx := t.findFirst(o<<1, l, r, f)
if idx < 0 {
idx = t.findFirst(o<<1|1, l, r, f)
}
return idx
}
// 线段树二分：返回 [l,r] 内最后一个满足 f 的下标，如果不存在，返回 -1
// 例如查询 [l,r] 内最后一个小于等于 target 的元素下标，需要线段树维护区间最小值
// t.findLast(1, l, r, func(nodeMin int) bool { return nodeMin <= target })
// 调用时 o=1
func (t seg) findLast(o, l, r int, f func(int) bool) int {
if t[o].l > r || t[o].r < l || !f(t[o].val) {
return -1
}
if t[o].l == t[o].r {
return t[o].l
}
idx := t.findLast(o<<1|1, l, r, f)
if idx < 0 {
idx = t.findLast(o<<1, l, r, f)
}
return idx
}
// a 的下标从 0 开始，线段树的区间下标也从 0 开始
func newSegmentTree(a []int) seg {
n := len(a)
if n == 0 {
panic("slice can't be empty")
}
t := make(seg, 2<<bits.Len(uint(n-1)))
t.build(a, 1, 0, n-1)
return t
}
//
// 延迟标记（区间修改）
// 有关区间 flip 的 0-1 线段树，见 segment_tree01.go
//
// 【单个更新操作】
// + min/max https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/A
// 【推荐】https://codeforces.com/problemset/problem/1208/D 1900
// https://codeforces.com/problemset/problem/1321/E 2000
// https://codeforces.com/problemset/problem/52/C 2200
// https://codeforces.com/problemset/problem/1110/F 2600
// 转换 https://codeforces.com/gym/294041/problem/E
// todo 转换 https://atcoder.jp/contests/abc327/tasks/abc327_f
// DP https://atcoder.jp/contests/dp/tasks/dp_w
// + ∑ https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/D
// https://www.luogu.com.cn/problem/P2068
// https://www.luogu.com.cn/problem/P3372
// + + ∑ https://atcoder.jp/contests/abc357/tasks/abc357_f
// | & https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/C
// = min https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/E
// = ∑ https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/F
// https://codeforces.com/problemset/problem/558/E 2300
// + 某个区间的不小于 x 的最小下标 https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/C
// https://codeforces.com/problemset/problem/292/E 1900 单点查询的简化写法
// - https://codeforces.com/contest/292/submission/173659179
// https://codeforces.com/problemset/problem/1881/G 2000 不含任何长度 >= 2 的回文串
// https://codeforces.com/problemset/problem/620/E 2100
// https://codeforces.com/problemset/problem/1295/E 2200
// https://codeforces.com/problemset/problem/1557/D 2200 max max 离散化
// https://codeforces.com/problemset/problem/718/C 2300 矩阵乘法 ∑
// https://codeforces.com/problemset/problem/1797/E 2300 phi*
// https://codeforces.com/problemset/problem/145/E 2400
// https://codeforces.com/problemset/problem/1114/F 2400
// https://codeforces.com/problemset/problem/240/F 2600
// https://codeforces.com/problemset/problem/1439/C 2600 =max 求和的 O(log^2) 性质
// https://codeforces.com/problemset/problem/1614/E 2600
// https://codeforces.com/problemset/problem/2009/G3 2700
// https://codeforces.com/problemset/problem/794/F 2800 数位修改 考察对懒标记的理解
// todo https://codeforces.com/problemset/problem/1209/G2 3200
//
// 线段树二分
// https://atcoder.jp/contests/abc389/tasks/abc389_f
// LC2502 https://leetcode.cn/problems/design-memory-allocator/
// - 加强版 https://www.luogu.com.cn/problem/P2894
// LC2589 https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/ 线段树二分与更新合并
// - LCP32 https://leetcode.cn/problems/t3fKg1/
//
// 维护平方和 LC2916 https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-ii/
// todo https://www.luogu.com.cn/problem/P1471
// 斐波那契 https://codeforces.com/problemset/problem/446/C 2400
// 区间加等差数列（差分法）https://www.luogu.com.cn/problem/P1438 https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/B
// 多项式更新 Competitive Programmer’s Handbook Ch.28
// 区间加等比数列（q 恒定）
// 提出首项后，剩余的是固定的 1 + q^1 + q^2 + ... + q^(线段树区间长度-1)
// 可以预处理 1 + q^1 + q^2 + ... 的前缀和
// 线段树维护首项的和
//
// 【多个更新操作复合】
// = + max https://www.luogu.com.cn/problem/P1253 代码 https://www.luogu.com.cn/record/207200750
// * + ∑ https://www.luogu.com.cn/problem/P3373 代码 https://www.luogu.com.cn/record/207204766
// LC1622 https://leetcode.cn/problems/fancy-sequence/
// https://atcoder.jp/contests/abc332/tasks/abc332_f 1786=CF2062 期望
// = + ∑ https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/A
// * + ∑ai^k(k≤10) https://www.zhihu.com/question/564007656 B
// 线段树维护区间加、乘、赋值、平方和、立方和 http://acm.hdu.edu.cn/showproblem.php?pid=4578
// - https://www.cnblogs.com/dyhaohaoxuexi/p/14046275.html
// 注：区间赋值（=x）可以看成是先 *0 再 +x
// 三维向量 * + 交换 ∑^2 http://118.190.20.162/view.page?gpid=T119（需要注册 CCF）
//
// 吉老师线段树 吉司机线段树 Segment Tree Beats (Seg-beats)
// todo https://oi-wiki.org/ds/seg-beats/
// https://codeforces.com/blog/entry/57319
// 区间最值操作与区间历史最值详解 https://www.luogu.com.cn/blog/Hakurei-Reimu/seg-beats
// 模板题 https://www.luogu.com.cn/problem/P6242
const todoInit = 0
type lazySeg []struct {
l, r int
sum int // info
todo int
}
func (lazySeg) mergeInfo(a, b int) int {
return a + b // % mod
}
func (lazySeg) mergeTodo(a, b int) int {
return a + b // % mod
}
func (t lazySeg) apply(o int, f int) {
cur := &t[o]
// 更新 f 对整个区间的影响（本例为区间加）
cur.sum += f * (cur.r - cur.l + 1) // % mod
cur.todo = t.mergeTodo(f, cur.todo)
}
func (t lazySeg) maintain(o int) {
t[o].sum = t.mergeInfo(t[o<<1].sum, t[o<<1|1].sum)
}
func (t lazySeg) spread(o int) {
f := t[o].todo
if f == todoInit {
return
}
t.apply(o<<1, f)
t.apply(o<<1|1, f)
t[o].todo = todoInit
}
// 下标从 0 开始
// 调用时 o=1, l=0, r=n-1
func (t lazySeg) build(a []int, o, l, r int) {
t[o].l, t[o].r = l, r
t[o].todo = todoInit
if l == r {
t[o].sum = a[l]
return
}
m := (l + r) >> 1
t.build(a, o<<1, l, m)
t.build(a, o<<1|1, m+1, r)
t.maintain(o)
}
// 调用时 o=1 [l,r] 0<=l<=r<=n-1
func (t lazySeg) update(o, l, r int, f int) {
if l <= t[o].l && t[o].r <= r {
t.apply(o, f)
return
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if l <= m {
t.update(o<<1, l, r, f)
}
if m < r {
t.update(o<<1|1, l, r, f)
}
t.maintain(o)
}
// 调用时 o=1 [l,r] 0<=l<=r<=n-1
func (t lazySeg) query(o, l, r int) int {
if l <= t[o].l && t[o].r <= r {
return t[o].sum
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if r <= m {
return t.query(o<<1, l, r)
}
if m < l {
return t.query(o<<1|1, l, r)
}
lRes := t.query(o<<1, l, r)
rRes := t.query(o<<1|1, l, r)
return t.mergeInfo(lRes, rRes)
}
func (t lazySeg) queryAll() int { return t[1].sum }
// 线段树二分：返回 [l,r] 内第一个满足 f 的下标，如果不存在，返回 -1
// 例如查询 [l,r] 内第一个大于等于 target 的元素下标，需要线段树维护区间最大值
// t.findFirst(1, l, r, func(nodeMax int) bool { return nodeMax >= target })
// 调用时 o=1
func (t lazySeg) findFirst(o, l, r int, f func(int) bool) int {
if t[o].l > r || t[o].r < l || !f(t[o].sum) {
return -1
}
if t[o].l == t[o].r {
return t[o].l
}
t.spread(o)
idx := t.findFirst(o<<1, l, r, f)
if idx < 0 {
idx = t.findFirst(o<<1|1, l, r, f)
}
return idx
}
// 线段树二分：返回 [l,r] 内最后一个满足 f 的下标，如果不存在，返回 -1
// 例如查询 [l,r] 内最后一个小于等于 target 的元素下标，需要线段树维护区间最小值
// t.findLast(1, l, r, func(nodeMin int) bool { return nodeMin <= target })
// 调用时 o=1
func (t lazySeg) findLast(o, l, r int, f func(int) bool) int {
if t[o].l > r || t[o].r < l || !f(t[o].sum) {
return -1
}
if t[o].l == t[o].r {
return t[o].l
}
t.spread(o)
idx := t.findLast(o<<1|1, l, r, f)
if idx < 0 {
idx = t.findLast(o<<1, l, r, f)
}
return idx
}
// a 的下标从 0 开始，线段树的区间下标也从 0 开始
func newLazySegmentTree(a []int) lazySeg {
n := len(a)
if n == 0 {
panic("slice can't be empty")
}
t := make(lazySeg, 2<<bits.Len(uint(n-1)))
t.build(a, 1, 0, n-1)
return t
}
// EXTRA: 适用于需要提取所有元素值的场景
// https://atcoder.jp/contests/abc332/tasks/abc332_f
func (t lazySeg) spreadAll(o int) {
if t[o].l == t[o].r {
return
}
t.spread(o)
t.spreadAll(o << 1)
t.spreadAll(o<<1 | 1)
}
//
// 动态开点线段树·其一·单点修改
// 注：如果 TLE 可以使用 func init() { debug.SetGCPercent(-1) } 加速
// LC327 https://leetcode.cn/problems/count-of-range-sum/
// LC2770 https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/ 1533
// LC2736 https://leetcode.cn/problems/maximum-sum-queries/ 2533
// https://codeforces.com/problemset/problem/2000/H 2200
// - 相似题目 https://www.luogu.com.cn/problem/P2894
// todo https://codeforces.com/problemset/problem/1614/E 2600
// https://atcoder.jp/contests/abc351/tasks/abc351_f
// 树套树见 fenwick_tree.go
var emptyStNode = &stNode{val: stNodeDefaultVal}
func init() {
emptyStNode.lo = emptyStNode
emptyStNode.ro = emptyStNode
}
const stNodeDefaultVal = 0 // 如果求最大值并且有负数，改成 math.MinInt
type stNode struct {
lo, ro *stNode
l, r int
val int
}
func (stNode) mergeInfo(a, b int) int {
return max(a, b)
}
func (o *stNode) maintain() {
// 注意这里没有判断 o.lo 和 o.ro 是空的，因为用的 emptyStNode
o.val = o.mergeInfo(o.lo.val, o.ro.val)
}
func (o *stNode) update(i, val int) {
if o.l == o.r {
o.val = o.mergeInfo(o.val, val)
return
}
m := (o.l + o.r) >> 1 // 使用右移而不是除法，这样保证负数也是下取整 或者 o.l + (o.r - o.l) / 2
if i <= m {
if o.lo == emptyStNode {
o.lo = &stNode{lo: emptyStNode, ro: emptyStNode, l: o.l, r: m, val: stNodeDefaultVal}
}
o.lo.update(i, val)
} else {
if o.ro == emptyStNode {
o.ro = &stNode{lo: emptyStNode, ro: emptyStNode, l: m + 1, r: o.r, val: stNodeDefaultVal}
}
o.ro.update(i, val)
}
o.maintain()
}
func (o *stNode) query(l, r int) int {
if o == emptyStNode || l > o.r || r < o.l {
return stNodeDefaultVal
}
if l <= o.l && o.r <= r {
return o.val
}
return o.mergeInfo(o.lo.query(l, r), o.ro.query(l, r))
}
// 询问范围的最小值、最大值
// 0 1e9
// -2e9 2e9
func newStRoot(l, r int) *stNode {
return &stNode{lo: emptyStNode, ro: emptyStNode, l: l, r: r, val: stNodeDefaultVal}
}
// 动态开点线段树·其二·延迟标记（区间修改）
// https://codeforces.com/problemset/problem/915/E（注：此题有多种解法）
// https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/F https://www.luogu.com.cn/problem/P5848
//（内存受限）https://codeforces.com/problemset/problem/1557/D
var emptyLazyNode = &lazyNode{sum: lazyNodeDefaultVal, todo: lazyNodeDefaultTodoVal}
func init() {
emptyLazyNode.lo = emptyLazyNode
emptyLazyNode.ro = emptyLazyNode
}
const lazyNodeDefaultVal = 0
const lazyNodeDefaultTodoVal = 0
type lazyNode struct {
lo, ro *lazyNode
l, r int
sum int // info
todo int
}
func (lazyNode) mergeInfo(a, b int) int {
return a + b // max(a, b)
}
func (lazyNode) mergeTodo(a, b int) int {
return a + b // max(a, b)
}
func (o *lazyNode) apply(f int) {
o.sum += (o.r - o.l + 1) * f // % mod
o.todo = o.mergeTodo(f, o.todo) // % mod
}
func (o *lazyNode) maintain() {
o.sum = o.mergeInfo(o.lo.sum, o.ro.sum)
}
func (o *lazyNode) spread() {
m := (o.l + o.r) >> 1
if o.lo == emptyLazyNode {
o.lo = &lazyNode{lo: emptyLazyNode, ro: emptyLazyNode, l: o.l, r: m, sum: lazyNodeDefaultVal, todo: lazyNodeDefaultTodoVal}
}
if o.ro == emptyLazyNode {
o.ro = &lazyNode{lo: emptyLazyNode, ro: emptyLazyNode, l: m + 1, r: o.r, sum: lazyNodeDefaultVal, todo: lazyNodeDefaultTodoVal}
}
if f := o.todo; f != lazyNodeDefaultTodoVal {
o.lo.apply(f)
o.ro.apply(f)
o.todo = lazyNodeDefaultTodoVal
}
}
func (o *lazyNode) update(l, r int, add int) {
if l <= o.l && o.r <= r {
o.apply(add)
return
}
o.spread()
m := (o.l + o.r) >> 1
if l <= m {
o.lo.update(l, r, add)
}
if m < r {
o.ro.update(l, r, add)
}
o.maintain()
}
func (o *lazyNode) query(l, r int) int {
if o == emptyLazyNode || l > o.r || r < o.l {
return lazyNodeDefaultVal
}
if l <= o.l && o.r <= r {
return o.sum
}
o.spread()
lRes := o.lo.query(l, r)
rRes := o.ro.query(l, r)
return o.mergeInfo(lRes, rRes)
}
// 询问范围的最小值、最大值
// 0 1e9
// -2e9 2e9
func newLazyRoot(l, r int) *lazyNode {
return &lazyNode{lo: emptyLazyNode, ro: emptyLazyNode, l: l, r: r, sum: lazyNodeDefaultVal, todo: lazyNodeDefaultTodoVal}
}
// EXTRA: 线段树合并
// https://www.luogu.com.cn/problem/P5494
// todo 一些题目 https://www.luogu.com.cn/blog/styx-ferryman/xian-duan-shu-ge-bing-zong-ru-men-dao-fang-qi
// https://codeforces.com/blog/entry/83969
// https://www.luogu.com.cn/problem/P4556
// https://www.luogu.com.cn/problem/P5298
// https://codeforces.com/problemset/problem/600/E
// rt = rt.merge(rt2)
func (o *stNode) merge(b *stNode) *stNode {
if o == nil {
return b
}
if b == nil {
return o
}
if o.l == o.r {
// 按照所需合并，如加法
o.val += b.val
return o
}
o.lo = o.lo.merge(b.lo)
o.ro = o.ro.merge(b.ro)
o.maintain()
return o
}
// EXTRA: 线段树分裂
// 将区间 [l,r] 从 o 中分离到 b 上
// https://www.luogu.com.cn/blog/cyffff/talk-about-segument-trees-split
// https://www.luogu.com.cn/problem/P5494
// rt, rt2 := rt.split(nil, l, r)
func (o *stNode) split(b *stNode, l, r int) (*stNode, *stNode) {
if o == emptyStNode || l > o.r || r < o.l {
return o, emptyStNode
}
if l <= o.l && o.r <= r {
return emptyStNode, o
}
if b == emptyStNode {
b = &stNode{lo: emptyStNode, ro: emptyStNode, l: o.l, r: o.r, val: stNodeDefaultVal}
}
o.lo, b.lo = o.lo.split(b.lo, l, r)
o.ro, b.ro = o.ro.split(b.ro, l, r)
o.maintain()
b.maintain()
return o, b
}
// 权值线段树求第 k 小
// 调用前需保证 1 <= k <= root.val
func (o *stNode) kth(k int) int {
if o.l == o.r {
return o.l
}
cntL := o.lo.val
if k <= cntL {
return o.lo.kth(k)
}
return o.ro.kth(k - cntL)
}
//
// 线段树分治
// todo https://www.luogu.com.cn/problem/P5787
// https://codeforces.com/problemset/problem/1140/F 2600
// 可持久化线段树（又称函数式线段树、主席树） Persistent Segment Tree
// https://oi-wiki.org/ds/persistent-seg/
// 静态+动态 https://www.acwing.com/blog/content/487/
// https://zhuanlan.zhihu.com/p/250565583
// https://blog.csdn.net/weixin_43914593/article/details/108861279
//
// 数组写法 https://codeforces.com/problemset/submission/840/254783792
// https://codeforces.com/problemset/submission/323/250523407
// 数组大小 n * (bits.Len(n-1) + 3)
//
// 另见 union_find.go 中的「可持久化并查集」
//
// 模板题 https://www.luogu.com.cn/problem/P3919
// https://www.luogu.com.cn/problem/P3834
// https://ac.nowcoder.com/acm/contest/7613/C
// https://atcoder.jp/contests/abc253/tasks/abc253_f 区间更新单点查询
// https://codeforces.com/problemset/problem/1262/D2 1800 *在线做法
// https://codeforces.com/problemset/problem/484/E 2500 二分，转换成找最长的已填入数字的区间，做法类似最大子段和
// https://codeforces.com/problemset/problem/840/D 2500
// todo 种类数 https://codeforces.com/problemset/problem/620/E
// https://codeforces.com/problemset/problem/786/C
// 差分 https://codeforces.com/problemset/problem/813/E
// https://codeforces.com/problemset/problem/837/G
// https://codeforces.com/problemset/problem/893/F 2300 与 DFS序+深度 结合
// https://codeforces.com/problemset/problem/961/E（不止一种做法）
type pstNode struct {
lo, ro *pstNode
l, r int // 注：如果 MLE 请换成传参的写法，或者使用数组版本
sum int
}
func (pstNode) mergeInfo(a, b int) int {
return a + b // 根据题目修改
}
// t := make([]*pstNode, 1, maxVersion+1)
// t[0] = buildPST(a, 0, len(a)-1)
// 或者 t := []*pstNode{buildPST(a, 0, len(a)-1)}
func buildPST(a []int, l, r int) *pstNode {
o := &pstNode{l: l, r: r}
if l == r {
o.sum = a[l]
return o
}
m := (l + r) >> 1
o.lo = buildPST(a, l, m)
o.ro = buildPST(a, m+1, r)
o.maintain()
return o
}
// 一般写法是更新到当前版本，然后把返回的新版本加在 t 的末尾，即
// t = append(t, t[len(t)-1].modify(i, add))
// t[i] = t[i-1].modify(i, add)
// 注意为了拷贝一份 pstNode，这里的接收器不是指针
func (o pstNode) modify(i int, add int) *pstNode {
if o.l == o.r {
o.sum += add
return &o
}
m := (o.l + o.r) >> 1
if i <= m {
o.lo = o.lo.modify(i, add)
} else {
o.ro = o.ro.modify(i, add)
}
o.maintain()
return &o
}
func (o *pstNode) maintain() {
o.sum = o.mergeInfo(o.lo.sum, o.ro.sum)
}
func (o *pstNode) queryRange(l, r int) int {
if l <= o.l && o.r <= r {
return o.sum
}
m := (o.l + o.r) >> 1
if r <= m {
return o.lo.queryRange(l, r)
}
if m < l {
return o.ro.queryRange(l, r)
}
vl := o.lo.queryRange(l, r)
vr := o.ro.queryRange(l, r)
return o.mergeInfo(vl, vr)
}
// 区间更新（只能配合单点查询）
// 调用前需要拷贝一份 root 节点
// 需要保证 add 非负
// https://atcoder.jp/contests/abc253/tasks/abc253_f
func (o *pstNode) update(l, r int, add int) {
if l <= o.l && o.r <= r {
o.sum += add
return
}
lo := *o.lo
o.lo = &lo
ro := *o.ro
o.ro = &ro
if add := o.sum; add > 0 {
o.lo.sum += add
o.ro.sum += add
o.sum = 0
}
m := (o.l + o.r) >> 1
if l <= m {
o.lo.update(l, r, add)
}
if r > m {
o.ro.update(l, r, add)
}
}
// 单点查询，配合上面的区间更新使用
func (o *pstNode) querySingle(i int) int {
if o.l == o.r {
return o.sum
}
m := (o.l + o.r) >> 1
if i <= m {
return o.sum + o.lo.querySingle(i)
}
return o.sum + o.ro.querySingle(i)
}
// 主席树相当于对数组的每个前缀建立一棵线段树
// 离散化时，求 kth 需要将相同元素也视作不同的
// 附：Wavelet Trees https://codeforces.com/blog/entry/52854 https://ideone.com/Tkters
// 题目见上
// EXTRA: 查询区间 [l,r] 中第 k 小（k 从 1 开始）的数
// 初始 t[0] = buildPST(1, len(a))
// t[i+1] = t[i].update(kth[i], 1) kth[i] 为 a[i] 离散化后的值（从 1 开始）
// 查询 t[r].kth(t[l-1], k) 类似前缀和 [l,r] 1<=l<=r<=n
// https://www.luogu.com.cn/problem/P2617
// https://codeforces.com/problemset/problem/840/D
func (o *pstNode) kth(old *pstNode, k int) int {
if o.l == o.r {
return o.l
}
cntL := o.lo.sum - old.lo.sum
if k <= cntL {
return o.lo.kth(old.lo, k)
}
return o.ro.kth(old.ro, k-cntL)
}
// EXTRA: 查询区间 [l,r] 中 val 的出现次数
// t[r].query(t[l-1], val)
// https://codeforces.com/problemset/problem/840/D
func (o *pstNode) query(old *pstNode, val int) int {
if o.l == o.r {
return o.sum - old.sum
}
m := (o.l + o.r) >> 1
if val <= m {
return o.lo.query(old.lo, val)
}
return o.ro.query(old.ro, val)
}
// todo EXTRA: rank
// 二分答案？
// 在线二维数点
// 查询区间 [l,r] 中在 [low,high] 范围内的元素个数
// low 和 high 为离散化后的值（从 1 开始）
// 离线二维数点见 fenwick_tree.go 中的 areaPointCountOffline
// https://codeforces.com/problemset/problem/323/C 2400
// https://codeforces.com/problemset/problem/538/F 2200
// http://acm.hdu.edu.cn/showproblem.php?pid=4417
// 调用方式同上 t[r].countRange(t[l-1], low, high)
func (o *pstNode) countRange(old *pstNode, low, high int) int {
if high < o.l || o.r < low {
return 0
}
if low <= o.l && o.r <= high {
return o.sum - old.sum
}
m := (o.l + o.r) >> 1
if high <= m {
return o.lo.countRange(old.lo, low, high)
}
if m < low {
return o.ro.countRange(old.ro, low, high)
}
return o.lo.countRange(old.lo, low, high) + o.ro.countRange(old.ro, low, high)
}
// EXTRA: countDiff 区间不同元素个数
// 做法是维护左侧相同元素的位置
// todo 参考 https://www.luogu.com.cn/problem/solution/SP3267
// https://www.luogu.com.cn/problem/P1972
// https://www.luogu.com.cn/problem/SP3267
// EXTRA: 区间绝对众数及其出现次数（注意返回的众数是离散化后的值）
// 没找到时返回的 mode = -1
// 题目链接见最上
// 调用方式 t[r].countMode(t[l-1], k)，取 k = (r-l+2)/2，即区间长度一半的上取整
// 这种 k 值使得递归时左右儿子至多调用其中一个
func (o *pstNode) countMode(old *pstNode, k int) (mode, count int) {
if o.l == o.r {
return o.l, o.sum - old.sum
}
if o.lo.sum-old.lo.sum >= k {
return o.lo.countMode(old.lo, k)
}
if o.ro.sum-old.ro.sum >= k {
return o.ro.countMode(old.ro, k)
}
return -1, 0