区间合并，试试看能否用区间\(dp\)进行操作。每次选取的区间肯定是越长越好，那么我们刚开始就把连续的，属于同一个国王的城镇区间缩成一个点。为了让能选的区间变得更长，要贪心地往左右区间合并。这时我们发现，如果左右区间的所属国王是相同的，那么我们只要修改中间这个区间的城镇，就能得到一个更长的区间。其余的就没区别了。那么我们预处理出每个区间的前一段和它属于同一个国王的区间在哪里，就能对这个区间进行状态转移了。
同时，我们这里是向前找上一个和最后的点相同的区间，所以对于所有的区间，我们都把它想象成向右合并的，才能得到最优解。
by GWTPEL @ 2023-03-23 20:32:47
@[herie](/user/679489) 我只是想问问贪心能做吗
by sundyLIUXY @ 2023-03-24 09:15:20
@[herie](/user/679489) 正解我会，这个贪心是我爸想出来的毒瘤，他非得问
by sundyLIUXY @ 2023-03-24 09:15:57
@[sundyLIUXY](/user/706737) 我就是只小白终于看到会的题了嘿嘿(～￣▽￣)～
by GWTPEL @ 2023-03-24 20:28:12
@[sundyLIUXY](/user/706737) 贪心当然可以，首先，对于每个国王，将其拥有的城镇按照从左到右的顺序进行编号为 $1$ 到 $k_i$，其中 $k_i$ 表示第 $i$ 个国王所拥有的城镇数量。
接下来考虑如何将某个国王的所有城镇都归属到另外一个国王下面。为了让操作次数最少，我们应该将相邻的城镇尽可能多地归属到同一个国王下面。因此，我们可以从左到右遍历该国王的城镇，每次向右扩展一段连续的城镇，直到扩展到了下一个国王的城镇或者到了该国王的最后一个城镇。然后将这一段连续的城镇都归属到某一个国王下面，使得这一段城镇归属到的国王拥有的城镇数量最小。在实现时，我们可以使用一个指针记录当前连续的城镇的左端点，然后从这个左端点开始向右扩展，扩展的过程中维护一个变量记录当前归属到哪一个国王下面可以使得该国王的城镇数量最小。当扩展到了一个新的国王的城镇或者到了该国王的最后一个城镇时，就将这一段连续的城镇都归属到上面记录的国王下面。
接下来考虑如何将所有城镇都归属到同一个国王下面。我们可以先对每个国王单独进行上述操作，将其所有城镇都归属到某一个国王下面。然后再对这些国王进行合并，使得所有城镇都归属到同一个国王下面。具体地，我们可以从左到右遍历每一个国王，对于每个国王，如果它的城镇归属到了前一个国王下面，那么就将它的城镇都归属到前一个国王下面，否则就继续处理下一个国王。
总的操作次数就是将所有城镇都归属到同一个国王下面所需的最小操作次数。
时间复杂度为 $O(N)$。
by Daben1 @ 2023-03-25 11:08:45
下面这是口胡的，没有样例导致正确性极其可疑，仅供参考
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
int a[MAXN], pre[MAXN], suf[MAXN];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
pre[1] = 0;
for (int i = 2; i <= n; i++)
{
if (a[i] == a[i - 1])
{
pre[i] = pre[i - 1];
}
else
{
pre[i] = i - 1;
}
}
suf[n] = n + 1;
for (int i = n - 1; i >= 1; i--)
{
if (a[i] == a[i + 1])
{
suf[i] = suf[i + 1];
}
else
{
suf[i] = i + 1;
}
}
vector<int> ops(n + 1);
for (int i = 1; i <= n; i++)
{
ops[a[i]] = max(ops[a[i]], min(i - pre[i], suf[i] - i));
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += ops[i];
}
cout << ans << endl;
return 0;
}
```
by Daben1 @ 2023-03-25 11:12:31