不过对于普通选手的我们来说还有救吗？有的兄弟，有的。
Redshift_Shine · · 科技·工程
前情提要：哇这个 GCC 9.3 的杂鱼展开好可爱呀。
在我家的 Arch Linux 电脑上，使用 GCC 15.2 编译此处提到的代码，并使用 -std=c++14 -O2 编译代码，在题目提供的第四个大样例上运行，并使用 /usr/bin/time -v 获取详细信息，得到如下结果：
Command being timed: "./replace"
User time (seconds): 0.05
System time (seconds): 0.02
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.08
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 276832
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 3107
Voluntary context switches: 1
Involuntary context switches: 1
Swaps: 0
File system inputs: 0
File system outputs: 8
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0而在学校的 NOI Linux 2.0 电脑上，给 query 加上 __attribute__((noinline)) 属性并使用 GCC 9.3 编译会得到以下结果：
Command being timed: "./replace"
User time (seconds): 0.08
System time (seconds): 0.06
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.14
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 259312
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 66101
Voluntary context switches: 1
Involuntary context switches: 4
Swaps: 0
File system inputs: 0
File system outputs: 8
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0重头戏来了！此时，我们将 query 的 __attribute__((noinline)) 删掉，再次使用 GCC 9.3 编译，并再次运行，得到以下结果：
Command being timed: "./replace"
User time (seconds): 0.08
System time (seconds): 0.06
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.15
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 320896
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 81492
Voluntary context switches: 1
Involuntary context switches: 4
Swaps: 0
File system inputs: 0
File system outputs: 8
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0首先希望各位读者自己尝试从上面的结果中看出一些端倪。
将目光放在 Maximum resident set size（最大驻留集大小）上。我们惊奇地发现，在强制禁用内联优化时，使用的内存大小在 253MiB 左右；而不禁用内联优化时，使用的内存大小直接达到了 313MiB 左右，内存占用增加了四分之一！
这显然是非常不正常的。四分之一？我们想到开线段树空间时开了四倍的空间，而开 O2 优化时多了四分之一的空间，所以问题在线段树上！
废话。在比赛时高度紧张的心理状态下，不会有人真的想到这点的，也包括我，甚至包括写出这种代码的 NOI 金牌选手。
那怎么查出这种问题呢？还是老办法，上汇编。
假如我们只通过阅读 g++ --help 的内容得到一个简略的编译工作流的话，我们可以得到一个结论：编译流程是预处理、编译至汇编代码、编译至二进制代码、链接。而 g++ 也提供了让我们干涉这个流程的方法。
使用如下代码来将 replace.cpp 编译至汇编文件 replace.s。
g++ -S replace.cpp -std=c++14 -O2 -o replace.s然后用随便一个你喜欢的文本编辑器或 IDE 打开 replace.s，慢慢地往下拉右边的条，眼睛盯着代码，看有没有一长串的类似的代码。很巧的是，确实有。
:::error[编译出的一长串的类似汇编代码]
.L87:
leaq qr(%rip), %rax
addq 72(%rsp), %rax
movq (%rax), %rdx
movq 8(%rax), %r9
cmpq %r9, %rdx
je .L81
movl tim(%rip), %r15d
leaq ans(%rip), %r12
leal 1(%r15), %eax
sarl %eax
leal 1(%rax), %ebx
movl %eax, %r13d
leal (%rbx,%r15), %eax
sarl %eax
leal 1(%rax), %edi
movl %eax, %esi
movl %eax, 24(%rsp)
leal (%rdi,%r15), %eax
movl %edi, 40(%rsp)
sarl %eax
leal 1(%rax), %r8d
movl %eax, %r11d
movl %eax, 84(%rsp)
leal (%r8,%r15), %eax
movl %r8d, 116(%rsp)
sarl %eax
leal 1(%rax), %ebp
movl %eax, %ecx
movl %eax, 148(%rsp)
leal 0(%rbp,%r15), %eax
movl %ebp, 376(%rsp)
sarl %eax
movl %eax, %r10d
movl %eax, 248(%rsp)
leal 1(%rax), %eax
movl %eax, 312(%rsp)
addl %r15d, %eax
sarl %eax
movl %eax, 788(%rsp)
addl $1, %eax
movl %eax, 792(%rsp)
movl %r10d, %eax
addl %ebp, %eax
sarl %eax
movl %eax, %r14d
movl %eax, 252(%rsp)
leal 1(%rax), %eax
movl %eax, 868(%rsp)
addl %r10d, %eax
sarl %eax
movl %eax, 780(%rsp)
addl $1, %eax
movl %eax, 784(%rsp)
movl %r14d, %eax
addl %ebp, %eax
sarl %eax
movl %eax, 772(%rsp)
addl $1, %eax
movl %eax, 776(%rsp)
movl %ecx, %eax
addl %r8d, %eax
sarl %eax
movl %eax, %r10d
movl %eax, 152(%rsp)
leal 1(%rax), %eax
addl %eax, %ecx
movl %eax, 308(%rsp)
movl %ecx, %eax
sarl %eax
movl %eax, 764(%rsp)
addl $1, %eax
movl %eax, 768(%rsp)
movl %r8d, %eax
addl %r10d, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 244(%rsp)
leal 1(%rax), %eax
movl %eax, 856(%rsp)
addl %r10d, %eax
sarl %eax
movl %eax, 756(%rsp)
addl $1, %eax
movl %eax, 760(%rsp)
movl %ecx, %eax
addl %r8d, %eax
movl %r11d, %r8d
sarl %eax
movl %eax, 748(%rsp)
addl $1, %eax
movl %eax, 752(%rsp)
movl %edi, %eax
addl %r11d, %eax
sarl %eax
leal 1(%rax), %r11d
movl %eax, %ecx
movl %eax, 96(%rsp)
movl %r11d, %eax
movl %r11d, 304(%rsp)
addl %r8d, %eax
sarl %eax
movl %eax, %r10d
movl %eax, 236(%rsp)
leal 1(%rax), %eax
movl %eax, 368(%rsp)
addl %r8d, %eax
sarl %eax
movl %eax, 740(%rsp)
addl $1, %eax
movl %eax, 744(%rsp)
movl %r11d, %eax
addl %r10d, %eax
sarl %eax
movl %eax, %r8d
movl %eax, 240(%rsp)
leal 1(%rax), %eax
addl %eax, %r10d
movl %eax, 860(%rsp)
movl %r10d, %eax
sarl %eax
movl %eax, 732(%rsp)
addl $1, %eax
movl %eax, 736(%rsp)
movl %r11d, %eax
addl %r8d, %eax
sarl %eax
movl %eax, 724(%rsp)
addl $1, %eax
movl %eax, 728(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %eax
leal 1(%rax), %r10d
movl %eax, %r11d
movl %eax, 228(%rsp)
movl %r10d, %eax
movl %r10d, 372(%rsp)
addl %ecx, %eax
sarl %eax
movl %eax, %r8d
movl %eax, 280(%rsp)
leal 1(%rax), %eax
movl %eax, 864(%rsp)
addl %ecx, %eax
sarl %eax
movl %eax, 716(%rsp)
addl $1, %eax
movl %eax, 720(%rsp)
movl %r8d, %eax
addl %r10d, %eax
sarl %eax
movl %eax, 708(%rsp)
addl $1, %eax
movl %eax, 712(%rsp)
movl %r11d, %eax
addl %edi, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 232(%rsp)
leal 1(%rax), %eax
movl %eax, 804(%rsp)
addl %r11d, %eax
sarl %eax
movl %eax, 700(%rsp)
addl $1, %eax
movl %eax, 704(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %eax
movl %eax, 692(%rsp)
addl $1, %eax
movl %eax, 696(%rsp)
leal (%rsi,%rbx), %eax
sarl %eax
leal 1(%rax), %edi
movl %eax, %r11d
movl %eax, 80(%rsp)
movl %esi, %eax
addl %edi, %eax
movl %edi, 108(%rsp)
sarl %eax
leal 1(%rax), %r14d
movl %eax, %ecx
movl %eax, 140(%rsp)
movl %esi, %eax
addl %r14d, %eax
movl %r14d, 364(%rsp)
sarl %eax
movl %eax, %r8d
movl %eax, 220(%rsp)
leal 1(%rax), %eax
movl %eax, 300(%rsp)
addl %esi, %eax
sarl %eax
movl %eax, 684(%rsp)
addl $1, %eax
movl %eax, 688(%rsp)
movl %r8d, %eax
addl %r14d, %eax
sarl %eax
movl %eax, %esi
movl %eax, 224(%rsp)
leal 1(%rax), %eax
movl %eax, 852(%rsp)
addl %r8d, %eax
sarl %eax
movl %eax, 676(%rsp)
addl $1, %eax
movl %eax, 680(%rsp)
movl %esi, %eax
addl %r14d, %eax
sarl %eax
movl %eax, 668(%rsp)
addl $1, %eax
movl %eax, 672(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %eax
movl %eax, %esi
movl %eax, 144(%rsp)
leal 1(%rax), %eax
addl %eax, %ecx
movl %eax, 296(%rsp)
movl %ecx, %eax
sarl %eax
movl %eax, 660(%rsp)
addl $1, %eax
movl %eax, 664(%rsp)
movl %edi, %eax
addl %esi, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 216(%rsp)
leal 1(%rax), %eax
addl %eax, %esi
movl %eax, 848(%rsp)
addl %ecx, %edi
movl %esi, %eax
sarl %eax
movl %eax, 652(%rsp)
addl $1, %eax
movl %eax, 656(%rsp)
movl %edi, %eax
sarl %eax
movl %eax, 644(%rsp)
addl $1, %eax
movl %eax, 648(%rsp)
leal (%r11,%rbx), %eax
sarl %eax
leal 1(%rax), %esi
movl %eax, %edi
movl %eax, 92(%rsp)
movl %esi, %eax
movl %esi, 292(%rsp)
addl %r11d, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 208(%rsp)
leal 1(%rax), %eax
movl %eax, 352(%rsp)
addl %r11d, %eax
sarl %eax
movl %eax, 636(%rsp)
addl $1, %eax
movl %eax, 640(%rsp)
movl %esi, %eax
addl %ecx, %eax
sarl %eax
movl %eax, %r8d
movl %eax, 212(%rsp)
leal 1(%rax), %eax
addl %eax, %ecx
movl %eax, 840(%rsp)
movl %ecx, %eax
sarl %eax
movl %eax, 628(%rsp)
addl $1, %eax
movl %eax, 632(%rsp)
movl %esi, %eax
addl %r8d, %eax
movl %ebx, %r8d
sarl %eax
sarl %r8d
movl %eax, 620(%rsp)
addl $1, %eax
movl %eax, 624(%rsp)
leal (%rdi,%rbx), %eax
sarl %eax
leal 1(%rax), %r11d
movl %eax, %esi
movl %eax, 136(%rsp)
movl %r11d, %eax
movl %r11d, 360(%rsp)
addl %edi, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 276(%rsp)
leal 1(%rax), %eax
movl %eax, 844(%rsp)
addl %edi, %eax
sarl %eax
movl %eax, 612(%rsp)
addl $1, %eax
movl %eax, 616(%rsp)
movl %ecx, %eax
addl %r11d, %eax
sarl %eax
movl %eax, 604(%rsp)
addl $1, %eax
movl %eax, 608(%rsp)
leal (%rsi,%rbx), %eax
sarl %eax
movl %eax, %edi
movl %eax, 204(%rsp)
leal 1(%rax), %eax
movl %eax, 800(%rsp)
addl %esi, %eax
sarl %eax
movl %r8d, 16(%rsp)
movl %eax, 596(%rsp)
addl $1, %eax
movl %eax, 600(%rsp)
leal (%rdi,%rbx), %eax
leal 1(%r8), %edi
sarl %eax
movl %edi, 32(%rsp)
movl %eax, 588(%rsp)
addl $1, %eax
movl %eax, 592(%rsp)
leal (%rdi,%r13), %eax
sarl %eax
leal 1(%rax), %r10d
movl %eax, %esi
movl %eax, 72(%rsp)
leal (%r10,%r13), %eax
movl %r10d, 112(%rsp)
sarl %eax
leal 1(%rax), %r11d
movl %eax, %ecx
movl %eax, 128(%rsp)
leal (%r11,%r13), %eax
movl %r11d, 288(%rsp)
sarl %eax
movl %eax, %r14d
movl %eax, 196(%rsp)
leal 1(%rax), %eax
movl %eax, 356(%rsp)
addl %r13d, %eax
sarl %eax
movl %eax, 580(%rsp)
addl $1, %eax
movl %eax, 584(%rsp)
movl %r11d, %eax
addl %r14d, %eax
sarl %eax
movl %eax, %ebp
movl %eax, 200(%rsp)
leal 1(%rax), %eax
movl %eax, 812(%rsp)
addl %r14d, %eax
sarl %eax
movl %eax, 572(%rsp)
addl $1, %eax
movl %eax, 576(%rsp)
movl %r11d, %eax
addl %ebp, %eax
movq %rdx, %rbp
sarl %eax
movl %eax, 564(%rsp)
addl $1, %eax
movl %eax, 568(%rsp)
movl %ecx, %eax
addl %r10d, %eax
sarl %eax
movl %eax, %r11d
movl %eax, 132(%rsp)
leal 1(%rax), %eax
movl %eax, 348(%rsp)
addl %ecx, %eax
sarl %eax
movl %eax, 556(%rsp)
addl $1, %eax
movl %eax, 560(%rsp)
movl %r11d, %eax
addl %r10d, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 192(%rsp)
leal 1(%rax), %eax
movl %eax, 808(%rsp)
addl %r11d, %eax
sarl %eax
movl %eax, 548(%rsp)
addl $1, %eax
movl %eax, 552(%rsp)
movl %ecx, %eax
addl %r10d, %eax
sarl %eax
movl %eax, 540(%rsp)
addl $1, %eax
movl %eax, 544(%rsp)
movl %esi, %eax
addl %edi, %eax
sarl %eax
leal 1(%rax), %r10d
movl %eax, %ecx
movl %eax, 88(%rsp)
movl %esi, %eax
addl %r10d, %eax
movl %r10d, 336(%rsp)
sarl %eax
movl %eax, 184(%rsp)
movl %eax, %r11d
leal 1(%rax), %eax
addl %eax, %esi
movl %eax, 344(%rsp)
movl %esi, %eax
sarl %eax
movl %eax, 532(%rsp)
addl $1, %eax
movl %eax, 536(%rsp)
movl %r11d, %eax
addl %r10d, %eax
sarl %eax
movl %eax, %esi
movl %eax, 188(%rsp)
leal 1(%rax), %eax
addl %eax, %r11d
movl %eax, 836(%rsp)
movl %r11d, %eax
sarl %eax
movl %eax, 524(%rsp)
addl $1, %eax
movl %eax, 528(%rsp)
movl %esi, %eax
addl %r10d, %eax
sarl %eax
movl %eax, 516(%rsp)
addl $1, %eax
movl %eax, 520(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %eax
leal 1(%rax), %r14d
movl %eax, %esi
movl %eax, 176(%rsp)
movl %ecx, %eax
addl %r14d, %eax
movl %r14d, 340(%rsp)
sarl %eax
movl %eax, %r11d
movl %eax, 272(%rsp)
leal 1(%rax), %eax
movl %eax, 828(%rsp)
addl %ecx, %eax
sarl %eax
movl %eax, 508(%rsp)
addl $1, %eax
movl %eax, 512(%rsp)
movl %r11d, %eax
addl %r14d, %eax
leaq rtp(%rip), %r14
sarl %eax
movl %eax, 500(%rsp)
addl $1, %eax
movl %eax, 504(%rsp)
movl %esi, %eax
addl %edi, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 180(%rsp)
leal 1(%rax), %eax
movl %eax, 824(%rsp)
addl %esi, %eax
sarl %eax
movl %eax, 492(%rsp)
addl $1, %eax
movl %eax, 496(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %edi
sarl %eax
leal 1(%rdi), %esi
movl %edi, 48(%rsp)
movl %eax, 484(%rsp)
addl $1, %eax
movl %eax, 488(%rsp)
movl %esi, %eax
addl %r8d, %eax
movl %esi, 104(%rsp)
sarl %eax
leal 1(%rax), %r11d
movl %eax, %ecx
movl %eax, 120(%rsp)
movl %r11d, %eax
movl %r11d, 284(%rsp)
addl %r8d, %eax
sarl %eax
movl %eax, %r10d
movl %eax, 168(%rsp)
leal 1(%rax), %eax
movl %eax, 332(%rsp)
addl %r8d, %eax
sarl %eax
movl %eax, 476(%rsp)
addl $1, %eax
movl %eax, 480(%rsp)
movl %r11d, %eax
addl %r10d, %eax
sarl %eax
movl %eax, %r8d
movl %eax, 172(%rsp)
leal 1(%rax), %eax
movl %eax, 832(%rsp)
addl %r10d, %eax
sarl %eax
movl %eax, 468(%rsp)
addl $1, %eax
movl %eax, 472(%rsp)
movl %r11d, %eax
addl %r8d, %eax
sarl %eax
movl %eax, 460(%rsp)
addl $1, %eax
movl %eax, 464(%rsp)
movl %ecx, %eax
addl %esi, %eax
sarl %eax
leal 1(%rax), %r8d
movl %eax, %r11d
movl %eax, 124(%rsp)
addl %r8d, %ecx
movl %r8d, 328(%rsp)
movl %ecx, %eax
sarl %eax
leal 1(%rax), %ecx
movl %eax, 268(%rsp)
addl %r8d, %eax
sarl %eax
movl %ecx, 448(%rsp)
movl %eax, 452(%rsp)
addl $1, %eax
movl %eax, 456(%rsp)
movl %esi, %eax
addl %r11d, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 164(%rsp)
leal 1(%rax), %eax
movl %eax, 820(%rsp)
addl %r11d, %eax
sarl %eax
movl %eax, 440(%rsp)
addl $1, %eax
movl %eax, 444(%rsp)
movl %ecx, %eax
addl %esi, %eax
sarl %esi
sarl %eax
leal 1(%rsi), %ecx
movl %esi, 100(%rsp)
movl %eax, 432(%rsp)
addl $1, %eax
movl %eax, 436(%rsp)
movl %edi, %eax
addl %ecx, %eax
movl %ecx, 324(%rsp)
sarl %eax
movl %eax, %r11d
movl %eax, 156(%rsp)
leal 1(%rax), %eax
addl %eax, %edi
movl %eax, 320(%rsp)
movl %edi, %eax
movl %ecx, %edi
sarl %eax
movl %eax, 424(%rsp)
addl $1, %eax
movl %eax, 428(%rsp)
movl %r11d, %eax
addl %ecx, %eax
sarl %eax
movl %eax, %ecx
movl %eax, 160(%rsp)
leal 1(%rax), %eax
movl %eax, 796(%rsp)
addl %r11d, %eax
sarl %eax
movl %eax, 416(%rsp)
addl $1, %eax
movl %eax, 420(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %eax
sarl %edi
movl %eax, 408(%rsp)
addl $1, %eax
movl %eax, 412(%rsp)
movl %esi, %eax
movl %edi, 256(%rsp)
addl $1, %edi
addl %edi, %eax
movl %edi, 316(%rsp)
sarl %eax
movl %eax, 264(%rsp)
movl %eax, %ecx
leal 1(%rax), %eax
addl %eax, %esi
movl %eax, 816(%rsp)
movl %esi, %eax
sarl %eax
movl %eax, 400(%rsp)
addl $1, %eax
movl %eax, 404(%rsp)
movl %ecx, %eax
addl %edi, %eax
sarl %edi
movl %ebx, 12(%rsp)
movq %r9, %rbx
sarl %eax
movl %edi, 260(%rsp)
movl %eax, 392(%rsp)
addl $1, %eax
movl %eax, 396(%rsp)
leal 1(%rdi), %eax
leaq T(%rip), %rdi
movl %eax, 380(%rsp)
sarl %eax
movl %eax, 384(%rsp)
addl $1, %eax
movl %eax, 388(%rsp)
.p2align 4,,10
.p2align 3:::
而如果禁用内联就没有这种东西了。
当然，如果你不愿意看汇编代码，也可以使用 LA 群群友当时讨论这个问题的时候使用的办法，加一个编译选项来了解编译器到底优化了什么：
g++ replace.cpp -std=c++14 -O2 -o replace -fopt-info-optimized随后，你会在终端看到这样的输出：
:::info[编译器提供的优化详情]
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4670 into void dfs1(int)/2022 which now has time 857.030833 and size 96, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4673 into int Segment_Tree::query(int, int, int, int)/4672 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4676 into int Segment_Tree::query(int, int, int, int)/4671 which now has time 13.803970 and size 15, net change of +25.
replace.cpp:174:8: optimized: Inlined void write(int)/4679 into int main()/2040 which now has time 6464.567436 and size 276, net change of +16.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4680 into int Segment_Tree::query(int, int, int, int)/4678 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4683 into int Segment_Tree::query(int, int, int, int)/4675 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4686 into int Segment_Tree::query(int, int, int, int)/4674 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4689 into int Segment_Tree::query(int, int, int, int)/4677 which now has time 13.803970 and size 15, net change of +25.
replace.cpp:77:8: optimized: Inlined void Segment_Tree::add(int&, int, int, int, int, int)/4692 into void dfs1(int)/2022 which now has time 1608.478796 and size 271, net change of +25.
replace.cpp:88:8: optimized: Inlined void Segment_Tree::add(int&, int, int, int, int, int)/4693 into void dfs1(int)/2022 which now has time 2352.441566 and size 296, net change of +25.
replace.cpp:16:15: optimized: Inlined void write(int)/4694 into void write(int)/4679 which now has time 28.530000 and size 21, net change of +16.
replace.cpp:102:16: optimized: Inlined int readstr(char*)/4695 into int main()/2040 which now has time 11508.762238 and size 313, net change of +21.
replace.cpp:102:30: optimized: Inlined int readstr(char*)/4696 into int main()/2040 which now has time 16511.774963 and size 334, net change of +21.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4697 into int Segment_Tree::query(int, int, int, int)/4682 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4700 into int Segment_Tree::query(int, int, int, int)/4681 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4703 into int Segment_Tree::query(int, int, int, int)/4688 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4706 into int Segment_Tree::query(int, int, int, int)/4687 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4709 into int Segment_Tree::query(int, int, int, int)/4685 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4712 into int Segment_Tree::query(int, int, int, int)/4684 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4715 into int Segment_Tree::query(int, int, int, int)/4691 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4718 into int Segment_Tree::query(int, int, int, int)/4690 which now has time 13.803970 and size 15, net change of +25.
replace.cpp:16:15: optimized: Inlined void write(int)/4721 into void write(int)/4694 which now has time 28.530000 and size 21, net change of +16.
replace.cpp:128:30: optimized: Inlined int readstr(char*)/4722 into int main()/2040 which now has time 18881.281067 and size 371, net change of +21.
replace.cpp:128:16: optimized: Inlined int readstr(char*)/1969 into int main()/2040 which now has time 21237.197144 and size 392, net change of -6.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4723 into int Segment_Tree::query(int, int, int, int)/4702 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4726 into int Segment_Tree::query(int, int, int, int)/4701 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4729 into int Segment_Tree::query(int, int, int, int)/4720 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4732 into int Segment_Tree::query(int, int, int, int)/4719 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4735 into int Segment_Tree::query(int, int, int, int)/4708 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4738 into int Segment_Tree::query(int, int, int, int)/4707 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4741 into int Segment_Tree::query(int, int, int, int)/4705 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4744 into int Segment_Tree::query(int, int, int, int)/4704 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4747 into int Segment_Tree::query(int, int, int, int)/4699 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4750 into int Segment_Tree::query(int, int, int, int)/4698 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4753 into int Segment_Tree::query(int, int, int, int)/4717 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4756 into int Segment_Tree::query(int, int, int, int)/4716 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4759 into int Segment_Tree::query(int, int, int, int)/4714 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4762 into int Segment_Tree::query(int, int, int, int)/4713 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4765 into int Segment_Tree::query(int, int, int, int)/4711 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4768 into int Segment_Tree::query(int, int, int, int)/4710 which now has time 13.803970 and size 15, net change of +25.
replace.cpp:16:15: optimized: Inlined void write(int)/4771 into void write(int)/4721 which now has time 28.530000 and size 21, net change of +16.
replace.cpp:153:37: optimized: Inlined std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >]/4772 into int main()/2040 which now has time 21403.847351 and size 439, net change of +31.
replace.cpp:16:15: optimized: Inlined void write(int)/4773 into void write(int)/4771 which now has time 28.530000 and size 21, net change of +16.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4774 into int Segment_Tree::query(int, int, int, int)/4767 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4777 into int Segment_Tree::query(int, int, int, int)/4743 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4780 into int Segment_Tree::query(int, int, int, int)/4742 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4783 into int Segment_Tree::query(int, int, int, int)/4728 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4786 into int Segment_Tree::query(int, int, int, int)/4727 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4789 into int Segment_Tree::query(int, int, int, int)/4731 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4792 into int Segment_Tree::query(int, int, int, int)/4730 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4795 into int Segment_Tree::query(int, int, int, int)/4746 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4798 into int Segment_Tree::query(int, int, int, int)/4745 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4801 into int Segment_Tree::query(int, int, int, int)/4755 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4804 into int Segment_Tree::query(int, int, int, int)/4754 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4807 into int Segment_Tree::query(int, int, int, int)/4740 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4810 into int Segment_Tree::query(int, int, int, int)/4739 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4813 into int Segment_Tree::query(int, int, int, int)/4725 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4816 into int Segment_Tree::query(int, int, int, int)/4724 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4819 into int Segment_Tree::query(int, int, int, int)/4734 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4822 into int Segment_Tree::query(int, int, int, int)/4733 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4825 into int Segment_Tree::query(int, int, int, int)/4749 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4828 into int Segment_Tree::query(int, int, int, int)/4748 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4831 into int Segment_Tree::query(int, int, int, int)/4752 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4834 into int Segment_Tree::query(int, int, int, int)/4751 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4837 into int Segment_Tree::query(int, int, int, int)/4737 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4840 into int Segment_Tree::query(int, int, int, int)/4736 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4843 into int Segment_Tree::query(int, int, int, int)/4758 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4846 into int Segment_Tree::query(int, int, int, int)/4757 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4849 into int Segment_Tree::query(int, int, int, int)/4761 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4852 into int Segment_Tree::query(int, int, int, int)/4760 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4855 into int Segment_Tree::query(int, int, int, int)/4764 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4858 into int Segment_Tree::query(int, int, int, int)/4763 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4861 into int Segment_Tree::query(int, int, int, int)/4770 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4864 into int Segment_Tree::query(int, int, int, int)/4769 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4867 into int Segment_Tree::query(int, int, int, int)/4766 which now has time 13.803970 and size 15, net change of +25.
replace.cpp:16:15: optimized: Inlined void write(int)/4870 into void write(int)/4773 which now has time 28.530000 and size 21, net change of +16.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4871 into int Segment_Tree::query(int, int, int, int)/4776 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4874 into int Segment_Tree::query(int, int, int, int)/4779 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4877 into int Segment_Tree::query(int, int, int, int)/4778 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4880 into int Segment_Tree::query(int, int, int, int)/4785 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4883 into int Segment_Tree::query(int, int, int, int)/4784 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4886 into int Segment_Tree::query(int, int, int, int)/4791 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4889 into int Segment_Tree::query(int, int, int, int)/4790 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4892 into int Segment_Tree::query(int, int, int, int)/4797 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4895 into int Segment_Tree::query(int, int, int, int)/4796 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4898 into int Segment_Tree::query(int, int, int, int)/4803 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4901 into int Segment_Tree::query(int, int, int, int)/4802 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4904 into int Segment_Tree::query(int, int, int, int)/4809 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4907 into int Segment_Tree::query(int, int, int, int)/4808 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4910 into int Segment_Tree::query(int, int, int, int)/4815 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4913 into int Segment_Tree::query(int, int, int, int)/4814 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4916 into int Segment_Tree::query(int, int, int, int)/4821 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4919 into int Segment_Tree::query(int, int, int, int)/4820 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4922 into int Segment_Tree::query(int, int, int, int)/4827 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4925 into int Segment_Tree::query(int, int, int, int)/4826 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4928 into int Segment_Tree::query(int, int, int, int)/4833 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4931 into int Segment_Tree::query(int, int, int, int)/4832 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4934 into int Segment_Tree::query(int, int, int, int)/4839 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4937 into int Segment_Tree::query(int, int, int, int)/4838 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4940 into int Segment_Tree::query(int, int, int, int)/4845 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4943 into int Segment_Tree::query(int, int, int, int)/4844 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4946 into int Segment_Tree::query(int, int, int, int)/4851 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4949 into int Segment_Tree::query(int, int, int, int)/4850 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4952 into int Segment_Tree::query(int, int, int, int)/4857 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4955 into int Segment_Tree::query(int, int, int, int)/4856 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4958 into int Segment_Tree::query(int, int, int, int)/4863 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4961 into int Segment_Tree::query(int, int, int, int)/4862 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4964 into int Segment_Tree::query(int, int, int, int)/4869 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4967 into int Segment_Tree::query(int, int, int, int)/4868 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4970 into int Segment_Tree::query(int, int, int, int)/4782 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4973 into int Segment_Tree::query(int, int, int, int)/4781 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4976 into int Segment_Tree::query(int, int, int, int)/4830 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4979 into int Segment_Tree::query(int, int, int, int)/4829 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4982 into int Segment_Tree::query(int, int, int, int)/4806 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4985 into int Segment_Tree::query(int, int, int, int)/4805 which now has time 13.803970 and size 15, net change of +25.
optimized: Inlined int Segment_Tree::query(int, int, int, int)/4988 into int Segment_Tree::query(int, int, int, int)/4854 which now has time 13.803970 and size 15, net change of +25.:::
相信我，当你看到这么一长串的相同内联展开的时候，这真的很不正常。
在考场上，解决这种问题最简单的办法就是换个写法。开多一些临时变量存储数据，就比如这样。
inline int query(int rt,int l,int r,int p){
if(!rt) return 0;
if(l==r) return a[rt].tag;
int mid=l+r>>1;
int ret=0,tmp=a[rt].tag;
if(p<=mid) ret=query(ls,l,mid,p);
else ret=query(rs,mid+1,r,p);
return ret+tmp;
}这种写法并不会触发错误的内联优化。
有关技术的部分到这里就结束了，如果不想看我下面的杂谈可以关掉。
写到这里的时候我真的很生气，但更多的是不解。现在的 CSP-J/S 到底在考什么？
考知识点存量吗？可能是，因为 CSP-S 2022 的数据传输考的是动态 DP。如果你没见过，你几乎不可能做得出来；考模拟吗？可能是，因为 CSP-S 2023 的结构体就是一道大模拟。这种题任何人给足时间都能做得出来，它没有任何思维上的难度，但是如果你架构没构思好，在一堆边界条件上浪费时间，那就不可能在考场上得到分；考思维吗？绝对就是，CSP-S 2024 的擂台游戏就是一道纯粹的思维题。它的正解完全不包含任何的高级数据结构，但它的思维链就是长到了极点，让 CSP-S 2024 成为了一场极难 AK 的 CSP-S。
那它考运气吗？其实也是。CSP-S 2025 的谐音替换，至少于我而言，相当考验运气。我很不喜欢偏序，以至于当我耗尽心力终于（看似）拿到了前两道题的 AC 之后，在这道题上完全想不到任何有关偏序的东西。我的思路竟然是排序+可持久化字典树，由于 C++ 中几乎任何 STL 元素都实现了 swap 方法，它确实跑得挺快的，也可以 AC。可以说在我完全不知道怎么用偏序解这题的前提下，我拿到这一百分的运气成分极大。
我们假设上面的考点全部都是合理的且的确能反应一个考生在解决题目方面的素养。然而这一切的前提都是它们与“解决题目”本身有关。在这个问题出现之后，为了保证自己的解不出现问题，我们甚至要研究汇编，要研究编译原理，甚至还要研究解决编译问题的方法！它们确实有助于我们更好地了解“程序”本身，但它与“解题”有关吗？没有！
解题的关键在于想出问题怎么做。思路和实现在信息学竞赛中都非常重要，但没有思路，何来实现？现在有选手有思路，也把它实现出来了，但就是要用一个与解题完全无关的东西（老旧编译器的负优化）绊他一脚。这是哪里来的道理？
我非常期望这次发现的问题能成为一个契机，让我们能在竞赛中用上更好的标准（至少是 C++20），用上更好的语言特性（结构化绑定，ranges）。OI 的最高比赛 IOI 所使用的 C++ 标准已经是 C++20，我们没有理由将我们的选手限制在 C++14。
我之所以如此期望，是因为在之前，Codeforces 出现过一个性质类似的事情。不妨让我们看看这个平台是怎么处理这个问题的。
2024 年 3 月 2 日，Codeforces 用户 pajenegod 发布了讨论帖 Slowdown bug affecting C++ (64 bit) on Codeforces，揭示了 Codeforces 当时使用的 C++ 语言选项存在巨大的问题，使得创建特定大小的 vector 可以直接使得原本正常运行的代码 TLE。该方法可以 hack 掉若干个 LGM 的代码。
不过，由于其触发的条件较为特别（必须是特定大小的二维 vector 数组，且对于 int 和 long long 大小不同，cin 输入过程必须处于 vector 生命周期之内），短期来看，只要不出现二维题目，其并不会对比赛公平造成很大的影响。
随后，ToxicPie9 给出了他的研究结果，将问题锁定在 MSVCRT 对 malloc 的实现。
对此 Mike 是怎么处理的呢？在三天之后（对于他来说这已经相当迅速了）他推出了使用 GCC 13 的 C++20 语言选项，同时隐藏了所有的已确定出现问题的 C++ 语言选项。然而不幸的是，问题仍然存在。Mike 在不久后直接禁用了所有 64 位 C++ 语言选项，使得当时的最高 C++ 标准下降至 C++17，且 __int128 无法使用。我在这期间使用 32 位 C++ 完成了两场比赛，分别是 CF Edu Round 163 和 CF Round 934。
一段时间后，GCC 13 被重新启用。五个月后，Mike 发布新帖 Welcome GNU G++23 14.2 (64 bit, msys2)，上述的 bug 最终失效。
你也许可以在一段时间内指责 Mike 反作弊不力，但你不能质疑 Mike 在技术问题上的尽职尽责。
我希望以后所有选手都不必在上面这样与解题无关的问题上消耗大量时间，让信息学竞赛的核心真正地放在“解出一道题”上，而不是“让编译器开心”。不过我们确实得让评测机开心，因为时间限制和内存限制正是因此而生的。