Educational Codeforces Round 10 C. Foe Pairs
解法
しゃくとり法を使って解きます。
まず前準備として, pos[i] = (数 i がある位置), memo[i].first = (数 i より左側にある数で, Foe Pair になってしまううち最も右側にあるもののの位置), memo[i].second = (数 i より右側にある数で, Foe Pair になってしまううち最も左側にあるもののの位置)
というのを計算しておきます。
で, しゃくとりをするときは, 2つのポインター 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; }