吓人题。
一个显然的想法是对于 \(k\), 将贡献分为 \(3\) 类 ：\([1,k]\) 子区间的贡献，\([k+1,n]\) 子区间的贡献和跨过 \(k\) 的贡献。
首先 \([1,k]\) 的贡献我们可以沿用 Pudding Monsters 的做法，从左往右枚举 \(r\)，统计 \(r\) 作为右端点的贡献。发现一个区间是 Copium 的当且仅当 \(\max-\min-len=-1\)，而区间内数互不相同，也就是 \(\max-\min-len\ge-1\)，且左端点在 \(r\) 时一定可以取到。于是我们用线段树维护每个左端点到 \(r\) 的 \(\max-\min-len\) 的值，贡献即为最小值的个数。维护两个单调栈，在退栈的时候更新即可。
其它的贡献要涉及到重排的问题。对于 \([k+1,n]\) 位置的数，它们一定能被分成值域上的若干连续段。显然重排过后一个连续段递增/递减的放在一起会更优。\([k+1,n]\) 只与连续段有关，是容易算出的，我们只需要考虑跨过 \(k\) 的贡献。
我们称位置在 \([k+1,n]\) 中的数是特殊的。定义一个 \(good\) 数组，它内部的元素单调递增。\(i\) 在 \(good\) 数组中当且仅当 \(i \le k\) 且 \([i,k]\) 位置的数在去掉所有特殊的数之后的值域上形成了一个连续段。比如当前 \([1,k]\) 中的数为：\([1,9,2,6,8,7,5,10]\)，那么 \(good=[1,2,8]\)。
考虑对于一个 \(k\) 怎么重排。我们从右往左扫描一遍当前的 \(good\) 数组。如果 \([good_i,k]\) 还不是 Copium 的，就把 \([good_i,k]\) 中缺失的数先放在前面，跨过 \(k\) 的贡献增加 \(1\)。比如 \(n=10\) 时，\([1,k]\) 的序列为 \([1,10,4,5,7,6]\)，我们肯定是把序列放成 \([1,10,4,5,7,6][8,9][3,2]\) 更优秀，使得跨过 \(k\) 的贡献增加了 \(4\)。在这个例子中，我们发现，三个好的位置 \(3,4,5\) 在加入 \([8,9]\) 后都产生了贡献。我们设 \(mn_i\) 和 \(mx_i\) 表示 \([good_i,k]\) 的最大/最小值，那么如果对于 \(good\) 上的一个子段有 \(mx_i=mx_{i+1}=\dots=mx_j\) 且 \(\forall i\le x <j, [good_x, good_{x+1}-1]\) 是 Copium 的，那么它们会在同一个子段加入后产生贡献。\(mn\) 也是同理的。于是对于每个 \(mn\) 和 \(mx\) 的值，维护满足上述条件的极长段，乘上相应的连续段的长度并加入答案。
那么我们让 \(k\) 从左往右扫一遍，对于 \(mn/mx\) 相等的每个前缀存储最长的串。对于 \(good\) 数组，每次它只会弹出一个后缀，直接从后往前弹即可。我们只需要考虑新加入两个位置：\(k\) 和最后一个满足 \(a_j<a_k\) 或 \(a_j>a_k\) 的 \(j\) 之后第一个 \(good\) 且必须满足它是 \(mn/mx\) 连续段中最后一个位置。
#include <bits/stdc++.h>
#include <functional>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
inline int read() {
register int s = 0;
register char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
return s;
}
int n, a[N], pos[N], pre[N], nxt[N], mn[N], mx[N], tpn = 0, tpx = 0;
set<int> st;
vector<int> good;
long long res[N], mid = 0, suf = 0;
#define SIT set<int>::iterator
#define VIT vector<int>::iterator
struct node {
int cur, mx, op;
inline node() { }
inline node(int C, int M, int O) : cur(C), mx(max(C, M)), op(O) { }
} lmn[N], lmx[N];
inline int qmin(int x) {
return a[*lower_bound(mn + 1, mn + tpn + 1, x)];
}
inline int qmax(int x) {
return a[*lower_bound(mx + 1, mx + tpx + 1, x)];
}
class RMQ {
int mn[N][20];
public :
inline void build() {
for (int i = 1; i <= n; ++i) mn[i][0] = pos[i];
for (int i = 1; i < 20; ++i)
for (int j = 1; j + (1 << i) - 1 <= n; ++j)
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << i - 1)][i - 1]);
}
inline int query(int l, int r) {
int t = __lg(r - l + 1);
return min(mn[l][t], mn[r - (1 << t) + 1][t]);
}
} rmq;
namespace PREF {
int mn[N << 2], tag[N << 2], cnt[N << 2];
inline void update(int now) {
mn[now] = min(mn[now << 1], mn[now << 1 | 1]);
cnt[now] = 0;
if (mn[now] == mn[now << 1]) cnt[now] += cnt[now << 1];
if (mn[now] == mn[now << 1 | 1]) cnt[now] += cnt[now << 1 | 1];
}
inline void pushdown(int now) {
if (!tag[now]) return ;
tag[now << 1] += tag[now]; tag[now << 1 | 1] += tag[now];
mn[now << 1] += tag[now]; mn[now << 1 | 1] += tag[now];
tag[now] = 0;
}
inline void modify(int now, int l, int r, int ql, int qr, int k) {
if (ql <= l && r <= qr) {
tag[now] += k; mn[now] += k;
return ;
} pushdown(now);
int mid = l + r >> 1;
if (ql <= mid) modify(now << 1, l, mid, ql, qr, k);
if (qr > mid) modify(now << 1 | 1, mid + 1, r, ql, qr, k);
update(now);
}
inline int query(int now, int l, int r, int ql, int qr) {
pushdown(now);
if (ql <= l && r <= qr) return mn[now] == 0 ? cnt[now] : 0;
int mid = l + r >> 1, ret = 0;
if (ql <= mid) ret += query(now << 1, l, mid, ql, qr);
if (qr > mid) ret += query(now << 1 | 1, mid + 1, r, ql, qr);
return ret;
}
inline void build(int now, int l, int r) {
tag[now] = 0;
if (l >= r) {
mn[now] = l; cnt[now] = 1;
return ;
} build(now << 1, l, l + r >> 1);
build(now << 1 | 1, (l + r >> 1) + 1, r);
mn[now] = mn[now << 1]; cnt[now] = cnt[now << 1];
return ;
}
int stk1[N], top1 = 0, stk2[N], top2 = 0;
void calc() {
build(1, 1, n); top1 = top2 = 0;
for (int i = 1; i <= n; ++i) {
res[i] = 0;
modify(1, 1, n, 1, n, -1);
while (top1 && a[stk1[top1]] < a[i]) {
modify(1, 1, n, stk1[top1 - 1] + 1, stk1[top1], a[i] - a[stk1[top1]]);
--top1;
} stk1[++top1] = i;
while (top2 && a[stk2[top2]] > a[i]) {
modify(1, 1, n, stk2[top2 - 1] + 1, stk2[top2], a[stk2[top2]] - a[i]);
--top2;
} stk2[++top2] = i;
res[i] = res[i - 1] + query(1, 1, n, 1, i);
}
}
}
int main() {
int T = read();
auto link = [](int x, int y) { nxt[x] = y; pre[y] = x; };
auto calc = [](int i, int j, bool fl) {
int xi = qmax(i), xj = qmax(j), ni = qmin(i), nj = qmin(j);
if (fl) {
mid -= 1ll * lmx[j].mx * (nxt[xj] - xj - 1);
mid -= 1ll * lmn[j].mx * (nj - pre[nj] - 1);
}
if (xi == xj) {
if (!fl) mid -= 1ll * lmx[i].mx * (nxt[xi] - xi - 1);
int op;
if (nj - ni == j - i) op = 0;
else if (pre[nj] + 1 - ni == j - i) op = 1;
else op = 2;
if (op == 2) lmx[j] = node(1, lmx[i].mx, 2);
else if (!lmx[i].op) lmx[j] = node(lmx[i].cur + 1, lmx[i].mx, op);
else lmx[j] = node(2, lmx[i].mx, op);
} else lmx[j] = node(1, 1, 3);
if (ni == nj) {
if (!fl) mid -= 1ll * lmn[i].mx * (ni - pre[ni] - 1);
int op;
if (xi - xj == j - i) op = 0;
else if (xi + 1 - nxt[xj] == j - i) op = 1;
else op = 2;
if (op == 2) lmn[j] = node(1, lmn[i].mx, 2);
else if (!lmn[i].op) lmn[j] = node(lmn[i].cur + 1, lmn[i].mx, op);
else lmn[j] = node(2, lmn[i].mx, op);
} else lmn[j] = node(1, 1, 3);
mid += 1ll * lmx[j].mx * (nxt[xj] - xj - 1);
mid += 1ll * lmn[j].mx * (nj - pre[nj] - 1);
};
while (T--) {
n = read();
for (int i = 1; i <= n; ++i) pos[a[i] = read()] = i, pre[i] = nxt[i] = 0, lmx[i] = lmn[i] = node(0, 0, 0);
PREF :: calc();
tpn = tpx = 0; good.clear(); st.clear();
mn[++tpn] = 0; mx[++tpx] = 0; st.insert(0); st.insert(n + 1);
rmq.build(); pre[n] = 0; nxt[0] = n;
printf("%lld ", suf = 1ll * n * (n + 1) / 2); mid = 0;
for (int i = 1; i <= n; ++i) {
while (!good.empty()) {
int r = *good.rbegin();
int np = qmin(r), xp = qmax(r);
if (rmq.query(min(np, a[i]), max(xp, a[i])) >= r) break;
mid -= 1ll * lmx[r].mx * (nxt[xp] - xp - 1);
mid -= 1ll * lmn[r].mx * (np - pre[np] - 1);
good.pop_back();
if (!good.empty()) {
if (lmx[r].op < 3)
mid += 1ll * lmx[*good.rbegin()].mx * (nxt[xp] - xp - 1);
if (lmn[r].op < 3)
mid += 1ll * lmn[*good.rbegin()].mx * (np - pre[np] - 1);
}
}
if (!good.empty()) {
int r = *good.rbegin();
int np = qmin(r), xp = qmax(r);
mid -= 1ll * lmx[r].mx * (nxt[xp] - xp - 1);
mid -= 1ll * lmn[r].mx * (np - pre[np] - 1);
} SIT it = st.upper_bound(a[i]); suf -= 1ll * (*it - a[i]) * (a[i] - *prev(it));
link(*prev(it), a[i]); link(a[i], *it); st.insert(a[i]);
while (tpx >= 2 && a[mx[tpx]] < a[i]) --tpx;
while (tpn >= 2 && a[mn[tpn]] > a[i]) --tpn;
mx[++tpx] = i; mn[++tpn] = i;
if (!good.empty()) {
int r = *good.rbegin();
int np = qmin(r), xp = qmax(r);
mid += 1ll * lmx[r].mx * (nxt[xp] - xp - 1);
mid += 1ll * lmn[r].mx * (np - pre[np] - 1);
calc(r, i, 0);
} else {
lmx[i] = lmn[i] = node(1, 1, 3);
mid += nxt[a[i]] - pre[a[i]] - 2;
} good.push_back(i);
if (tpn >= 2) {
VIT it = upper_bound(good.begin(), good.end(), mn[tpn - 1]);
if (it != good.begin() && it != good.end()) {
int x = *it; int y = *(--it);
calc(y, x, 1);
}
}
if (tpx >= 2) {
VIT it = upper_bound(good.begin(), good.end(), mx[tpx - 1]);
if (it != good.begin() && it != good.end()) {
int x = *it; int y = *(--it);
calc(y, x, 1);
}
}
printf("%lld ", res[i - 1] + good.size() + mid + suf);
} puts("");
} return 0;
}