結果
| 問題 |
No.1054 Union add query
|
| コンテスト | |
| ユーザー |
 回転
|
| 提出日時 | 2025-09-13 00:20:11 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 692 ms / 2,000 ms |
| コード長 | 9,726 bytes |
| コンパイル時間 | 3,623 ms |
| コンパイル使用メモリ | 294,368 KB |
| 実行使用メモリ | 90,112 KB |
| 最終ジャッジ日時 | 2025-09-13 00:20:21 |
| 合計ジャッジ時間 | 9,272 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 |
ソースコード
/*
from collections import defaultdict
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
self.retu = [[i] for i in range(n)]
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
if(len(self.retu[x]) <= len(self.retu[y])):
for i in self.retu[x]:
self.retu[y].append(i)
self.retu[x],self.retu[y] = self.retu[y],self.retu[x]
else:
for i in self.retu[y]:
self.retu[x].append(i)
def size(self, x):
return -self.parents[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
return len(self.roots())
def all_group_members(self):
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members
def __str__(self):
return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())
def segfunc(x,y):
return x+y
class LazySegTree_RAQ:
def __init__(self,init_val,segfunc,ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1<<(n-1).bit_length()
self.tree = [ide_ele]*2*self.num
self.lazy = [0]*2*self.num
for i in range(n):
self.tree[self.num+i] = init_val[i]
for i in range(self.num-1,0,-1):
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
def gindex(self,l,r):
l += self.num
r += self.num
lm = l>>(l&-l).bit_length()
rm = r>>(r&-r).bit_length()
while r>l:
if l<=lm:
yield l
if r<=rm:
yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
def propagates(self,*ids):
for i in reversed(ids):
v = self.lazy[i]
if v==0:
continue
self.lazy[i] = 0
self.lazy[2*i] += v
self.lazy[2*i+1] += v
self.tree[2*i] += v
self.tree[2*i+1] += v
def add(self,l,r,x):
ids = self.gindex(l,r)
l += self.num
r += self.num
while l<r:
if l&1:
self.lazy[l] += x
self.tree[l] += x
l += 1
if r&1:
self.lazy[r-1] += x
self.tree[r-1] += x
r >>= 1
l >>= 1
for i in ids:
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1]) + self.lazy[i]
def query(self,l,r):
self.propagates(*self.gindex(l,r))
res = self.ide_ele
l += self.num
r += self.num
while l<r:
if l&1:
res = self.segfunc(res,self.tree[l])
l += 1
if r&1:
res = self.segfunc(res,self.tree[r-1])
l >>= 1
r >>= 1
return res
from collections import defaultdict
import sys
input = sys.stdin.readline
N,Q = list(map(int,input().split()))
query = [list(map(int,input().split())) for _ in range(Q)]
uf = UnionFind(N)
for i in range(Q):
t,a,b, = query[i]
a -= 1;b -= 1
if(t == 1):uf.union(a,b)
v = []
done = set()
for p in uf.roots():
if(p in done):continue
done.add(p)
v += uf.retu[p]
place = [-1 for _ in range(N)]
for i in range(N):place[v[i]] = i
uf = UnionFind(N)
T = LazySegTree_RAQ([0 for _ in range(N)],segfunc,0)
for i in range(Q):
t,a,b, = query[i]
if(t == 1):
uf.union(a-1,b-1)
elif(t == 2):
ap = uf.find(a-1)
head = uf.retu[ap][0]
end = uf.retu[ap][-1]
T.add(place[head],place[end]+1,b)
else:
p = place[a-1]
print(T.query(p,p+1))
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ---------- UnionFind (retu を保持) ----------
struct UnionFind {
int n;
vector<int> parents; // negative size for root
vector<vector<int>> retu; // members lists per root-index
UnionFind(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
parents.assign(n, -1);
retu.assign(n, vector<int>());
for (int i = 0; i < n; ++i) retu[i].push_back(i);
}
int find(int x) {
if (parents[x] < 0) return x;
return parents[x] = find(parents[x]);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
// ensure x is the bigger (more negative)
if (parents[x] > parents[y]) swap(x, y);
parents[x] += parents[y];
parents[y] = x;
// merge retu exactly like Python version
if (retu[x].size() <= retu[y].size()) {
// append retu[x] into retu[y], then swap so retu[x] becomes combined list
for (int v : retu[x]) retu[y].push_back(v);
retu[x].swap(retu[y]);
} else {
for (int v : retu[y]) retu[x].push_back(v);
}
}
int size(int x) { return -parents[find(x)]; }
bool same(int x, int y) { return find(x) == find(y); }
vector<int> roots() {
vector<int> res;
for (int i = 0; i < n; ++i) if (parents[i] < 0) res.push_back(i);
return res;
}
};
// ---------- Lazy Segment Tree (range add, range sum) ----------
// Implemented with standard recursive lazy propagation
struct LazySegTreeRAQ {
int n;
vector<ll> seg; // segment sums
vector<ll> lz; // lazy addition (to add to children)
LazySegTreeRAQ() { n = 0; }
LazySegTreeRAQ(int _n) { build(_n); }
LazySegTreeRAQ(const vector<ll>& init) { build(init); }
void build(int _n) {
n = 1;
while (n < _n) n <<= 1;
seg.assign(2*n, 0);
lz.assign(2*n, 0);
}
void build(const vector<ll>& init) {
int m = (int)init.size();
n = 1;
while (n < m) n <<= 1;
seg.assign(2*n, 0);
lz.assign(2*n, 0);
for (int i = 0; i < m; ++i) seg[n+i] = init[i];
for (int i = n-1; i >= 1; --i) seg[i] = seg[2*i] + seg[2*i+1];
}
void push(int k, int l, int r) {
if (lz[k] != 0 && k < n) {
ll v = lz[k];
int mid = (l + r) >> 1;
// left child covers [l,mid), right [mid,r)
seg[2*k] += v * (mid - l);
seg[2*k+1] += v * (r - mid);
lz[2*k] += v;
lz[2*k+1] += v;
lz[k] = 0;
}
}
// add x to [a,b)
void add(int a, int b, ll x) { add_impl(a,b,x,1,0,n); }
void add_impl(int a, int b, ll x, int k, int l, int r) {
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
seg[k] += x * (r - l);
lz[k] += x;
return;
}
push(k,l,r);
int mid = (l + r) >> 1;
add_impl(a,b,x,2*k,l,mid);
add_impl(a,b,x,2*k+1,mid,r);
seg[k] = seg[2*k] + seg[2*k+1];
}
// sum on [a,b)
ll sum(int a, int b) { return sum_impl(a,b,1,0,n); }
ll sum_impl(int a, int b, int k, int l, int r) {
if (b <= l || r <= a) return 0;
if (a <= l && r <= b) return seg[k];
push(k,l,r);
int mid = (l + r) >> 1;
return sum_impl(a,b,2*k,l,mid) + sum_impl(a,b,2*k+1,mid,r);
}
};
// ---------- main ----------
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
if (!(cin >> N >> Q)) return 0;
vector<array<int,3>> query(Q);
for (int i = 0; i < Q; ++i) {
int t, a, b;
cin >> t >> a >> b;
query[i] = {t, a, b};
}
// 1st pass: build components by applying all t==1 unions
UnionFind uf1(N);
for (int i = 0; i < Q; ++i) {
int t = query[i][0], a = query[i][1], b = query[i][2];
if (t == 1) {
uf1.unite(a-1, b-1);
}
}
// collect v by concatenating retu of roots (same as Python)
vector<int> v;
vector<int> roots1 = uf1.roots();
// Python code iterates roots() in increasing order; roots1 is in increasing order
for (int p : roots1) {
// append whole retu[p]
for (int x : uf1.retu[p]) v.push_back(x);
}
// place mapping: element -> position in v
vector<int> place(N, -1);
for (int i = 0; i < N; ++i) place[v[i]] = i;
// 2nd pass: process queries incrementally with fresh UnionFind and LazySegTree
UnionFind uf2(N);
LazySegTreeRAQ T(N); // length N, initial zeros
for (int i = 0; i < Q; ++i) {
int t = query[i][0], a = query[i][1], b = query[i][2];
if (t == 1) {
uf2.unite(a-1, b-1);
} else if (t == 2) {
int ap = uf2.find(a-1);
// head and end from retu[ap]
int head = uf2.retu[ap].front();
int end = uf2.retu[ap].back();
// add b to range [place[head], place[end]+1)
T.add(place[head], place[end] + 1, (ll)b);
} else if (t == 3) {
int p = place[a-1];
cout << T.sum(p, p+1) << '\n';
}
}
return 0;
}