CS Academy 069 DIV2 B - Reverse Subarray

B なのに難しかったのん。

CSA 069 DIV2 B Reverse Subarray

---

N 要素からなる数列が与えられる。
ここから連続する区間を reverse することで元の数列全体が単調非減少となるようにしたい。
そのような区間の選び方は何通りあるか？
またそのような区間のうち、(left, right) が辞書順最小のものを求めよ。

・1 <= N <= 10⁵
・0 <= A[i] <= 10⁵

---

元の数列が単調非減少かどうかで場合分け

• 単調非減少なとき、同じ数字が連続している箇所でのみひっくり返すのが答え。数え上げも簡単。辞書順最小は (1, 1)
• そうでないとき
  A[i] > A[i+1] となる場所が存在する。そこを含む範囲内で極大な単調非増加箇所を抽出する。
  そこを flip する以外には解が存在しえないことが示せる。
  ここを flip してダメだったらダメ。

＜コード＞

#include <iostream>
using namespace std;

int N;
int A[110000];
int main() {
    while (cin >> N) {
        for (int i = 0; i < N; ++i) cin >> A[i];
        int leftmost = -1, rightmost = -1;
        bool exist_up = false;
        for (int i = 0; i < N-1; ++i) {
            if (A[i] > A[i+1]) {
                if (leftmost == -1) leftmost = i;
                rightmost = i;
                if (exist_up) {
                    cout << 0 << endl;
                    return 0;
                }
            }
            else if (A[i] < A[i+1]) {
                if (leftmost != -1) {
                    exist_up = true;
                }
            }
        }
        
        if (leftmost == -1) {
            long long res = 0;
            map<int,long long> ma;
            for (int i = 0; i < N; ++i) {
                ma[A[i]]++;
            }
            EACH(it,ma) {
                long long num = it->second;
                res += num * (num+1) / 2;
            }
            cout << res << endl;
            cout << 1 << " " << 1 << endl;
        }
        else {
            int upnum = 0;
            int downnum = 0;
            for (int k = leftmost; k >= 0; --k) {
                if (A[k] == A[leftmost]) ++upnum;
                else break;
            }
            for (int k = rightmost + 1; k < N; ++k) {
                if (A[k] == A[rightmost+1]) ++downnum;
                else break;
            }
            int left = leftmost - upnum + 1;
            int right = rightmost + downnum;
            
            if (left > 0 && A[left-1] > A[right]) {
                cout << 0 << endl;
                return 0;
            }
            if (right + 1 < N && A[right + 1] < A[left]) {
                cout << 0 << endl;
                return 0;
            }
            
            cout << 1 << endl;
            cout << left+1 << " " << right+1 << endl;
        }
        
    }
}