不妨先考虑一个弱化版的问题，这个问题和原来的问题仅有一个区别：\(k\) 是给定整数。
称最后 \(n-k\) 个数是“特殊的”。那么我们可以注意到，每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列 \([7,5,8,1,4,2,6,3]\) 而且 \(k=2\)，那么极大段的下标应该是 \([1,4],[6,6],[8,8]\)。
我们把所有的好子串分成三部分，一部分是前缀，一部分是后缀，剩下的是第三部分。对于前两种子串，用 CF526F 的算法就可以顺利解决，这里略去讲解。
我们定义一个优雅的数组 \(ele\) 满足 \(\forall i,ele_i<ele_{i+1}\) 且 \(p[ele_i,k]\) 包括了连续非特殊数字。
接下来，我们尝试着向已有的排列（即排列的一部分）中添加特殊数字。
对于这个优雅数组，我们从右向左的处理，而特殊的数字则从左向右加。那么对于一个数组中的元素 \(ele_i\)，先把特殊数字放进去以让答案加一，然后考虑两个极大段，他们分别包含 \(mn_i-1\) 和 \(mx_i+1\)，其中 \(mn,mx\) 分别为 \(p[ele_i,k]\)。我们可以把这俩段放上以增大答案。
另一方面，注意到 \(mx_i=mx_{i+1}=\dots=mx_{j}\) 的时候，如果 \(\forall i\le x<j, p[ele_x,ele_{x+1}]\) 是好的，那么他们都可以获得贡献。
对每个有相同 \(mn\) 的优雅位置分别计算即可。
那么对于每一个 \(k\)，我们预处理 \(mn,mx\) 等价位置的前缀。转移时我们只需要考虑两个优雅位置：一个是 \(k\)（此时，若 \(p_{k-1}<p_k\)，直接令 \(j=lst(p_j>p_k)\)，反之亦然），下一个当然就是 \(j\) 的下一个位置，而显然它具有性质：它必然是最后一个 \(mn,mx\) 等价位置。那么处理这些位置不会影响后面的位置。复杂度显然是 \(O(n\log n)\) 的。
核心代码大致如下：
void work(int i, int j, bool recalc) {
int imin = calc_min(i), imax = calc_max(i), jmin = calc_min(j), jmax = calc_max(j);
int type;
if (recalc) {
mid -= 1ll * lmax[j].maxx * (rr[jmax] - jmax - 1);
mid -= 1ll * lmin[j].maxx * (jmin - ll[jmin] - 1);
}
if (imax == jmax) {
if (!recalc)
mid -= 1ll * lmax[i].maxx * (rr[imax] - imax - 1);
if (jmin - imin == j - i)
type = 0;
else {
type = 2 - (imin + j - i == ll[jmin] + 1);
}
if (type == 2)
lmax[j] = cop(1, lmax[i].maxx, type);
else if (lmax[i].type == 0)
lmax[j] = cop(lmax[i].curr + 1, lmax[i].maxx, type);
else
lmax[j] = cop(2, lmax[i].maxx, type);
} else
lmax[j] = {1, 1, 3};
if (imin == jmin) {
if (!recalc)
mid -= 1ll * lmin[i].maxx * (imin - ll[imin] - 1);
if (imax - jmax == j - i)
type = 0;
else if (imax + i - j == rr[jmax] - 1)
type = 1;
else
type = 2;
if (type == 2)
lmin[j] = cop(1, lmin[i].maxx, type);
else if (lmin[i].type == 0)
lmin[j] = cop(lmin[i].curr + 1, lmin[i].maxx, type);
else
lmin[j] = cop(2, lmin[i].maxx, type);
} else
lmin[j] = {1, 1, 3};
mid += 1ll * lmax[j].maxx * (rr[jmax] - jmax - 1);
mid += 1ll * lmin[j].maxx * (jmin - ll[jmin] - 1);
}
void solve() {
elem.clear();
minn.assign(1, 0), maxx.assign(1, 0);
set<int> ss;
ss.insert(0), ss.insert(n + 1);
pre = 0, suf = 1ll * n * (n + 1) / 2, mid = 0;
cout << suf << ' ';
ll[n] = 0, rr[0] = n;
seg1.build(1, 1, n);
init();
for (int i = 1; i <= n; i++) {
while (elem.size()) {
int j = elem.back();
int jmin = calc_min(j), jmax = calc_max(j);
if (get_min_pos(min(jmin, a[i]), max(jmax, a[i])) < j) {
mid -= 1ll * lmax[j].maxx * (rr[jmax] - jmax - 1);
mid -= 1ll * lmin[j].maxx * (jmin - ll[jmin] - 1);
elem.pop_back();
if (elem.size()) {
if (lmax[j].type < 3)
mid += 1ll * lmax[elem.back()].maxx * (rr[jmax] - jmax - 1);
if (lmin[j].type < 3)
mid += 1ll * lmin[elem.back()].maxx * (jmin - ll[jmin] - 1);
}
} else
break;
}
if (elem.size()) {
int j = elem.back();
int jmin = calc_min(j), jmax = calc_max(j);
mid -= 1ll * lmax[j].maxx * (rr[jmax] - jmax - 1);
mid -= 1ll * lmin[j].maxx * (jmin - ll[jmin] - 1);
}
auto it = ss.upper_bound(a[i]);
suf -= 1ll * (*it - a[i]) * (a[i] - *prev(it));
connect(*prev(it), a[i]), connect(a[i], *it);
ss.insert(a[i]);
while (maxx.size() > 1 && a[maxx.back()] < a[i]) {
seg1.easy_update(maxx[maxx.size() - 2] + 1,
maxx.back(), a[i] - a[maxx.back()]);
maxx.pop_back();
}
while (minn.size() > 1 && a[minn.back()] > a[i]) {
seg1.easy_update(minn[minn.size() - 2] + 1,
minn.back(), a[minn.back()] - a[i]);
minn.pop_back();
}
maxx.push_back(i), minn.push_back(i);
if (elem.size()) {
int j = elem.back();
int jmin = calc_min(j), jmax = calc_max(j);
mid += 1ll * lmax[j].maxx * (rr[jmax] - jmax - 1) + 1ll * lmin[j].maxx * (jmin - ll[jmin] - 1);
work(j, i, 0);
} else {
lmax[i] = lmin[i] = {1, 1, 3};
mid += rr[a[i]] - ll[a[i]] - 2;
}
elem.push_back(i);
if (minn.size() >= 2) {
int k = search(minn[minn.size() - 2]);
if (k > 0 && k < elem.size())
work(elem[k - 1], elem[k], 1);
}
if (maxx.size() >= 2) {
int k = search(maxx[maxx.size() - 2]);
if (k > 0 && k < elem.size())
work(elem[k - 1], elem[k], 1);
}
cout << pre + elem.size() + mid + suf << ' ';
pre += seg1.nodes[1].cnt;
}
cout << '\n';
}