結果
問題 | No.2640 traO Stamps |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:09:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 6,281 bytes |
コンパイル時間 | 1,881 ms |
コンパイル使用メモリ | 203,084 KB |
最終ジャッジ日時 | 2025-02-19 17:03:50 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>namespace zawa {using i16 = std::int16_t;using i32 = std::int32_t;using i64 = std::int64_t;using i128 = __int128_t;using u8 = std::uint8_t;using u16 = std::uint16_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using usize = std::size_t;} // namespace zawanamespace zawa {void SetFastIO() {std::cin.tie(nullptr)->sync_with_stdio(false);}void SetPrecision(u32 dig) {std::cout << std::fixed << std::setprecision(dig);}} // namespace zawa#include <type_traits>namespace zawa {template <class Group>class FenwickTree {private:using Value = typename Group::Element;usize n_;u32 bitWidth_;std::vector<Value> a_, dat_;constexpr i32 lsb(i32 x) const noexcept {return x & -x;}// a[i] <- a[i] + vvoid addDat(i32 i, const Value& v) {assert(0 <= i and i < static_cast<i32>(n_));for ( i++ ; i < static_cast<i32>(dat_.size()) ; i += lsb(i)) {dat_[i] = Group::operation(dat_[i], v);}}// return a[0] + a[1] + .. + a[i - 1]Value product(i32 i) const {assert(0 <= i and i <= static_cast<i32>(n_));Value res{ Group::identity() };for ( ; i > 0 ; i -= lsb(i)) {res = Group::operation(res, dat_[i]);}return res;}public:FenwickTree() : n_{}, bitWidth_{}, a_{}, dat_{} {}FenwickTree(usize n) : n_{ n }, bitWidth_{ std::__lg(static_cast<u32>(n)) + 1 }, a_(n), dat_(n + 1, Group::identity()) {dat_.shrink_to_fit();}FenwickTree(const std::vector<Value>& a) : n_{ a.size() }, bitWidth_{ std::__lg(static_cast<u32>(a.size())) + 1 }, a_(a), dat_(a.size() + 1,Group::identity()) {dat_.shrink_to_fit();for (i32 i{} ; i < static_cast<i32>(n_) ; i++) {addDat(i, a[i]);}}// return a[i]const Value& get(usize i) const noexcept {assert(i < n_);return a_[i];}// return a[i]const Value& operator[](usize i) const noexcept {assert(i < n_);return a_[i];}usize size() const noexcept {return n_;}// a[i] <- a[i] + vvoid operation(usize i, const Value& v) {assert(i < n_);addDat(i, v);a_[i] = Group::operation(a_[i], v);}// a[i] <- vvoid set(usize i, const Value& v) {assert(i < n_);addDat(i, Group::operation(Group::inverse(a_[i]), v));a_[i] = v;}// return a[0] + a[1] + ... + a[r - 1]Value prefixProduct(usize r) const {assert(r <= n_);return product(r);}// return a[l] + a[l + 1] ... + a[r - 1]Value product(usize l, usize r) const {assert(l <= r and r <= n_);return Group::operation(Group::inverse(product(l)), product(r));}template <class Function>u32 maxRight(usize l, const Function& f) const {static_assert(std::is_convertible_v<decltype(f), std::function<bool(Value)>>, "maxRight's argument f must be function bool(T)");assert(l < n_);Value sum{ Group::inverse(product(l)) };u32 r{};for (u32 bit{ bitWidth_ } ; bit ; ) {bit--;u32 nxt{ r | (1u << bit) };if (nxt < dat_.size() and f(Group::operation(sum, dat_[nxt]))) {sum = Group::operation(sum, dat_[nxt]);r = std::move(nxt);}}assert(l <= r);return r;}template <class Function>u32 minLeft(usize r, const Function& f) const {static_assert(std::is_convertible_v<decltype(f), std::function<bool(Value)>>, "minLeft's argument f must be function bool(T)");assert(r <= n_);Value sum{ product(r) };u32 l{};for (u32 bit{ bitWidth_ } ; bit ; ) {bit--;u32 nxt{ l | (1u << bit) };if (nxt <= r and not f(Group::operation(Group::inverse(dat_[nxt]), sum))) {sum = Group::operation(Group::inverse(dat_[nxt]), sum);l = std::move(nxt);}}assert(l <= r);return l;}// debug printfriend std::ostream& operator<<(std::ostream& os, const FenwickTree& ft) {for (u32 i{} ; i <= ft.size() ; i++) {os << ft.prefixProduct(i) << (i == ft.size() ? "" : " ");}return os;}};} // namespace zawanamespace zawa {template <class T>class AdditiveGroup {public:using Element = T;static constexpr T identity() noexcept {return T{};}static constexpr T operation(const T& l, const T& r) noexcept {return l + r;}static constexpr T inverse(const T& v) noexcept {return -v;}};} // namespace zawausing namespace zawa;int main() {SetFastIO();int n, m, k; std::cin >> n >> m >> k;std::vector<int> s(k + 1);for (int i{} ; i < k + 1 ; i++) {std::cin >> s[i];s[i]--;}const long long INF{(long long)1e18};std::vector g(n, std::vector<long long>(n, INF));for (int i{} ; i < n ; i++) g[i][i] = 0;for (int _{} ; _ < m ; _++) {int u, v; std::cin >> u >> v;u--; v--;long long c; std::cin >> c;g[u][v] = std::min(g[u][v], c);g[v][u] = std::min(g[v][u], c);}for (int v{} ; v < n ; v++) {for (int i{} ; i < n ; i++) {for (int j{} ; j < n ; j++) {g[i][j] = std::min(g[i][v] + g[v][j], g[i][j]);}}}FenwickTree<AdditiveGroup<long long>> fen(k);for (int i{1} ; i < k + 1 ; i++) {fen.set(i - 1, g[s[i - 1]][s[i]]);}int q; std::cin >> q;for (int _{} ; _ < q ; _++) {int t; std::cin >> t;if (t == 1) {int x, y; std::cin >> x >> y;y--;if (x) fen.set(x - 1, g[s[x - 1]][y]);if (x + 1 < k + 1) fen.set(x, g[y][s[x + 1]]);s[x] = y;}else if (t == 2) {int x, y; std::cin >> x >> y;long long ans{fen.product(x, y)};std::cout << ans << '\n';}else {assert(!"input fail");}}}