# Untitled

unknown
c_cpp
5 months ago
2.6 kB
3
Indexable
Never
```#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

constexpr int K = 450;
constexpr int N = 1e5;

void solve() {
int n, m;
cin >> n >> m;
vector<int> v(n);
for (int &i : v) {
cin >> i;
i--;
}
vector<int> g[n];
int ans = 0;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--; b--;
if (v[a] != v[b]) {
ans++;
}
g[a].push_back(b);
g[b].push_back(a);
}
auto is_heavy = [&](int a) {
return (int)g[a].size() >= K;
};
int dp[K][N];
int cur = 0;
int mp[n];
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end(), [&](int lhs, int rhs) {
return g[lhs].size() > g[rhs].size();
});
if (is_heavy(i)) {
mp[i] = cur++;
fill(dp[mp[i]], dp[mp[i]] + N, 0);
}
}
for (int i = 0; i < n; i++) {
if (is_heavy(i)) {
for (int &u : g[i]) {
if (!is_heavy(u)) {
dp[mp[i]][v[u]]++;
}
}
}
}
int q;
cin >> q;
while (q--) {
int C, V;
cin >> C >> V;
C--; V--;
if (v[C] == V) {
cout << ans << '\n';
continue;
}
if (!is_heavy(C)) {
for (int &u : g[C]) {
if (!is_heavy(u)) {
if (v[u] == v[C]) {
ans++;
}
if (v[u] == V) {
ans--;
}
} else {
dp[mp[u]][v[C]]--;
dp[mp[u]][V]++;
if (v[u] == v[C]) {
ans++;
}
if (v[u] == V) {
ans--;
}
}
}
} else {
for (int &u : g[C]) {
if (!is_heavy(u)) break;
if (v[u] == v[C]) {
ans++;
}
if (v[u] == V) {
ans--;
}
}
ans -= dp[mp[C]][v[C]];
ans += dp[mp[C]][V];
}
v[C] = V;
cout << ans << '\n';
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int tests = 1;
// cin >> tests;
while (tests--) {
solve();
}
return 0;
}```