Educational Codeforces Round 10 C. Foe Pairs

問題

codeforces.com

解法

しゃくとり法を使って解きます。

まず前準備として, pos[i] = (数 i がある位置), memo[i].first = (数 i より左側にある数で, Foe Pair になってしまううち最も右側にあるもののの位置), memo[i].second = (数 i より右側にある数で, Foe Pair になってしまううち最も左側にあるもののの位置)
というのを計算しておきます。

で, しゃくとりをするときは, ２つのポインター lp, rp が memo[p[lp]].second < rp, memo[p[rp]].first > lp を満たすように動かしていけば良いです。(lp, rp) に到達可能な時, rp を右端にするような場合の数が rp-lp+1 通りあるので, それぞれ足していきます。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> p(N), pos(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i]; p[i]--;
        pos[p[i]] = i;
    }
    vector<pii> memo(N, pii(-1, N));
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (pos[a] < pos[b]) {
            memo[a].second = min(memo[a].second, pos[b]);
            memo[b].first = max(memo[b].first, pos[a]);
        } else {
            memo[b].second = min(memo[b].second, pos[a]);
            memo[a].first = max(memo[a].first, pos[b]);
        }
    }
    int lp = 0, rp = 0;
    ll ans = 0;
    for (;;) {
        while (rp < N && memo[p[lp]].second > rp && memo[p[rp]].first < lp) {
            ans += rp-lp+1;
            rp++;
        }
        if (rp == N) break;
        while (lp <= rp && (memo[p[lp]].second <= rp || memo[p[rp]].first >= lp)) {
            lp++;
        }
    }
    cout << ans << endl;
    return 0;
}