题解：说好的幸福呢

喵仔牛奶 · 2025-01-10 18:05:58 · 题解

Solution

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

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

考虑区间 [l,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;
    }
}