解题思路

题目本质： 有一个可动态删减的序列，指令依次指定“初始下标”的元素进入“向左合并”状态：

• 若它左边相邻元素值相同，则合并成一个值+1的新数，并继续向左尝试合并；
• 一旦某个原始元素参与过合并（无论是左还是右），它就失去“标识”，之后的指令再也不能作用到它。

关键点：

1. 序列会被频繁删除元素（合并时删除一个），需要高效维护前驱/后继。
2. 指令使用的是“初始下标”，而序列位置会不断变化，所以要维护“初始下标 → 当前节点”的映射。
3. 合并时，参与合并的两个“原始元素”的标识都要失效（即之后指令不能再找到它们）。

核心算法

使用 数组实现的双向链表 + 标记数组 来模拟整个过程：

1. 初始化：

   • val[i]：当前节点 i 的数值（初始为输入数组）。
   • left[i]、right[i]：节点 i 在当前序列中的左邻和右邻（-1 表示不存在）。
   • orig[i]：这个节点最初对应的“初始下标”（0~N-1），若已变成“合并产生的新数”，则设为 -1。
   • pos[id]：记录“初始下标 id”当前所在的节点编号，若该元素已参与过合并，则设为 -1。
   • length：当前序列长度，初始为 N，每发生一次合并长度减 1。

2. 处理每条指令 id：

   • 找到当前节点：node = pos[id]，若为 -1，说明对应原始数字已被合并掉，跳过。

   • 否则，从该节点开始作为“需要合并”的数字，一直向左尝试：

     cur = node
     while True:
         prev = left[cur]
         若 prev 不存在 或 val[prev] != val[cur] ：停止
         否则合并 prev 和 cur：
            - 两个节点的“原始标识”都失效：
               若 orig[cur] != -1: pos[orig[cur]] = -1
               若 orig[prev] != -1: pos[orig[prev]] = -1
               orig[cur] = orig[prev] = -1
            - 把值加到左边节点：val[prev] += 1
            - 把右边节点 cur 从链表中删掉：
               right[prev] = right[cur]
               若 right[cur] 存在：left[right[cur]] = prev
            - 当前“需要合并”的数字变成合并后的 prev，继续向左：
               cur = prev
               length -= 1
     

   • 注意：如果一次都没进入循环，说明左边没有相同的，当前元素也没参与合并，因此它的标识仍然有效，之后指令还可以再次作用在它上。

3. 所有指令处理完后，输出 length 即为最终序列剩余元素个数。

正确性关键点说明：

• 每次合并至少删除一个节点，最多删除 N-1 个节点，因此总合并次数 O(N)。
• 合并时，所有参与过合并的“原始位置”的 pos 都设成 -1，能保证后续指令不会再错误地命中“新产生的数字”。
• 向左合并只沿着双向链表移动，整体时间复杂度可控。

复杂度分析

• 初始化：O(N)

• 每条指令：从被指定的节点向左尝试合并，每成功合并一次就删除一个节点。 一共最多有 N-1 次合并，因此所有指令总合并次数 ≤ N-1。

• 因此整题时间复杂度： [ O(N + M + \text{总合并次数}) = O(N + M) ]

• 空间复杂度：

  • 需要存储 val、left、right、orig、pos 五个长度为 N 的数组，
  • 空间复杂度：O(N)

在 N ≤ 10⁵ 的范围内，完全可以通过。

代码实现

Python 实现

# 序列合并游戏 - Python 实现
# 使用数组模拟双向链表，按题意依次处理指令

import sys

# 主要逻辑写在 solve 函数中
def solve():
    data = sys.stdin.read().split()
    it = iter(data)

    # 读入 N 和初始序列
    N = int(next(it))
    vals = [int(next(it)) for _ in range(N)]

    # 读入 M 和指令序列
    M = int(next(it))
    cmds = [int(next(it)) for _ in range(M)]

    # 双向链表数组
    val = vals[:]                     # 当前节点的值
    left = [i - 1 for i in range(N)]  # 左指针
    right = [i + 1 for i in range(N)] # 右指针
    right[N - 1] = -1                 # 最后一个没有右节点

    orig = [i for i in range(N)]      # 每个节点当前对应的原始下标，合并后设为 -1
    pos = [i for i in range(N)]       # 每个原始下标当前所在的节点编号，失效后设为 -1

    length = N  # 当前序列长度

    # 依次处理每条指令
    for idx in cmds:
        node = pos[idx]
        # 如果该原始位置的数字已经参与过合并，则无动作
        if node == -1:
            continue

        cur = node  # 当前处于“需要合并”状态的节点

        while True:
            prev = left[cur]
            # 没有前驱或者值不同，不能再合并
            if prev == -1 or val[prev] != val[cur]:
                break

            # 合并 prev 和 cur

            # 1. 对两个参与合并的原始下标清除映射
            if orig[cur] != -1:
                pos[orig[cur]] = -1
            if orig[prev] != -1:
                pos[orig[prev]] = -1

            # 合并后产生的新数字没有标识
            orig[cur] = -1
            orig[prev] = -1

            # 2. 数值 +1 叠加到左边节点 prev 上
            val[prev] += 1

            # 3. 把右边节点 cur 从链表中删除
            nxt = right[cur]
            right[prev] = nxt
            if nxt != -1:
                left[nxt] = prev

            # 可选：标记 cur 已删除
            left[cur] = -1
            right[cur] = -1

            # 4. 合并后，新数字位于 prev，继续向左尝试合并
            cur = prev
            length -= 1

    # 输出最终序列长度
    print(length)


if __name__ == "__main__":
    solve()

Java 实现

// 序列合并游戏 - Java 实现
// 使用数组模拟双向链表，按题意依次处理指令

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    // 主要逻辑写在 solve 函数中
    public static void solve(InputStream in, PrintStream out) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringTokenizer st;

        // 读入 N
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        // 读入初始序列
        int[] val = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            val[i] = Integer.parseInt(st.nextToken());
        }

        // 读入 M
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());

        // 读入指令
        int[] cmds = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            cmds[i] = Integer.parseInt(st.nextToken());
        }

        // 双向链表数组
        int[] left = new int[N];
        int[] right = new int[N];
        int[] orig = new int[N];  // 每个节点当前对应的原始下标
        int[] pos = new int[N];   // 原始下标 -> 当前节点编号

        for (int i = 0; i < N; i++) {
            left[i] = i - 1;          // 左邻
            right[i] = (i == N - 1) ? -1 : i + 1; // 右邻
            orig[i] = i;              // 初始每个节点就是自己
            pos[i] = i;               // 原始下标 i 对应节点 i
        }

        int length = N;  // 当前序列长度

        // 依次处理每条指令
        for (int k = 0; k < M; k++) {
            int idx = cmds[k];
            int node = pos[idx];

            // 已经参与过合并的原始位置，无动作
            if (node == -1) {
                continue;
            }

            int cur = node;  // 当前“需要合并”的节点

            while (true) {
                int prev = left[cur];
                // 没有前驱或值不同，不能再合并
                if (prev == -1 || val[prev] != val[cur]) {
                    break;
                }

                // 合并 prev 和 cur

                // 1. 清除两个参与合并的原始标识
                if (orig[cur] != -1) {
                    pos[orig[cur]] = -1;
                }
                if (orig[prev] != -1) {
                    pos[orig[prev]] = -1;
                }
                orig[cur] = -1;
                orig[prev] = -1;

                // 2. 数值加到左边节点 prev 上
                val[prev] += 1;

                // 3. 从链表中删除 cur
                int nxt = right[cur];
                right[prev] = nxt;
                if (nxt != -1) {
                    left[nxt] = prev;
                }
                left[cur] = -1;
                right[cur] = -1;

                // 4. 新数字位于 prev，继续向左尝试合并
                cur = prev;
                length--;
            }
        }

        // 输出最终序列长度
        out.println(length);
    }

    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }
}

C++ 实现

// 序列合并游戏 - C++ 实现
// 使用数组模拟双向链表，按题意依次处理指令

#include <bits/stdc++.h>
using namespace std;

// 主要逻辑写在 solve 函数中
void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return;

    vector<int> val(N);
    for (int i = 0; i < N; ++i) {
        cin >> val[i];
    }

    int M;
    cin >> M;
    vector<int> cmds(M);
    for (int i = 0; i < M; ++i) {
        cin >> cmds[i];
    }

    // 双向链表数组
    vector<int> left(N), right(N), orig(N), pos(N);
    for (int i = 0; i < N; ++i) {
        left[i] = i - 1;              // 左邻
        right[i] = (i == N - 1) ? -1 : i + 1; // 右邻
        orig[i] = i;                  // 初始对应的原始下标
        pos[i] = i;                   // 原始下标 i 当前所在节点
    }

    int length = N;  // 当前序列长度

    // 依次处理每条指令
    for (int k = 0; k < M; ++k) {
        int idx = cmds[k];
        int node = pos[idx];

        // 该原始位置对应数字已参与过合并，跳过
        if (node == -1) continue;

        int cur = node;  // 当前“需要合并”的节点

        while (true) {
            int prev = left[cur];
            // 没有前驱或值不同，则无法继续合并
            if (prev == -1 || val[prev] != val[cur]) break;

            // 合并 prev 和 cur

            // 1. 清除两个参与合并的原始标识
            if (orig[cur] != -1) {
                pos[orig[cur]] = -1;
            }
            if (orig[prev] != -1) {
                pos[orig[prev]] = -1;
            }
            orig[cur] = -1;
            orig[prev] = -1;

            // 2. 值累加到左节点 prev 上
            val[prev] += 1;

            // 3. 从链表中删除 cur
            int nxt = right[cur];
            right[prev] = nxt;
            if (nxt != -1) {
                left[nxt] = prev;
            }
            left[cur] = -1;
            right[cur] = -1;

            // 4. 合并后的新数在 prev，继续向左尝试
            cur = prev;
            --length;
        }
    }

    // 输出最终序列长度
    cout << length << "\n";
}

int main() {
    solve();
    return 0;
}

题目内容

你会得到一个由数字组成的序列，你需要记住每个数字的值和每个数字在序列中的相对位置（从 $0$ 开始编号），该相对位置将用于标识这个数字。

比如输入 $1$ $1$ $2$ $3$ $4$

那么 $0$ 号标识的数字就是 $1$ ，$1$ 号标识的数字也是 $1$，$2$ 号标识的数字是 $2$ ，以此类推。

游戏开始后你会收到以标识为内容的指令，一旦收到指令，且如果该标识对应的数字存在，那么该数字将处于需要合并的状态。对于该状态的数字，其将遵循如下规则。

1.规则 $1$ ：如果该数字的前一个数字和该数字数值相同，那么两个数字将合并为新的数字，新的数字将等于原有的数字加 $1$ ；

2.规则 $2$ ：合并后的数字保留需要合并的状态，并将继续尝试和它之前的数字合并，直到它之前的数字和它不同或者该数字成为序列首元素；

3.规则 $3$ ：合并的新数字不具有标识，所以无法通过指令主动进入需要合并的状态，但该数字仍旧可以参与合并，并基于规则 $2$ 获得需要合并的状态。

在游戏的最后，你需要回答序列最后剩下的数字数量。

输入描述

输入由 $4$ 行组成:

第一行包含一个数字 $N$ ，代表了初始数组的规格

第二行包含了 $N$ 个数字 $X_i(0<=i<N)$，代表了初始序列的内容

第三行包含一个数字 $M$ ，代表了指令的数量

第二行包含了 $M$ 个数字 $Y_j(0<=j<M)$ ，代表了指令的内容;指令代表了数字在初始序列中的位置，位置 为从 $0$ 开始的顺序标号。

其中：

$1 <= N <= 10^5$

$1 <= M <= 10^3$

$1 <=X_i <= 30$

$0<=Y_j<N$

输出描述

输出一个数字，代表最终序列中的数字数量。

样例1

输入

5
2 2 2 1 1
3
4 1 2

输出

2

说明

经过第一个和第二个指令后，数据变为：3 3

第三个指令下发是，原数字已经在第一条指令执行时被合并，基于规则3，合并的新数字不具有标识，无法通过指令主动进入需要合并的状态，所以无动作

样例2

输入

12
7 5 4 3 2 1 1 9 8 7 7 10
4
0 10 11 6

输出

3

说明

本样例描述的初始序列如下表所示,指令的位置如头标识。

**

第一个指令描述了序列开头，其前没有元素，所以执行后序列没有变化执行后内容：$7$ $5$ $4$ $3$ $2$ $1$ $1$ $9$ $8$ $7$ $7$ $10$

第二个指令触发了合并，执行后内容：$7$ $5$ $4$ $3$ $2$ $1$ $1$ $10$ $10$

第三个指令触发了合并，执行后内容：$7$ $5$ $4$ $3$ $2$ $1$ $1$ $11$

第四个指令触发了合并，执行后内容：$7$ $6$ $11$

样例3

输入

6
5 4 3 2 1 1
1
5

输出

1

说明

本样例描述的初始序列如下表所示。

对于唯一的指令，其标记序号 $4$ 的数字即序列尾部的 $1$ 位需要合并。

该数字将逐步和前述的数字合并，其步骤为：

第一步：$5$ $4$ $3$ $2$ $2$

第二步：$5$ $4$ $3$ $3$

第三步：$5$ $4$ $4$

第四步：$5$ $5$

第五步：$6$

最终序列中只剩下一个元素