結果
| 問題 | No.1054 Union add query |
| ユーザー |
 minato
|
| 提出日時 | 2020-11-16 16:35:15 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 252 ms / 2,000 ms |
| コード長 | 8,411 bytes |
| コンパイル時間 | 4,071 ms |
| コンパイル使用メモリ | 244,488 KB |
| 実行使用メモリ | 44,564 KB |
| 最終ジャッジ日時 | 2023-09-30 07:19:05 |
| 合計ジャッジ時間 | 8,413 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 191 ms
28,340 KB |
| testcase_04 | AC | 248 ms
44,440 KB |
| testcase_05 | AC | 178 ms
25,444 KB |
| testcase_06 | AC | 185 ms
38,432 KB |
| testcase_07 | AC | 157 ms
38,312 KB |
| testcase_08 | AC | 182 ms
38,436 KB |
| testcase_09 | AC | 252 ms
44,372 KB |
| testcase_10 | AC | 157 ms
44,564 KB |
ソースコード
#ifdef ONLINE_JUDGE
#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
constexpr char ln = '\n';
istream& operator>>(istream& is, __int128_t& x) {
x = 0;
string s;
is >> s;
int n = int(s.size()), it = 0;
if (s[0] == '-') it++;
for (; it < n; it++) x = (x * 10 + s[it] - '0');
if (s[0] == '-') x = -x;
return is;
}
ostream& operator<<(ostream& os, __int128_t x) {
if (x == 0) return os << 0;
if (x < 0) os << '-', x = -x;
deque<int> deq;
while (x) deq.emplace_front(x % 10), x /= 10;
for (int e : deq) os << e;
return os;
}
template<class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
for (int i = 0; i < int(v.size()); i++) {
if (i) os << ", ";
os << v[i];
}
return os << "}";
}
template<class Container> inline int SZ(Container& v) { return int(v.size()); }
template<class T> inline void UNIQUE(vector<T>& v) { v.erase(unique(v.begin(), v.end()), v.end()); }
template<class T1, class T2> inline bool chmax(T1& a, T2 b) { if (a < b) {a = b; return true ;} return false ;}
template<class T1, class T2> inline bool chmin(T1& a, T2 b) { if (a > b) {a = b; return true ;} return false ;}
inline int topbit(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
inline int topbit(long long x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(int x) { return x == 0 ? 32 : __builtin_ctz(x); }
inline int botbit(long long x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(int x) { return __builtin_popcount(x); }
inline int popcount(long long x) { return __builtin_popcountll(x); }
inline int kthbit(long long x, int k) { return (x>>k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x-1) * 10; }
inline void print() { cout << "\n"; }
template<class T>
inline void print(const vector<T>& v) {
for (int i = 0; i < int(v.size()); i++) {
if (i) cout << " ";
cout << v[i];
}
print();
}
template<class T, class... Args>
inline void print(const T& x, const Args& ... args) {
cout << x << " ";
print(args...);
}
#ifdef MINATO_LOCAL
inline void debug_out() { cerr << endl; }
template <class T, class... Args>
inline void debug_out(const T& x, const Args& ... args) {
cerr << " " << x;
debug_out(args...);
}
#define debug(...) cerr << __LINE__ << " : [" << #__VA_ARGS__ << "] =", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
struct mergetree {
using pii = pair<int, int>;
public:
mergetree() {}
mergetree(int n) : n(n) {}
vector<pii> build(const vector<int>& type, const vector<pii>& vs) {
q = int(type.size());
parent_or_size.assign(n,-1);
root.resize(n);
iota(root.begin(),root.end(),0);
vid.resize(n);
child.resize(q);
range.resize(n+q);
vector<int> idx(q,-1);
for (int i = 0; i < q; i++) {
if (type[i] == 1) {
auto[a,b] = vs[i];
if (same(a,b)) continue;
child[i] = pii(root[leader(a)],root[leader(b)]);
root[merge(a,b)] = n + i;
} else {
int x = vs[i].first;
idx[i] = root[leader(x)];
}
}
int pos = 0;
for (int i = 0; i < n; i++) {
if (leader(i) == i) {
dfs(root[i],pos);
}
}
vector<pii> ret(q);
for (int i = 0; i < q; i++) {
if (~idx[i]) {
ret[i] = range[idx[i]];
}
}
return ret;
}
int operator[](int i) { return vid[i]; }
private:
int n,q;
// root node: -1 * component size
// otherwise: parent
vector<int> parent_or_size,root,vid;
vector<pii> child,range;
void dfs(int v, int& pos) {
int l = pos;
if (v < n) {
vid[v] = pos++;
} else {
dfs(child[v-n].first,pos);
dfs(child[v-n].second,pos);
}
int r = pos;
range[v] = pii(l,r);
};
int merge(int a, int b) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
};
template<class T, class U, class G, class H>
struct DualSegmentTree {
private:
G mapping;
H composition;
U id;
int _n, size ,log;
vector<T> node;
vector<U> lazy;
public:
DualSegmentTree() {}
DualSegmentTree(const G& mapping, const H& composition, U id, const vector<T>& v)
: mapping(mapping), composition(composition), id(id), _n(int(v.size())), log(0) {
while ((1<<log) < _n) log++;
size = 1 << log;
node.resize(size);
for (int i = 0; i < _n; i++) node[i] = v[i];
lazy = vector<U>(size, id);
}
void set(int p, T x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
node[p-size] = x;
}
void apply(int p, U val) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
node[p-size] = val == id ? node[p-size] : mapping(node[p-size], val);
}
void apply(int l, int r, U val) {
if (l >= r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, val);
if (r & 1) all_apply(--r, val);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
}
T operator[](int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return node[p-size];
}
private:
void all_apply(int k, U val) {
if (k >= size) node[k-size] = val == id ? node[k-size] : mapping(node[k-size], val);
else lazy[k] = composition(lazy[k], val);
}
void push(int k) {
if (lazy[k] == id) return;
all_apply(2 * k, lazy[k]);
all_apply(2 * k + 1, lazy[k]);
lazy[k] = id;
}
};
int main() {
int N,Q; cin >> N >> Q;
vector<int> T(Q);
vector<pii> vs(Q);
rep(i,Q) {
cin >> T[i] >> vs[i].first >> vs[i].second;
vs[i].first--;
if (T[i] == 1) vs[i].second--;
}
auto f=[](ll a, ll b) {return a+b;};
constexpr ll id = 0;
vector<ll> arr(N);
DualSegmentTree seg(f,f,id,arr);
mergetree G(N);
auto ret = G.build(T,vs);
rep(i,Q) {
if (T[i]==2) {
auto[l,r] = ret[i];
seg.apply(l,r,vs[i].second);
}
if (T[i]==3) {
int k = G[vs[i].first];
cout << seg[k] << ln;
}
}
}