Можешь почитать, если интересно

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) begin(x), end(x)

const int N     = 2.1e5;
const int K     = 30;
const int H     = N + 310;
// int overflow?

struct fenw {
    int f[N], ind[H], val[H], s;
    fenw() {
        fill(all(f), 0);
        s = 0;
    }
    void add(int i, int d) {
        for (; i < N; i |= i + 1) {
            assert(s < H); /// TL
            ind[s] = i;
            val[s] = f[i];
            ++s;
            f[i] += d;
        }
    }
    int prefix(int i) {
        int su = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) {
            su += f[i];
        }
        return su;
    }
    void back_to(int t) {
        assert(t >= 0);
        while (s > t) {
            --s;
            f[ind[s]] = val[s];
        }
        assert(s == t);
    }
    int segment(int l, int r) {
        assert(l - 1 <= r);
        return prefix(r) - prefix(l - 1);
    }
    void clear() {
        fill(all(f), 0);
        s = 0;
    }
};

vector<int> g[N], vip[N];
int n, m, q, query[N];
int used[N], ff;
int value[N];
ll a[N], b[N];
fenw ab[K + 1], on[K + 1];

void solve_block(int lq, int rq) {
    ff = 0;
    fill(all(used), 0);
    for (int i = lq; i < rq; ++i) {
        used[query[i]] = ++ff;
    }
    assert(ff <= K);
    fill(all(a), 0);
    fill(all(b), 0);
    for (int i = 0; i < n; ++i) {
        vip[i].clear();
        for (int j : g[i]) {
            assert(value[i] != value[j]);
            if (value[j] < value[i]) {
                ++a[i];
            } else {
                ++b[i];
            }
            if (used[j]) {
                vip[i].push_back(j);
            }
        }
    }
    ll cur_answer = 0;
    for (int i = 0; i < n; ++i) {
        cur_answer += a[i] * b[i];
        if (!used[i]) {
            continue;
        }
        int v = used[i];
        for (int j : g[i]) {
            assert(value[j] < N);
            on[v].add(value[j], 1);
            ab[v].add(value[j], a[j] - b[j]);
        }
    }
    if (lq == 0) {
        cout << cur_answer << "\n";
    }
    for (int id = lq; id < rq; ++id) {
        int i = query[id];
        assert(used[i]);
        for (int j : vip[i]) {
            assert(used[j]);
            int v = used[j];
            on[v].add(value[j], -1);
            ab[v].add(value[j], -(a[j] - b[j]));
        }

        cur_answer -= a[i] * b[i];
        int old = value[i];
        int cur = n + id;
        assert(old != cur);

        if (old < cur) {
            assert(used[i]);
            int v = used[i];
            cur_answer += ab[v].segment(old + 1, cur - 1) - on[v].segment(old + 1, cur - 1);
        } else {
            assert(false);
        }

        value[i] = n + id;
        a[i] = on[used[i]].prefix(value[i] - 1);
        assert(a[i] == on[used[i]].prefix(value[i]));
        b[i] = ll(g[i].size()) - a[i];
        cur_answer += a[i] * b[i];

        for (int j : vip[i]) {
            assert(used[j]);
            int v = used[j];
            on[v].add(value[j], +1);
            ab[v].add(value[j], +(a[j] - b[j]));
            a[j] = on[v].prefix(value[j] - 1);      /// TL
            assert(a[j] == on[v].prefix(value[j])); /// TL
            b[j] = ll(g[j].size()) - a[j];
        }

        cout << cur_answer << "\n";
    }

    for (int i = 0; i <= K; ++i) {
        ab[i].back_to(0);
        on[i].back_to(0);
    }
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int v, u, i = 0; i < m; ++i) {
        cin >> v >> u;
        --v;
        --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    cin >> q;
    for (int i = 0; i < n; ++i) {
        cin >> query[i];
        --query[i];
    }
    iota(value, value + n, 0);
    for (int i = 0; i < q; i += K) {
        solve_block(i, min(q, i + K));
    }
    cerr << 1000 * clock() / CLOCKS_PER_SEC << endl;
    return 0;
}