test/aoj/DSL_2_H.test.cpp

• View this file on GitHub
• Last update: 2025-07-07 14:21:50+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_H

Depends on

• Ordered Map and Range Query (data_structure/ordered_map_and_range_query.hpp)

Required by

• test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_H"

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

#include "../../data_structure/ordered_map_and_range_query.hpp"

using ll = long long;
constexpr ll INF64 = 1LL << 60;

using K = ll;
bool compare(K a, K b) { return a < b; }

using S = ll;
S op(S a, S b) { return min(a, b); }
S e() { return INF64; }

using F = ll;
S mapping(F f, S a) { return a + f; }
F composition(F f, F g) { return f + g; }
F id() { return 0LL; }

int main() {
    int N, Q;
    cin >> N >> Q;

    OrderedMapAndRangeQuery<K, compare, S, op, e, F, mapping, composition, id> rbst;
    rbst.insert(-INF64, 0LL);
    rbst.insert(INF64, 0LL);

    for (; Q--;) {
        int t;
        cin >> t;
        if (t == 0) {
            int l, r;
            cin >> l >> r;
            r++;
            ll x;
            cin >> x;
            if (!rbst.count(l)) {
                rbst.insert(l, rbst.get(rbst.lower_bound(l) - 1).second);
            }
            if (!rbst.count(r)) {
                rbst.insert(r, rbst.get(rbst.lower_bound(r) - 1).second);
            }
            rbst.apply(rbst.lower_bound(l), rbst.lower_bound(r), x);
        } else {
            int l, r;
            cin >> l >> r;
            r++;
            S ans = rbst.prod(rbst.upper_bound(l) - 1, rbst.lower_bound(r));
            if (ans == e())
                cout << 0LL << endl;
            else
                cout << ans << endl;
        }
    }
}

#line 1 "test/aoj/DSL_2_H.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_H"

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

#line 2 "data_structure/ordered_map_and_range_query.hpp"

/**
 * @brief Ordered Map and Range Query
 */
template <class K,
          bool (*compare)(K, K),
          class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
class OrderedMapAndRangeQuery {
  private:
    class Node {
      public:
        int size;
        Node *left, *right;
        K key;
        S value, sum;
        F lazy;

        Node(K _key) : Node(_key, e()) {}
        Node(K _key, S _value) : Node(_key, _value, id()) {}
        Node(K _key, S _value, F _lazy)
            : size(1),
              left(nullptr),
              right(nullptr),
              key(_key),
              value(_value),
              sum(_value),
              lazy(_lazy) {}
    };

    Node* root;

    int size(Node* node) {
        if (node == nullptr)
            return 0;
        return node->size;
    }

    S value(Node* node) {
        if (node == nullptr)
            return e();
        return node->value;
    }

    S sum(Node* node) {
        if (node == nullptr)
            return e();
        return node->sum;
    }

    F lazy(Node* node) {
        if (node == nullptr)
            return id();
        return node->lazy;
    }

    void propagate(Node* node, F f) {
        if (node == nullptr)
            return;
        node->value = mapping(f, value(node));
        node->sum = mapping(f, sum(node));
        node->lazy = composition(f, lazy(node));
    }

    void push(Node* node) {
        if (node == nullptr)
            return;
        if (lazy(node) != id()) {
            propagate(node->left, lazy(node));
            propagate(node->right, lazy(node));
            node->lazy = id();
        }
    }

    void update(Node* node) {
        push(node);
        if (node == nullptr)
            return;
        node->sum = op(op(sum(node->left), value(node)), sum(node->right));
        node->size = size(node->left) + 1 + size(node->right);
    }

    int lower_bound(Node* node, K k) {
        push(node);
        if (node == nullptr)
            return 0;
        if (compare(node->key, k)) {
            return size(node->left) + lower_bound(node->right, k) + 1;
        }
        return lower_bound(node->left, k);
    }

    int upper_bound(Node* node, K k) {
        push(node);
        if (node == nullptr)
            return 0;
        if (compare(k, node->key)) {
            return upper_bound(node->left, k);
        }
        return size(node->left) + upper_bound(node->right, k) + 1;
    }

    pair<K, S> get(Node* node, int i) {
        push(node);
        assert(node != nullptr);
        if (i == size(node->left))
            return make_pair(node->key, value(node));
        if (i < size(node->left))
            return get(node->left, i);
        return get(node->right, i - size(node->left) - 1);
    }

    unsigned xor128() {
        static unsigned x = 123'456'789, y = 362'436'069, z = 521'288'629, w = 88'675'123;
        unsigned t = x ^ (x << 11);
        x = y, y = z, z = w, w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return w;
    }

    Node* merge(Node* l, Node* r) {
        push(l), push(r);
        if (l == nullptr)
            return r;
        if (r == nullptr)
            return l;
        if (xor128() % (size(l) + size(r)) < unsigned(size(l))) {
            l->right = merge(l->right, r);
            update(l);
            return l;
        }
        r->left = merge(l, r->left);
        update(r);
        return r;
    }

    pair<Node*, Node*> split(Node* node, int i) {
        push(node);
        if (node == nullptr)
            return make_pair(nullptr, nullptr);
        if (i <= size(node->left)) {
            pair<Node*, Node*> s = split(node->left, i);
            node->left = s.second;
            update(node);
            return make_pair(s.first, node);
        }
        pair<Node*, Node*> s = split(node->right, i - size(node->left) - 1);
        node->right = s.first;
        update(node);
        return make_pair(node, s.second);
    }

  public:
    OrderedMapAndRangeQuery() : root(nullptr) {}

    int size() { return size(root); }

    int lower_bound(K k) { return lower_bound(root, k); }

    int upper_bound(K k) { return upper_bound(root, k); }

    bool count(K k) { return upper_bound(k) != lower_bound(k); }

    pair<K, S> get(int i) { return get(root, i); }

    void erase(K k) {
        if (!count(k))
            return;
        pair<Node*, Node*> s = split(root, lower_bound(k));
        pair<Node*, Node*> t = split(s.second, 1);
        delete t.first;
        root = merge(s.first, t.second);
    }

    void insert(K k, S v) {
        if (count(k))
            erase(k);
        pair<Node*, Node*> s = split(root, lower_bound(k));
        root = merge(merge(s.first, new Node(k, v)), s.second);
    }

    S prod(int a, int b) {
        pair<Node*, Node*> s = split(root, a);
        pair<Node*, Node*> t = split(s.second, b - a);
        S res = sum(t.first);
        root = merge(s.first, merge(t.first, t.second));
        return res;
    }

    void apply(int a, int b, F f) {
        pair<Node*, Node*> s = split(root, a);
        pair<Node*, Node*> t = split(s.second, b - a);
        propagate(t.first, f);
        root = merge(s.first, merge(t.first, t.second));
    }
};
#line 8 "test/aoj/DSL_2_H.test.cpp"

using ll = long long;
constexpr ll INF64 = 1LL << 60;

using K = ll;
bool compare(K a, K b) { return a < b; }

using S = ll;
S op(S a, S b) { return min(a, b); }
S e() { return INF64; }

using F = ll;
S mapping(F f, S a) { return a + f; }
F composition(F f, F g) { return f + g; }
F id() { return 0LL; }

int main() {
    int N, Q;
    cin >> N >> Q;

    OrderedMapAndRangeQuery<K, compare, S, op, e, F, mapping, composition, id> rbst;
    rbst.insert(-INF64, 0LL);
    rbst.insert(INF64, 0LL);

    for (; Q--;) {
        int t;
        cin >> t;
        if (t == 0) {
            int l, r;
            cin >> l >> r;
            r++;
            ll x;
            cin >> x;
            if (!rbst.count(l)) {
                rbst.insert(l, rbst.get(rbst.lower_bound(l) - 1).second);
            }
            if (!rbst.count(r)) {
                rbst.insert(r, rbst.get(rbst.lower_bound(r) - 1).second);
            }
            rbst.apply(rbst.lower_bound(l), rbst.lower_bound(r), x);
        } else {
            int l, r;
            cin >> l >> r;
            r++;
            S ans = rbst.prod(rbst.upper_bound(l) - 1, rbst.lower_bound(r));
            if (ans == e())
                cout << 0LL << endl;
            else
                cout << ans << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	02_corner_00.in	AC	4 ms	3 MB
g++	02_corner_01.in	AC	4 ms	3 MB
g++	02_corner_02.in	AC	4 ms	3 MB
g++	03_rand_00.in	AC	4 ms	4 MB
g++	03_rand_01.in	AC	4 ms	3 MB
g++	03_rand_02.in	AC	4 ms	4 MB
g++	03_rand_03.in	AC	6 ms	4 MB
g++	03_rand_04.in	AC	7 ms	3 MB
g++	03_rand_05.in	AC	22 ms	4 MB
g++	03_rand_06.in	AC	21 ms	4 MB
g++	03_rand_07.in	AC	24 ms	3 MB
g++	04_all_00.in	AC	11 ms	4 MB
g++	04_all_01.in	AC	12 ms	4 MB
g++	05_large_00.in	AC	33 ms	4 MB
g++	05_large_01.in	AC	34 ms	4 MB
g++	05_large_02.in	AC	50 ms	4 MB
g++	05_large_03.in	AC	49 ms	4 MB
g++	06_maximum_00.in	AC	389 ms	8 MB
g++	06_maximum_01.in	AC	365 ms	8 MB
g++	06_maximum_02.in	AC	443 ms	7 MB
g++	06_maximum_03.in	AC	183 ms	4 MB
g++	07_critical_00.in	AC	119 ms	3 MB
g++	07_critical_01.in	AC	152 ms	4 MB
g++	07_critical_02.in	AC	79 ms	3 MB
g++	08_critical_03.in	AC	208 ms	3 MB
g++	08_extreme_00.in	AC	68 ms	4 MB
g++	08_extreme_01.in	AC	74 ms	4 MB
g++	08_extreme_02.in	AC	76 ms	4 MB
g++	08_extreme_03.in	AC	75 ms	3 MB

Back to top page