P11786 「FAOI-R4」说好的幸福呢


小 M 有一个长度为 $n$ 的排列 $a$。 对于一个长度为 $k$ 的序列 $b$，小 M 可以执行以下操作： - 选择一个满足 $1\leq i\leq k$ 的位置 $i$，将序列变为 $[b_i,b_{i+1},\cdots,b_{k},b_{1},b_{2},\cdots,b_{i-2},b_{i-1}]$。也就是说，将 $b$ 的一个后缀移到开头。 定义序列 $b$ 的价值 $f(b)$ 为「将 $b$ 变成严格上升序列的最小操作数」。若无法通过操作变成严格上升序列，则 $f(b)=0$。 你需要求出 $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}f([a_{l},a_{l+1},\cdots,a_{r-1},a_{r}])$，即 $a$ 中所有子串的价值之和。

无

无

#### 【样例解释】 对于第三组样例：区间 $[1,1],[2,2]$ 已经是严格上升序列，不需要操作。而对于区间 $[1,2]$，选择 $i=2$ 即可将其变为严格上升序列。故答案为 $0+0+1=1$。 对于第六组样例：区间 $[1,2]$ 可以通过一次 $i=2$ 的操作变为严格上升序列，而对于区间 $[1,3]$，可以证明无论如何操作都无法将其排序。 #### 【数据范围与约定】 **本题开启子任务捆绑测试。** - Subtask 1（15 pts）：$n\leq10$，$\sum n\leq20$。 - Subtask 2（35 pts）：$n\leq10^3$，$\sum n\leq10^4$。 - Subtask 3（30 pts）：$n\leq10^5$，$\sum n\leq5\times10^5$。 - Subtask 4（20 pts）：无特殊限制。 对于所有数据，保证 $1\leq T\leq10^5$，$1\leq n\leq5\times10^6$，$\sum n\leq10^7$。 #### 【提示】 本题输入量略大，你可以在程序的开头加上 `std::cin.tie(0)->sync_with_stdio(0)`，并使用 `std::cin` 来读入，保证可以在 600ms 内读入所有数据。可以参考以下程序： ```cpp #include using namespace std; const int N = 5e6 + 1; int T, n, ans, a[N]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> T; while (T --) { cin >> n; for (int i = 1; i > a[i]; // compute the answer cout