企业官网建设流程全解析

最近在帮几个学弟学妹备战大厂暑期实习笔试，聊到阿里工程岗4月8日那场笔试题时，大家普遍反映第三题“相邻等值对贡献和”看着不难，但真正动手写的时候却容易卡住。这道题很有意思，它不考什么冷门数据结构，也不考复杂的算法模板，核心就是一道“想明白就秒杀、想不明白就超时”的思维模拟题。今天我把这道题的完整思路、Java/C++/Python三种语言的写法，以及我在实际调试中踩过的坑都整理出来，给正在刷题备战的同学们一份可以直接抄作业的参考。

先说结论：这道题只要理解了“单点修改只会影响局部相邻关系”这个关键点，代码量其实非常小，三种语言的核心逻辑都在二十行以内。但恰恰是这层窗户纸，很多人现场没捅破，硬生生写成每次修改都全数组重新遍历，复杂度直接爆炸。下面我把题目还原、思路推导、代码实现和常见坑位一步步拆开讲清楚。

1. 题目理解与考点剖析

1.1 题目描述还原

我根据同学们考后的回忆，把题目核心信息还原如下（细节表述可能和原题有出入，但考点和思路是一致的）：

给定一个长度为n的整数数组a，下标从1开始。定义对于任意满足1 <= i < n且a[i] == a[i + 1]的相邻下标对(i, i+1)，称为一个“相邻等值对”，它的贡献值为下标i。整个数组的“相邻等值对贡献和”，就是所有相邻等值对下标i的加总sum。

现在有q次操作，每次操作给出两个整数pos和val，表示把a[pos]的值修改为val。每次修改之后，需要输出当前整个数组的相邻等值对贡献和。

举个例子：

输入： 5 3 1 2 2 3 3 2 3 3 3 5 1 输出： 4 9 5

初始数组是[1, 2, 2, 3, 3]，其中a[2] == a[3]，贡献下标2；a[4] == a[5]，贡献下标4，所以初始贡献和是6。第一次修改把a[2]改成3，数组变成[1, 3, 2, 3, 3]，此时只有a[4] == a[5]，贡献和为4。第二次修改把a[3]改成3，数组变成[1, 3, 3, 3, 3]，此时a[2] == a[3]、a[3] == a[4]、a[4] == a[5]三对都成立，贡献和是2 + 3 + 4 = 9。第三次修改把a[5]改成1，数组变成[1, 3, 3, 3, 1]，此时贡献和是2 + 3 = 5。

注意：这里的贡献值是下标i，而不是固定为1。如果题目改成每对等值对贡献都是1，核心解法完全一样，只需要把累加的量从i改成1即可。后面的实现我会用“下标贡献”这个版本讲，因为它更贴合“贡献和”这个题眼，稍微有一点点区分度。

1.2 这道题真正在考什么

很多同学一看到这题，第一反应是“这不就是遍历数组统计嘛”，然后唰唰唰写了个双重循环：每次修改后重新把整个数组扫一遍，统计所有a[i] == a[i+1]的位置，累加下标输出。

这做法对不对？逻辑上完全对，但性能上就是灾难。n和q的范围题目一般不会给得太小，在阿里的笔试里，这种题的n和q大概率会跑到1e5甚至2e5级别。如果每次修改都O(n)遍历，总复杂度O(nq)就是1e10量级，随便哪个评测机都扛不住，运行超时基本是板上钉钉的。

所以这道题真正的考点不是“你会不会统计相邻相等元素”，而是“你能不能发现单点修改对全局答案的影响其实是有限的”。换句话说，它考察的是局部变更对全局状态影响范围的洞察力，这是很多工程场景里非常核心的思维习惯——改了一个变量，哪些依赖它的结果会变，哪些不会变，你心里得有一本账。

另外它也考察基本的贡献转换思想：全局答案可以拆成若干个局部贡献之和，而局部贡献只在特定条件下发生变化，维护起来自然就快。这种思想在LeetCode上也经常出现，比如那些“翻转一段区间后求总和”的题目，套路都是一样的。

2. 从暴力到O(1)更新：解题思路拆解

2.1 暴力做法为什么会被卡

先把最直白的暴力思路写出来，方便大家对照：

每次修改完，从i = 1到n - 1遍历，如果a[i] == a[i+1]，就把i加到答案里，然后输出。

这个写法的复杂度是O(nq)，以n = 1e5、q = 1e5举例，总的判断次数是1e10次。现代CPU每秒大概执行1e8到1e9次简单操作，一个测试点就要跑几十秒甚至几分钟。笔试系统通常单个用例限制1到2秒，所以暴力代码交上去就是TLE，没有任何侥幸空间。

有同学可能会想：能不能用前缀和或者树状数组优化？前缀和预处理确实能把单次查询优化到O(1)，但问题在于每次修改后，前缀和数组本身也要重新算，算一次依然要O(n)，本质上没有优化。树状数组可以做区间求和，但前提是你能找到一种方式，让每次修改只影响O(log n)以内的数据项。这道题确实存在这样的结构，但不需要把线段树树状数组搬出来，因为影响范围比log n还小，只有常数个位置。

2.2 单点修改的影响范围

现在我们掰开揉碎来分析：当a[pos]发生改变时，哪些相邻等值对的状态可能受影响？

相邻等值对一共只有n - 1对，分别是(1,2)、(2,3)、...、(n-1,n)。注意a[pos]只出现在以下这些相邻对中：

• 作为左元素：当pos < n时，出现在(pos, pos+1)这对中；
• 作为右元素：当pos > 1时，出现在(pos-1, pos)这对中。

所以一个位置被修改，最多只会影响两对相邻关系：(pos-1, pos)和(pos, pos+1)。其他所有相邻对的两个元素都没变，相等关系自然也不会变，对应的贡献值不需要动。

这里可以打个生活化的比方：想象一排灯串，每个灯泡之间有一个开关接头。如果你把整排灯串中间某一个灯泡换了，那么会受影响的只有这个灯泡和左边灯泡之间的接头、以及这个灯泡和右边灯泡之间的接头。其他所有接头两端的灯泡都没动过，开合状态当然不会变。

明白了这一点，维护答案就变得很简单了：

1. 预处理：先把初始数组的贡献和ans算出来，这个需要O(n)。
2. 每次修改前，把(pos-1, pos)和(pos, pos+1)这两对当前的贡献从ans中减掉。
3. 修改a[pos]的值。
4. 重新检查这两对相邻关系，如果它们变成等值对了，就把对应贡献加到ans里。
5. 输出ans。

这样单次修改的时间复杂度是O(1)，整个过程是O(n + q)，跑1e5级别的数据轻轻松松。

2.3 贡献值定义变化不影响核心思路

这里再展开说一下，诸多阿里的同学反馈中，这道题具体贡献值的定义可能有不同版本。有的版本是每对相邻等值对贡献1，直接输出对的数量；有的版本是贡献下标i；还有的版本可能是贡献i和i+1的和之类的变体。但无论贡献值怎么定义，只要每一对(i, i+1)的贡献是一个预先可以确定的数（比如bound[i]），核心维护思想完全一样：

• 预处理时，把“满足a[i] == a[i+1]的bound[i]”全部累加进ans；
• 修改pos时，先把pos附近两对可能存在的贡献从ans中扣除；
• 改完值后，再把新的两对贡献加回来。

所以你在考场上不用纠结题目具体定义的是哪种贡献，只需要先明确“每对相邻等值对的贡献是多少”以及“我用的数组下标是1-based还是0-based”，剩下的事情就是机械地套这个局部更新模板。这种“剥离开具体数值、抓住增量维护逻辑”的抽象能力，往往是笔试能不能快速AC的分水岭。

3. 三种语言实现与踩坑点

3.1 Java版实现：注意读入和长整型

Java的代码我放在下面，用的是BufferedReader + StringTokenizer做输入，输出用StringBuilder统一攒着再一次性打印。笔试场景下Java的Scanner读数据太慢，遇到大数据量很容易TLE，这是老生常谈的坑。

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int[] a = new int[n + 2]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i] = Integer.parseInt(st.nextToken()); } long ans = 0; for (int i = 1; i < n; i++) { if (a[i] == a[i + 1]) { ans += i; } } StringBuilder sb = new StringBuilder(); while (q-- > 0) { st = new StringTokenizer(br.readLine()); int pos = Integer.parseInt(st.nextToken()); int val = Integer.parseInt(st.nextToken()); // 先移除旧贡献 for (int i = pos - 1; i <= pos; i++) { if (i >= 1 && i < n && a[i] == a[i + 1]) { ans -= i; } } a[pos] = val; // 再添加新贡献 for (int i = pos - 1; i <= pos; i++) { if (i >= 1 && i < n && a[i] == a[i + 1]) { ans += i; } } sb.append(ans).append('\n'); } System.out.print(sb); } }

这里我用了一个小技巧：把“移除旧贡献”和“添加新贡献”都写成循环遍历i = pos - 1到i = pos，这样即使pos在数组边界，比如pos=1，循环里的i会取到0，配合i >= 1的判断直接跳过，不会出现数组越界。代码也简洁清晰，不用单独写if分支处理头尾特殊情况。

为什么ans要声明为long而不是int？因为贡献值是下标i的累加，极端情况下数组里所有相邻元素都相等，也就是n-1对全都贡献，那么ans最大是1 + 2 + ... + (n-1) = n(n-1)/2，当n=2e5时约为2e10，明显超出int范围。笔试里因为溢出吃WA是非常冤的，我建议只要看到“和”这种统计，一律用long。

3.2 C++版：关闭同步别乱混

C++版本核心逻辑和Java完全一致，最大的区别在于输入输出。我用了ios::sync_with_stdio(false)和cin.tie(nullptr)两行提速，这样cin/cout就足够快了。但要特别注意，一旦关闭同步，代码里就不要再混用scanf/printf，否则可能出现诡异的输入错乱。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<long long> a(n + 2); for (int i = 1; i <= n; i++) { cin >> a[i]; } long long ans = 0; for (int i = 1; i < n; i++) { if (a[i] == a[i + 1]) { ans += i; } } while (q--) { int pos; long long val; cin >> pos >> val; for (int i = pos - 1; i <= pos; i++) { if (i >= 1 && i < n && a[i] == a[i + 1]) { ans -= i; } } a[pos] = val; for (int i = pos - 1; i <= pos; i++) { if (i >= 1 && i < n && a[i] == a[i + 1]) { ans += i; } } cout << ans << '\n'; } return 0; }

C++的vector默认初始化为0，所以开n+2大小后a[0]和a[n+1]都是0，配合边界判断用起来很安全。有人可能会想，既然a[0]和a[n+1]都是0，那如果数组里其他位置也恰好是0，会不会误判？不会，因为边界判断i >= 1 && i < n保证了我们永远不会去检查a[0]和a[n+1]参与的相邻对，这两个哨兵位置纯粹是为了防止数组越界，不会进入逻辑判断。

3.3 Python版：用缓冲区读入

Python版本我用sys.stdin.buffer.read()一次把所有输入读进来，按空格直接切分成整数列表，避免多次调用input()造成性能损耗。这在数据量大的时候效果非常明显。

import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) idx = 0 n, q = data[idx], data[idx + 1] idx += 2 a = [0] * (n + 2) for i in range(1, n + 1): a[i] = data[idx] idx += 1 ans = 0 for i in range(1, n): if a[i] == a[i + 1]: ans += i out = [] for _ in range(q): pos, val = data[idx], data[idx + 1] idx += 2 for i in (pos - 1, pos): if 1 <= i < n and a[i] == a[i + 1]: ans -= i a[pos] = val for i in (pos - 1, pos): if 1 <= i < n and a[i] == a[i + 1]: ans += i out.append(str(ans)) sys.stdout.write("\n".join(out)) if __name__ == "__main__": main()

Python版本里我用元组(pos - 1, pos)而不是range循环，主要是省去循环变量自增的开销，代码也更直观。这里要注意的是Python的int没有溢出问题，所以ans随便累加，不用担心。

3.4 三份代码对比与易错点

为了让你一眼看清三种实现的异同，我整理了一张对比表。

这里我特别想多说一句下标的问题。很多算法题默认数组下标从0开始，但本题为了贡献值用下标i表示更自然，我用的是1-based下标。如果你平时写0-based写习惯了，很容易在边界判断上出错。一个保险的做法是：不管题目怎么给，你在代码里明确注释“a数组下标1..n有效”，然后所有循环和判断都围绕这个约定来，不要中间切来切去。

4. 在线测试与自测用例

4.1 手动推演一遍样例

题目做完了，还需要能自己验证。上面那个样例是我特意挑的，它覆盖了好几种情况：初始有相邻等值对、修改中间位置、修改末尾位置、修改产生新的连续等值段。我们手动推演一遍，顺便帮你验证理解是否正确。

初始数组：[1, 2, 2, 3, 3]，a[2]==a[3]贡献2，a[4]==a[5]贡献4，ans=6。

第一次操作：pos=2, val=3。修改前受影响的是(1,2)和(2,3)两对。当前(1,2)：a[1]=1, a[2]=2，不相等，贡献0；(2,3)：a[2]=2, a[3]=2，相等贡献2，ans先减去2。修改a[2]=3，数组变[1,3,2,3,3]。重新检查(1,2)：1 != 3，不贡献；(2,3)：3 != 2，不贡献。ans=6-2=4。输出4。

第二次操作：pos=3, val=3。修改前受影响的是(2,3)和(3,4)两对。当前(2,3)：a[2]=3, a[3]=2，不相等；(3,4)：a[3]=2, a[4]=3，不相等，所以ans不减。修改a[3]=3，数组变[1,3,3,3,3]。重新检查(2,3)：3==3，加贡献2；(3,4)：3==3，加贡献3。ans=4+2+3=9。输出9。

第三次操作：pos=5, val=1。修改前受影响的是(4,5)这一对（因为pos-1=4，pos=5，但pos=n时，i=n超出i < n限制被跳过，实际上只检查(4,5)）。当前(4,5)：a[4]=3, a[5]=3，相等贡献4，ans减去4。修改a[5]=1，数组变[1,3,3,3,1]。重新检查(4,5)：3 != 1，不贡献。ans=9-4=5。输出5。

手动推演结果和输出完全一致，说明逻辑是对的。

4.2 边界用例与自测要点

在线测试除了跑题目给的样例，我建议你补上这几类边界数据，能迅速暴露代码里最常见的隐患：

• n=1的情况。此时没有任何相邻对，无论怎么修改，ans始终为0。代码里预处理循环for (int i = 1; i < n; i++)根本不会执行，更新时pos - 1可能等于0，pos可能等于1，但边界判断会拦下来，输出0。
• 修改pos=1（数组首元素）。此时只有(1,2)这一对可能受影响，更新循环里的i依次为0和1，i=0被边界拦掉，i=1正常检查。
• 修改pos=n（数组末尾元素）。此时只有(n-1,n)这一对可能受影响，更新循环里的i依次为n-1和n，i=n被i < n拦掉。
• 所有位置都相等，比如n=5, a=[7,7,7,7,7]，此时贡献和是1+2+3+4=10，连续修改中间位置观察ans变化，能验证减法加法是否成对出现。
• 修改pos后新值恰好和旧值一样。这种情况下先减后加会互相抵消，ans不会变。但如果你贪图省事不写“先减后加”，改成“先判断新旧是否相同再决定要不要更新”，逻辑就容易出bug——因为即使a[pos]没变，它和左邻、右邻的相等关系本来就要重新确认，写起来反而要嵌套一堆条件分支。所以我推荐统一用“无条件先减、再加”的写法，保证逻辑不会漏。

5. 常见问题与排查技巧

5.1 笔试现场容易踩的坑

先说个我见过很多次的错误：更新时只减了a[pos]和a[pos+1]这一对，忽略了a[pos-1]和a[pos]这一对。这样会导致修改后左侧的相邻等值对没有被正确更新，样例能过一部分，但一跑到中间位置的修改用例就WA。记住，a[pos]同时是左右两对相邻关系的参与者，漏掉任何一对都不行。

第二个高频坑是用int存ans。我前面算过，即使n只有2e5，贡献和就能到2e10，int最大只能表示约2.1e9，直接溢出成负数。笔试系统不会提示你“这里该用long”，它只会给你一个Wrong Answer，排查起来非常浪费时间。

第三个坑在Java和Python里格外明显：用Scanner和input()逐行读大数据。有些题n和q是2e5，输入文件能有几十万甚至上百万个整数，Scanner的解析开销很大，Python的input()更不用说，每调用一次都有系统级开销。如果你的算法没问题却仍然TLE，先检查读入方式是不是太慢了。

第四个坑是关于更新顺序。一定要牢记：先根据旧值减掉可能存在的旧贡献，再修改a[pos]，最后根据新值添加新贡献。如果先把a[pos]改了再去做减法，你减掉的是新值产生的贡献，而不是旧值的，ans就会错乱。写代码的时候这两步之间不要插入任何其他对a数组的修改。

5.2 题目如果想升级怎么办

这道题的简单版本是单点修改+全局查询。如果面试官或者笔试变体把问题升级，比如把“全局查询”改成“区间查询”，问你每次修改后，输出某个区间[l,r]内相邻等值对的贡献和，那原来的O(1)增量维护就不够用了，因为你还需要快速回答任意区间的和。

这种情况有两条路。一是用前缀和：预处理时维护一个前缀贡献数组pre[i]，表示前i个相邻位置的总贡献，也就是pre[i] = pre[i-1] + (a[i] == a[i+1] ? 贡献i : 0)，这样查询[l,r]区间内相邻等值对贡献和就是pre[r-1] - pre[l-1]，O(1)查询。但缺点也很明显，一旦发生单点修改，前缀和数组要重新计算，退化成O(n)。

二是因为有修改，更合适的是用线段树或树状数组。每个叶子节点存“当前位置相邻对是否相等产生的贡献”，修改a[pos]时，更新两个叶子节点pos-1和pos，然后向上合并区间和，查询和更新都是O(log n)。如果题目数据范围达到1e5甚至1e6，log n的复杂度依然轻松应对。不过说实话，单点修改+全局查询的场景，硬上线段树属于杀鸡用牛刀，笔试时间有限，还是O(1)维护来得干脆。

还有一种升级是把“相等”条件改成更复杂的比较规则，比如a[i]+a[i+1]为奇数、a[i]和a[i+1]的差的绝对值小于k等等。这种变体下，核心的“修改pos只影响pos-1和pos两对”的性质仍然成立，你还是可以用维护贡献的方式，只是判断条件变了而已。抓住这个性质，不管题目怎么包装，你都能很快写出更新逻辑。

5.3 三种语言在笔试中的选择建议

如果让我给建议，平时练题用Python最舒服，代码短、调试快、不容易因为类型问题翻车，很适合快速验证思路。但笔试的时候，我更推荐用自己最熟练的语言，而不是“理论上最快”的语言。因为考试拼的不只是性能，更是你在紧张状态下写对代码的概率。

C++的优点是运行速度快、模板库齐全，但也正因为各种隐式类型转换、指针和迭代器容易出错，调试成本高。Java则夹在中间，代码量比Python多，但比C++更容易写出不出错的代码，加上JVM的垃圾回收，实际运行速度在1e5级别数据下完全没问题。Python的缺点是输入输出慢，但配合sys.stdin.buffer.read()基本也能应对大部分笔试数据量。

我个人在笔试里一般用Java，因为它的长整型明确，集合类工具多，IO模板我背得很熟，遇到这类思维模拟题可以做到“脑中思路清晰，手上代码咔咔出”。建议你也在考试前准备好自己的固定输入输出模板，Java的BufferedReader模板、C++的ios同步关闭模板、Python的buffer读入模板，分别背熟一个，考场上就不用现场想。

最后说点个人经验。我在模拟这道题的时候，一开始也走了弯路，总想着用Map记录每个相等位置的集合，再维护一个有序结构来处理修改，写了七八十行代码。后来冷静下来画了个数组下标示意图，发现被修改的位置左右各扫一眼就够了，根本不需要任何复杂数据结构。很多时候笔试卡住不是因为题目难，而是我们下意识地把问题想复杂了。遇到这种“维护全局状态”的题目，先停下来说清楚“一次变更会影响哪些局部”，往往答案就自己浮出来了。你在考场上如果没思路，也可以试试在草稿纸上画一排格子，手动模拟一次修改，把变化的位置圈出来，这比闭着眼睛空想要管用得多。