398D - Instant Messanger - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

// #include "debug.h"

using ll = long long;

#define set unordered_set

const int N = 50000+1;
const int M = 150000+1;
const int Q = 250000+1;
const int S = 550;
const int H = 550;
 
struct Query {
  char t;
  int u, v, idx, ans;
};
 
int n, m, qq;
bool online[N];
int maxedges[N];
bool heavy[N];
vector<int> hvy;
set<int> ofriends[N];
int lfriends[N];
set<int> pointing[N];
set<int> adj[N];
set<int> hadj[N];

void add_edge(int u, int v) {
  adj[u].insert(v);
  adj[v].insert(u);
  if (heavy[v]) hadj[u].insert(v);
  if (heavy[u]) hadj[v].insert(u);
}

void del_edge(int u, int v) {
  adj[u].erase(v);
  adj[v].erase(u);
  if (heavy[v]) hadj[u].erase(v);
  if (heavy[u]) hadj[v].erase(u);
}
 
void recompute() {
  for (int i = 0; i < n; ++i) {
    ofriends[i].clear(); 
    lfriends[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    if (online[i]) {
      for (int j : adj[i]) {
        if (heavy[i]) ofriends[j].insert(i);
        if (not heavy[i]) ++lfriends[j];
        if (heavy[i] and heavy[j]) pointing[i].insert(j);
      }
    }
  }
}

void update_heavy() {
  for (int i : hvy) {
    ofriends[i].clear();
  }
  for (int i : hvy) {
    if (online[i]) {
      for (int j : hadj[i]) {
        ofriends[j].insert(i);
      }
    }
  }
}

void apply(const Query& q) {
  if (q.t == 'O') {
    online[q.u] = true;
    if (not heavy[q.u]) {
      for (int j : adj[q.u]) {
        ++lfriends[j];
      }
    }
  }
  else if (q.t == 'F') {
    online[q.u] = false;
    if (not heavy[q.u]) {
      for (int j : adj[q.u]) {
        --lfriends[j];
      }
    }
  }
  else if (q.t == 'A') {
    add_edge(q.u, q.v);
    if (online[q.u] and not heavy[q.u]) {
      ++lfriends[q.v];
    }
    if (online[q.v] and not heavy[q.v]) {
      ++lfriends[q.u];
    }
  }
  else if (q.t == 'D') {
    del_edge(q.u, q.v);
    if (online[q.u] and not heavy[q.u]) {
      --lfriends[q.v];
    }
    if (online[q.v] and not heavy[q.v]) {
      --lfriends[q.u];
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  cin >> n >> m >> qq;
  for (int i = 0; i < n; ++i) {
    adj[i] = set<int>();
    pointing[i] = set<int>();
    ofriends[i] = set<int>();
    hadj[i] = set<int>();
    adj[i].max_load_factor(0.5);
    pointing[i].max_load_factor(0.5);
    ofriends[i].max_load_factor(0.5);
    hadj[i].max_load_factor(0.5);
    online[i] = false;
    maxedges[i] = 0;
  }

  int o;
  cin >> o;
  for (int i = 0; i < o; ++i) {
    int x;
    cin >> x; --x;
    online[x] = true;
  }

  vector<pair<int,int>> initial_edges;

  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b; --a; --b;
    initial_edges.emplace_back(a, b);
    ++maxedges[a], ++maxedges[b];
  }
 
  vector<Query> qs(qq);
  for (int i = 0; i < qq; ++i) {
    Query& q = qs[i];
    q.idx = i;
    q.ans = -1;
    cin >> q.t >> q.u, --q.u;
    if (q.t == 'A' or q.t == 'D')
      cin >> q.v, --q.v;
    else
      q.v = -1;
    if (q.t == 'A')
      ++maxedges[q.u], ++maxedges[q.v];
  }

  for (int i = 0; i < n; ++i) {
    adj[i].reserve(maxedges[i]);
    ofriends[i].reserve(maxedges[i]);
    pointing[i].reserve(maxedges[i]);
    hadj[i].reserve(maxedges[i]);
    heavy[i] = (maxedges[i] >= H);
    if (heavy[i]) hvy.push_back(i);
  }

  for (auto e : initial_edges) {
    add_edge(e.first, e.second);
  }

  recompute();

  set<int> modified;
  modified.max_load_factor(0.5);
  modified.reserve(S);

  for (Query& q : qs) {
    if (modified.size() >= S) {
      recompute();
      modified.clear();
    }

    if (q.t == 'C') {
      // D(modified.size()) << endl;
      if (heavy[q.u]) {
        q.ans = lfriends[q.u] + (int)ofriends[q.u].size();
        for (int i : modified) {
          if (ofriends[q.u].count(i)) {
            if ((not online[i]) or (not adj[q.u].count(i)))
              --q.ans;
          }
          else {
            if (online[i] and adj[q.u].count(i))
              ++q.ans;
          }
        }
      }
      else {
        q.ans = lfriends[q.u];
        for (int i : hadj[q.u]) {
          if (online[i]) ++q.ans;
        }
      }
      cout << q.ans << '\n';
    }
    else {
      apply(q);
      if (heavy[q.u]) modified.insert(q.u);
      if (q.v != -1 and heavy[q.v]) modified.insert(q.v);
    }
  }
}