結果
| 問題 | No.833 かっこいい電車 |
| ユーザー |
 Iván Soto
|
| 提出日時 | 2021-05-14 01:11:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 100 ms / 2,000 ms |
| コード長 | 6,264 bytes |
| コンパイル時間 | 3,269 ms |
| コンパイル使用メモリ | 232,360 KB |
| 最終ジャッジ日時 | 2025-01-21 10:50:38 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
/*** author: ivanzuki* created: Thu May 13 2021**/#include <bits/stdc++.h>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 <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>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 <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}template<typename T> void dout(string name, int idx, T arg) {cerr << name << " = " << to_string(arg);}template<typename T1, typename... T2> 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#endifconst 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<int> p, rnk;vector<long long> sum;int comps;stack<dsu_save> 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<vector<query>> 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<long long>& 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<long long> solve() {vector<long long> 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<pair<int, int>> qs(q);// (type, x)vector<vector<array<int, 3>>> xs(n);vector<array<int, 2>> 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<long long> ans = query_tree.solve();for (int i = 0; i < q; i++) {if (ask[i] > -1) {cout << ans[i] << '\n';}}return 0;}