-
Notifications
You must be signed in to change notification settings - Fork 641
/
Copy pathcommon.go
2513 lines (2284 loc) · 94.6 KB
/
common.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 (
"maps"
"math"
"math/bits"
"math/rand"
"reflect"
"slices"
"sort"
"unsafe"
)
/*
如何科学刷题？ https://leetcode.cn/circle/discuss/RvFUtj/
1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针） https://leetcode.cn/circle/discuss/0viNMK/
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小） https://leetcode.cn/circle/discuss/SqopEo/
3. 单调栈（基础/矩形面积/贡献法/最小字典序） https://leetcode.cn/circle/discuss/9oZFK9/
4. 网格图（DFS/BFS/综合应用） https://leetcode.cn/circle/discuss/YiXPXW/
5. 位运算（基础/性质/拆位/试填/恒等式/思维） https://leetcode.cn/circle/discuss/dHn9Vk/
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径） https://leetcode.cn/circle/discuss/01LUak/
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望） https://leetcode.cn/circle/discuss/tXLS3i/
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树） https://leetcode.cn/circle/discuss/mOr1u6/
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法） https://leetcode.cn/circle/discuss/IYT3ss/
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造） https://leetcode.cn/circle/discuss/g6KTKL/
11. 链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA） https://leetcode.cn/circle/discuss/K0n2gO/
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机） https://leetcode.cn/circle/discuss/SJFwQI/
https://leetcode.cn/studyplan/primers-list/
https://leetcode.cn/studyplan/programming-skills/ 可选
字符串基础
https://codeforces.com/problemset/problem/1101/B
https://leetcode.cn/problems/apply-operations-to-make-string-empty/
暴力枚举
https://codeforces.com/problemset/problem/681/B 1300
- [2207. 字符串中最多数目的子序列](https://leetcode.cn/problems/maximize-number-of-subsequences-in-a-string/) 1550
另见 search.go
枚举右，维护左
- [1. 两数之和](https://leetcode.cn/problems/two-sum/)
- https://codeforces.com/problemset/problem/702/B
- [1512. 好数对的数目](https://leetcode.cn/problems/number-of-good-pairs/) 1161 经典题
- https://leetcode.cn/problems/sum-of-digit-differences-of-all-pairs/
- 反向构造 https://codeforces.com/problemset/problem/1927/B 900
https://leetcode.com/discuss/interview-question/3685049/25-variations-of-Two-sum-question
https://atcoder.jp/contests/abc342/tasks/abc342_d
https://codeforces.com/problemset/problem/1420/B 1200
https://codeforces.com/problemset/problem/318/B 1300 子串
https://codeforces.com/problemset/problem/1926/D 1300
https://codeforces.com/problemset/problem/159/D 1500 回文子串
https://codeforces.com/problemset/problem/1800/F 1900 异或
枚举右，维护左：需要维护两种值（pair）
https://codeforces.com/problemset/problem/1931/D 1300
https://leetcode.cn/problems/count-beautiful-substrings-ii/ 2445
枚举中间
https://codeforces.com/problemset/problem/1957/D 1900 前后缀分解 从高到低思考
https://atcoder.jp/contests/abc102/tasks/arc100_b 1801=CF2073
任意下标 i 和 j
https://codeforces.com/problemset/problem/1895/C 1400
哈希表
- [2260. 必须拿起的最小连续卡牌数](https://leetcode.cn/problems/minimum-consecutive-cards-to-pick-up/) 1365
- [982. 按位与为零的三元组](https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/) 2085
- [面试题 16.21. 交换和](https://leetcode.cn/problems/sum-swap-lcci/)
前缀和
https://codeforces.com/problemset/problem/466/C
前缀和+哈希表（双变量思想）
- [560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/)
- 子数组中的和为 k 的子数组的个数之和 https://codeforces.com/problemset/problem/1996/E 1600
- [974. 和可被 K 整除的子数组](https://leetcode.cn/problems/subarray-sums-divisible-by-k/) 1676
- 变形：乘积可以被 k 整除
- a[i] = gcd(a[i], k) 之后窗口乘积是 k 的倍数就行，不会乘爆
https://atcoder.jp/contests/abc146/tasks/abc146_e 1762
https://atcoder.jp/contests/abc233/tasks/abc233_d
交错前缀和 https://codeforces.com/contest/1915/problem/E
https://codeforces.com/problemset/problem/1446/D1 2600 转换
https://www.luogu.com.cn/problem/AT_joisc2014_h 三个字母映射到一些大整数上，从而区分开
前缀和思想 LC1523 https://leetcode.cn/problems/count-odd-numbers-in-an-interval-range/
有点数形结合 https://codeforces.com/problemset/problem/1748/C
前缀和的前缀和（二重前缀和）
LC2281 https://leetcode.cn/problems/sum-of-total-strength-of-wizards/
https://atcoder.jp/contests/abc058/tasks/arc071_b
前缀和+异或
模 3 & 字符集大小为 n https://codeforces.com/problemset/problem/1418/G 2500
https://atcoder.jp/contests/abc295/tasks/abc295_d
https://ac.nowcoder.com/acm/contest/75174/E
https://leetcode.cn/problems/find-longest-subarray-lcci/
https://codeforces.com/problemset/problem/1296/C
前后缀分解
部分题目也可以用状态机 DP 解决
- [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/)（[视频讲解](https://www.bilibili.com/video/BV1Qg411q7ia/?t=3m05s)）
注：带修改的接雨水 https://codeforces.com/gym/104821/problem/M
- https://www.zhihu.com/question/627281278/answer/3280684055
- 全排列接雨水 https://atcoder.jp/contests/tenka1-2015-final/tasks/tenka1_2015_final_e
- [926. 将字符串翻转到单调递增](https://leetcode.cn/problems/flip-string-to-monotone-increasing/)
- https://codeforces.com/problemset/problem/180/C 1400
- https://codeforces.com/problemset/problem/846/A 1500
https://codeforces.com/problemset/problem/234/C 1300
https://codeforces.com/problemset/problem/1178/B 1300
https://codeforces.com/problemset/problem/1443/B 1300
https://codeforces.com/problemset/problem/2026/B 1300 做到 O(n)
https://codeforces.com/problemset/problem/1706/C 1400
https://codeforces.com/problemset/problem/1980/D 1400 pairwise 的前后缀分解
https://codeforces.com/problemset/problem/2008/E 1500
https://codeforces.com/problemset/problem/1029/C 1600
https://codeforces.com/problemset/problem/2028/C 1600
https://codeforces.com/problemset/problem/2031/D 1700
https://codeforces.com/problemset/problem/1957/D 1900
https://codeforces.com/problemset/problem/1969/D 1900
https://codeforces.com/problemset/problem/1837/F 2400
https://codeforces.com/problemset/problem/2005/D 2400 GCD logTrick
昆明 2024：至多修改一个子数组 [L,R] ：把元素都加上 k，最大化整个数组的 GCD
- 预处理前后缀 GCD，由于前缀 GCD 只有 O(logU) 个不同的值，可以只枚举 O(logU) 个 L 和 O(n) 个 R，
- 枚举 R 的同时计算修改后的子数组 GCD，然后和前后缀 GCD 求 GCD
定长滑动窗口
https://codeforces.com/problemset/problem/716/B 1300
https://codeforces.com/problemset/problem/1955/D 1400
https://codeforces.com/problemset/problem/608/B 1500
https://codeforces.com/problemset/problem/1687/A 1600
https://codeforces.com/problemset/problem/69/E 1800
https://codeforces.com/problemset/problem/371/E 2000
不定长滑动窗口（求最长/最大）
- [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)
- 翻转至多一个任意子串后的无重复字符的最长子串 https://codeforces.com/contest/1234/problem/F
- [1658. 将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/) 1817
- https://codeforces.com/problemset/problem/1692/E 1200
与单调队列结合 https://www.luogu.com.cn/problem/P3594
https://codeforces.com/problemset/problem/1873/F 1300
https://codeforces.com/problemset/problem/1794/C 1300 式子变形
不定长滑动窗口（求最短/最小）
https://codeforces.com/problemset/problem/1354/B 1200
https://codeforces.com/problemset/problem/224/B 1500 和最小
https://codeforces.com/problemset/problem/701/C 1500
https://codeforces.com/problemset/problem/1777/C 1700
不定长滑动窗口（求子数组个数）
https://atcoder.jp/contests/abc130/tasks/abc130_d 和至少为 k 的子数组个数
https://codeforces.com/problemset/problem/550/B 变形：改成子数组
其它题目见【前缀和】
滑窗的同时维护数据
https://codeforces.com/problemset/problem/898/D 1600
多指针
https://codeforces.com/problemset/problem/602/B 入门题
https://codeforces.com/problemset/problem/279/B 入门题
https://codeforces.com/problemset/problem/1971/F 1600
https://atcoder.jp/contests/abc229/tasks/abc229_d
https://atcoder.jp/contests/abc098/tasks/arc098_b
较为复杂 https://atcoder.jp/contests/abc294/tasks/abc294_e
- https://ac.nowcoder.com/acm/contest/62033/D
https://codeforces.com/problemset/problem/1208/B
https://codeforces.com/problemset/problem/1765/D
https://codeforces.com/problemset/problem/895/B
https://codeforces.com/contest/1833/problem/F
计算有多少子数组，其中有至少 k 个相同的数 https://codeforces.com/problemset/problem/190/D
https://codeforces.com/problemset/problem/165/C
- [1099. 小于 K 的两数之和](https://leetcode.cn/problems/two-sum-less-than-k/)（会员题）
单序列双指针
LC2972 https://leetcode.cn/problems/count-the-number-of-incremovable-subarrays-ii/
- https://codeforces.com/problemset/problem/1167/E 2100
https://codeforces.com/contest/2032/problem/C 1400
双序列双指针
https://codeforces.com/contest/489/problem/B 1200
https://atcoder.jp/contests/abc312/tasks/abc312_f
相向双指针
题单 https://leetcode.cn/leetbook/read/sliding-window-and-two-pointers/odt2yh/
LC2824 https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/
LC923 https://leetcode.cn/problems/3sum-with-multiplicity/
https://www.facebook.com/codingcompetitions/hacker-cup/2023/practice-round/problems/C
同时用到同向双指针和相向双指针的题
https://atcoder.jp/contests/abc155/tasks/abc155_d
- 相似题目 https://leetcode.cn/problems/kth-smallest-product-of-two-sorted-arrays/
a[i] + b[j] <= target 的方案数
- 相向双指针
- LC2824 https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/
- https://codeforces.com/problemset/problem/1538/C 1300
- https://atcoder.jp/contests/abc366/tasks/abc366_e
- https://leetcode.cn/problems/3sum-smaller/
a[i] + b[j] >= target 的方案数
- 反向思维转换成 <，所有方案数减去 < 的方案数，就是 >= 的方案数，所以做法同上
- https://atcoder.jp/contests/abc353/tasks/abc353_c
a[i] - b[j] <= target 的方案数
- 同向双指针
- 另一种思路：把 b 数组取反再 reverse，就变成 a[i] + (-b[j]) <= target 了
a[i] - b[j] >= target 的方案数
- 反向思维转换成 <，所有方案数减去 < 的方案数，就是 >= 的方案数，所以做法同上
子数组元素和 = < > target 的方案数
- 用前缀和，转换成上面 a[i] - b[j] 的形式（= 可以转换成 <=t 减去 <=t-1）
子序列元素和 = < > target 的方案数
- 0-1 背包恰好/至多/至少，见 https://www.bilibili.com/video/BV16Y411v7Y6/ 末尾的总结
分组循环
https://leetcode.cn/problems/longest-even-odd-subarray-with-threshold/solution/jiao-ni-yi-ci-xing-ba-dai-ma-xie-dui-on-zuspx/
**适用场景**：按照题目要求，数组会被分割成若干组，每一组的判断/处理逻辑是相同的。
**核心思想**：
- 外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案最大值）。
- 内层循环负责遍历组，找出这一组最远在哪结束。
这个写法的好处是，各个逻辑块分工明确，也不需要特判最后一组（易错点）。以我的经验，这个写法是所有写法中最不容易出 bug 的，推荐大家记住。
见题单第六章 https://leetcode.cn/circle/discuss/0viNMK/
LC1180（会员）https://leetcode.cn/problems/count-substrings-with-only-one-distinct-letter/
LC2257 https://leetcode.cn/problems/count-unguarded-cells-in-the-grid/
- https://atcoder.jp/contests/abc317/tasks/abc317_e
LC2495（会员）逆向思维 https://leetcode.cn/problems/number-of-subarrays-having-even-product/
https://codeforces.com/problemset/problem/1272/C 1200
https://codeforces.com/problemset/problem/1343/C 1200
https://codeforces.com/problemset/problem/1821/C 1300 枚举答案
https://codeforces.com/problemset/problem/1873/F 1300
https://codeforces.com/problemset/problem/363/C 1400 分组循环的分组循环
https://codeforces.com/problemset/problem/1380/C 1400
https://codeforces.com/problemset/problem/620/C 1500
https://codeforces.com/problemset/problem/525/C 1600
https://codeforces.com/problemset/problem/1748/C 1600
https://codeforces.com/problemset/problem/1849/D 1700
https://codeforces.com/problemset/problem/2031/D 1700
哨兵
- [1465. 切割后面积最大的蛋糕](https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/) 1445
- [2975. 移除栅栏得到的正方形田地的最大面积](https://leetcode.cn/problems/maximum-square-area-by-removing-fences-from-a-field/) 1873
不是哨兵，但图像类似 [2943. 最大化网格图中正方形空洞的面积](https://leetcode.cn/problems/maximize-area-of-square-hole-in-grid/) 1677
巧妙枚举
LC939 https://leetcode.cn/problems/minimum-area-rectangle/
- [1577. 数的平方等于两数乘积的方法数](https://leetcode.cn/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/) 1594
LC3234 https://leetcode.cn/problems/count-the-number-of-substrings-with-dominant-ones/
- 这个代码的时间复杂度怎么证明？https://leetcode.cn/circle/discuss/GNUiDD/view/wPi6zR/
https://codeforces.com/problemset/problem/846/C 1800
https://codeforces.com/problemset/problem/1181/C 1900
https://codeforces.com/problemset/problem/1626/D 2100
https://codeforces.com/problemset/problem/339/E 2700
贪心及其证明
- [881. 救生艇](https://leetcode.cn/problems/boats-to-save-people/) 1530
- https://codeforces.com/problemset/problem/1690/E
- https://www.lanqiao.cn/problems/4174/learning/?contest_id=135
- https://codeforces.com/problemset/problem/1765/D
- [2350. 不可能得到的最短骰子序列](https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls/) 1961
- https://codeforces.com/problemset/problem/1924/A 1500 输出方案
- [1686. 石子游戏 VI](https://leetcode.cn/problems/stone-game-vi/) 2001
- https://codeforces.com/contest/1914/problem/E2 1400
- todo 复习 [2193. 得到回文串的最少操作次数](https://leetcode.cn/problems/minimum-number-of-moves-to-make-palindrome/) 2091
- todo 复习 [659. 分割数组为连续子序列](https://leetcode.cn/problems/split-array-into-consecutive-subsequences/)
https://codeforces.com/problemset/problem/1920/B 1100
https://codeforces.com/problemset/problem/1993/B 1100
https://codeforces.com/problemset/problem/2047/B ~1200 做到 O(n)
https://codeforces.com/problemset/problem/545/D 1300
https://codeforces.com/problemset/problem/1443/B 1300
https://codeforces.com/problemset/problem/1498/B 1300 从大到小贪心
https://codeforces.com/problemset/problem/1902/C 1300
https://codeforces.com/problemset/problem/388/A 1400
https://codeforces.com/problemset/problem/437/C 1400 排序不等式/交换论证法
https://codeforces.com/problemset/problem/492/C 1400
https://codeforces.com/problemset/problem/1369/C 1400
提示 1：前 k 大的数一定可以作为最大值。且尽量把大的数放在 w[i] = 1 的组中，这样可以计入答案两次。
如果某个前 k 大的数 x 没有作为最大值（其中一个组的最大值是不在前 k 大中的 y），那么把 x 和 y 交换，
如果 x 是某个组的最小值，那么交换后 y 必然也是最小值，此时答案不变。
如果 x 不是某个组的最小值（这个组的最小值是 z）：
如果 y 交换后变成了最小值，那么答案变大了 x-z。
如果 y 交换后也不是最小值，那么答案变大了 x-y。
无论如何，这样交换都不会使答案变小，因此前 k 大的数一定可以作为最大值。
提示 2：然后来说最小值。a 的最小值必然要分到某个组中，为了「跳过」尽量多的较小的数，优先把 a 中较小的数分到 w 较大的组中。所以 a 从小到大遍历，w 从大到小遍历。
https://codeforces.com/problemset/problem/1443/C 1400
https://codeforces.com/problemset/problem/1691/C 1400
https://codeforces.com/problemset/problem/1895/C 1400
https://codeforces.com/problemset/problem/1896/C 1400
https://codeforces.com/problemset/problem/864/D 1500
https://codeforces.com/problemset/problem/985/C 1500
https://codeforces.com/problemset/problem/1659/C 1500
https://codeforces.com/problemset/problem/1759/E 1500
https://codeforces.com/problemset/problem/1873/G 1500
https://codeforces.com/problemset/problem/1924/A 1500
https://codeforces.com/problemset/problem/913/C 1600
https://codeforces.com/problemset/problem/1707/A 1600 倒序思维
https://codeforces.com/problemset/problem/1157/C2 1700
https://codeforces.com/problemset/problem/1661/C 1700 奇数天+1 偶数天 +2
https://codeforces.com/problemset/problem/1995/B2 1700
https://codeforces.com/problemset/problem/2035/D 1800
https://codeforces.com/problemset/problem/2042/C 1800
https://codeforces.com/problemset/problem/3/B 1900
https://codeforces.com/problemset/problem/1479/B1 1900
https://codeforces.com/problemset/problem/1804/D 2000
https://codeforces.com/problemset/problem/1029/E 2100 树
https://codeforces.com/problemset/problem/1479/B2 2100
https://www.luogu.com.cn/blog/wsyhb/post-ti-xie-cf1479b1-painting-the-array-i
https://codeforces.com/problemset/problem/442/C 2500
如果 x>=y<=z，那么删除 y 最优
结束后剩下一个长为 m 的 /\ 形状的序列，由于无法取到最大值和次大值，那么加上剩下最小的 m-2 个数
https://atcoder.jp/contests/arc147/tasks/arc147_e 难
https://www.luogu.com.cn/problem/P1016
https://www.luogu.com.cn/problem/UVA11384 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2379
交换论证法
https://atcoder.jp/contests/arc149/tasks/arc149_b
https://codeforces.com/problemset/problem/437/C 1400 排序不等式
数学思维
https://codeforces.com/problemset/problem/23/C 2500
- https://codeforces.com/problemset/problem/798/D 2400
乘法贪心
https://codeforces.com/problemset/problem/1406/B 1200 5 个数的最大乘积
https://codeforces.com/problemset/problem/45/I 1400
https://codeforces.com/problemset/problem/934/A 1400
https://atcoder.jp/contests/abc173/tasks/abc173_e 1607=CF1926 k 个数的最大乘积
删除一个数后，最小化 k 个数的最大乘积
中位数贪心（右边数字为难度分） // 注：算长度用左闭右开区间思考，算中间值用闭区间思考 两个中位数分别是 a[(n-1)/2] 和 a[n/2]
有两种证明方法，见 https://leetcode.cn/problems/5TxKeK/solution/zhuan-huan-zhong-wei-shu-tan-xin-dui-din-7r9b/
【思考题】插入一个数再选定一个 x，每次操作 +x/-x，计算最小操作次数
https://codeforces.com/problemset/problem/710/B 1400
中位数相关 https://codeforces.com/problemset/problem/166/C 1500 *可以做到对不同的 x 用 O(log n) 时间回答
排序不等式
https://codeforces.com/problemset/problem/276/C 1500
https://codeforces.com/problemset/problem/1165/E 1600
相邻不同
每次取两个数减一，最后剩下的数最小 / 操作次数最多 https://cs.stackexchange.com/a/145450
- [1953. 你可以工作的最大周数](https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work/) 1804
- https://codeforces.com/problemset/problem/1579/D 1400
https://codeforces.com/problemset/problem/1521/E 2700 二维+对角不同
每次取数组中大于 0 的连续一段同时减 1，求使数组全为 0 的最少操作次数
https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/solutions/371326/xing-cheng-mu-biao-shu-zu-de-zi-shu-zu-zui-shao-ze/
https://codeforces.com/problemset/problem/448/C
邻项交换（最小代价排序/字典序最小） Exchange Arguments
https://codeforces.com/blog/entry/63533
某些题目和逆序对有关
LC1665. 完成所有任务的最少初始能量 https://leetcode.cn/problems/minimum-initial-energy-to-finish-tasks/ 1901
- https://www.luogu.com.cn/problem/P3619
https://codeforces.com/problemset/problem/1638/B 1100
https://codeforces.com/problemset/problem/920/C 1400
https://codeforces.com/problemset/problem/435/B 1400
https://codeforces.com/contest/246/problem/A 900
https://atcoder.jp/contests/arc147/tasks/arc147_b
https://atcoder.jp/contests/abc268/tasks/abc268_f
相邻两数之差的绝对值为 1 https://ac.nowcoder.com/acm/contest/65259/C
非邻项交换（最小代价排序/字典序最小）
某些题目可以在 i 到 a[i] 之间连边建图
LC1202 https://leetcode.cn/problems/smallest-string-with-swaps/ 1855
LC2948 https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/ 2047
https://codeforces.com/contest/252/problem/B
https://codeforces.com/problemset/problem/1768/D 1800
https://codeforces.com/contest/109/problem/D 2000
shift+reverse https://codeforces.com/contest/1907/problem/F
区间与点的最大匹配/覆盖问题
https://www.luogu.com.cn/problem/P2887
https://codeforces.com/problemset/problem/555/B
https://codeforces.com/problemset/problem/863/E
倒序
LC2718 https://leetcode.cn/problems/sum-of-matrix-after-queries/
- 加强版 https://www.luogu.com.cn/problem/P9715 ?contestId=126251
思维：观察、结论
- [2498. 青蛙过河 II](https://leetcode.cn/problems/frog-jump-ii/) 1759
- [782. 变为棋盘](https://leetcode.cn/problems/transform-to-chessboard/) 2430
https://codeforces.com/problemset/problem/1811/C 1100
https://codeforces.com/problemset/problem/1822/D 1200
https://codeforces.com/problemset/problem/1077/C 1300
https://codeforces.com/problemset/problem/1364/B 1300
https://codeforces.com/problemset/problem/1844/C 1300 假设答案是某些数之和，经过什么样的操作可以得到这些数？
https://codeforces.com/problemset/problem/1765/K 1500
https://codeforces.com/problemset/problem/1990/C 1500
https://codeforces.com/problemset/problem/1608/C 1700
https://codeforces.com/problemset/problem/1442/A 1800
https://codeforces.com/problemset/problem/558/C 1900
https://codeforces.com/problemset/problem/1744/F 2000
https://codeforces.com/problemset/problem/1610/E 2300
https://codeforces.com/problemset/problem/2004/F 2600
思维：脑筋急转弯
LC1503 https://leetcode.cn/problems/last-moment-before-all-ants-fall-out-of-a-plank/
LC2731 https://leetcode.cn/problems/movement-of-robots/
LC280 https://leetcode.cn/problems/wiggle-sort/
LC3012 https://leetcode.cn/problems/minimize-length-of-array-using-operations/
https://www.codechef.com/problems/CLEARARR 2037
https://codeforces.com/problemset/problem/2049/A 800
https://codeforces.com/problemset/problem/1632/B 1000 位运算 XOR
https://codeforces.com/problemset/problem/1708/B 1100
https://codeforces.com/problemset/problem/2044/D 1100
https://codeforces.com/problemset/problem/1009/B 1400
https://codeforces.com/problemset/problem/1883/F 1400
https://codeforces.com/problemset/problem/1904/C 1400
https://codeforces.com/problemset/problem/1012/A 1500
https://codeforces.com/problemset/problem/1169/B 1500
https://codeforces.com/problemset/problem/500/C 1600
https://codeforces.com/problemset/problem/601/A 1600
https://codeforces.com/problemset/problem/1763/C 2000
https://atcoder.jp/contests/abc194/tasks/abc194_e
https://atcoder.jp/contests/abc196/tasks/abc196_e
https://www.luogu.com.cn/problem/UVA10881 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1822
- [LCS 01. 下载插件](https://leetcode.cn/problems/Ju9Xwi/)
MEX
https://codeforces.com/problemset/problem/1793/D 1800
https://atcoder.jp/contests/abc194/tasks/abc194_e
注意值域
LC2653 https://leetcode.cn/problems/sliding-subarray-beauty/ 1786
LC2250 https://leetcode.cn/problems/count-number-of-rectangles-containing-each-point/ 1998
LC2857 https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/ 2082
LC1906 https://leetcode.cn/problems/minimum-absolute-difference-queries/ 2147
LC1766 https://leetcode.cn/problems/tree-of-coprimes/ 2232
LC2198 https://leetcode.cn/problems/number-of-single-divisor-triplets/（会员题）
注意指数/对数
LC2188 https://leetcode.cn/problems/minimum-time-to-finish-the-race/ 2315
LC2920 https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes/ 2351
枚举答案
https://codeforces.com/contest/1977/problem/C
构造
题单 https://www.luogu.com.cn/training/14#problems
LC767 https://leetcode.cn/problems/reorganize-string/
LC667 https://leetcode.cn/problems/beautiful-arrangement-ii/
LC2745 https://leetcode.cn/problems/construct-the-longest-new-string/ 1607
LC2573 https://leetcode.cn/problems/find-the-string-with-lcp/ 2682
LC3311 https://leetcode.cn/problems/construct-2d-grid-matching-graph-layout/
构造反例 https://leetcode.cn/problems/parallel-courses-iii/solution/tuo-bu-pai-xu-dong-tai-gui-hua-by-endles-dph6/2310439
构造 TLE 数据 https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805413/bitset-you-hua-0-1-bei-bao-by-endlessche-m1xn/comments/2320111
https://codeforces.com/problemset/problem/1927/B 900
https://codeforces.com/problemset/problem/1772/C 1000
https://codeforces.com/problemset/problem/1998/B 1000
https://codeforces.com/problemset/problem/2037/C 1000
https://codeforces.com/problemset/problem/2039/B 1000 分析性质
https://codeforces.com/problemset/problem/2040/B 1000
https://codeforces.com/problemset/problem/2044/D 1100 脑筋急转弯
https://atcoder.jp/contests/keyence2020/tasks/keyence2020_c 625=CF1183
https://codeforces.com/problemset/problem/482/A 1200
https://codeforces.com/problemset/problem/651/B 1200
https://codeforces.com/problemset/problem/1028/B 1200
https://codeforces.com/problemset/problem/1713/C 1200
https://codeforces.com/problemset/problem/1717/C 1300
https://codeforces.com/problemset/problem/1788/C 1300
https://codeforces.com/problemset/problem/1815/A 1300
https://codeforces.com/problemset/problem/1978/C 1300
https://codeforces.com/problemset/problem/2031/C 1300 数学
https://codeforces.com/problemset/problem/803/A 1400
https://codeforces.com/problemset/problem/1838/C 1400
https://codeforces.com/problemset/problem/1863/D 1400
https://codeforces.com/problemset/problem/1896/C 1400
https://codeforces.com/problemset/problem/1974/D 1400
https://codeforces.com/problemset/problem/1630/A 1500
https://codeforces.com/problemset/problem/1710/A 1500
https://codeforces.com/problemset/problem/1722/G 1500
https://codeforces.com/problemset/problem/1809/C 1500
https://codeforces.com/problemset/problem/1968/E 1600
https://codeforces.com/problemset/problem/201/A 1700
https://codeforces.com/problemset/problem/584/C 1700 分类讨论
https://codeforces.com/problemset/problem/1332/D 1700 给你一个错误代码，构造 hack 数据
https://codeforces.com/problemset/problem/1893/B 1700
https://codeforces.com/problemset/problem/142/B 1800 棋盘放最多的马
https://codeforces.com/problemset/problem/847/C 1800
https://codeforces.com/problemset/problem/1156/B 1800 相邻字母在字母表中不相邻
https://codeforces.com/problemset/problem/1267/L 1800
https://codeforces.com/problemset/problem/1304/D 1800 最短/最长 LIS
https://codeforces.com/problemset/problem/1554/D 1800
https://codeforces.com/problemset/problem/1965/B 1800 二进制分解
https://codeforces.com/problemset/problem/118/C 1900 贪心
https://codeforces.com/problemset/problem/327/D 1900
https://codeforces.com/problemset/problem/388/B 1900 两点间恰好 k 条最短路径
https://codeforces.com/problemset/problem/550/D 1900 度数均为 k 且至少（恰好）有一条割边
https://codeforces.com/problemset/problem/708/B 1900 分类讨论
https://codeforces.com/problemset/problem/1823/D 1900
https://codeforces.com/problemset/problem/1854/A2 1900 分类讨论
https://codeforces.com/problemset/problem/2040/D 1900 树 质数
https://atcoder.jp/contests/arc088/tasks/arc088_b 1646=CF1956
https://codeforces.com/problemset/problem/515/D 2000
https://codeforces.com/problemset/problem/1558/C 2000
https://codeforces.com/problemset/problem/1789/D 2200 推荐 位运算 把 X 变成 Y 不断靠近答案
https://codeforces.com/problemset/problem/1761/E 2400
https://codeforces.com/problemset/problem/1227/G 2600 证明是亮点
https://codeforces.com/problemset/problem/1521/E 2700 二维相邻不同
https://codeforces.com/problemset/problem/1838/F 3000 交互 二分
https://atcoder.jp/contests/arc145/tasks/arc145_a
https://atcoder.jp/contests/agc015/tasks/agc015_d bit OR
不好想到的构造
https://codeforces.com/contest/1659/problem/D
https://atcoder.jp/contests/abc178/tasks/abc178_f
https://codeforces.com/problemset/problem/1689/E 脑筋急转弯
https://codeforces.com/problemset/problem/1787/E
不变量（想一想，操作不会改变什么）
https://codeforces.com/problemset/problem/1881/D 1300
https://codeforces.com/problemset/problem/1365/F 2100 仍然对称
https://codeforces.com/problemset/problem/1775/E 2100 有点差分的味道，想想前缀和
https://atcoder.jp/contests/arc119/tasks/arc119_c 操作不影响交错和
不变量 2（总和）
把一个环形数组切两刀，分成两段，要求相等，求方案数 => 和为 sum(a)/2 的子数组个数
LC494 https://leetcode.cn/problems/target-sum/
行列独立
LC3189 https://leetcode.cn/problems/minimum-moves-to-get-a-peaceful-board/
分类讨论（部分题是易错题）
https://codeforces.com/problemset/problem/2039/B 1000
https://codeforces.com/problemset/problem/262/B 1200
https://codeforces.com/problemset/problem/1364/A 1200
https://codeforces.com/problemset/problem/870/C 1300
https://codeforces.com/problemset/problem/1698/C 1300
https://codeforces.com/problemset/problem/30/A 1400
https://codeforces.com/problemset/problem/45/I 1400
https://codeforces.com/problemset/problem/489/C 1400
https://codeforces.com/problemset/problem/934/A 1400
https://codeforces.com/problemset/problem/1009/B 1400 脑筋急转弯
https://codeforces.com/problemset/problem/1251/B 1400
https://codeforces.com/problemset/problem/1292/A 1400 也有简单写法
https://codeforces.com/problemset/problem/1605/C 1400
https://codeforces.com/problemset/problem/115/B 1500
https://codeforces.com/problemset/problem/960/B 1500
https://codeforces.com/problemset/problem/1051/C 1500
https://codeforces.com/problemset/problem/1180/B 1500
https://codeforces.com/problemset/problem/1250/L 1500
https://codeforces.com/problemset/problem/750/C 1600 *也有偏数学的做法
https://codeforces.com/problemset/problem/898/E 1600
https://codeforces.com/problemset/problem/1822/E 1600 样例给的挺良心的
https://codeforces.com/problemset/problem/1861/C 1600 好题！
https://codeforces.com/problemset/problem/1976/C 1600
https://codeforces.com/problemset/problem/1978/D 1600
https://atcoder.jp/contests/abc173/tasks/abc173_e 1607=CF1926 乘法
https://codeforces.com/problemset/problem/193/A 1700
https://codeforces.com/problemset/problem/382/C 1700
https://codeforces.com/problemset/problem/411/C 1700
https://codeforces.com/problemset/problem/1516/C 1700
https://codeforces.com/problemset/problem/1799/C 1700
https://codeforces.com/problemset/problem/1468/J 1800 MST
https://codeforces.com/problemset/problem/1833/G 1800 样例给的挺良心的
https://codeforces.com/problemset/problem/796/C 1900
https://codeforces.com/problemset/problem/1095/E 1900
https://codeforces.com/problemset/problem/1714/F 1900 锻炼代码实现技巧的好题
https://codeforces.com/problemset/problem/1914/F 1900
https://codeforces.com/problemset/problem/1088/D 2000
https://codeforces.com/problemset/problem/1763/C 2000
https://codeforces.com/problemset/problem/1978/E 2000
https://codeforces.com/problemset/problem/2051/F 2000
https://codeforces.com/problemset/problem/1811/F 2100
https://codeforces.com/problemset/problem/1798/E 2300
https://codeforces.com/problemset/problem/209/C 2400
https://codeforces.com/problemset/problem/1594/F 2400
https://codeforces.com/problemset/problem/1736/C2 2400
https://codeforces.com/problemset/problem/1761/E 2400
https://codeforces.com/problemset/problem/1832/D2 2400
https://codeforces.com/problemset/problem/599/E 2600
https://codeforces.com/problemset/problem/1016/F 2600
https://codeforces.com/problemset/problem/1730/E 2700
https://codeforces.com/gym/105139/problem/L
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c
https://atcoder.jp/contests/abc155/tasks/abc155_d
https://atcoder.jp/contests/abc125/tasks/abc125_d
https://atcoder.jp/contests/arc134/tasks/arc134_d 1998
- [335. 路径交叉](https://leetcode.cn/problems/self-crossing/)
- [2162. 设置时间的最少代价](https://leetcode.cn/problems/minimum-cost-to-set-cooking-time/) 1852
https://leetcode.cn/problems/maximize-the-number-of-partitions-after-operations/
https://leetcode.cn/problems/count-the-number-of-houses-at-a-certain-distance-ii/
大量分类讨论
https://codeforces.com/problemset/problem/2045/A 1700 做到 O(n)
https://codeforces.com/problemset/problem/796/C 1900
https://codeforces.com/problemset/problem/1647/D 1900
https://codeforces.com/problemset/problem/356/C 2100
https://codeforces.com/problemset/problem/460/D 2300
https://codeforces.com/problemset/problem/1527/D 2400
https://codeforces.com/problemset/problem/1374/E2 2500
https://atcoder.jp/contests/arc153/tasks/arc153_c +构造
https://atcoder.jp/contests/agc015/tasks/agc015_d
https://atcoder.jp/contests/abc164/tasks/abc164_f
LC420 https://leetcode.cn/problems/strong-password-checker/
LC3348 https://leetcode.cn/problems/smallest-divisible-digit-product-ii/ 可以避免大量分类讨论
LC3366 https://leetcode.cn/problems/minimum-array-sum/ 做到 O(nlogn)
LC1534 https://leetcode.cn/problems/count-good-triplets/ 做到 O(nlogU) 或者 O(nlogn)
贡献法
见数学题单 §2.5 节 https://leetcode.cn/circle/discuss/IYT3ss/
LC2681 https://leetcode.cn/problems/power-of-heroes/
- https://atcoder.jp/contests/arc116/tasks/arc116_b
LC2763 https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-subarrays/
- https://atcoder.jp/contests/abc390/tasks/abc390_f
更多贡献法题目，见 monotone_stack.go
https://codeforces.com/problemset/problem/2019/B 1200
https://codeforces.com/problemset/problem/1648/A 1400
https://codeforces.com/problemset/problem/1691/C 1400
https://codeforces.com/problemset/problem/1789/C 1500 好题！
https://codeforces.com/problemset/problem/383/A 1600 好题
https://codeforces.com/problemset/problem/1165/E 1600
https://codeforces.com/problemset/problem/1715/C 1700 也可以用增量法
https://atcoder.jp/contests/abc356/tasks/abc356_e 1506=CF1700
https://codeforces.com/problemset/problem/1777/D 1900 树
https://codeforces.com/problemset/problem/1788/D 2000 好题！
https://atcoder.jp/contests/abc390/tasks/abc390_f 1801=CF2073
https://codeforces.com/problemset/problem/912/D 2100
https://codeforces.com/problemset/problem/1808/D 2100
https://codeforces.com/problemset/problem/520/E 2200
https://codeforces.com/problemset/problem/1208/E 2200
https://codeforces.com/problemset/problem/2063/E 2300
https://codeforces.com/problemset/problem/749/E 2400
https://codeforces.com/problemset/problem/915/F 2400
https://codeforces.com/problemset/problem/2004/F 2600
https://atcoder.jp/contests/abc290/tasks/abc290_e 好题！
https://atcoder.jp/contests/abc159/tasks/abc159_f 与 0-1 背包结合
^+ https://atcoder.jp/contests/abc201/tasks/abc201_e
https://atcoder.jp/contests/abc384/tasks/abc384_f 恰好 -> 至少
https://atcoder.jp/contests/abc127/tasks/abc127_e 1938
https://atcoder.jp/contests/abc104/tasks/abc104_d 1739=CF2026
- 抄袭？https://codeforces.com/problemset/problem/1426/F 2000
https://www.lanqiao.cn/problems/12467/learning/?contest_id=167
https://codeforces.com/group/BJlsDCvlJO/contest/586547/problem/I
增量法
- [2262. 字符串的总引力](https://leetcode.cn/problems/total-appeal-of-a-string/) 2033
https://atcoder.jp/contests/abc371/tasks/abc371_e 一样的题目
结合线段树优化 DP https://codeforces.com/contest/833/problem/B 2200
- [828. 统计子串中的唯一字符](https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/) 2034
- [2916. 子数组不同元素数目的平方和 II](https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-ii/) 2816
https://codeforces.com/problemset/problem/1715/C 1700 也可以用贡献法
https://codeforces.com/problemset/problem/1428/F 2400
小模拟
LC2534 https://leetcode.cn/problems/time-taken-to-cross-the-door/
https://atcoder.jp/contests/abc279/tasks/abc279_f
中模拟
https://atcoder.jp/contests/abc319/tasks/abc319_f
其他
删除一个字符 + 删除最长连续前缀 https://codeforces.com/problemset/problem/1430/D
https://codeforces.com/problemset/problem/521/D
先撤销，再恢复
LC3187 https://leetcode.cn/problems/peaks-in-array/
合法括号字符串 (Regular Bracket Sequence, RBS)
https://codeforces.com/problemset/problem/1097/C 1400
https://codeforces.com/problemset/problem/1837/D 1400
https://codeforces.com/problemset/problem/990/C 1500
https://codeforces.com/problemset/problem/847/C 1800 构造
https://codeforces.com/problemset/problem/1821/E 2100
https://codeforces.com/problemset/problem/1830/C 2400
https://codeforces.com/problemset/problem/3/D 2600 反悔贪心（反悔堆）
= 变成 <= 或者 >=
求前缀和/后缀和
https://leetcode.cn/problems/maximum-product-of-the-length-of-two-palindromic-substrings/
连续性 + 上下界
https://atcoder.jp/contests/arc137/tasks/arc137_b
https://codeforces.com/contest/1695/problem/C
异类双变量：固定某变量统计另一变量的 [0,n)
EXTRA: 值域上的双变量，见 https://codeforces.com/contest/486/problem/D
同类双变量①：固定 i 统计 [0,n)
同类双变量②：固定 i 统计 [0,i-1]
套路：预处理数据（按照某种顺序排序/优先队列/BST/...），或者边遍历边维护，
然后固定变量 i，用均摊 O(1)~O(logn) 的复杂度统计范围内的另一变量 j
这样可以将复杂度从 O(n^2) 降低到 O(n) 或 O(nlogn)
https://codeforces.com/problemset/problem/1194/E
进阶：https://codeforces.com/problemset/problem/1483/D
删除一段的最长连续递增 CERC10D https://codeforces.com/gym/101487
统计量是二元组的情形 https://codeforces.com/problemset/problem/301/D
好题 空间优化 https://codeforces.com/contest/1830/problem/B
双变量+下取整：枚举分母，然后枚举分子的范围，使得在该范围内的分子/分母是一个定值
LC1862 https://leetcode.cn/problems/sum-of-floored-pairs/
https://codeforces.com/problemset/problem/1706/D2
利用前缀和实现巧妙的构造 https://www.luogu.com.cn/blog/duyi/qian-zhui-he
邻项修改->前缀和->单项修改 https://codeforces.com/problemset/problem/1254/B2 https://ac.nowcoder.com/acm/contest/7612/C
二进制枚举
https://www.luogu.com.cn/problem/UVA11464 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2459
横看成岭侧成峰
转换为距离的众数 https://codeforces.com/problemset/problem/1365/C
转换为差分数组 https://codeforces.com/problemset/problem/1110/E 2200
https://codeforces.com/problemset/problem/1442/A 1800
https://codeforces.com/problemset/problem/1700/C 1700
https://codeforces.com/problemset/problem/1779/D 改成修改长为 x 的数组？
https://www.luogu.com.cn/problem/P4552
转换为差 http://www.51nod.com/Challenge/Problem.html#problemId=1217
考虑每个点产生的贡献 https://codeforces.com/problemset/problem/1009/E
考虑每条边产生的负贡献 https://atcoder.jp/contests/abc173/tasks/abc173_f
考虑符合范围要求的贡献 https://codeforces.com/problemset/problem/1151/E
和式的另一视角。若每一项的值都在一个范围，不妨考虑另一个问题：值为 x 的项有多少个？https://atcoder.jp/contests/abc162/tasks/abc162_e
对所有排列考察所有子区间的性质，可以转换成对所有子区间考察所有排列。将子区间内部的排列和区间外部的排列加以区分，内部的性质单独研究，外部的当作 (n-(r-l))! 个排列 https://codeforces.com/problemset/problem/1284/C
从最大值入手 https://codeforces.com/problemset/problem/1381/B
等效性 LC1183 https://leetcode.cn/problems/maximum-number-of-ones/
LC1526 https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
置换 https://atcoder.jp/contests/abc250/tasks/abc250_e
排序+最小操作次数 https://codeforces.com/contest/1367/problem/F2
https://codeforces.com/contest/1830/problem/A
从绝对值最大的开始思考 https://codeforces.com/contest/351/problem/E
https://codeforces.com/problemset/problem/777/C 1600
棋盘染色 LC2577 https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/
https://codeforces.com/contest/1848/problem/A
others https://codeforces.com/blog/entry/118706
离线
由于所有的询问数据都给出了，我们可以通过修改询问的顺序，达到降低时间复杂度的效果。相应的，在线算法就是按照输入的顺序处理，来一个处理一个。
https://codeforces.com/problemset/problem/1932/C 1400
https://atcoder.jp/contests/abc375/tasks/abc375_f
https://atcoder.jp/contests/abc379/tasks/abc379_f
逆向思维 / 正难则反
不可行方案通常比可行方案好求
- [2171. 拿出最少数目的魔法豆](https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/) 1748
- [1354. 多次求和构造目标数组](https://leetcode.cn/problems/construct-target-array-with-multiple-sums/) 2015
LC803 https://leetcode.cn/problems/bricks-falling-when-hit/
LC936 https://leetcode.cn/problems/stamping-the-sequence/
LC1199 https://leetcode.cn/problems/minimum-time-to-build-blocks/
LC2382 https://leetcode.cn/problems/maximum-segment-sum-after-removals/
LCP52 https://leetcode.cn/problems/QO5KpG/
https://codeforces.com/problemset/problem/1792/C 1500
- 相似题目 https://codeforces.com/problemset/problem/1367/F1 2100
https://codeforces.com/problemset/problem/1882/B
https://codeforces.com/problemset/problem/712/C 1600
https://codeforces.com/problemset/problem/621/C 1700
https://codeforces.com/problemset/problem/1301/C 1700
https://codeforces.com/problemset/problem/1644/D 1700
https://codeforces.com/problemset/problem/1672/D 1700
https://codeforces.com/problemset/problem/1759/G 1900 求字典序最小，通常可以从大往小思考
https://codeforces.com/problemset/problem/1638/D 2000
https://codeforces.com/problemset/problem/571/A 2100
https://codeforces.com/problemset/problem/1919/D 2100
https://codeforces.com/problemset/problem/369/E 2200
删除变添加
https://codeforces.com/problemset/problem/295/B
https://leetcode.cn/problems/maximum-segment-sum-after-removals/
奇偶性
https://codeforces.com/problemset/problem/763/B
https://codeforces.com/problemset/problem/1270/E
https://codeforces.com/problemset/problem/1332/E 配对法：将合法局面与非法局面配对
LC932 https://leetcode.cn/problems/beautiful-array/ 分治
相邻 传递性
https://codeforces.com/problemset/problem/1582/E
归纳：solve(n)->solve(n-1) 或者 solve(n-1)->solve(n)
https://codeforces.com/problemset/problem/1517/C
https://codeforces.com/problemset/problem/412/D
https://codeforces.com/problemset/problem/266/C
见微知著：考察单个点的规律，从而推出全局规律
https://codeforces.com/problemset/problem/1510/K
LC1806 https://leetcode.cn/problems/minimum-number-of-operations-to-reinitialize-a-permutation/ 1491
「恰好」转换成「至少/至多」
https://codeforces.com/problemset/problem/1188/C
反悔贪心
另见 heap.go 中的「反悔堆」
https://djy-juruo.blog.luogu.org/qian-tan-fan-hui-tan-xin
https://www.jvruo.com/archives/1844/
https://www.cnblogs.com/nth-element/p/11768155.html
题单 https://www.luogu.com.cn/training/8793
LC1388 双向链表反悔贪心 https://leetcode.cn/problems/pizza-with-3n-slices/
LC2813 https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/
集合哈希
https://codeforces.com/problemset/problem/1394/B
https://www.luogu.com.cn/problem/P6688
操作树
和莫队类似，通过改变查询的顺序来优化复杂度
https://codeforces.com/problemset/problem/707/D
Golang 卡常技巧（注：关于 IO 的加速见 io.go）
对于存在海量小对象的情况（如 trie, treap 等），使用 debug.SetGCPercent(-1) 来禁用 GC，能明显减少耗时
对于可以回收的情况（如 append 在超过 cap 时），使用 debug.SetGCPercent(-1) 虽然会减少些许耗时，但若有大量内存没被回收，会有 MLE 的风险
其他情况下使用 debug.SetGCPercent(-1) 对耗时和内存使用无明显影响
对于多组数据的情况，若禁用 GC 会 MLE，可在每组数据的开头或末尾调用 runtime.GC() 或 debug.FreeOSMemory() 手动 GC
参考 https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/
https://zhuanlan.zhihu.com/p/77943973
128MB ~1e7 个 int64
256MB ~3e7 个 int64
512MB ~6e7 个 int64
1GB ~1e8 个 int64
如果没有禁用 GC 但 MLE，可以尝试 1.19 新增的 debug.SetMemoryLimit
例如 debug.SetMemoryLimit(200<<20)，其中 200 可以根据题目的约束来修改
具体见如下测试：
180<<20 1996ms 255100KB https://codeforces.com/contest/1800/submission/203769679
195<<20 779ms 257800KB https://codeforces.com/contest/1800/submission/203768086
200<<20 654ms 259300KB https://codeforces.com/contest/1800/submission/203768768
205<<20 764ms 220100KB https://codeforces.com/contest/1800/submission/203771041
210<<20 MLE
参考 https://go.dev/doc/gc-guide#Memory_limit
对于二维矩阵，以 make([][mx]int, n) 的方式使用，比 make([][]int, n) 嵌套 make([]int, m) 更高效（100MB 以上时可以快 ~150ms）
但需要注意这种方式可能会向 OS 额外申请一倍的内存
对比 https://codeforces.com/problemset/submission/375/118043978
https://codeforces.com/problemset/submission/375/118044262
函数内的递归 lambda 会额外消耗非常多的内存（100~200MB / 1e6 递归深度）
写在 main 里面 + slice MLE https://codeforces.com/contest/767/submission/174193385
写在 main 外面 + slice 188364KB https://codeforces.com/contest/767/submission/174194380
附：
写在 main 里面 + array 257424KB https://codeforces.com/contest/767/submission/174194515
写在 main 外面 + array 154500KB https://codeforces.com/contest/767/submission/174193693
在特殊情况下，改为手动模拟栈可以减少 > 100MB 的内存
见这题的 Go 提交记录 https://codeforces.com/problemset/problem/163/E
测试：哈希表用时是数组的 13 倍（本题瓶颈）
slice 249ms https://codeforces.com/problemset/submission/570/209063267
hashmap 3259ms https://codeforces.com/problemset/submission/570/209063603
bool to int
int(*(*uint8)(unsafe.Pointer(&boolVal)))
[]int to []int64
*(*[]int64)(unsafe.Pointer(&nums))
*/
// slice 作为 map 的 key
// 长度为 0 的 slice 对应空字符串
func intSliceAsMapKeyExample(cnt map[string]int, a []int) {
// 如果后面还会修改 a，可以先 copy 一份
// a = slices.Clone(a)
sh := (*reflect.SliceHeader)(unsafe.Pointer(&a))
sh.Len *= bits.UintSize / 8 // 装作 byte slice
s := *(*string)(unsafe.Pointer(sh))
cnt[s]++
}
func _() {
const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
pow10 := func(x int) int { return int(math.Pow10(x)) } // 底层实现是查表，不需要 round
// TIPS: dir4[i] 和 dir4[i^1] 互为相反方向
dir4 := []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右（网格）
// TIPS: dir4[i] 和 dir4[i^2] 互为相反方向
dir4 = []struct{ x, y int }{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 右下左上（网格，顺时针）
dir4 = []struct{ x, y int }{{0, 1}, {-1, 0}, {0, -1}, {1, 0}} // 右上左下（网格，逆时针）
dir4 = []struct{ x, y int }{{1, 0}, {0, -1}, {-1, 0}, {0, 1}} // 右下左上（坐标系，顺时针）
dir4 = []struct{ x, y int }{{1, 0}, {0, 1}, {-1, 0}, {0, -1}} // 右上左下（坐标系，逆时针）
dir4R := []struct{ x, y int }{{1, 1}, {-1, 1}, {-1, -1}, {1, -1}} // 斜向
/* 方向
- [1041. 困于环中的机器人](https://leetcode.cn/problems/robot-bounded-in-circle/) 1521
- [874. 模拟行走机器人](https://leetcode.cn/problems/walking-robot-simulation/) 1846
- [2069. 模拟行走机器人 II](https://leetcode.cn/problems/walking-robot-simulation-ii/) 1919
- [3443. K 次修改后的最大曼哈顿距离](https://leetcode.cn/problems/maximum-manhattan-distance-after-k-changes/) ~1900
*/
dir4 = []struct{ x, y int }{'W': {-1, 0}, 'E': {1, 0}, 'S': {0, -1}, 'N': {0, 1}} // 西东南北（坐标系）
dir4 = []struct{ x, y int }{'W': {0, -1}, 'E': {0, 1}, 'S': {1, 0}, 'N': {-1, 0}} // 西东南北（网格）
dir4 = []struct{ x, y int }{'L': {-1, 0}, 'R': {1, 0}, 'D': {0, -1}, 'U': {0, 1}} // 左右下上（坐标系）
dir4 = []struct{ x, y int }{'L': {0, -1}, 'R': {0, 1}, 'U': {-1, 0}, 'D': {1, 0}} // 左右下上（网格）
dir8 := []struct{ x, y int }{{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}} // 逆时针（坐标系）
dir8 = []struct{ x, y int }{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}} // 顺时针（矩阵）
dir8 = []struct{ x, y int }{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}} // 马走日
// https://codeforces.com/problemset/problem/1983/C 1400
perm3 := [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}}
perm4 := [][]int{
{0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1}, {0, 3, 1, 2}, {0, 3, 2, 1},
{1, 0, 2, 3}, {1, 0, 3, 2}, {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0},
{2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0}, {2, 3, 0, 1}, {2, 3, 1, 0},
{3, 0, 1, 2}, {3, 0, 2, 1}, {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0},
}
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
/*
关于上取整的计算，当 $a$ 和 $b$ 均为正整数时，我们有
$$
\left\lceil\dfrac{a}{b}\right\rceil = \left\lfloor\dfrac{a-1}{b}\right\rfloor + 1
$$
讨论 $a$ 被 $b$ 整除，和不被 $b$ 整除两种情况，可以证明上式的正确性。
*/
// - [1936. 新增的最少台阶数](https://leetcode.cn/problems/add-minimum-number-of-rungs/) 1323
// - [1785. 构成特定和需要添加的最少元素](https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum/) 1432
ceil := func(a, b int) int {
// assert a >= 0 && b > 0
if a == 0 {
return 0
}
return (a-1)/b + 1
}
// 另一种写法，无需考虑 a 为 0 的情况
ceil = func(a, b int) int {
return (a + b - 1) / b
}
// 顺时针旋转矩阵 90°
// 返回一个拷贝
// Python3: list(zip(*reversed(a))) 或者 list(zip(*a[::-1]))
// 注：逆时针旋转矩阵 90° 就是 list(zip(*a))[::-1]
rotateCopy := func(a [][]int) [][]int {
n, m := len(a), len(a[0])
b := make([][]int, m)
for i := range b {
b[i] = make([]int, n)
}
for i, r := range a {
for j, v := range r {
b[j][n-1-i] = v
}
}
return b
}
rotate := rotateCopy
// 转置
transposeCopy := func(a [][]int) [][]int {
n, m := len(a), len(a[0])
b := make([][]int, m)
for i := range b {
b[i] = make([]int, n)
for j, r := range a {
b[i][j] = r[i]
}
}
return b
}
// 按顺序从小到大生成所有回文数
// https://oeis.org/A002113
// LC2967 https://leetcode.cn/problems/minimum-cost-to-make-array-equalindromic/
// LC906 https://leetcode.cn/problems/super-palindromes/
// LC2081 https://leetcode.cn/problems/sum-of-k-mirror-numbers/
// LC3272 https://leetcode.cn/problems/find-the-count-of-good-integers/
// EXTRA: 单个数字的情况 LC564 https://leetcode.cn/problems/find-the-closest-palindrome/
// https://codeforces.com/problemset/problem/897/B 1300
initPalindromeNumber := func() {
const mx int = 1e9
pal := []int{}
// 哨兵。根据题目来定，也可以设置成 -2e9 等
pal = append(pal, 0)
outer:
for base := 1; ; base *= 10 {
// 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999
for i := base; i < base*10; i++ {
x := i
for t := i / 10; t > 0; t /= 10 {
x = x*10 + t%10
}
if x > mx {
break outer
}
pal = append(pal, x)
}
// 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999
for i := base; i < base*10; i++ {
x := i
for t := i; t > 0; t /= 10 {
x = x*10 + t%10
}
if x > mx {
break outer
}
pal = append(pal, x)
}
}
// 哨兵。根据 mx 调整，如果 mx 是 2e9 的话要写成 mx+2
pal = append(pal, mx+1)
}
// 合并有序数组，保留重复元素