結果

問題 No.2861 Slime Party
ユーザー square1001
提出日時 2024-07-25 20:40:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,998 ms / 4,000 ms
コード長 5,174 bytes
コンパイル時間 1,674 ms
コンパイル使用メモリ 96,344 KB
最終ジャッジ日時 2025-02-23 18:03:16
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 76
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long INF = 3LL << 59;
class query {
public:
    int t, a; long long b;
    query() : t(-1), a(-1), b(-1) {}
};
class node {
public:
    int p, l, r;
    node() : p(-1), l(-1), r(-1) {}
};
class binary_tree {
public:
    int root;
    vector<node> v;
    binary_tree(int n) : root(-1), v(vector<node>(n)) {}
};
binary_tree cartesian_tree(int N, const vector<long long>& A) {
    binary_tree T(N);
    vector<int> st;
    int pos = 0;
    for (int i = 0; i < N; i++) {
        int u = -1;
        while (!st.empty() && A[st.back()] < A[i]) {
            u = st.back();
            st.pop_back();
        }
        if (u != -1) {
            T.v[i].l = u;
            T.v[u].p = i;
        }
        if (!st.empty()) {
            T.v[i].p = st.back();
            T.v[st.back()].r = i;
        }
        st.push_back(i);
    }
    T.root = st[0];
    return T;
}
class segment_tree {
    // range add / range max
private:
    int size;
    vector<long long> v;
    vector<long long> lazy;
    void push(int k) {
        v[k] += lazy[k];
        if (k < size) {
            lazy[k * 2 + 0] += lazy[k];
            lazy[k * 2 + 1] += lazy[k];
        }
        lazy[k] = 0;
    }
public:
    segment_tree(int n) : size(1 << (n >= 2 ? 32 - __builtin_clz(n - 1) : 0)), v(size * 2), lazy(size * 2) {}
    void range_add(int l, int r, long long x) {
        auto recur = [&](auto& self, int k, int s, int t) -> void {
            if (l <= s && t <= r) {
                lazy[k] += x;
                push(k);
                return;
            }
            push(k);
            if (r <= s || t <= l) {
                return;
            }
            self(self, k * 2 + 0, s, (s + t) / 2);
            self(self, k * 2 + 1, (s + t) / 2, t);
            v[k] = max(v[k * 2 + 0], v[k * 2 + 1]);
        };
        recur(recur, 1, 0, size);
    }
    long long range_max(int l, int r) {
        auto recur = [&](auto& self, int k, int s, int t) -> long long {
            push(k);
            if (l <= s && t <= r) {
                return v[k];
            }
            if (r <= s || t <= l) {
                return -INF;
            }
            long long zl = self(self, k * 2 + 0, s, (s + t) / 2);
            long long zr = self(self, k * 2 + 1, (s + t) / 2, t);
            v[k] = max(v[k * 2 + 0], v[k * 2 + 1]);
            return max(zl, zr);
        };
        return recur(recur, 1, 0, size);
    }
};
class heavy_light {
private:
    int n;
    vector<int> par;
    vector<int> id;
    vector<int> id_vertex;
    vector<int> head;
    segment_tree seg;
public:
    heavy_light(const vector<int>& par_) : n(par_.size()), par(par_), seg(n) {
        vector<vector<int> > g(n);
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (par[i] != -1) {
                g[par[i]].push_back(i);
            } else {
                root = i;
            }
        }
        vector<int> subsize(n, 1);
        auto build_order = [&](auto& self, int v) -> void {
            for (int &i : g[v]) {
                self(self, i);
                subsize[v] += subsize[i];
                if (subsize[i] > subsize[g[v][0]]) {
                    swap(g[v][0], i);
                }
            }
        };
        build_order(build_order, root);
        int cur = 0;
        id.resize(n);
        id_vertex.resize(n);
        head.resize(n);
        auto build_tree = [&](auto& self, int v) -> void {
            id[v] = cur;
            id_vertex[cur] = v;
            cur++;
            for (int i : g[v]) {
                head[i] = (i == g[v][0] ? head[v] : i);
                self(self, i);
            }
        };
        head[root] = root;
        build_tree(build_tree, root);
    }
    void add_vertex(int v, long long x) {
        seg.range_add(id[v], id[v] + 1, x);
    }
    void add_path(int v, long long x) {
        while (v != -1) {
            seg.range_add(id[head[v]], id[v] + 1, x);
            v = par[head[v]];
        }
    }
    long long get_vertex(int v) {
        return seg.range_max(id[v], id[v] + 1);
    }
    int query(int v, long long x) {
        // first unreachable ancestor from v by only passing vertex with < x
        while (v != -1) {
            if (seg.range_max(id[head[v]], id[v] + 1) >= x) {
                break;  
            }
            v = par[head[v]];
        }
        if (v == -1) {
            return -1;
        }
        int l = id[head[v]], r = id[v] + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (seg.range_max(m, id[v] + 1) >= x) {
                l = m;
            } else {
                r = m;
            }
        }
        return id_vertex[l];
    }
};
vector<long long> solve(int N, int Q, long long L, const vector<long long>& A, const vector<long long>& X, const vector<query>& qs) {
    binary_tree T = cartesian_tree(N, A);
    vector<int> par(N);
    for (int i = 0; i < N; i++) {
        par[i] = T.v[i].p;
    }
    heavy_light hld(par);
    for (int i = 0; i < N; i++) {
        hld.add_path(i, -X[i]);
        if (i != T.root) {
            hld.add_vertex(i, A[par[i]]);
        }
    }
    vector<long long> CX = X;
    vector<long long> ans;
    for (query q : qs) {
        if (q.t == 1) {
            long long d = q.b - CX[q.a];
            CX[q.a] = q.b;
            hld.add_path(q.a, -d);
        }
        if (q.t == 2) {
            int base = (A[q.a] < A[q.a + 1] ? q.a : q.a + 1);
            if (A[base] < L) {
                int pos = hld.query(base, L);
                if (pos == -1) {
                    pos = T.root;
                }
                long long subans = hld.get_vertex(pos);
                ans.push_back(-(subans - (pos != T.root ? A[T.v[pos].p] : 0)) + L);
            } else {
                ans.push_back(L);
            }
        }
    }
    return ans;
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, Q; long long L;
    cin >> N >> Q >> L;
    vector<long long> A(N), X(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }
    vector<query> qs(Q);
    for (int i = 0; i < Q; i++) {
        cin >> qs[i].t >> qs[i].a;
        if (qs[i].t == 1) {
            cin >> qs[i].b;
        }
        qs[i].a--;
    }
    vector<long long> ans = solve(N, Q, L, A, X, qs);
    for (int i = 0; i < int(ans.size()); i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0