QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245554 | #7767. 数据结构 | hos_lyric# | 15 | 268ms | 63424kb | C++14 | 14.8kb | 2023-11-10 01:23:15 | 2024-07-04 02:24:05 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// T: monoid representing information of an interval.
// T() should return the identity.
// T(S s) should represent a single element of the array.
// T::push(T &l, T &r) should push the lazy update.
// T::pull(const T &l, const T &r) should pull two intervals.
template <class T> struct SegmentTreeRange {
int logN, n;
vector<T> ts;
SegmentTreeRange() : logN(0), n(0) {}
explicit SegmentTreeRange(int n_) {
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
}
template <class S> explicit SegmentTreeRange(const vector<S> &ss) {
const int n_ = ss.size();
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
build();
}
T &at(int i) {
return ts[n + i];
}
void build() {
for (int u = n; --u; ) pull(u);
}
inline void push(int u) {
ts[u].push(ts[u << 1], ts[u << 1 | 1]);
}
inline void pull(int u) {
ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
}
// Applies T::f(args...) to [a, b).
template <class F, class... Args>
void ch(int a, int b, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return;
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) (ts[aa++].*f)(args...);
if (bb & 1) (ts[--bb].*f)(args...);
}
for (int h = 1; h <= logN; ++h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) pull(aa);
} else {
if ((aa << h) != a) pull(aa);
if ((bb << h) != b) pull(bb);
}
}
}
// Calculates the product for [a, b).
T get(int a, int b) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return T();
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
T prodL, prodR, t;
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) { t.pull(prodL, ts[aa++]); prodL = t; }
if (bb & 1) { t.pull(ts[--bb], prodR); prodR = t; }
}
t.pull(prodL, prodR);
return t;
}
// Calculates T::f(args...) of a monoid type for [a, b).
// op(-, -) should calculate the product.
// e() should return the identity.
template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
auto
#else
decltype((std::declval<T>().*F())())
#endif
get(int a, int b, Op op, E e, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return e();
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
auto prodL = e(), prodR = e();
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...));
if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR);
}
return op(prodL, prodR);
}
// Find min b s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from left to right.
// Returns n + 1 if there is no such b.
template <class F, class... Args>
int findRight(int a, F f, Args &&... args) {
assert(0 <= a); assert(a <= n);
if ((T().*f)(args...)) return a;
if (a == n) return n + 1;
a += n;
for (int h = logN; h; --h) push(a >> h);
for (; ; a >>= 1) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < n; ) {
push(a);
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - n + 1;
}
++a;
if (!(a & (a - 1))) return n + 1;
}
}
// Find max a s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from right to left.
// Returns -1 if there is no such a.
template <class F, class... Args>
int findLeft(int b, F f, Args &&... args) {
assert(0 <= b); assert(b <= n);
if ((T().*f)(args...)) return b;
if (b == 0) return -1;
b += n;
for (int h = logN; h; --h) push((b - 1) >> h);
for (; ; b >>= 1) if ((b & 1) || b == 2) {
if ((ts[b - 1].*f)(args...)) {
for (; b <= n; ) {
push(b - 1);
if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
}
return b - n - 1;
}
--b;
if (!(b & (b - 1))) return -1;
}
}
};
////////////////////////////////////////////////////////////////////////////////
struct Hld {
int n, rt;
// needs to be tree
// vertex lists
// modified in build(rt) (parent removed, heavy child first)
vector<vector<int>> graph;
vector<int> sz, par, dep;
int zeit;
vector<int> dis, fin, sid;
// head vertex (minimum depth) in heavy path
vector<int> head;
Hld() : n(0), rt(-1), zeit(0) {}
explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfsSz(int u) {
sz[u] = 1;
for (const int v : graph[u]) {
auto it = std::find(graph[v].begin(), graph[v].end(), u);
if (it != graph[v].end()) graph[v].erase(it);
par[v] = u;
dep[v] = dep[u] + 1;
dfsSz(v);
sz[u] += sz[v];
}
}
void dfsHld(int u) {
dis[u] = zeit++;
const int deg = graph[u].size();
if (deg > 0) {
int vm = graph[u][0];
int jm = 0;
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
if (sz[vm] < sz[v]) {
vm = v;
jm = j;
}
}
swap(graph[u][0], graph[u][jm]);
head[vm] = head[u];
dfsHld(vm);
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
head[v] = v;
dfsHld(v);
}
}
fin[u] = zeit;
}
void build(int rt_) {
assert(0 <= rt_); assert(rt_ < n);
rt = rt_;
sz.assign(n, 0);
par.assign(n, -1);
dep.assign(n, -1);
dep[rt] = 0;
dfsSz(rt);
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
head.assign(n, -1);
head[rt] = rt;
dfsHld(rt);
assert(zeit == n);
sid.assign(n, -1);
for (int u = 0; u < n; ++u) sid[dis[u]] = u;
}
friend ostream &operator<<(ostream &os, const Hld &hld) {
const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
vector<string> ss(2 * maxDep + 1);
int pos = 0, maxPos = 0;
for (int j = 0; j < hld.n; ++j) {
const int u = hld.sid[j];
const int d = hld.dep[u];
if (hld.head[u] == u) {
if (j != 0) {
pos = maxPos + 1;
ss[2 * d - 1].resize(pos, '-');
ss[2 * d - 1] += '+';
}
} else {
ss[2 * d - 1].resize(pos, ' ');
ss[2 * d - 1] += '|';
}
ss[2 * d].resize(pos, ' ');
ss[2 * d] += std::to_string(u);
if (maxPos < static_cast<int>(ss[2 * d].size())) {
maxPos = ss[2 * d].size();
}
}
for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
return os;
}
bool contains(int u, int v) const {
return (dis[u] <= dis[v] && dis[v] < fin[u]);
}
int lca(int u, int v) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
return (dis[u] > dis[v]) ? v : u;
}
int jumpUp(int u, int d) const {
assert(0 <= u); assert(u < n);
assert(d >= 0);
if (dep[u] < d) return -1;
const int tar = dep[u] - d;
for (u = head[u]; ; u = head[par[u]]) {
if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
}
}
int jump(int u, int v, int d) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(d >= 0);
const int l = lca(u, v);
const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
if (d <= du) {
return jumpUp(u, d);
} else if (d <= du + dv) {
return jumpUp(v, du + dv - d);
} else {
return -1;
}
}
// [u, v) or [u, v]
template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
assert(contains(v, u));
for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
if (inclusive) {
f(dis[v], dis[u] + 1);
} else {
if (v != u) f(dis[v] + 1, dis[u] + 1);
}
}
// not path order, include lca(u, v) or not
template <class F> void doPath(int u, int v, bool inclusive, F f) const {
const int l = lca(u, v);
doPathUp(u, l, false, f);
doPathUp(v, l, inclusive, f);
}
// (vs, ps): compressed tree
// vs: DFS order (sorted by dis)
// vs[ps[x]]: the parent of vs[x]
// ids[vs[x]] = x, not set for non-tree vertex
vector<int> ids;
pair<vector<int>, vector<int>> compress(vector<int> us) {
// O(n) first time
ids.resize(n, -1);
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
int usLen = us.size();
assert(usLen >= 1);
for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
usLen = us.size();
for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
vector<int> ps(usLen, -1);
for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
return make_pair(us, ps);
}
};
////////////////////////////////////////////////////////////////////////////////
template <class T> struct NodeSum {
int sz;
T sum;
T lz;
NodeSum() : sz(0), sum(0), lz(0) {}
NodeSum(const T &val) : sz(1), sum(val), lz(0) {}
void push(NodeSum &l, NodeSum &r) {
l.add(lz);
r.add(lz);
lz = 0;
}
void pull(const NodeSum &l, const NodeSum &r) {
sz = l.sz + r.sz;
sum = l.sum + r.sum;
}
void add(const T &val) {
sum += val * sz;
lz += val;
}
T getSum() const {
return sum;
}
bool accSum(T &acc, const T &tar) const {
if (acc + sum >= tar) return true;
acc += sum;
return false;
}
};
template <class T> T getSum(SegmentTreeRange<NodeSum<T>> &seg, int a, int b) {
return seg.get(a, b,
[&](const T &l, const T &r) -> T { return l + r; },
[&]() -> T { return 0; },
&NodeSum<T>::getSum);
}
using U = unsigned long long;
int N, Q;
vector<int> A, B;
vector<int> O, X, Y, K;
vector<U> V;
Hld hld;
namespace sub2 {
vector<U> run() {
cerr<<"[sub2::run]"<<endl;
SegmentTreeRange<NodeSum<U>> seg(vector<U>(N, 0));
vector<U> anss;
for (int q = 0; q < Q; ++q) {
scanf("%d", &O[q]);
if (O[q] == 1) {
int x = X[q], y = Y[q];
if (x > y) swap(x, y);
x = max(x - K[q], 0);
y = min(y + K[q], N - 1);
hld.doPath(x, y, true, [&](int l, int r) -> void {
seg.ch(l, r, &NodeSum<U>::add, V[q]);
});
} else if (O[q] == 2) {
seg.ch(hld.dis[X[q]], hld.fin[X[q]], &NodeSum<U>::add, V[q]);
} else if (O[q] == 3) {
int x = X[q], y = Y[q];
if (x > y) swap(x, y);
x = max(x - K[q], 0);
y = min(y + K[q], N - 1);
U ans = 0;
hld.doPath(x, y, true, [&](int l, int r) -> void {
ans += getSum(seg, l, r);
});
anss.push_back(ans);
} else if (O[q] == 4) {
const U ans = getSum(seg, hld.dis[X[q]], hld.fin[X[q]]);
anss.push_back(ans);
} else {
assert(false);
}
}
return anss;
}
} // sub2
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
O.assign(Q, -1);
X.assign(Q, -1);
Y.assign(Q, -1);
K.assign(Q, -1);
V.assign(Q, 0);
for (int q = 0; q < Q; ++q) {
scanf("%d", &O[q]);
if (O[q] == 1) {
scanf("%d%d%d%llu", &X[q], &Y[q], &K[q], &V[q]);
--X[q];
--Y[q];
} else if (O[q] == 2) {
scanf("%d%llu", &X[q], &V[q]);
--X[q];
} else if (O[q] == 3) {
scanf("%d%d%d", &X[q], &Y[q], &K[q]);
--X[q];
--Y[q];
} else if (O[q] == 4) {
scanf("%d", &X[q]);
--X[q];
} else {
assert(false);
}
}
hld = Hld(N);
for (int i = 0; i < N - 1; ++i) {
hld.ae(A[i], B[i]);
}
hld.build(0);
// cerr<<hld<<endl;
bool spe2 = true;
for (int q = 0; q < Q; ++q) if (O[q] == 1 || O[q] == 3) spe2 = spe2 && (K[q] == 0);
bool spe3 = true;
for (int u = 1; u < N; ++u) spe3 = spe3 && (hld.par[u] == u - 1);
vector<U> anss;
if (spe2 || spe3) {
anss = sub2::run();
} else {
assert(false);
}
for (const U ans : anss) {
printf("%llu\n", ans);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
result:
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 233ms
memory: 40268kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 0
Accepted
time: 268ms
memory: 40096kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 5
Accepted
Test #5:
score: 5
Accepted
time: 146ms
memory: 63404kb
input:
200000 200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
0 134315201201061 38210069287857 75889674481730 25202765567748 179527420359031 75824479907233 156951577189979 246509811214535 251383387317167 181645886595511 285463150681348 213797241401335 244909583142805 53376921005282 451665818220 379334117147250 720759810155057 768646965102274 224741692238593 18...
result:
ok 100065 numbers
Test #6:
score: 0
Accepted
time: 147ms
memory: 63424kb
input:
200000 200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
0 1950387013442 2906443199266 2144858813468 3137341049831 1081425884175 20924388962208 73530126133368 136609133052209 125022026678010 22502893517249 99022896674514 84010333777754 13909990392191 43442491331837 190816082733002 92810414504491 244006706308139 42843404030538 126151201042579 7249812065288...
result:
ok 99740 numbers
Subtask #4:
score: 0
Runtime Error
Test #7:
score: 0
Runtime Error
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 5...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #4:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%