CFR Educational 10 C. Foe Pairs ( Amortized Complexity )
Problem - C - Codeforces
每次即時刪除無用的編號( 因為所有編號相異 ),似乎就能夠均攤解決。
#include <bits/stdc++.h> using namespace std; const int MAXN = 3e5 + 5; const int MAXM = 3e5 + 5; typedef long long ll; int n, m; int p[ MAXN ]; set< int > foe[ MAXN ]; void bye(int x){ for( int y: foe[ x ] ) foe[ y ].erase( x ); } void solve(){ ll ans = 0; int rb = 0; set< int > cur; for(int lb = 0; lb < n; ++lb){ for( ; rb < n; ++rb){ bool ok = true; for(int y: foe[ p[ rb ] ]) if( cur.count( y ) ){ ok = false; break; } if( !ok ) break; cur.insert( p[ rb ] ); // printf("insert %d", p[rb]); } // printf("%d %d\n", lb, rb); ans += rb - lb; bye( p[ lb ] ); cur.erase( p[ lb ] ); // printf("erase %d\n", p[ lb ]); } printf("%I64d\n", ans); } int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i) scanf("%d", p + i); for(int i = 0; i < m; ++i){ int a, b; scanf("%d%d", &a, &b); foe[ a ].insert( b ); foe[ b ].insert( a ); } solve(); return 0; }