Codeforces Testing Round 1 C. Circular RMQ

Codeforces Testing Round 1 C. Circular RMQ

Problem - C - Codeforces

感想

区間加算、区間最小値を処理する遅延セグメント木をライブラリに追加したので、貼るだけの問題で試しておいた。

解法

貼るだけ。ただし入力が親切じゃないので、getlineで入力をとって' 'でパースしてどちらのクエリなのかをみないといけない。

実装

#include "bits/stdc++.h"
using namespace std;

static const int INF = 0x3f3f3f3f;

//区間加算、区間最小値
template<typename Type>
struct LazySegmentTree {
        vector<Type> data, lazy;
        int n;
        LazySegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                data.resize(2 * n - 1, INF);
                lazy.resize(2 * n - 1, 0);
        }
        void init(int k, Type p) {
                k += n - 1;
                data[k] = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        void add(int a, int b, int x) { return add(a, b, x, 0, 0, n); } //[a, b)
        void add(int a, int b, int x, int k, int l, int r) {
                if (r <= a || b <= l) return;
                if (a <= l && r <= b) {
                        lazy[k] += x;
                        return;
                }
                int m = (l + r) / 2;
                add(a, b, x, k * 2 + 1, l, m);
                add(a, b, x, k * 2 + 2, m, r);
                data[k] = min(data[k * 2 + 1] + lazy[k * 2 + 1], data[k * 2 + 2] + lazy[k * 2 + 2]);
        }
        Type getmin(int a, int b) { return getmin(a, b, 0, 0, n); } //[a, b)
        Type getmin(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return INF;
                if (a <= l && r <= b) return data[k] + lazy[k];
                int m = (l + r) / 2;
                Type left = getmin(a, b, k * 2 + 1, l, m);
                Type right = getmin(a, b, k * 2 + 2, m, r);
                return min(left, right) + lazy[k];
        }
};

void solve() {
        int n;
        cin >> n;
        LazySegmentTree<int> st(n);
        for (int i = 0; i < n; i ++) { 
                int a;
                cin >> a;
                st.init(i, a);
        }
        int q;
        cin >> q;
        cin.ignore();
        while (q --) {
                string s;
                getline(cin, s);
                int cnt = 0;
                for (int i = 0; i < s.size(); i ++) cnt += s[i] == ' ';
                if (cnt == 1) {
                        int sp;
                        for (int i = 0; i < s.size(); i ++) {
                                if (s[i] == ' ') { 
                                        sp = i;
                                        break;
                                }
                        }
                        int l = stoi(s.substr(0, sp));
                        int r = stoi(s.substr(sp, s.size()));
                        if (l <= r) cout << st.getmin(l, r + 1) << endl;
                        else cout << min(st.getmin(0, r + 1), st.getmin(l, n)) << endl;
                } else {
                        int sp1 = 0, sp2;
                        for (int i = 0; i < s.size(); i ++) {
                                if (s[i] == ' ' && !sp1) {
                                        sp1 = i;
                                        continue;
                                }
                                if (s[i] == ' ' && sp1) {
                                        sp2 = i;
                                }
                        }
                        int l = stoi(s.substr(0, sp1));
                        int r = stoi(s.substr(sp1, sp2));
                        int v = stoi(s.substr(sp2, s.size()));
                        if (l <= r) { 
                                st.add(l, r + 1, v);
                        } else {
                                st.add(0, r + 1, v);
                                st.add(l, n, v);
                        }
                }
        }
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}