Tinkoff, SQRT D

#include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); #define forn(i, a, b) for (int i = (a); i < (b); i++) #define ford(i, a, b) for (int i = (b)-1; i >= (a); i--) #define all(x) (x).begin(),(x).end() #define fi first #define se second #define szof(x) ((int)(x).size()) #define rsz resize #define lb lower_bound #define ub upper_bound #define INF (int)1e9 #define INFL (long long)1e18 #define re return #define pb push_back #define mp make_pair #define mt make_tuple #define ll long long #define ld long double #define PII pair<int,int> #define VI vector<int> #define VVI vector<vector <int> > #define VVLL vector<vector <long long> > #define VLL vector <long long> #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #define debug(x) cout << #x << " is " << x << '\n'; #define debug2(x) cout << #x << " is : "; for (auto elem : x) { cout << elem << " " ;} cout << "\n"; using namespace std; const int MAXN = 1e5; int n,m; vector <int> g[MAXN]; short int cnt[1000][MAXN+1]; //Счетчик для тежлых вершин. Сколько вершин цвета от 1 до MAXN соседи тяжелой вершины int color[MAXN]; // Цвет int ans; int len; //sqrt N int num[MAXN]; // сжатый номер для тяжелой вершины void solve() { vector <int> deg(n); // Степень vector <int> big; for (int i = 0; i < n; i++) { deg[i] = szof(g[i]); if (deg[i] >= len) { //тяжелая вершина big.pb(i); } } sort(all(big)); for (int i = 0; i < szof(big); i++) { int v = big[i]; num[v] = i; //Типа сжимаем вершины, чтобы cnt был размера не MAXN (попытка ускориться, не всегда же доступ к массиву O(1)) } //Предпосчет, запускаеся от вершин и смотрим сколько вершин другого цвета for (int v = 0; v < n; v++) { for (auto u : g[v]) { if (color[u] != color[v]) { ans++; } if (deg[v] >= len) { cnt[num[v]][color[u]]++; //Опа, наша v - тяжелая. Помечаем что у тяжелой есть такой цвет в соседях } } } ans /= 2; for (auto v : big) { sort(all(g[v]), [&](int a, int b) { return deg[a] > deg[b]; }); // сортируем вершины по убыванию степени. У тяжелых вершин убираем ребра в более легкие, у которых степень меньше корня while(!g[v].empty() && deg[g[v].back()] < len) { g[v].pop_back(); } } int q; cin >> q; for (int i = 0; i < q;i++) { int c,col; cin >> c >> col; c--; // запросик if (deg[c] < len) { // легкая for (auto u : g[c]) { // идем по соседям. Сначала прибавляем обратно цвет, который у вершины сейчас if (color[u] == color[c]) { ans++; } if (color[u] == col) { // и отнимаем новый ans--; } if (deg[u] >= len) { // нашли соседа тяжелую вершину cnt[num[u]][color[c]]--; cnt[num[u]][col]++; } } color[c] = col; // обнова } else { ans += cnt[num[c]][color[c]]; // вершина тяжелая, идем по ребрам в другие тяжелые for (auto u : g[c]) { cnt[num[u]][color[c]]--; cnt[num[u]][col]++; } color[c] = col; ans -= cnt[num[c]][color[c]]; } cout << ans << "\n"; // опа ответ } // Ну и че ты TL получаешь, падла? } int main() { fastIO; cin >> n >> m; len = sqrt(n); forn(i, 0, n) { cin >> color[i]; } for (int i = 0; i < m; i++) { int a,b; cin >> a >> b; a--;b--; g[a].pb(b); g[b].pb(a); } solve(); return 0; }