/** * author: ivanzuki * created: Thu May 13 2021 **/ #include using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } template void dout(string name, int idx, T arg) { cerr << name << " = " << to_string(arg); } template void dout(string names, int idx, T1 arg, T2... args) { cerr << names.substr(0, names.find(',')) << " = " << to_string(arg) << ", "; dout(names.substr(names.find(',') + 2), idx + 1, args...); } #ifdef LOCAL #define debug(...) cerr << "[", dout(#__VA_ARGS__, 0, __VA_ARGS__), cerr << "]" << endl; #else #define debug(...) 42 #endif const int N = 100010; int a[N]; int ask[N]; enum QueryType { UNITE, ADD }; struct dsu_save { int v, rnkv, u, rnku; long long sumv, sumu; dsu_save() {} dsu_save(int _v, int _rnkv, int _u, int _rnku, long long _sumv, long long _sumu) : v(_v), rnkv(_rnkv), u(_u), rnku(_rnku), sumv(_sumv), sumu(_sumu) {} }; struct dsu_with_rollbacks { vector p, rnk; vector sum; int comps; stack op; dsu_with_rollbacks() {} dsu_with_rollbacks(int n) { p.resize(n); rnk.resize(n); sum.resize(n); for (int i = 0; i < n; i++) { p[i] = i; rnk[i] = 0; sum[i] = a[i]; } comps = n; } int find_set(int v) { return (v == p[v]) ? v : find_set(p[v]); } bool unite(int v, int u) { v = find_set(v); u = find_set(u); if (v == u) return false; comps--; if (rnk[v] > rnk[u]) swap(v, u); op.push(dsu_save(v, rnk[v], u, rnk[u], sum[v], sum[u])); p[v] = u; sum[u] += sum[v]; if (rnk[u] == rnk[v]) rnk[u]++; return true; } void add(int v, int add) { v = find_set(v); sum[v] += add; } void rollback() { if (op.empty()) return; dsu_save x = op.top(); op.pop(); comps++; p[x.v] = x.v; rnk[x.v] = x.rnkv; sum[x.v] = x.sumv; p[x.u] = x.u; rnk[x.u] = x.rnku; sum[x.u] = x.sumu; } }; struct query { int v, u; bool united; QueryType type; query(int _v, int _u, QueryType _type) : v(_v), u(_u), type(_type) { } }; struct QueryTree { vector> t; dsu_with_rollbacks dsu; int T; QueryTree() {} QueryTree(int _T, int n) : T(_T) { dsu = dsu_with_rollbacks(n); t.resize(4 * T + 4); } void add_to_tree(int v, int l, int r, int ul, int ur, query& q) { if (ul > ur) return; if (l == ul && r == ur) { t[v].push_back(q); return; } int mid = (l + r) / 2; add_to_tree(2 * v, l, mid, ul, min(ur, mid), q); add_to_tree(2 * v + 1, mid + 1, r, max(ul, mid + 1), ur, q); } void add_query(query q, int l, int r) { add_to_tree(1, 0, T - 1, l, r, q); } void dfs(int v, int l, int r, vector& ans) { for (query& q : t[v]) { if (q.type == ADD) { assert(q.u == -1); dsu.add(q.v, 1); } } for (query& q : t[v]) { if (q.type == UNITE) { q.united = dsu.unite(q.v, q.u); } } if (l == r) { if (ask[l] > -1) { ans[l] = dsu.sum[dsu.find_set(ask[l])]; } } else { int mid = (l + r) / 2; dfs(2 * v, l, mid, ans); dfs(2 * v + 1, mid + 1, r, ans); } for (query q : t[v]) { if (q.type == UNITE) { if (q.united) { dsu.rollback(); } } } for (query q : t[v]) { if (q.type == ADD) { dsu.add(q.v, - 1); } } } vector solve() { vector ans(T); dfs(1, 0, T - 1, ans); return ans; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { cin >> a[i]; } memset(ask, -1, sizeof ask); vector> qs(q); // (type, x) vector>> xs(n); vector> add; for (int i = 0; i < q; i++) { cin >> qs[i].first >> qs[i].second; --qs[i].second; int type = qs[i].first; int x = qs[i].second; if (type == 1) { if (xs[x].empty() || xs[x].back()[0] == 2) { xs[x].push_back({type, x, i}); } } else if (type == 2) { if (!xs[x].empty() && xs[x].back()[0] == 1) { xs[x].push_back({type, x, i}); } } else if (type == 3) { add.push_back({x, i}); } else if (type == 4) { ask[i] = x; } else { assert(0); } } QueryTree query_tree(q, n); for (int x = 0; x < n; x++) { query qry(x, x + 1, UNITE); for (int i = 0; i + 1 < (int) xs[x].size(); i += 2) { assert(xs[x][i][0] == 1 && xs[x][i + 1][0] == 2); query_tree.add_query(qry, xs[x][i][2], xs[x][i + 1][2] - 1); } if ((int) xs[x].size() % 2) { query_tree.add_query(qry, xs[x].back()[2], q - 1); } } for (const auto& inc : add) { int x = inc[0], i = inc[1]; query qry(x, -1, ADD); query_tree.add_query(qry, i, q - 1); } vector ans = query_tree.solve(); for (int i = 0; i < q; i++) { if (ask[i] > -1) { cout << ans[i] << '\n'; } } return 0; }