Codeforces 1229C / 1210D Konrad and Company Evaluation

三元环计数,于是考虑暴力。答案显然为每个点的入度 \(\times\) 出度和,每次修改一个点的时候,遍历所有的入边,将其改为出边,更新答案,一次更新的复杂度是 \(\mathcal{O}(入度)\) 的。

不妨设 \(n,m,q\) 同阶,下面证明其复杂度为 \(\mathcal{O}(n\sqrt n)\):

在初始状态时,设入度 \(\leq \sqrt{2m}\) 的点集为 \(A\),设入度 \(>\sqrt{2m}\) 的点集为 \(B\),定义一个点的势能为入度,一次操作所带来的复杂度即为一个点的势能。

  1. 操作 \(A\) 中的点,释放 \(\leq \sqrt{2m}\) 的势能,给 \(B\) 带来的势能 \(\leq \sqrt{2m}\);
  2. 操作 \(B\) 中的点,释放 \(B\) 给其的势能,由于 \(|B|<\sqrt {2m}\),所以这部分 \(\leq \sqrt 2m\);
  3. 操作 \(B\) 中的点,释放 \(A\) 给其的势能,根据 1. 中的分析,其总量 \(\leq q\sqrt {2m}\).

综上所述,总的时间复杂度为 \(\mathcal{O}(n+m+q\sqrt 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\n", ans);
	int q; read(q);
	for(int i = 1; i <= q; ++i) {
		int u; read(u);
		Rev(u);
		printf("%lld\n", ans);
	}
	return 0;
}
上一篇:Codeforces Round #751 (Div. 2) D. Frog Traveler(DP)


下一篇:一次单片机 SFR 页引发的“事故”