三元环计数，于是考虑暴力。答案显然为每个点的入度 ( imes) 出度和，每次修改一个点的时候，遍历所有的入边，将其改为出边，更新答案，一次更新的复杂度是 (mathcal{O}(入度)) 的。
不妨设 (n,m,q) 同阶，下面证明其复杂度为 (mathcal{O}(nsqrt n))：
在初始状态时，设入度 (leq sqrt{2m}) 的点集为 (A)，设入度 (>sqrt{2m}) 的点集为 (B)，定义一个点的势能为入度，一次操作所带来的复杂度即为一个点的势能。
- 操作 (A) 中的点，释放 (leq sqrt{2m}) 的势能，给 (B) 带来的势能 (leq sqrt{2m})；
- 操作 (B) 中的点，释放 (B) 给其的势能，由于 (|B|<sqrt {2m})，所以这部分 (leq sqrt 2m)；
- 操作 (B) 中的点，释放 (A) 给其的势能，根据 1. 中的分析，其总量 (leq qsqrt {2m})．
综上所述，总的时间复杂度为 (mathcal{O}(n+m+qsqrt n))．
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<pii> vpii;
typedef std::vector<ll> vll;
const ll mod = 998244353;
ll Add(ll x, ll y) { return (x+y>=mod) ? (x+y-mod) : (x+y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return x < 0 ? (x + mod) : (x >= mod ? (x-mod) : x); }
ll cadd(ll &x, ll y) { return x = (x+y>=mod) ? (x+y-mod) : (x+y); }
ll cMul(ll &x, ll y) { return x = x * y % mod; }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T cmax(T &x, T y) { return x = x > y ? x : y; }
template <typename T> T cmin(T &x, T y) { return x = x < y ? x : y; }
template <typename T>
T &read(T &r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
const int N = 1001000;
int n, m, deg[N];
vi eg[N];
ll ans;
ll Calc(int x) {
return (ll)eg[x].size() * (deg[x] - (ll)eg[x].size());
}
void Rev(int x) {
ans -= Calc(x);
for(auto v : eg[x]) {
ans -= Calc(v);
eg[v].pb(x);
ans += Calc(v);
}
eg[x].clear();
}
signed main() {
read(n); read(m);
for(int i = 1, u, v; i <= m; ++i) {
read(u); read(v);
if(u < v) std::swap(u, v);
eg[v].pb(u); ++deg[u]; ++deg[v];
}
for(int i = 1; i <= n; ++i) ans += Calc(i);
printf("%lld
", ans);
int q; read(q);
for(int i = 1; i <= q; ++i) {
int u; read(u);
Rev(u);
printf("%lld
", ans);
}
return 0;
}