不得不说这道区间 \(DP\) 码量巨少，但是很考验思维。

---

简单分析题目后基本上就可以确定是区间 \(DP\) 了，绝大多数人一开始想到的一定是用 \(f[l][r]\) 来表示区间 \([l, r]\) 所能合并出的最大值。但是，\(2 \le n \le 262144\) 的数据范围让人望而退却。

虽然这个数据范围很恐怖，却也为我们解题提供了新的思路。首先，题目中给出的合并方式是两个相邻且同为 \(a\) 的数字可以合并成一个 \(a + 1\)，假设我们现在要在一个全 \(1\) 序列中从合并出 \(n\)，需要多少个数字 \(1\) 呢？

显然是需要 \(2^{n - 1}\) 个（因为 \(2\) 个 \(1\) 可以合并成 \(1\) 个 \(2\)，\(4\) 个 \(1\) 可以合并成 \(2\) 个 \(2\) 再合成 \(1\) 个 \(3\)，以此类推）。再看数据范围，\(262144\) 既不是 \(10\) 的整数倍又不是一个素数，有极大的可能与正解有关联 除非出题人丧心病狂。所以我们将 \(262144\) 与前面所发现的规律联系，发现 \(262144\) 正好是 \(2^{18}\) 。再加上题目中也给定了初始序列中的每一个整数 \(a_i\) 都满足 \(1 \le a_i \le 40\)，不难发现最终序列里的最大值必定 \(\le 58\)。

再考虑我们最初的想法，状态与区间左端点 \(l\)，区间右端点 \(r\)，和 \([l, r]\) 所能合并出的最大值有关，那我们不如换一种方式设计状态。令 \(f[i][j]\) 为合并出的最大值为 \(i\) 且以 \(j\) 为区间左端点的区间右端点。

如图，在转移时，我们可以找到最大值为 \(i - 1\) 且以 \(f[i - 1][j]\) 为区间左端点的区间右端点，进而转移，所以状态转移方程就是 \(f[i][j] = f[i - 1][f[i - 1][j]]\)。

---

以为这就结束了吗？

还有一个细节需要注意，通过转移其实可以发现：这里的区间并不是闭区间，而是一个左闭右开的区间！（否则第一个 \(i - 1\) 点会被算两遍），因此，初始化时应注意 \(f[a_i][i] = i+ 1\) 而非简单的 \(f[a_i][i] = i\)。

放代码说实话这题大家的代码都大同小异放了也意义不大

#include <bits/stdc++.h>

#define MAXN 60
#define MAXM 262200

using namespace std;

int n, a[MAXN], f[MAXN][MAXM], ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[a[i]][i] = i + 1;
    }
    for (int i = 2; i <= 58; i++) {
        for (int j = 1; j <= n; j++) {
            if (!f[i][j]) f[i][j] = f[i - 1][f[i - 1][j]];
            if (f[i][j]) ans = i;
        }
    }
    printf("%d", ans);
    return 0;
}