cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc384_g.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/DataStructure/Mo/Mo.hpp"
#include "../../Src/DataStructure/FenwickTree/FenwickTree.hpp"
#include "../../Src/Sequence/CompressedSequence.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"

/*
 * AtCoder Beginner Contest 384 G - Abs Sum
 * https://atcoder.jp/contests/abc384/submissions/67045346
 */

using namespace zawa;

int N, K, A[100000], B[100000];
struct query {
    usize l, r;
};
query Q[10000];

void solve() {
    CompressedSequence a{std::vector(A, A + N)}, b{std::vector(B, B + N)};
    FenwickTree<AdditiveGroup<int>> ca(a.size()), cb(b.size());
    FenwickTree<AdditiveGroup<long long>> sa(a.size()), sb(b.size());
    long long ans = 0;
    auto addA = [&](int i) -> void {
        // std::cout << "addA " << i << std::endl;
        int sm = cb.prefixProduct(b[A[i]]); 
        ans += (long long)A[i] * sm;
        ans += (long long)-A[i] * (cb.prefixProduct(b.size()) - sm);
        ans += sb.prefixProduct(b.size()) - 2LL * sb.prefixProduct(b[A[i]]);
        sa.operation(a.map(i), A[i]);
        ca.operation(a.map(i), 1);
    };
    auto addB = [&](int i) -> void {
        // std::cout << "addB " << i << std::endl;
        int sm = ca.prefixProduct(a[B[i]]);
        ans += (long long)B[i] * sm;
        ans += (long long)-B[i] * (ca.prefixProduct(a.size()) - sm);
        ans += sa.prefixProduct(a.size()) - 2LL * sa.prefixProduct(a[B[i]]);
        sb.operation(b.map(i), B[i]);
        cb.operation(b.map(i), 1);
    };
    auto delA = [&](int i) -> void {
        // std::cout << "delA " << i << std::endl;
        int sm = cb.prefixProduct(b[A[i]]); 
        ans -= (long long)A[i] * sm;
        ans -= (long long)-A[i] * (cb.prefixProduct(b.size()) - sm);
        ans -= sb.prefixProduct(b.size()) - 2LL * sb.prefixProduct(b[A[i]]);
        sa.operation(a.map(i), -A[i]);
        ca.operation(a.map(i), -1);
    };
    auto delB = [&](int i) -> void {
        // std::cout << "delB " << i << std::endl;
        int sm = ca.prefixProduct(a[B[i]]);
        ans -= (long long)B[i] * sm;
        ans -= (long long)-B[i] * (ca.prefixProduct(a.size()) - sm);
        ans -= sa.prefixProduct(a.size()) - 2LL * sa.prefixProduct(a[B[i]]);
        sb.operation(b.map(i), -B[i]);
        cb.operation(b.map(i), -1);
    };
    auto eval = [&](int) -> long long {
        // std::cout << "eval " << i << std::endl;
        return ans;
    };
    for (long long a : Mo(std::vector<query>(Q, Q + K), addA, addB, delA, delB, eval)) {
        std::cout << -a << '\n';
    }
}

int main() {
#ifdef ATCODER
    SetFastIO();
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    for (int i = 0 ; i < N ; i++) std::cin >> B[i];
    std::cin >> K;
    for (int i = 0 ; i < K ; i++) {
        std::cin >> Q[i].l >> Q[i].r;
    }
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc384_g.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

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 zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/DataStructure/Mo/Mo.hpp"

#line 4 "Src/DataStructure/Mo/Mo.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>
#include <type_traits>

namespace zawa {

namespace internal {

// reference: https://codeforces.com/blog/entry/61203?#comment-1064868
u64 hilbertOrder(u64 x, u64 y, usize dim) {
    const u64 max{(1ull << dim) - 1};
    assert(x <= max);
    assert(y <= max);
    u64 res{};
    for (u64 s{1ull << (dim - 1)} ; s ; s >>= 1) {
        bool rx{static_cast<bool>(x & s)}, ry{static_cast<bool>(y & s)};
        res = (res << 2) | (rx ? ry ? 2 : 1 : ry ? 3 : 0);
        if (!rx) {
            if (ry) x ^= max, y ^= max;
            std::swap(x, y);
        }
    }
    return res;
}

} // namespace internal

template <class T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(std::vector<T> qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {
    usize log{};
    for (const T& lr : qs) log = std::max<usize>(log, std::bit_width(lr.r));
    std::vector<std::pair<T, usize>> ord(qs.size());
    std::vector<u64> h(qs.size());
    for (usize i{} ; i < qs.size() ; i++) {
        ord[i] = {qs[i], i};
        h[i] = internal::hilbertOrder(qs[i].l, qs[i].r, log);
    }
    std::sort(ord.begin(), ord.end(), [&](const auto& L, const auto& R) -> bool {
            return h[L.second] < h[R.second];
            });
    std::vector<typename std::invoke_result_t<Eval, usize>> res(qs.size());
    usize L{}, R{};
    for (const auto& [lr, id] : ord) {
        while (R < lr.r) addR(R++);
        while (L > lr.l) addL(--L);
        while (R > lr.r) delR(--R);
        while (L < lr.l) delL(L++);
        res[id] = eval(id);
    }
    if (reset) while (R > L) delR(--R);
    return res;
}

} // namespace zawa
#line 2 "Src/DataStructure/FenwickTree/FenwickTree.hpp"

#line 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/FenwickTree/FenwickTree.hpp"

#line 8 "Src/DataStructure/FenwickTree/FenwickTree.hpp"
#include <ostream>
#include <functional>
#line 11 "Src/DataStructure/FenwickTree/FenwickTree.hpp"

namespace zawa {

template <concepts::Group Group>
class FenwickTree {
public:

    using VM = Group;
    
    using V = typename VM::Element;

    FenwickTree() = default;

    explicit FenwickTree(usize n) : m_n{ n }, m_bitwidth{ std::__lg(n) + 1 }, m_a(n), m_dat(n + 1, VM::identity()) {
        m_dat.shrink_to_fit();
        m_a.shrink_to_fit();
    }

    explicit FenwickTree(const std::vector<V>& a) : m_n{ a.size() }, m_bitwidth{ std::__lg(a.size()) + 1 }, m_a(a), m_dat(a.size() + 1, VM::identity()) {
        m_dat.shrink_to_fit();  
        m_a.shrink_to_fit();
        for (i32 i{} ; i < static_cast<i32>(m_n) ; i++) {
            addDat(i, a[i]);
        }
    }

    inline usize size() const noexcept {
        return m_n;
    }

    // return a[i]
    const V& get(usize i) const noexcept {
        assert(i < size());
        return m_a[i];
    }

    // return a[i]
    const V& operator[](usize i) const noexcept {
        assert(i < size());
        return m_a[i];
    }

    // a[i] <- a[i] + v
    void operation(usize i, const V& v) {
        assert(i < size());
        addDat(i, v);
        m_a[i] = VM::operation(m_a[i], v);
    }

    // a[i] <- v
    void assign(usize i, const V& v) {
        assert(i < size());
        addDat(i, VM::operation(VM::inverse(m_a[i]), v));
        m_a[i] = v;
    }

    // return a[0] + a[1] + ... + a[r - 1]
    V prefixProduct(usize r) const {
        assert(r <= size());
        return product(r);
    }

    // return a[l] + a[l + 1] ... + a[r - 1]
    V product(usize l, usize r) const {
        assert(l <= r and r <= size());
        return VM::operation(VM::inverse(product(l)), product(r));
    }

    template <class Function>
    usize maxRight(usize l, const Function& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "maxRight's argument f must be function bool(T)");
        assert(l < size());
        V sum{ VM::inverse(product(l)) }; 
        usize r{};
        for (usize bit{ m_bitwidth } ; bit ; ) {
            bit--;
            usize nxt{ r | (1u << bit) };
            if (nxt < m_dat.size() and f(VM::operation(sum, m_dat[nxt]))) {
                sum = VM::operation(sum, m_dat[nxt]);
                r = std::move(nxt);
            }
        }
        assert(l <= r);
        return r;
    }

    template <class Function>
    usize minLeft(usize r, const Function& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "minLeft's argument f must be function bool(T)");
        assert(r <= size());
        V sum{ product(r) };
        usize l{};
        for (usize bit{ m_bitwidth } ; bit ; ) {
            bit--;
            usize nxt{ l | (1u << bit) };
            if (nxt <= r and not f(VM::operation(VM::inverse(m_dat[nxt]), sum))) {
                sum = VM::operation(VM::inverse(m_dat[nxt]), sum);
                l = std::move(nxt);
            }
        }
        assert(l <= r);
        return l;
    }

    // debug print
    friend std::ostream& operator<<(std::ostream& os, const FenwickTree& ft) {
        for (usize i{} ; i <= ft.size() ; i++) {
            os << ft.prefixProduct(i) << (i == ft.size() ? "" : " ");
        }
        return os;
    }

private:

    usize m_n{};

    usize m_bitwidth{};

    std::vector<V> m_a, m_dat;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }
    
    // a[i] <- a[i] + v
    void addDat(i32 i, const V& v) {
        assert(0 <= i and i < static_cast<i32>(m_n));
        for ( i++ ; i < static_cast<i32>(m_dat.size()) ; i += lsb(i)) {
            m_dat[i] = VM::operation(m_dat[i], v);
        }
    }

    // return a[0] + a[1] + .. + a[i - 1]
    V product(i32 i) const {
        assert(0 <= i and i <= static_cast<i32>(m_n));
        V res{ VM::identity() };
        for ( ; i > 0 ; i -= lsb(i)) {
            res = VM::operation(res, m_dat[i]);
        }
        return res;
    }

};

} // namespace zawa
#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 4 "Src/Sequence/CompressedSequence.hpp"

#line 8 "Src/Sequence/CompressedSequence.hpp"
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace 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 zawa
#line 8 "Test/AtCoder/abc384_g.test.cpp"

/*
 * AtCoder Beginner Contest 384 G - Abs Sum
 * https://atcoder.jp/contests/abc384/submissions/67045346
 */

using namespace zawa;

int N, K, A[100000], B[100000];
struct query {
    usize l, r;
};
query Q[10000];

void solve() {
    CompressedSequence a{std::vector(A, A + N)}, b{std::vector(B, B + N)};
    FenwickTree<AdditiveGroup<int>> ca(a.size()), cb(b.size());
    FenwickTree<AdditiveGroup<long long>> sa(a.size()), sb(b.size());
    long long ans = 0;
    auto addA = [&](int i) -> void {
        // std::cout << "addA " << i << std::endl;
        int sm = cb.prefixProduct(b[A[i]]); 
        ans += (long long)A[i] * sm;
        ans += (long long)-A[i] * (cb.prefixProduct(b.size()) - sm);
        ans += sb.prefixProduct(b.size()) - 2LL * sb.prefixProduct(b[A[i]]);
        sa.operation(a.map(i), A[i]);
        ca.operation(a.map(i), 1);
    };
    auto addB = [&](int i) -> void {
        // std::cout << "addB " << i << std::endl;
        int sm = ca.prefixProduct(a[B[i]]);
        ans += (long long)B[i] * sm;
        ans += (long long)-B[i] * (ca.prefixProduct(a.size()) - sm);
        ans += sa.prefixProduct(a.size()) - 2LL * sa.prefixProduct(a[B[i]]);
        sb.operation(b.map(i), B[i]);
        cb.operation(b.map(i), 1);
    };
    auto delA = [&](int i) -> void {
        // std::cout << "delA " << i << std::endl;
        int sm = cb.prefixProduct(b[A[i]]); 
        ans -= (long long)A[i] * sm;
        ans -= (long long)-A[i] * (cb.prefixProduct(b.size()) - sm);
        ans -= sb.prefixProduct(b.size()) - 2LL * sb.prefixProduct(b[A[i]]);
        sa.operation(a.map(i), -A[i]);
        ca.operation(a.map(i), -1);
    };
    auto delB = [&](int i) -> void {
        // std::cout << "delB " << i << std::endl;
        int sm = ca.prefixProduct(a[B[i]]);
        ans -= (long long)B[i] * sm;
        ans -= (long long)-B[i] * (ca.prefixProduct(a.size()) - sm);
        ans -= sa.prefixProduct(a.size()) - 2LL * sa.prefixProduct(a[B[i]]);
        sb.operation(b.map(i), -B[i]);
        cb.operation(b.map(i), -1);
    };
    auto eval = [&](int) -> long long {
        // std::cout << "eval " << i << std::endl;
        return ans;
    };
    for (long long a : Mo(std::vector<query>(Q, Q + K), addA, addB, delA, delB, eval)) {
        std::cout << -a << '\n';
    }
}

int main() {
#ifdef ATCODER
    SetFastIO();
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    for (int i = 0 ; i < N ; i++) std::cin >> B[i];
    std::cin >> K;
    for (int i = 0 ; i < K ; i++) {
        std::cin >> Q[i].l >> Q[i].r;
    }
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page