0w1

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;
}