Solution

我们可以发现操作多次等于操作一次，我们考虑然后求出需要恰好一次操作的区间个数。

将序列划分为若干个极长上升子段，也就是说从 $a_i>a_{i+1}$ 处断开。

考虑区间 $[l,r]$ 需要恰好一次操作的条件：

• 恰好在两个子段内。因为在一个子段内无需操作，而在三个子段内无法将其排序。
• $a_l>a_r$，否则无法排序。

枚举所有子段 $x$，我们需要对所有 $x$ 中的下标 $i$ 添加有多少在子段 $x-1$ 中的下标 $j$ 满足 $a_j>a_i$。由于子段内单调递增，使用双指针法，从左往右扫描 $i$，维护最小的满足 $a_j>a_i$ 的 $j$，若 $a_j<a_i$ 一直 $j\gets j+1$ 即可。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 5e6 + 5;
	LL n, rs, a[N]; vector<pii> s;
	int main() {
		cin >> n, rs = 0, s.clear();
		REP(i, 1, n) cin >> a[i];
		REP(i, 1, n) {
			int p = i;
			while (p < n && a[p] < a[p + 1]) p ++;
			s.pb(i, p), i = p;
		}
		REP(x, 1, SZ(s) - 1) {
			auto [l, r] = s[x - 1];
			int p = l;
			REP(i, s[x].fi, s[x].se) {
				while (p <= r && a[p] < a[i]) p ++;
				rs += r - p + 1;
			}
		}
		cout << rs << '\n';
		return 0;
	}
}