-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
2162 lines (1761 loc) · 383 KB
/
index.html
File metadata and controls
2162 lines (1761 loc) · 383 KB
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
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"blog.happypie.net","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","offset":12,"onmobile":false,"padding":18},"copycode":{"enable":true,"show_result":true,"style":"mac"},"back2top":{"enable":true,"sidebar":true,"scrollpercent":true},"bookmark":{"enable":true,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"nav":null,"lazyload":false},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
</script>
<meta property="og:type" content="website">
<meta property="og:title" content="Happier233的博客">
<meta property="og:url" content="https://blog.happypie.net/index.html">
<meta property="og:site_name" content="Happier233的博客">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="Happier233">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://blog.happypie.net/">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'zh-CN'
};
</script>
<title>Happier233的博客</title>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
<link rel="alternate" href="/atom.xml" title="Happier233的博客" type="application/atom+xml">
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container use-motion">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">Happier233的博客</h1>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="main-menu menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="home fa-fw"></i>首页</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section"><i class="tags fa-fw"></i>标签</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section"><i class="th fa-fw"></i>分类</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档</a>
</li>
<li class="menu-item menu-item-sitemap">
<a href="/sitemap.xml" rel="section"><i class="sitemap fa-fw"></i>站点地图</a>
</li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup">
<div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off"
placeholder="搜索..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div id="search-result">
<div id="no-result">
<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
</div>
</div>
</div>
</div>
</div>
</header>
<a role="button" class="book-mark-link book-mark-link-fixed"></a>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content index posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://blog.happypie.net/2021/07/25/xcpc/xcpc-optimize/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.jpg">
<meta itemprop="name" content="Happier233">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Happier233的博客">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/07/25/xcpc/xcpc-optimize/" class="post-title-link" itemprop="url">ACM题优化经验</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-07-25 00:30:00 / 修改时间：23:19:45" itemprop="dateCreated datePublished" datetime="2021-07-25T00:30:00+08:00">2021-07-25</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/" itemprop="url" rel="index"><span itemprop="name">XCPC</span></a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="为什么要优化"><a class="markdownIt-Anchor" href="#为什么要优化"></a> 为什么要优化</h1>
<p>如果一个算法的复杂度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span> ，那么实际耗时往往是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi>k</mi><mo>×</mo><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">T(n)=k \times f(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span>, <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span></span></span></span> 就是代码的常数，但常数过大的时候就有可能超时。有些出题人会有意无意地卡常数，这时候不会代码优化技巧，则有可能被卡常错失AC。另外有可能因为对底层机制的了解不够，而踩坑，导致非常数因素的大幅耗时，最终TLE。</p>
<p>有些出题人对算法是有要求的，那么有可能会刻意卡掉一些空间需求高的算法，那么需要学会计算内存空间和空间优化。</p>
<h1 id="时间优化技巧"><a class="markdownIt-Anchor" href="#时间优化技巧"></a> 时间优化技巧</h1>
<h2 id="io优化"><a class="markdownIt-Anchor" href="#io优化"></a> IO优化</h2>
<p>从最基本的算法无关的优化点开始，IO优化。在输入输出的时候，底层都是会涉及IO，那么有IO操作的地方，必定有IO耗时，这个是操作系统的知识，这里不展开。</p>
<p>如果全代码都只用到了scanf, printf, gets, putchar这一系列的C语言函数，则不需要考虑IO优化。</p>
<p>如果使用到了C++的cin/cout，则有几个点需要注意。</p>
<ol>
<li>在输入或输出上不可以将C和C++的IO库混用。例如：在输入上不可scanf, getchar 和 cin 混用；在输出上不可printf 和 cout 混用；但 scanf 和 cout 是可以混用的。</li>
<li>若使用到了C++的IO库，则需要在代码中添加以下3行代码。但由于添加这3行代码后，输出结果不会立刻出现在控制台，会导致本地调试的时候困难，所以推荐在本地编译的时候增加宏定义，来区分是否是本地环境。<strong>切记这个宏定义不可和OJ添加的宏定义重名。</strong></li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">ios_base::sync_with_stdio(<span class="literal">false</span>); <span class="comment">// 关闭c和c++的同步流</span></span><br><span class="line"><span class="built_in">cin</span>.tie(<span class="number">0</span>); <span class="comment">// 关闭cin的缓存流绑定</span></span><br><span class="line"><span class="built_in">cout</span>.tie(<span class="number">0</span>); <span class="comment">// 关闭cout的缓存流绑定</span></span><br></pre></td></tr></table></figure>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"><span class="meta">#<span class="meta-keyword">ifdef</span> ACM_LOCAL</span></span><br><span class="line"> freopen(<span class="string">"./data/std.in"</span>, <span class="string">"r"</span>, <span class="built_in">stdin</span>);</span><br><span class="line"> <span class="comment">// freopen("./data/std.out", "w", stdout);</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">else</span></span></span><br><span class="line"> ios_base::sync_with_stdio(<span class="literal">false</span>);</span><br><span class="line"> <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cout</span>.tie(<span class="number">0</span>);</span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">ifdef</span> ACM_LOCAL</span></span><br><span class="line"> <span class="keyword">auto</span> start = clock();</span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"> <span class="keyword">int</span> t = <span class="number">1</span>;</span><br><span class="line"><span class="comment">// cin >> t;</span></span><br><span class="line"> <span class="keyword">while</span> (t--)</span><br><span class="line"> solve();</span><br><span class="line"><span class="meta">#<span class="meta-keyword">ifdef</span> ACM_LOCAL</span></span><br><span class="line"> <span class="keyword">auto</span> end = clock();</span><br><span class="line"> <span class="built_in">cerr</span> << <span class="string">"Run Time: "</span> << <span class="keyword">double</span>(end - start) / CLOCKS_PER_SEC << <span class="string">"s"</span> << <span class="built_in">endl</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<ol start="3">
<li>由于C++的<code>endl</code>包含了<code>flush</code>，会导致输出流刷新。但由于内部机制，会使得输入流也发生同步行为，会导致IO耗时暴增，所以可以参考第二条，在非本地情况下将<code>endl</code>通过宏定义的方式，替换成 <code>'\n'</code>。</li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">ifndef</span> ACM_LOCAL</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> endl <span class="meta-string">'\n'</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br></pre></td></tr></table></figure>
<p>完整代码基础样板可以参考 <a href="https://github.com/happier233/ACM-Code/blob/master/00_%E5%A4%B4%E6%96%87%E4%BB%B6/00_Header.cpp" target="_blank" rel="noopener">https://github.com/happier233/ACM-Code/blob/master/00_头文件/00_Header.cpp</a></p>
<p>不建议在平时做题的时候经常使用快读模板，会养成坏习惯，在现场赛的时候往往没有时间去敲一份快读模板。正常情况下出题人不会硬卡IO的耗时，所以如果用快读模板过了题，但有可能去除快读还是会TLE，这说明你的算法没有达到正确的耗时要求。</p>
<p><strong>在开启IO优化的情况下，可以完全保证C++的cin, cout耗时和C的scanf, printf的耗时持平。</strong></p>
<h2 id="内存访问优化"><a class="markdownIt-Anchor" href="#内存访问优化"></a> 内存访问优化</h2>
<h3 id="介绍"><a class="markdownIt-Anchor" href="#介绍"></a> 介绍</h3>
<p>内存访问优化在于每次去读取特大的数组的时候，尽量保持连续的内存空间访问。<br />
先举个代码例子，用来求一个二维矩阵上的一个问题的代码，为了防止逻辑过于简单导致编译器优化，所以采取了一些方法屏蔽了编译器优化。</p>
<h3 id="测试代码"><a class="markdownIt-Anchor" href="#测试代码"></a> 测试代码</h3>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">10000</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> a[N][N], b[N][N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum1</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> s = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++) {</span><br><span class="line"> s += a[i][<span class="number">0</span>];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j < N; j++) {</span><br><span class="line"> a[i][j] += a[i][j - <span class="number">1</span>];</span><br><span class="line"> s += a[i][j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> s;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum2</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> s = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++) {</span><br><span class="line"> s += a[<span class="number">0</span>][i];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j < N; j++) {</span><br><span class="line"> a[j][i] += a[j - <span class="number">1</span>][i];</span><br><span class="line"> s += a[j][i];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> s;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">rnd</span><span class="params">()</span> </span>{</span><br><span class="line"> srand(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j < N; j++) {</span><br><span class="line"> b[i][j] = rand();</span><br><span class="line"> b[j][i] = b[i][j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">clone</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">memcpy</span>(b[<span class="number">0</span>], a[<span class="number">0</span>], N * N * <span class="keyword">sizeof</span>(<span class="keyword">int</span>));</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>{</span><br><span class="line"> rnd();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">clock_t</span> s, t;</span><br><span class="line"></span><br><span class="line"> clone();</span><br><span class="line"> s = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum1: %d\n"</span>, sum1());</span><br><span class="line"> t = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum1 clock delte: %lld\n"</span>, ll(t - s));</span><br><span class="line"></span><br><span class="line"> clone();</span><br><span class="line"> s = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum2: %d\n"</span>, sum2());</span><br><span class="line"> t = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum2 clock delte: %lld\n"</span>, ll(t - s));</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="输出结果"><a class="markdownIt-Anchor" href="#输出结果"></a> 输出结果</h3>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">sum1: -682505014</span><br><span class="line">sum1 clock delte: 90491</span><br><span class="line">sum2: -682505014</span><br><span class="line">sum2 clock delte: 782007</span><br></pre></td></tr></table></figure>
<h3 id="分析"><a class="markdownIt-Anchor" href="#分析"></a> 分析</h3>
<p>最终的输出结果可见产生了<strong>近10倍的耗时差距</strong>，这个耗时差距随着第二维增大而增大。接下来分析一下产生的原因。<br />
由于同一个数组的内存是连续的，不论是一维还是二维还是三维。</p>
<p>为了便于计算，对<code>int a[1024][1024]</code>，进行讨论那么如果<code>a[0][0]</code>是在地址<code>0x0000</code>，那么<code>a[1][0]</code>的内存地址是<code>0x1000</code>（<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1024</mn><mo>∗</mo><mn>4</mn></mrow><annotation encoding="application/x-tex">1024*4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord">0</span><span class="mord">2</span><span class="mord">4</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">4</span></span></span></span>，一个int是4字节)，<code>a[2][0]</code>的内存地址是<code>0x2000</code>。</p>
<p>因为CPU是有Cache机制的，为了降低访问内存的延时造成CPU空等，这个知识可以在计组和体系结构学到。所以在每次计算一次，需要访问4Kb的内存。CPU每次不是只读取一个int的内存，而是读取几百字节或者几k字节的，那么Cache命中率会大幅下降。但在 <code>sum1</code> 的写法中，CPU读取一次内存，可以进行几百次操作，可以大幅提高处理效率。</p>
<p>这个现象在写 dp 算法的时候尤其需要注意。不只是二维，在一维或者当维度变多的时候都适用。原则就是尽量访问靠近的内存。<strong>但不要刻意为了这个优化让代码变得过于复杂。</strong></p>
<h2 id="空间大小对时间的优化"><a class="markdownIt-Anchor" href="#空间大小对时间的优化"></a> 空间大小对时间的优化</h2>
<p>先给出测试代码和输出结果，就是一个简单的对数组求和。在数组的计算过程中，由于可能会爆int，所以有人干脆会把数组开成long long，但这在复杂数据结构中会产生巨大的耗时常数影响。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="keyword">int</span>(<span class="number">1e7</span>);</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MOD = <span class="keyword">int</span>(<span class="number">1e9</span> + <span class="number">7</span>);</span><br><span class="line"></span><br><span class="line">ll a[N];</span><br><span class="line"><span class="keyword">int</span> b[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>{</span><br><span class="line"> a[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i < N; i++) b[i] = a[i] = a[i - <span class="number">1</span>] * i % MOD;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>{</span><br><span class="line"> init();</span><br><span class="line"> <span class="keyword">clock_t</span> s, t;</span><br><span class="line"></span><br><span class="line"> s = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum1: %d\n"</span>, accumulate(a, a + N, <span class="number">0</span>));</span><br><span class="line"> t = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum1 clock delte: %lld\n"</span>, ll(t - s));</span><br><span class="line"></span><br><span class="line"> s = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum2: %d\n"</span>, accumulate(b, b + N, <span class="number">0</span>));</span><br><span class="line"> t = clock();</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"sum2 clock delte: %lld\n"</span>, ll(t - s));</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">sum1: -1246626476</span><br><span class="line">sum1 clock delte: 8125</span><br><span class="line">sum2: -1246626477</span><br><span class="line">sum2 clock delte: 3392</span><br></pre></td></tr></table></figure>
<p>可见，<strong>对a的求和时间是b的两倍多</strong>，这就直接让常数产生了翻倍，虽然实际算法中，对单个数组的访问不会占到大比例，但确实会产生影响，如果数据的结果是不会超出int的，并且对自己代码的耗时不确定能否通过的，建议修改成int进行存储。</p>
<h2 id="小技巧"><a class="markdownIt-Anchor" href="#小技巧"></a> 小技巧</h2>
<p>这些小技巧优化有限，虽然不知道具体导致这些代码编译后的差异何在，但实测的确有效果，主要受到编译器优化影响。</p>
<h3 id="取模连写"><a class="markdownIt-Anchor" href="#取模连写"></a> 取模连写</h3>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> a, b, c, mod; <span class="comment">// 假设a, b, mod都已经有实际值，这里不写具体值</span></span><br><span class="line"></span><br><span class="line">a = a * b % mod; <span class="comment">// 基础写法</span></span><br><span class="line">(a *= b) %= mod; <span class="comment">// 技巧</span></span><br><span class="line"></span><br><span class="line">a = ((a * b) % mod) + c) % mod; <span class="comment">// 基础写法</span></span><br><span class="line">((a *= b) %= mod) += c) %= mod; <span class="comment">// 技巧</span></span><br></pre></td></tr></table></figure>
<h3 id="减少取模次数"><a class="markdownIt-Anchor" href="#减少取模次数"></a> 减少取模次数</h3>
<p>假设 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>=</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></mrow><annotation encoding="application/x-tex">mod=10^9+7</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">o</span><span class="mord mathdefault">d</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.897438em;vertical-align:-0.08333em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">9</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">7</span></span></span></span>, 有2个二维非负整数矩阵 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>a</mi><mo separator="true">,</mo><mi>b</mi></mrow><annotation encoding="application/x-tex">a, b</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">a</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">b</span></span></span></span>，都是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>×</mo><mi>m</mi></mrow><annotation encoding="application/x-tex">n \times m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">m</span></span></span></span> 大小， <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo separator="true">,</mo><mi>m</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>1</mn><mo separator="true">,</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">n, m \in [1, 10^4]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7335400000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault">n</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">m</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span><span class="mclose">]</span></span></span></span>，其中所有值都有 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>a</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo separator="true">,</mo><msub><mi>b</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">a_{ij}, b_{ij} \in [0, 10^4]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span><span class="mclose">]</span></span></span></span>，求 $ \sum_{i=1}^n ((\sum_{j=1}^m {a_{ij}}) \times (\sum_{j=1}^m {b_{ij}})) \bmod MOD $</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">10005</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MOD = <span class="number">1000000007</span>;</span><br><span class="line"><span class="keyword">const</span> ll MOD2 = <span class="number">1l</span>l * MOD * MOD;</span><br><span class="line"><span class="keyword">int</span> a[N][N], b[N][N];</span><br><span class="line"></span><br><span class="line"><span class="comment">// 常规写法</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">calc1</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> s = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> <span class="keyword">int</span> sa = <span class="number">0</span>, sb = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < m; j++) {</span><br><span class="line"> (sa += a[i][j]) %= MOD;</span><br><span class="line"> (sb += a[i][j]) %= MOD;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> si = (<span class="number">1l</span>l * sa * sb) % MOD;</span><br><span class="line"> (s += si) %= MOD;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> s;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 一次优化写法</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">calc2</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span> </span>{</span><br><span class="line"> ll s = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> ll sa = <span class="number">0</span>, sb = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < m; j++) {</span><br><span class="line"> sa += a[i][j];</span><br><span class="line"> sb += b[i][j];</span><br><span class="line"> }</span><br><span class="line"> ll si = sa * sb;</span><br><span class="line"> (s += si) %= MOD;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> s;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 二次优化写法</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">calc3</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span> </span>{</span><br><span class="line"> ll s = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> ll sa = <span class="number">0</span>, sb = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < m; j++) {</span><br><span class="line"> sa += a[i][j];</span><br><span class="line"> sb += b[i][j];</span><br><span class="line"> }</span><br><span class="line"> ll si = sa * sb;</span><br><span class="line"> s += si;</span><br><span class="line"> <span class="keyword">if</span> (s >= MOD2) s -= MOD2;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> s % MOD;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 二次优化+偷懒写法</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">calc4</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span> </span>{</span><br><span class="line"> ll s = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> ll sa = accumulate(a[i], a[i] + m, <span class="number">0l</span>l);</span><br><span class="line"> ll sb = accumulate(b[i], b[i] + m, <span class="number">0l</span>l);</span><br><span class="line"> ll si = sa * sb;</span><br><span class="line"> s += si;</span><br><span class="line"> <span class="keyword">if</span> (s >= MOD2) s -= MOD2;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> s % MOD;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>可以看得出，在每层for里，calc1一共有4次取模，calc2只有1次取模。通过在线编译查看编译后的汇编代码，<a href="https://gcc.godbolt.org/" target="_blank" rel="noopener">https://gcc.godbolt.org/</a>，对比这2个代码的汇编，也可以确认calc1执行了4次取模。由于CPU对于取模的运算耗时是巨大的，所以降低取模次数，可以很好的降低常数。</p>
<p>一次优化原理如下，由于 $\sum_{j=1}^m {a_{ij}} $ 和 $ \sum_{j=1}^m {b_{ij}}$ 都在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>1</mn><msup><mn>0</mn><mn>8</mn></msup><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[0, 10^{8}]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">8</span></span></span></span></span></span></span></span></span><span class="mclose">]</span></span></span></span> 范围内，所以可以用 <code>long long</code> 存下，所以 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>s</mi><mi>i</mi></msub><mo>=</mo><mo stretchy="false">(</mo><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>m</mi></msubsup><msub><mi>a</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo><mo>×</mo><mo stretchy="false">(</mo><msubsup><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>m</mi></msubsup><msub><mi>b</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">)</mo><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>1</mn><msup><mn>0</mn><mn>16</mn></msup><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">s_i = (\sum_{j=1}^m {a_{ij}}) \times (\sum_{j=1}^m {b_{ij}}) \in [0, 10^{16}]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.24011em;vertical-align:-0.43581800000000004em;"></span><span class="mopen">(</span><span class="mop"><span class="mop op-symbol small-op" style="position:relative;top:-0.0000050000000000050004em;">∑</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.804292em;"><span style="top:-2.40029em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span><span class="mrel mtight">=</span><span class="mord mtight">1</span></span></span></span><span style="top:-3.2029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">m</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.43581800000000004em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.24011em;vertical-align:-0.43581800000000004em;"></span><span class="mopen">(</span><span class="mop"><span class="mop op-symbol small-op" style="position:relative;top:-0.0000050000000000050004em;">∑</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.804292em;"><span style="top:-2.40029em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span><span class="mrel mtight">=</span><span class="mord mtight">1</span></span></span></span><span style="top:-3.2029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">m</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.43581800000000004em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mtight">6</span></span></span></span></span></span></span></span></span><span class="mclose">]</span></span></span></span> 也可以用 <code>long long</code> 存下，但由于最终的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span></span></span></span> 是在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">[</mo><mn>0</mn><mo separator="true">,</mo><mn>1</mn><msup><mn>0</mn><mn>20</mn></msup><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[0, 10^{20}]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mord mtight">0</span></span></span></span></span></span></span></span></span><span class="mclose">]</span></span></span></span> 超出了 <code>long long</code>的表达范围，所以需要对 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span></span></span></span> 的加法结果进行取模。</p>
<p>二次优化原理如下，由于实际<code>long long</code>可以表达到 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">[</mo><mo>−</mo><msup><mn>2</mn><mn>63</mn></msup><mo separator="true">,</mo><msup><mn>2</mn><mn>63</mn></msup><mo>−</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[-2^{63}, 2^{63}-1]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">−</span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">6</span><span class="mord mtight">3</span></span></span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">6</span><span class="mord mtight">3</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">]</span></span></span></span> 范围，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mn>2</mn><mn>63</mn></msup></mrow><annotation encoding="application/x-tex">2^{63}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">6</span><span class="mord mtight">3</span></span></span></span></span></span></span></span></span></span></span></span> 约等于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>9</mn><mo>∗</mo><mn>1</mn><msup><mn>0</mn><mn>18</mn></msup></mrow><annotation encoding="application/x-tex">9*10^{18}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">9</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mtight">8</span></span></span></span></span></span></span></span></span></span></span></span>。我们可以使用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>M</mi><mi>O</mi><msup><mi>D</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">MOD^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span> 作为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span></span></span></span> 的模数，最终返回的时候再对 MOD 取模一次，正确性可以通过数论证明，这里不做展开，那么 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">s</span></span></span></span> 只有大约 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mfrac><mn>1</mn><mn>100</mn></mfrac></mrow><annotation encoding="application/x-tex">\frac{1}{100}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.190108em;vertical-align:-0.345em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.845108em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span><span class="mord mtight">0</span><span class="mord mtight">0</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span> 的概率实际需要进行取模，在平时题目中，这个概率是不确定的但往往是比较小的一个概率，那么使用 if 来判定然后做减法，往往会比取模效率提高非常多。</p>
<p>二次优化+偷懒原理如下，由于这种求和操作非常普通，但往往写起来需要时间，赛场上的任何一秒钟都是重要的，而且为了防止自己写错，可以使用C++ algorithm 中的 accumulate 函数来进行求和操作。accumulate 函数具体用法参考以下手册链接。<br />
<a href="https://zh.cppreference.com/w/cpp/algorithm/accumulate" target="_blank" rel="noopener">https://zh.cppreference.com/w/cpp/algorithm/accumulate</a></p>
<h3 id="gcc内置函数"><a class="markdownIt-Anchor" href="#gcc内置函数"></a> gcc内置函数</h3>
<p>使用gcc编译器作为本地编译器的时候，可以考虑使用gcc内置函数解决一些小问题。<a href="https://www.cnblogs.com/liuzhanshan/p/6861596.html" target="_blank" rel="noopener">https://www.cnblogs.com/liuzhanshan/p/6861596.html</a></p>
<p>另外gcc还有一个内置的扩展stl库，叫<code>pb_ds</code>，里面的rbtree可以解决stl中set无法解决的一些问题，在不需要刻意降低常数的情况下使用，避免自己需要额外编写数据结构的时间。</p>
<h1 id="空间优化技巧"><a class="markdownIt-Anchor" href="#空间优化技巧"></a> 空间优化技巧</h1>
<h2 id="2倍空间线段树"><a class="markdownIt-Anchor" href="#2倍空间线段树"></a> 2倍空间线段树</h2>
<p>在普通的线段树写法中，线段树空间都是需要开4倍才能保证正确性的，这里我不做展开证明。<br />
但如果4倍空间开不下怎么办，那么我有一个2倍空间的线段树写法，并且可以数学证明正确性。<br />
这种写法会带来 %5 ~ %10的性能损耗，但却可以有一个全新的方法访问线段树中的任意一个[l, r]节点，前提该线段树中存在该区间的节点。例如可以方便的访问叶子节点，具体有什么用途未知，但可以发挥想象，万一哪天就用到了呢。</p>
<p>传统线段树中用 k 作为当前节点的下标，线段树的根节点为1。<br />
在优化后的线段树中，对于每个覆盖了[l, r]的区间来说，他的下标是 <code>(l + r) | (l != r)</code> 。**所以这种线段树覆盖的区间最左值必须是非负整数。**最好的覆盖区间是 [0, n] 或者 [1, n]。<br />
这种情况下，下标最大的节点必定是最右端的叶子节点，也就是n的2倍。那么接下来证明线段树中的任意一个节点不可能发生seg1 [l, r]算出来的下标和 seg2 [x, y]重复。</p>
<p>分几种情况进行讨论：</p>
<ol>
<li>若 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>r</mi><mo><</mo><mi>x</mi></mrow><annotation encoding="application/x-tex">r < x</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span></span></span></span>，说明 seg1在seg2的左侧。那么seg1的最大ID就是当 $ l=r $ 或 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>+</mo><mn>1</mn><mo>=</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">l + 1 = r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span>的时候，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>=</mo><mn>2</mn><mo>∗</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">ID_1=2*r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span>。那么seg2的最小ID就是当<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>=</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x=y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span>的时候，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo>=</mo><mn>2</mn><mo>∗</mo><mi>x</mi></mrow><annotation encoding="application/x-tex">ID_2=2*x</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span></span></span></span>，由于<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>r</mi><mo><</mo><mi>x</mi></mrow><annotation encoding="application/x-tex">r<x</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span></span></span></span>，所以<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo><</mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">ID_1<ID_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>。不重复</li>
<li>若 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi><mo><</mo><mi>l</mi></mrow><annotation encoding="application/x-tex">y < l</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7335400000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span></span></span></span>，说明恰好与情况1相反，不再论证。</li>
<li>由于线段树的性质，2个线段树的节点覆盖的区间不可能相交，要么没有交集，要么是包含关系。这里就讨论seg1包含seg2的情况。若seg1包含seg2，则<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>≤</mo><mi>x</mi><mo>≤</mo><mi>y</mi><mo>≤</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">l \le x \le y \le r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83041em;vertical-align:-0.13597em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8304100000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span>，并且线段树具有2分的性质，要么seg2在seg1的左半区间，要么在seg1的右半区间。后面2种情况分别列举左右区间问题。</li>
<li>若seg2在seg1的左半区间，则<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mo stretchy="false">(</mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo stretchy="false">)</mo><mo>=</mo><mn>2</mn><mo>∗</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">max(ID_2)=2*y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">a</span><span class="mord mathdefault">x</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi><mo>≤</mo><mo stretchy="false">⌊</mo><mfrac><mrow><mi>l</mi><mo>+</mo><mi>r</mi></mrow><mn>2</mn></mfrac><mo stretchy="false">⌋</mo></mrow><annotation encoding="application/x-tex">y \le \lfloor \frac{l + r}{2} \rfloor</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8304100000000001em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.2251079999999999em;vertical-align:-0.345em;"></span><span class="mopen">⌊</span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8801079999999999em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.01968em;">l</span><span class="mbin mtight">+</span><span class="mord mathdefault mtight" style="margin-right:0.02778em;">r</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose">⌋</span></span></span></span>。当 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>+</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">l + r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span>是偶数的时候，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mo>+</mo><mn>1</mn><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo>=</mo><mn>2</mn><mo>∗</mo><mi>y</mi><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>></mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">ID_1=l+r+1，ID_2=2*y=l+r，ID_1>ID_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord">1</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>；当 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>+</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">l + r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 是奇数的时候，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo>=</mo><mn>2</mn><mo>∗</mo><mi>y</mi><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mo>−</mo><mn>1</mn><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>></mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">ID_1=l+r，ID_2=2*y=l+r-1，ID_1>ID_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord">1</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>。</li>
<li>若seg2在seg1的右半区间，则<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mi>i</mi><mi>n</mi><mo stretchy="false">(</mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo stretchy="false">)</mo><mo>=</mo><mn>2</mn><mo>∗</mo><mi>x</mi></mrow><annotation encoding="application/x-tex">min(ID_2)=2*x</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">m</span><span class="mord mathdefault">i</span><span class="mord mathdefault">n</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>></mo><mo stretchy="false">⌊</mo><mfrac><mrow><mi>l</mi><mo>+</mo><mi>r</mi></mrow><mn>2</mn></mfrac><mo stretchy="false">⌋</mo></mrow><annotation encoding="application/x-tex">x > \lfloor \frac{l + r}{2} \rfloor</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.2251079999999999em;vertical-align:-0.345em;"></span><span class="mopen">⌊</span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8801079999999999em;"><span style="top:-2.6550000000000002em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.01968em;">l</span><span class="mbin mtight">+</span><span class="mord mathdefault mtight" style="margin-right:0.02778em;">r</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.345em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose">⌋</span></span></span></span>。当 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>+</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">l + r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span>是偶数的时候，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mo>+</mo><mn>1</mn><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo>=</mo><mn>2</mn><mo>∗</mo><mi>x</mi><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mo>+</mo><mn>2</mn><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo><</mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">ID_1=l+r+1，ID_2=2*x=l+r+2，ID_1<ID_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord">1</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord">2</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>；当 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>+</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">l + r</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span></span></span></span> 是奇数的时候，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub><mo>=</mo><mn>2</mn><mo>∗</mo><mi>x</mi><mo>=</mo><mi>l</mi><mo>+</mo><mi>r</mi><mo>+</mo><mn>1</mn><mi mathvariant="normal">，</mi><mi>I</mi><msub><mi>D</mi><mn>1</mn></msub><mo><</mo><mi>I</mi><msub><mi>D</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">ID_1=l+r，ID_2=2*x=l+r+1，ID_1<ID_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord">1</span><span class="mord cjk_fallback">，</span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.02778em;">D</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.02778em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>。</li>
</ol>
<p>所以不论什么情况下，都不可能出现 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>I</mi><mi>D</mi></mrow><annotation encoding="application/x-tex">ID</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">I</span><span class="mord mathdefault" style="margin-right:0.02778em;">D</span></span></span></span> 重复，由于线段树的性质，当覆盖的区间长度为n，那么实际节点为<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mo>∗</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2*n-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">∗</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>个，所以这种写法的线段树可以充分使用数组空间。</p>
<p>普通线段树区间修改求和模板：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">100005</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> a[N];</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">SegTree</span> {</span></span><br><span class="line"> ll sum[N << <span class="number">1</span>], laz[N << <span class="number">1</span>];</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> (l + r) | (l != r);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">up</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> sum[get(l, r)] = sum[get(l, mid)] + sum[get(mid + <span class="number">1</span>, r)];</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (laz[get(l, r)] == <span class="number">0</span>) <span class="keyword">return</span>;</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line"> laz[get(l, mid)] += laz[get(l, r)];</span><br><span class="line"> sum[get(l, mid)] += laz[get(l, r)] * (mid - l + <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"> laz[get(mid + <span class="number">1</span>, r)] += laz[get(l, r)];</span><br><span class="line"> sum[get(mid + <span class="number">1</span>, r)] += laz[get(l, r)] * (r - mid);</span><br><span class="line"></span><br><span class="line"> laz[get(l, r)] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">build</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> laz[get(l, r)] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">if</span> (l == r) {</span><br><span class="line"> a[get(l, r)] = a[l];</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> build(l, mid);</span><br><span class="line"> build(mid + <span class="number">1</span>, r);</span><br><span class="line"> up(l, r);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 区间更新, a[i] += w</span></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> x, <span class="keyword">int</span> y, ll w)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l == x && r == y) {</span><br><span class="line"> sum[get(l, r)] += (l - r + <span class="number">1</span>) * w;</span><br><span class="line"> laz[get(l, r)] += w;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> push(l, r);</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (y <= mid) {</span><br><span class="line"> update(l, mid, x, y, w);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (x >= mid) {</span><br><span class="line"> update(mid + <span class="number">1</span>, r, x, y, w);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> update(l, mid, x, mid, w);</span><br><span class="line"> update(mid + <span class="number">1</span>, r, mid + <span class="number">1</span>, y, w);</span><br><span class="line"> }</span><br><span class="line"> up(l, r);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 区间求和</span></span><br><span class="line"> <span class="function">ll <span class="title">query</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l == x && r == y) {</span><br><span class="line"> <span class="keyword">return</span> sum[get(l, r)];</span><br><span class="line"> }</span><br><span class="line"> push(l, r);</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (y <= mid) {</span><br><span class="line"> <span class="keyword">return</span> query(l, mid, x, y);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (x >= mid) {</span><br><span class="line"> <span class="keyword">return</span> query(mid + <span class="number">1</span>, r, x, y);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">return</span> query(l, mid, x, mid) + query(mid + <span class="number">1</span>, r, mid + <span class="number">1</span>, y);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<p>再给出一种偷懒写法，虽然我自己不太常用这种偷懒写法，但有时候的确省时间：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">100005</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> a[N];</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">SegTree</span> {</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> smid ((l + r) >> 1)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> self get(l, r)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> lson get(l, smid)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> rson get(smid + 1, r)</span></span><br><span class="line"></span><br><span class="line"> ll sum[N << <span class="number">1</span>], laz[N << <span class="number">1</span>];</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> (l + r) | (l != r);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">up</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> sum[self] = sum[lson] + sum[rson];</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (laz[self] == <span class="number">0</span>) <span class="keyword">return</span>;</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> </span><br><span class="line"> laz[lson] += laz[self];</span><br><span class="line"> sum[lson] += laz[self] * (mid - l + <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"> laz[rson] += laz[self];</span><br><span class="line"> sum[rson] += laz[self] * (r - mid);</span><br><span class="line"></span><br><span class="line"> laz[self] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">build</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> laz[self] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">if</span> (l == r) {</span><br><span class="line"> a[self] = a[l];</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> build(l, mid);</span><br><span class="line"> build(mid + <span class="number">1</span>, r);</span><br><span class="line"> up(l, r);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 区间更新, a[i] += w</span></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> x, <span class="keyword">int</span> y, ll w)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l == x && r == y) {</span><br><span class="line"> sum[self] += (l - r + <span class="number">1</span>) * w;</span><br><span class="line"> laz[self] += w;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> push(l, r);</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (y <= mid) {</span><br><span class="line"> update(l, mid, x, y, w);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (x >= mid) {</span><br><span class="line"> update(mid + <span class="number">1</span>, r, x, y, w);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> update(l, mid, x, mid, w);</span><br><span class="line"> update(mid + <span class="number">1</span>, r, mid + <span class="number">1</span>, y, w);</span><br><span class="line"> }</span><br><span class="line"> up(l, r);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 区间求和</span></span><br><span class="line"> <span class="function">ll <span class="title">query</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l == x && r == y) {</span><br><span class="line"> <span class="keyword">return</span> sum[self];</span><br><span class="line"> }</span><br><span class="line"> push(l, r);</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) >> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (y <= mid) {</span><br><span class="line"> <span class="keyword">return</span> query(l, mid, x, y);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (x >= mid) {</span><br><span class="line"> <span class="keyword">return</span> query(mid + <span class="number">1</span>, r, x, y);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">return</span> query(l, mid, x, mid) + query(mid + <span class="number">1</span>, r, mid + <span class="number">1</span>, y);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://blog.happypie.net/2021/05/31/xcpc/xcpc-ending/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.jpg">
<meta itemprop="name" content="Happier233">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Happier233的博客">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/05/31/xcpc/xcpc-ending/" class="post-title-link" itemprop="url">XCPC退役总结</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-05-31 16:53:42" itemprop="dateCreated datePublished" datetime="2021-05-31T16:53:42+08:00">2021-05-31</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-07-25 00:04:29" itemprop="dateModified" datetime="2021-07-25T00:04:29+08:00">2021-07-25</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/" itemprop="url" rel="index"><span itemprop="name">XCPC</span></a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="奖项列表"><a class="markdownIt-Anchor" href="#奖项列表"></a> 奖项列表</h1>
<p>在5月30日的下午，在北京CCPC Final的现场，我终于退役啦，结束了大学四年的XCPC生涯。<br />
先总结一下四年打过的比赛和奖项吧。</p>
<table>
<thead>
<tr>
<th>序号</th>
<th>日期</th>
<th>名称</th>
<th>奖项</th>
<th>队友</th>
<th>备注</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>2018/01</td>
<td>2017 浙江工商大学新生赛</td>
<td>第一</td>
<td></td>
<td>进入ZJGSU ACM实验室</td>
</tr>
<tr>
<td>2</td>
<td>2018/04</td>
<td>2018 浙江工商大学校赛</td>
<td>第四</td>
<td></td>
<td></td>
</tr>
<tr>
<td>3</td>
<td>2018/04</td>
<td>2018 浙江省大学生程序设计竞赛</td>
<td>铁牌</td>
<td></td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>2018/06</td>
<td>2018 ICPC 上海邀请赛</td>
<td>铜牌</td>
<td>黄队，蛋神</td>
<td>第一次拿牌</td>
</tr>
<tr>
<td>5</td>
<td>2018/10</td>
<td>2018 ICPC 南京区域赛</td>
<td>铁牌</td>
<td>噗噗，老板</td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>2019/04</td>
<td>2019 浙江工商大学校赛</td>
<td>第二</td>
<td></td>
<td></td>
</tr>
<tr>
<td>7</td>
<td>2019/04</td>
<td>2019 浙江省大学生程序设计竞赛</td>
<td>铜牌</td>
<td></td>
<td></td>
</tr>
<tr>
<td>8</td>
<td>2019/05</td>
<td>2019 CCPC 湘潭邀请赛</td>
<td>铜牌</td>
<td>缪少爷，龙神</td>
<td>全新组队</td>
</tr>
<tr>
<td>9</td>
<td>2019/06</td>
<td>2019 ICPC 南昌邀请赛</td>
<td>银牌</td>
<td>缪少爷，龙神</td>
<td></td>
</tr>
<tr>
<td>10</td>
<td>2019/09</td>
<td>2019 CCPC 秦皇岛区域赛</td>
<td>银牌</td>
<td>缪少爷，龙神</td>
<td></td>
</tr>
<tr>
<td>11</td>
<td>2019/11</td>
<td>2019 ICPC 南昌区域赛</td>
<td>银牌</td>
<td>缪少爷，龙神</td>
<td></td>
</tr>
<tr>
<td>12</td>
<td>2019/12</td>
<td>2019 ICPC EC-Final 西安</td>
<td>铁牌</td>
<td>缪少爷，龙神</td>
<td></td>
</tr>
<tr>
<td>13</td>
<td>2019/11</td>
<td>2019 CCPC Final 北京</td>
<td>铁牌</td>
<td>经理，噗噗</td>
<td></td>
</tr>
<tr>
<td>14</td>
<td>2020/10</td>
<td>2020 浙江省大学生程序设计竞赛</td>
<td>银牌</td>
<td>徐总，缪少爷</td>
<td>退役后重新再战</td>
</tr>
<tr>
<td>15</td>
<td>2020/11</td>
<td>2020 CCPC 威海区域赛</td>
<td>银牌</td>
<td>徐总，缪少爷</td>
<td></td>
</tr>
<tr>
<td>16</td>
<td>2021/04</td>
<td>2020 ICPC 昆明区域赛</td>
<td>银牌</td>
<td>徐总，缪少爷</td>
<td></td>
</tr>
<tr>
<td>17</td>
<td>2021/04</td>
<td>2020 ICPC EC-Final 西安</td>
<td>银牌</td>
<td>徐总，缪少爷</td>
<td></td>
</tr>
<tr>
<td>18</td>
<td>2021/05</td>
<td>2020 ICPC 银川区域赛</td>
<td>金牌</td>
<td>徐总，缪少爷</td>
<td>第一次金牌</td>
</tr>
<tr>
<td>19</td>
<td>2021/06</td>
<td>2020 CCPC Final 北京</td>
<td>铁牌</td>
<td>徐总，缪少爷</td>
<td>退役之战</td>
</tr>
</tbody>
</table>
<h1 id="组队过程"><a class="markdownIt-Anchor" href="#组队过程"></a> 组队过程</h1>
<p>除去非常规组队，一共经历3次组队。</p>
<p>第一次加入实验室后的第一个暑期集训，与室友和好朋友一起组了第一个队伍，最后打铁与南京站。</p>
<p>第二次加入实验室后的第二个暑期集训，与实验室的大佬缪少爷（保研浙大）和我的学弟龙神（安徽OI爷）。这期间一路从铜牌开始打到银牌，其实本来有希望在2020年上半年就获得第一个金牌，但可惜2020年疫情打破了一切计划。2020年初正值我ACM生涯巅峰时间，CF首次达到紫名，可惜疫情导致整个上半年赛季全部暂缓和取消，最终我和缪少爷进入了原地退役模式。</p>
<p>第三次在2020年9月，得知下半年赛站将以线上赛模式进行，比赛恢复常态化，当时我还在实习，和两位队友讨论后，决定再次组队，圆一下大学的梦，一直维持到毕业。</p>
<h1 id="总结"><a class="markdownIt-Anchor" href="#总结"></a> 总结</h1>
<p>这四年，我一共有3年半的时间付出在了ACM竞赛上，最终也算是没有遗憾的毕业了。这四年从来没有后悔过大一选择了ACM，或许说这个竞赛并不是适合所有人，但至少我在这个竞赛上得到了我想要的。</p>
<p>虽然曾一度想要靠ACM的奖项保研，但由于在2020年7月之前，没有得到那个梦寐以求的金牌，外加绩点排名没有其他人那么亮眼，所以我在申请了保研之后处于一种放弃的状态。2020年上半年退役后，有学长帮我内推了蚂蚁，我也是非常幸运的拿到了实习Offer。当时我没有Java基础，完全是在学长的鼓励下，抱着试试看的心态，几天时间突击了一波面经。最后在10月的时候通过了转正答辩，得到了我人生的第一份工作。</p>
<p>如果要说ACM给我带来了什么，那我的答案有几项内容：</p>
<ul>
<li>大学四年有了一项可以一直坚持下去事情，没有荒废这四年时光。</li>
<li>让我认识了一群努力的人，每年暑假只有两周，每年寒假都是坚持到封校，都在为了自己想要的在奋斗。</li>
<li>让我的付出成为了一个个奖牌，让我无数次跌倒，又能让我无数次在AC后呐喊，那种喜悦和成就感是可以一直去回忆的。</li>
</ul>
<p>虽然说弱校打ACM出不了成绩，但在那么多届学长的铺垫下，但至少我做到了，我的学弟们也都做到了。强校很多选手都是OI出身的，有着多年的算法竞赛经验，这是他们的绝对优势，但并不是真的无法追赶，无非是自己愿不愿意，能不能看得到希望罢了。希望ZJGSU ACM越来越好，希望实验室的柜子能有一天金牌多到放不下。</p>
<p>最后感谢 <strong>MS教练</strong> ，我们亲爱的老大！</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://blog.happypie.net/2020/12/20/xcpc/zjgsu/2020-acm-new/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.jpg">
<meta itemprop="name" content="Happier233">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Happier233的博客">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/20/xcpc/zjgsu/2020-acm-new/" class="post-title-link" itemprop="url">2020年浙江工商大学新生赛</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-12-20 18:00:00" itemprop="dateCreated datePublished" datetime="2020-12-20T18:00:00+08:00">2020-12-20</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-07-24 23:59:50" itemprop="dateModified" datetime="2021-07-24T23:59:50+08:00">2021-07-24</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/" itemprop="url" rel="index"><span itemprop="name">XCPC</span></a>
</span>
，
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/OJ/" itemprop="url" rel="index"><span itemprop="name">OJ</span></a>
</span>
，
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/OJ/ZJGSU/" itemprop="url" rel="index"><span itemprop="name">ZJGSU</span></a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="开篇"><a class="markdownIt-Anchor" href="#开篇"></a> 开篇</h1>
<p>首先很感谢各位新生们的参与</p>
<h1 id="题目难度"><a class="markdownIt-Anchor" href="#题目难度"></a> 题目难度</h1>
<p>题目列表</p>
<table>
<thead>
<tr>
<th style="text-align:center">ID</th>
<th style="text-align:center">Title</th>
<th style="text-align:center">Ratio</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">0</td>
<td style="text-align:center">站神的 A+B problem</td>
<td style="text-align:center">3.84% (27/704)</td>
</tr>
<tr>
<td style="text-align:center">1</td>
<td style="text-align:center">站神与最简单的语言</td>
<td style="text-align:center">9.09% (1/11)</td>
</tr>
<tr>
<td style="text-align:center">2</td>
<td style="text-align:center">站神和一笔画圆</td>
<td style="text-align:center">9.11% (38/417)</td>
</tr>
<tr>
<td style="text-align:center">3</td>
<td style="text-align:center">站神打包快递</td>
<td style="text-align:center">3.33% (7/210)</td>
</tr>
<tr>
<td style="text-align:center">4</td>
<td style="text-align:center">站神的梦</td>
<td style="text-align:center">0.00% (0/12)</td>
</tr>
<tr>
<td style="text-align:center">5</td>
<td style="text-align:center">站神数颜色</td>
<td style="text-align:center">5.62% (9/160)</td>
</tr>
<tr>
<td style="text-align:center">6</td>
<td style="text-align:center">站神与肃正协议</td>
<td style="text-align:center">14.29% (79/553)</td>
</tr>
<tr>
<td style="text-align:center">7</td>
<td style="text-align:center">站神的演讲</td>
<td style="text-align:center">26.77% (106/396)</td>
</tr>
<tr>
<td style="text-align:center">8</td>
<td style="text-align:center">打破复读机</td>
<td style="text-align:center">26.84% (142/529)</td>
</tr>
<tr>
<td style="text-align:center">9</td>
<td style="text-align:center">吃米饭的站神</td>
<td style="text-align:center">24.31% (115/473)</td>
</tr>
</tbody>
</table>
<p>预计难度<br />
<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>8</mn><mo><</mo><mn>6</mn><mo><</mo><mn>7</mn><mo><</mo><mn>9</mn><mo><</mo><mn>0</mn><mo><</mo><mn>2</mn><mo><</mo><mn>5</mn><mo><</mo><mn>3</mn><mo><</mo><mn>1</mn><mo><</mo><mn>4</mn></mrow><annotation encoding="application/x-tex">8 < 6 < 7 < 9 < 0 < 2 < 5 < 3 < 1 < 4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">8</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">6</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">7</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">9</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">5</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">3</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">4</span></span></span></span><br />
实际过题排序<br />
<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>8</mn><mo><</mo><mn>9</mn><mo><</mo><mn>7</mn><mo><</mo><mn>6</mn><mo><</mo><mn>2</mn><mo><</mo><mn>0</mn><mo><</mo><mn>5</mn><mo><</mo><mn>3</mn><mo><</mo><mn>1</mn><mo><</mo><mn>4</mn></mrow><annotation encoding="application/x-tex">8 < 9 < 7 < 6 < 2 < 0 < 5 < 3 < 1 < 4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">8</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">9</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">7</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">6</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">5</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">3</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68354em;vertical-align:-0.0391em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">4</span></span></span></span></p>
<h1 id="评价"><a class="markdownIt-Anchor" href="#评价"></a> 评价</h1>
<p>今年难度比往年普遍大幅降低，原计划是3+3+3+1的难度区分，3个基础题，3个需要一些数学能力的题目，3个需要一些代码能力的题目，还有一道防AK题。但防AK题并不是刻意让你们做不出来的题，只不过考虑到选手的实力，会选择需要一定思考深度和能力要求的题目。</p>
<p>所以最后的过体量大致还是符合出题组预想的结果的，而且大部分选手都留到了最后，不知道参赛选手们的参赛体验如何，如果有更好的建议和批评都欢迎提出来呀</p>
<h1 id="题解链接们"><a class="markdownIt-Anchor" href="#题解链接们"></a> 题解链接们</h1>
<p><strong>括号内为题号</strong><br />
龙神的题解[2,3,5]：<a href="https://blog.csdn.net/panggeQAQ/article/details/111460746" target="_blank" rel="noopener">https://blog.csdn.net/panggeQAQ/article/details/111460746</a><br />
老会长的题解[1,6,9]：<a href="https://blog.csdn.net/m0_43448982/article/details/111460449" target="_blank" rel="noopener">https://blog.csdn.net/m0_43448982/article/details/111460449</a><br />
林大佬的题解[0,7,8]：<a href="https://blog.csdn.net/weixin_44282912/article/details/111460476" target="_blank" rel="noopener">https://blog.csdn.net/weixin_44282912/article/details/111460476</a><br />
开心点的题解[4]: <a href="https://happier233.github.io/2020/12/20/contest/2019-ec-final/" target="_blank" rel="noopener">https://happier233.github.io/2020/12/20/contest/2019-ec-final/</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://blog.happypie.net/2020/12/20/xcpc/contest/2019-ec-final/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.jpg">
<meta itemprop="name" content="Happier233">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Happier233的博客">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/20/xcpc/contest/2019-ec-final/" class="post-title-link" itemprop="url">2019 ICPC EC Final</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-12-20 18:00:00" itemprop="dateCreated datePublished" datetime="2020-12-20T18:00:00+08:00">2020-12-20</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-07-25 00:03:09" itemprop="dateModified" datetime="2021-07-25T00:03:09+08:00">2021-07-25</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/" itemprop="url" rel="index"><span itemprop="name">XCPC</span></a>
</span>
，
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/OJ/" itemprop="url" rel="index"><span itemprop="name">OJ</span></a>
</span>
，
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/%E7%88%86%E6%90%9C/" itemprop="url" rel="index"><span itemprop="name">爆搜</span></a>
</span>
，
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/XCPC/OJ/%E7%89%9B%E5%AE%A2/" itemprop="url" rel="index"><span itemprop="name">牛客</span></a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="题解"><a class="markdownIt-Anchor" href="#题解"></a> 题解</h1>
<h2 id="m"><a class="markdownIt-Anchor" href="#m"></a> M</h2>
<p><a href="https://ac.nowcoder.com/acm/contest/3732/M" target="_blank" rel="noopener">牛客题目链接</a></p>
<h3 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h3>
<p>Pang believes that one cannot make an omelet without breaking eggs.</p>
<p>For a subset <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span></span></span></span> of <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><mi>n</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{1,2,\ldots,n\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault">n</span><span class="mclose">}</span></span></span></span>, we calculate the score of <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span></span></span></span> as follows:</p>
<ol>
<li>Initialize the score as {0}0.</li>
<li>For any <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi><mo>∈</mo><mi>A</mi></mrow><annotation encoding="application/x-tex">i \in A</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69862em;vertical-align:-0.0391em;"></span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span></span></span></span>, add <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">a_i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> to the score.</li>
<li>For any pair of integers <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(i, j)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">i</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mclose">)</span></span></span></span> satisfying <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi><mo>≥</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">i \ge 2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.79549em;vertical-align:-0.13597em;"></span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span></span></span></span>, <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi><mo>≥</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">j \ge 2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span></span></span></span>, <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi><mo>∈</mo><mi>A</mi></mrow><annotation encoding="application/x-tex">i \in A</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69862em;vertical-align:-0.0391em;"></span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span></span></span></span>, if there exists positive integer <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi><mo>></mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k \gt 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.73354em;vertical-align:-0.0391em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span> such that <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>i</mi><mi>k</mi></msup><mo>=</mo><mi>j</mi></mrow><annotation encoding="application/x-tex">i^k=j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">i</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span>, subtract <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>b</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">b_j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span></span> from the score.</li>
</ol>
<p>Find the maximum possible score over the choice of <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span></span></span></span>.</p>
<h3 id="思考"><a class="markdownIt-Anchor" href="#思考"></a> 思考</h3>
<p>我任意选择一个子集<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">A</span></span></span></span>，只考虑条件2，可以得到的分值为<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mi>A</mi></mrow></msub><msub><mi>a</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">\sum_{i\in{A}}{a_i}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.07708em;vertical-align:-0.32708000000000004em;"></span><span class="mop"><span class="mop op-symbol small-op" style="position:relative;top:-0.0000050000000000050004em;">∑</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.17862099999999992em;"><span style="top:-2.40029em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mrel mtight">∈</span><span class="mord mtight"><span class="mord mathdefault mtight">A</span></span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.32708000000000004em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span><br />
如果需要扣除<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>b</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">b_j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span></span>的得分，必定存在某个<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>i</mi><mi>k</mi></msup><mo>=</mo><mi>j</mi></mrow><annotation encoding="application/x-tex">i^k=j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">i</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span><br />
那么就可以反过来思考，我枚举所有的<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>i</mi><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">i^k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">i</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi><mo>≥</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k \ge 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83041em;vertical-align:-0.13597em;"></span><span class="mord mathdefault" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>i</mi><mi>k</mi></msup><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">i^k \le n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.985078em;vertical-align:-0.13597em;"></span><span class="mord"><span class="mord mathdefault">i</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">n</span></span></span></span>，例如：</p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><mn>2</mn><mo separator="true">,</mo><mn>4</mn><mo separator="true">,</mo><mn>8</mn><mo separator="true">,</mo><mn>16</mn><mo separator="true">,</mo><mn>32</mn><mo separator="true">,</mo><mo>…</mo><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{2,4,8,16,32,\ldots\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">4</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">8</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord">6</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">3</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span><span class="mclose">}</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><mn>3</mn><mo separator="true">,</mo><mn>9</mn><mo separator="true">,</mo><mn>27</mn><mo separator="true">,</mo><mn>91</mn><mo separator="true">,</mo><mo>…</mo><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{3,9,27,91,\ldots\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">3</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">9</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">2</span><span class="mord">7</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">9</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span><span class="mclose">}</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><mn>5</mn><mo separator="true">,</mo><mn>25</mn><mo separator="true">,</mo><mn>125</mn><mo separator="true">,</mo><mn>625</mn><mo separator="true">,</mo><mo>…</mo><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{5,25,125,625,\ldots\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">5</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">2</span><span class="mord">5</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">1</span><span class="mord">2</span><span class="mord">5</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">6</span><span class="mord">2</span><span class="mord">5</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span><span class="mclose">}</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><mn>6</mn><mo separator="true">,</mo><mn>36</mn><mo separator="true">,</mo><mo>…</mo><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{6,36,\ldots\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">6</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord">3</span><span class="mord">6</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="minner">…</span><span class="mclose">}</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>…</mo></mrow><annotation encoding="application/x-tex">\ldots</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.12em;vertical-align:0em;"></span><span class="minner">…</span></span></span></span></li>
</ul>
<p>对于以上每个集合，分别考虑里面的数字选与不选，比如第一个<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mn>2</mn><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">2^k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span></span></span></span>的集合，当我没有选择2但选择了4的时候，所有<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>b</mi><mi>j</mi></msub><mo stretchy="false">(</mo><mi>j</mi><mo>∈</mo><mi>A</mi><mo>&</mo><mi>j</mi><mo>=</mo><msup><mn>4</mn><mi>k</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">b_j(j \in A \And j=4^k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault">b</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathdefault">A</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">&</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.099108em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord">4</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span>都需要扣除，那么对于单个集合计算的复杂度就是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mo><mi>log</mi><mo></mo></mo><mi>i</mi></msub><mi>n</mi><mo>×</mo><msup><mn>2</mn><mrow><msub><mo><mi>log</mi><mo></mo></mo><mi>i</mi></msub><mi>n</mi></mrow></msup></mrow><annotation encoding="application/x-tex">\log_{i}{n} \times 2^{\log_{i}{n}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.93858em;vertical-align:-0.24414em;"></span><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.21752399999999997em;"><span style="top:-2.4558600000000004em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.24414em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">n</span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.849108em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mop mtight"><span class="mop mtight">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.20521714285714282em;"><span style="top:-2.2341314285714287em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.26586857142857145em;"><span></span></span></span></span></span></span><span class="mspace mtight" style="margin-right:0.19516666666666668em;"></span><span class="mord mtight"><span class="mord mathdefault mtight">n</span></span></span></span></span></span></span></span></span></span></span></span></span>，那么总体复杂度的上界就是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msubsup><mo>∑</mo><mi>i</mi><mi>n</mi></msubsup><mrow><msub><mo><mi>log</mi><mo></mo></mo><mi>i</mi></msub><mi>n</mi><mo>×</mo><msup><mn>2</mn><mrow><msub><mo><mi>log</mi><mo></mo></mo><mi>i</mi></msub><mi>n</mi></mrow></msup></mrow></mrow><annotation encoding="application/x-tex">\sum_i^n{\log_{i}{n} \times 2^{\log_{i}{n}}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.148818em;vertical-align:-0.29971000000000003em;"></span><span class="mop"><span class="mop op-symbol small-op" style="position:relative;top:-0.0000050000000000050004em;">∑</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.804292em;"><span style="top:-2.40029em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span><span style="top:-3.2029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.29971000000000003em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.21752399999999997em;"><span style="top:-2.4558600000000004em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.24414em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">n</span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.849108em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mop mtight"><span class="mop mtight">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.20521714285714282em;"><span style="top:-2.2341314285714287em;margin-right:0.07142857142857144em;"><span class="pstrut" style="height:2.5em;"></span><span class="sizing reset-size3 size1 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.26586857142857145em;"><span></span></span></span></span></span></span><span class="mspace mtight" style="margin-right:0.19516666666666668em;"></span><span class="mord mtight"><span class="mord mathdefault mtight">n</span></span></span></span></span></span></span></span></span></span></span></span></span></span>，用起算器算一下当<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>=</mo><mn>100000</mn></mrow><annotation encoding="application/x-tex">n=100000</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span></span></span></span>的时候，上界不超过<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2000000</mn></mrow><annotation encoding="application/x-tex">2000000</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span><span class="mord">0</span></span></span></span>的</p>
<h3 id="代码"><a class="markdownIt-Anchor" href="#代码"></a> 代码</h3>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 巨菜的ACMer-Happier233</span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">//-----</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">double</span> db;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">int</span> ui;</span><br><span class="line"><span class="keyword">typedef</span> <span class="built_in">vector</span><<span class="keyword">int</span>> vi;</span><br><span class="line"><span class="keyword">typedef</span> pair<<span class="keyword">int</span>, <span class="keyword">int</span>> pii;</span><br><span class="line"><span class="keyword">typedef</span> pair<ll, ll> pll;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> fi first</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> se second</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pw(x) (1ll << (x))</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> bt(x, k) (((x) >> k) & 1)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> sz(x) ((int)(x).size())</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> all(x) (x).begin(),(x).end()</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> rep(i, l, r) for(int i=(l);i<(r);++i)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> per(i, l, r) for(int i=(r)-1;i>=(l);--i)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mst(t, v, n) memset(t, v, sizeof(decltype(*(t))) * (n))</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> sf(x) scanf(<span class="meta-string">"%d"</span>, &(x))</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">if</span> (not defined(ACM_LOCAL) || defined(ACM_TEST))</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> endl <span class="meta-string">'\n'</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">10</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MOD = <span class="number">998244353</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> M = <span class="number">30</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n, m;</span><br><span class="line"><span class="comment">// a表示题目输入的a,b，b来存放当前i的i^k的所有数字的a,b组合</span></span><br><span class="line">pii a[N], b[N];</span><br><span class="line"><span class="comment">// c表示当前枚举集合的第j个=数字要选的时候需要被减去几次</span></span><br><span class="line"><span class="keyword">int</span> c[N] = {<span class="number">0</span>};</span><br><span class="line"><span class="comment">// 表示当前i是否被访问过，比如需要跳过4,8,9之类的数字</span></span><br><span class="line"><span class="keyword">bool</span> vis[N];</span><br><span class="line">ll rst;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> k, ll w)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (k > m) {</span><br><span class="line"> rst = max(rst, w);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> dfs(k + <span class="number">1</span>, w);</span><br><span class="line"> w += b[k].first;</span><br><span class="line"> w -= <span class="number">1l</span>l * b[k].second * c[k];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = k; i <= m; i += k) {</span><br><span class="line"> c[i]++;</span><br><span class="line"> }</span><br><span class="line"> dfs(k + <span class="number">1</span>, w);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = k; i <= m; i += k) {</span><br><span class="line"> c[i]--;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">while</span> (<span class="built_in">cin</span> >> n) {</span><br><span class="line"> <span class="built_in">memset</span>(vis, <span class="literal">false</span>, <span class="keyword">sizeof</span>(vis));</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) <span class="built_in">cin</span> >> a[i].first;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) <span class="built_in">cin</span> >> a[i].second;</span><br><span class="line"></span><br><span class="line"> ll ans = a[<span class="number">1</span>].first;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i <= n; i++) {</span><br><span class="line"> <span class="keyword">if</span> (vis[i]) <span class="keyword">continue</span>;</span><br><span class="line"> m = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (ll k = i; k <= n; k *= i) {</span><br><span class="line"> vis[k] = <span class="literal">true</span>;</span><br><span class="line"> b[++m] = a[k];</span><br><span class="line"> }</span><br><span class="line"> rst = <span class="number">0</span>;</span><br><span class="line"> dfs(<span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line"> ans += rst;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="built_in">endl</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"><span class="meta">#<span class="meta-keyword">ifdef</span> ACM_LOCAL</span></span><br><span class="line"> freopen(<span class="string">"./data/std.in"</span>, <span class="string">"r"</span>, <span class="built_in">stdin</span>);</span><br><span class="line"><span class="comment">// freopen("./data/std.out", "w", stdout);</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">if</span> (not defined(ACM_LOCAL) || defined(ACM_TEST))</span></span><br><span class="line"> ios_base::sync_with_stdio(<span class="literal">false</span>);</span><br><span class="line"> <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cout</span>.tie(<span class="number">0</span>);</span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">ifdef</span> ACM_LOCAL</span></span><br><span class="line"> <span class="keyword">clock_t</span> start = clock();</span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"> <span class="keyword">int</span> t = <span class="number">1</span>;</span><br><span class="line"><span class="comment">// cin >> t;</span></span><br><span class="line"> <span class="keyword">while</span> (t--)</span><br><span class="line"> solve();</span><br><span class="line"><span class="meta">#<span class="meta-keyword">ifdef</span> ACM_LOCAL</span></span><br><span class="line"> <span class="keyword">clock_t</span> end = clock();</span><br><span class="line"> <span class="built_in">cerr</span> << <span class="string">"Run Time: "</span> << <span class="keyword">double</span>(end - start) / CLOCKS_PER_SEC << <span class="string">"s"</span> << <span class="built_in">endl</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://blog.happypie.net/2020/12/17/project/mysql8-mq/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.jpg">
<meta itemprop="name" content="Happier233">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Happier233的博客">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/17/project/mysql8-mq/" class="post-title-link" itemprop="url">基于MySQL 8的特性实现拉模型的消息队列</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2020-12-17 20:34:49" itemprop="dateCreated datePublished" datetime="2020-12-17T20:34:49+08:00">2020-12-17</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-07-24 23:59:04" itemprop="dateModified" datetime="2021-07-24T23:59:04+08:00">2021-07-24</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="概述"><a class="markdownIt-Anchor" href="#概述"></a> 概述</h1>
<h2 id="mysql-8-新特性"><a class="markdownIt-Anchor" href="#mysql-8-新特性"></a> mysql 8 新特性</h2>
<p>MySQL 8增加了 <strong>Locking Read Concurrency with NOWAIT and SKIP LOCKED</strong> 的实现<br />
官方文档：<a href="https://dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html" target="_blank" rel="noopener">mysql8 15.7.2.4 Locking Reads</a></p>
<h2 id="消息队列"><a class="markdownIt-Anchor" href="#消息队列"></a> 消息队列</h2>
<p> 普通的消息队列就是由生产者与消费者组成，多数场景下数据都会先落库然后将消息发送到消息队列，等待消费者进行消费。消费者在消费的时候往往需要保证执行的成功性，如果失败则需要进行n次重试。在某些场景下还需要事务消息的存在，需要保证消息与数据库写入同时成功。<br />
在一些小型项目内完全没有必要引入体量巨大的消息队列中间件，但多数项目都有数据库的依赖。所以直接使用mysql进行消息队列实现可以简化某些项目的体量。</p>
<h1 id="实现"><a class="markdownIt-Anchor" href="#实现"></a> 实现</h1>
<h2 id="原理"><a class="markdownIt-Anchor" href="#原理"></a> 原理</h2>
<p>使用单表记录存放消息<br />
结构：</p>
<table>
<thead>
<tr>
<th>字段</th>
<th>类型</th>
<th>用途</th>
</tr>
</thead>
<tbody>
<tr>
<td>id</td>
<td>int(11)</td>
<td>主键</td>
</tr>
<tr>
<td>topic</td>
<td>varchar(64)</td>
<td>主题</td>
</tr>
<tr>
<td>key</td>
<td>varchar(64)</td>
<td>消息唯一性</td>
</tr>
<tr>
<td>status</td>
<td>int(11)</td>
<td>消费状态</td>
</tr>
<tr>
<td>retry</td>
<td>int(11)</td>
<td>剩余重试次数</td>
</tr>
<tr>
<td>start_time</td>
<td>bigint(20)</td>
<td>任务最小开始执行的时间</td>
</tr>
<tr>
<td>exception</td>
<td>varchar(11)</td>
<td>错误内容</td>
</tr>
<tr>
<td>msg</td>
<td>varchar(256)</td>
<td>消息主体</td>
</tr>
</tbody>
</table>
<p>建立唯一索引1(topic, key, retry)，建立普通索引2(topic, status, start_time)<br />
状态分为：0（未消费），1（消费失败），2（消费成功）</p>
<h2 id="处理逻辑"><a class="markdownIt-Anchor" href="#处理逻辑"></a> 处理逻辑</h2>
<h3 id="查找可以消费的消息"><a class="markdownIt-Anchor" href="#查找可以消费的消息"></a> 查找可以消费的消息</h3>
<p>先开启事务，查找可以消费的消息，指定Topic，指定状态是待消费，开始时间小于等于当前时间</p>
<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">SELECT</span> * <span class="keyword">FROM</span> task <span class="keyword">WHERE</span> topic=<span class="string">'topic1'</span> <span class="keyword">status</span>=<span class="number">0</span> <span class="keyword">AND</span> start_time<=<span class="number">1608212942</span> <span class="keyword">LIMIT</span> <span class="number">1</span> <span class="keyword">FOR</span> <span class="keyword">UPDATE</span> <span class="keyword">SKIP</span> <span class="keyword">LOCKED</span>;</span><br></pre></td></tr></table></figure>
<h3 id="消费成功"><a class="markdownIt-Anchor" href="#消费成功"></a> 消费成功</h3>
<p>更新状态为3，表示消费成功</p>
<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">UPDATE</span> task <span class="keyword">SET</span> <span class="keyword">status</span>=<span class="number">3</span> <span class="keyword">WHERE</span> <span class="keyword">id</span>=<span class="number">1000</span>;</span><br></pre></td></tr></table></figure>
<h3 id="消费失败"><a class="markdownIt-Anchor" href="#消费失败"></a> 消费失败</h3>
<p>更新状态为2，表示当前消息消费失败<br />
检查当前retry是否大于0，若大于0，则插入一条新的消息，状态为0，retry-1</p>
<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">UPDATE</span> task <span class="keyword">SET</span> <span class="keyword">status</span>=<span class="number">2</span> <span class="keyword">WHERE</span> <span class="keyword">id</span>=<span class="number">1000</span>;</span><br></pre></td></tr></table></figure>
<h3 id="异常退出"><a class="markdownIt-Anchor" href="#异常退出"></a> 异常退出</h3>
<p>若消费者在消费期间异常退出，则事务会被rollback，那么最多当前消费行为被当做无效行为，但可以保证会被下一个消费者重试，但无法保证重试次数是有效的。但异常退出本身就是少数情况，正常情况下的代码逻辑异常都会被捕获，不会导致该情况发生。</p>
<h1 id="注意点"><a class="markdownIt-Anchor" href="#注意点"></a> 注意点</h1>
<p>由于是通过事务来进行的行锁，所以在逻辑调用的时候要防止内部逻辑中有数据库操作导致的关联rollback，最好开启多个session进行数据库操作</p>
<h1 id="性能问题"><a class="markdownIt-Anchor" href="#性能问题"></a> 性能问题</h1>
<p>消息拉取的SQL会走索引2，所以在mysql8的innodb引擎中，会命中行锁，所以不会产生并发问题，但由于整个消费期间事务不会被释放，所以会有大量的事务和链接保持，会数据库有一定的性能影响，具体影响有多少未进行测试。这个设计也仅仅是一个轻量级的拉模式消息队列实现，至少保证了事务一定会被消费成功。<br />
后续有时间会进行简单的性能测试。</p>
<h1 id="额外"><a class="markdownIt-Anchor" href="#额外"></a> 额外</h1>
<p>基于这个表还可以实现消费结果的存放</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>