P1011 猫猫的积木块

问题转化

初始有 $n$ 个格子，每次合并操作会减少一个格子，因此 最多合并次数 $= n - \text{最少剩余格子数}$。

问题等价于：将原序列划分成最少的段，使得每一段内的所有积木块能够通过若干次合并操作（按题目规则）最终合并成一个格子。

判断一段能否合并成一个

给定一个子数组 $a[l..r]$，如何判断它能否完全合并成一个？

观察合并规则：两个相邻格子能合并当且仅当它们的值域区间不重叠，即一个的最大值小于另一个的最小值，或反之。
进一步分析发现，若一个格子内包含多个积木，它的值域是这些积木的最小值和最大值。在最优合并策略下，我们总是优先合并值域相邻的两个格子，因为如果中间有空隙，合并后会产生“空洞”，这个空洞会阻止后续落入其中的积木与之合并，最终导致无法全部合并。因此，能合并成一个的充要条件是：可以通过不断合并值域恰好相邻的两个格子，最终变成一个。

这启发我们设计一个线性模拟算法（离散化后）：

1. 将区间内所有数按值排序，得到它们的排名（$0$ 到 $len-1$）。
2. 按照原始顺序，每个位置上的数对应一个排名，初始时每个格子只包含一个数，所以该格子的最小排名 $=$ 最大排名 $=$ 这个排名。
3. 用双向链表维护相邻关系，反复扫描：
   • 检查相邻两格，如果它们的值域区间恰好相邻（即一个的最大排名与另一个的最小排名相差 $1$），就将它们合并。
   • 合并后，新区间的最小排名为两者最小值，最大排名为两者最大值，并更新链表。
4. 最终若所有格子合并成一个，则返回 true，否则返回 false。

该算法的时间复杂度为 $O(len \log len)$，主要来自排序。

贪心分段

我们要将整个序列划分成尽可能少的段，每个段都能完全合并。
显然，从左到右贪心是最优的：每次从当前位置 $l$ 出发，找到最远的 $r$ 使得 $a[l..r]$ 可合并，然后令 $l = r+1$ 继续。

现在问题变为：给定左端点 $l$，如何快速找到最大的 $r$？

朴素二分

直接对 $r$ 进行二分，每次调用一次 $O(len \log len)$ 的 check 函数。
但这样总复杂度可能达到 $O(n^2 \log n)$，不可接受。

倍增 + 二分

经典的优化技巧：先通过倍增确定一个合适的二分上界，再在区间内二分。

具体流程（设当前左端点为 $l$，当前已确定的可合并右端点 $r$ 初始为 $l$，步长 $k=1$）：

1. 尝试扩展 $k$ 个元素：若 $a[l..r+k]$ 可合并，则令 $r \leftarrow r+k$，$k \leftarrow 2k$，继续尝试。
2. 否则，将 $k$ 减半，继续尝试（直到 $k=0$ 停止）。
3. 最终得到的 $r$ 就是当前段的最远右端点。

这样做，每个元素被检查的次数为 $O(\log n)$，每次 check 需要 $O(len \log len)$ 时间，但所有检查的区间长度之和是 $O(n \log n)$ 级别（因为每次倍增都会产生新的区间，总长度受倍增过程控制）。更精确的分析表明总复杂度为 $O(n \log^2 n)$，在 $n \le 10^5$ 时可接受。

算法步骤总结

1. 读入 $T$ 组数据，每组数据有 $n$ 和排列 $a$。
2. 初始化 $l = 0$（$0$‑based），段数 cnt = 0。
3. 当 $l < n$ 时：
   • 令 $r = l$，$k = 1$。
   • 先将当前段的首个元素放入临时数组 tc（tc[0] = a[l]）。
   • 倍增扩展：
     • 当 $r + k < n$ 且 sol(l, r, k) 为真时，执行 $r \leftarrow r + k$，$k \leftarrow 2k$。
     • 否则，不断将 $k$ 减半，直到 $k = 0$，并在过程中如果 sol(l, r, k) 为真则更新 $r$。
   • 此时 $r$ 为当前段能合并的最后一个位置，cnt++，令 $l = r + 1$。
4. 输出 $n - cnt$。

关键函数 sol(l, r, nw)

判断区间 $a[l..r]$（已确认可合并）加上后面 $nw$ 个元素 $a[r+1..r+nw]$ 能否整体合并成一个。

实现细节：

• 已知当前段 $a[l..r]$ 内部已经合并成了有序序列 ta（在之前的调用中已维护在 tc 中），新部分 tb 为 $a[r+1..r+nw]$。
• 将 ta 拷贝出来（memcpy(ta, tc, (r-l+1)*4)），将 tb 排序，然后将 ta 和 tb 归并到 tc 中，得到整个区间所有数的有序列表。
• 建立排名：rk[tc[i]] = i。
• 初始化链表：对于 $i = 0..(r-l+nw)$，位置 $i$ 对应原始顺序中的 $a[l+i]$，其 li[i]=ri[i]=rk[a[l+i]]，前驱 prv[i]=i-1，后继 nxt[i]=i+1。注意链表数组大小比实际多一位（用于哨兵）。
• 模拟合并：
  • 从第一个格子 cur=0 开始。
  • 向右合并：当 nxt[cur] < pc 且 li[cur] - ri[nxt[cur]] == 1 或 li[nxt[cur]] - ri[cur] == 1 时，调用 mer(cur, nxt[cur]) 合并。
  • 向左合并：当 prv[cur] >= 0 且满足相邻条件时，调用 mer(prv[cur], cur) 并将 cur 指向合并后的节点（cur = prv[cur]）。
  • 然后 cur = nxt[cur] 继续扫描。
• 重复直到 cur >= pc。
• 判断是否只剩一个格子：检查 prv[cur] == 0（cur 此时是链表末尾的哨兵，其前驱为 $0$ 表示链表中只有节点 $0$）。
• 若成功返回 $1$，否则恢复 tc 为原来的 ta 并返回 $0$。

复杂度分析

• 每个元素在倍增过程中被检查 $O(\log n)$ 次，每次检查需要排序和模拟，模拟部分线性。
• 排序的总复杂度：每个元素参与归并的次数也是 $O(\log n)$，每次归并的代价与其所在段长度有关，但总复杂度为 $O(n \log^2 n)$。由于所有测试数据的 $n$ 总和不超过 $10^5$，该复杂度足以通过。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const int P=998244353;

int t,n,m;
int a[N],b[N];
int ta[N],tb[N],tc[N];
int rk[N];
int li[N],ri[N],prv[N],nxt[N];

void mer(int x,int y){
    li[x]=min(li[x],li[y]);
    ri[x]=max(ri[x],ri[y]);
    nxt[x]=nxt[y];
    prv[nxt[x]]=x;
}

bool sol(int l,int r,int nw){
    memcpy(ta,tc,(r-l+1)*4);
    for(int i=0;i<nw;i++){
        tb[i]=a[i+r+1];
    }
    sort(tb,tb+nw);
    int pa=0,pb=0,pc=0;
    int na=r-l+1,nb=nw;
    while(pa<na&&pb<nb){
        if(ta[pa]<tb[pb])tc[pc++]=ta[pa++];
        else tc[pc++]=tb[pb++];
    }
    while(pa<na)tc[pc++]=ta[pa++];
    while(pb<nb)tc[pc++]=tb[pb++];
    for(int i=0;i<pc;i++)rk[tc[i]]=i;
    for(int i=0;i<=pc;i++){
        li[i]=ri[i]=rk[a[l+i]];
        prv[i]=i-1;nxt[i]=i+1;
    }
    int cur=0;
    while(cur<pc){
        while(nxt[cur]<pc){
            int pt=nxt[cur];
            if(li[cur]-ri[pt]==1||li[pt]-ri[cur]==1){
                mer(cur,pt);
            }else break;
        }
        while(prv[cur]>=0){
            int pt=prv[cur];
            if(li[cur]-ri[pt]==1||li[pt]-ri[cur]==1){
                mer(pt,cur);
                cur=pt;
            }else break;
        }
        cur=nxt[cur];
    }
    if(prv[cur]==0)return 1;
    else{
        memcpy(tc,ta,(r-l+1)*4);
        return 0;
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",a+i);
        }
        int l=0,r=0,k=1,cnt=0;
        while(l<n){
            tc[0]=a[l];
            while(r+k<n&&sol(l,r,k)){
                r+=k;
                k*=2;
            }
            while(r+k>=n)k/=2;
            while(k){
                if(sol(l,r,k))r+=k;
                k/=2;
            }
            cnt++;
            l=r+1;r=l;k=1;
        }
        printf("%d\n",n-cnt);
    }
    return 0;
}

总结

本题的核心在于：

• 将最多合并次数转化为最少段数。
• 设计一个高效的区间可合并性判定算法（离散化 $+$ 链表模拟）。
• 利用倍增 $+$ 二分快速找出每个段的最大右端点，避免 $O(n^2)$ 的复杂度。

总时间复杂度 $O(n \log^2 n)$，空间复杂度 $O(n)$，可以顺利通过所有测试数据。