結果
問題 | No.2861 Slime Party |
ユーザー |
|
提出日時 | 2024-05-14 03:46:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 13,406 bytes |
コンパイル時間 | 3,043 ms |
コンパイル使用メモリ | 225,828 KB |
最終ジャッジ日時 | 2025-02-21 13:58:18 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 56 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>pair<vector<vector<int>>, int> cartesianTree(vector<T> &a){int n = a.size();vector<vector<int>> G(n);vector<int> par(n, -1), st;for(int i = 0; i < n; ++i){int prev = -1;while(!st.empty() && a[i] > a[st.back()]){prev = st.back();st.pop_back();}if(prev != -1){par[prev] = i;}if(!st.empty()){par[i] = st.back();}st.emplace_back(i);}int root = -1;for(int i = 0; i < n; ++i){if(par[i] != -1){G[par[i]].emplace_back(i);} else{root = i;}}return make_pair(G, root);}class HeavyLightDecomposition{protected:int V;vector<vector<int>> G;vector<int> stsize, parent, pathtop, depth, in, reverse_in, out;int root;private:// Subtree Sizevoid buildStsize(int curr, int prev){stsize[curr] = 1, parent[curr] = prev;for(int &v : G[curr]){if(v == prev){if(v == G[curr].back()) break;else swap(v, G[curr].back());}buildStsize(v, curr);stsize[curr] += stsize[v];if(stsize[v] > stsize[G[curr][0]]){swap(v, G[curr][0]);}}}void buildPath(int curr, int prev, int &t){in[curr] = t++;reverse_in[in[curr]] = curr;for(int v : G[curr]){if(v == prev) continue;if(v == G[curr][0]){pathtop[v] = pathtop[curr];} else{pathtop[v] = v;}depth[v] = depth[curr] + 1;buildPath(v, curr, t);}out[curr] = t;}public:HeavyLightDecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1),pathtop(V, -1), depth(V, 0), in(V, -1), reverse_in(V, -1), out(V, -1){}void add_edge(int u, int v){G[u].push_back(v);G[v].push_back(u);}void build(int _root = 0){root = _root;int t = 0;buildStsize(root, -1);pathtop[root] = root;buildPath(root, -1, t);}inline int get(int a){return in[a];}int la(int a, int k) {while(true){int u = pathtop[a];if(in[a] - k >= in[u]) return reverse_in[in[a] - k];k -= in[a] - in[u] + 1;a = parent[u];}}int lca(int a, int b){int pa = pathtop[a], pb = pathtop[b];while(pathtop[a] != pathtop[b]){if(in[pa] > in[pb]){a = parent[pa], pa = pathtop[a];} else{b = parent[pb], pb = pathtop[b];}}if(in[a] > in[b]) swap(a, b);return a;}int dist(int a, int b){ return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }int jump(int from, int to, int k) {if(!k) return from;int l = lca(from, to);int d = dist(from, to);if(d < k) return -1;if(depth[from] - depth[l] >= k) return la(from, k);k -= depth[from] - depth[l];return la(to, depth[to] - depth[l] - k);}void subtree_query(int a, const function<void(int, int)> &func){func(in[a], out[a]);}void path_query(int a, int b, const function<void(int, int)> &func, bool include_root = true, bool reverse_path = false){vector<pair<int, int>> path;int pa = pathtop[a], pb = pathtop[b];while(pathtop[a] != pathtop[b]){if(in[pa] > in[pb]){path.emplace_back(in[pa], in[a] + 1);a = parent[pa], pa = pathtop[a];} else{path.emplace_back(in[pb], in[b] + 1);b = parent[pb], pb = pathtop[b];}}if(in[a] > in[b]) swap(a, b);if(include_root) path.emplace_back(in[a], in[b] + 1);else path.emplace_back(in[a] + 1, in[b] + 1);if(!reverse_path) reverse(path.begin(), path.end());else for(auto &p : path) p = make_pair(V - p.second, V - p.first);for(auto [u, v] : path){func(u, v);}}void path_noncommutative_query(int a, int b, const function<void(int, int)> &func, const function<void(int, int)> &func2){int l = lca(a, b);path_query(a, l, func2, false, true);path_query(l, b, func, true, false);}};template <typename X>struct SegTree{using FX = function<X(X, X)>; // X•X -> X となる関数の型int n;FX fx;const X ex;vector<X> dat;SegTree(int n_, const FX &fx_, const X &ex_) : n(), fx(fx_), ex(ex_){int x = 1;while(n_ > x){x *= 2;}n = x;dat.assign(n * 2, ex);}X get(int i) const {return dat[i + n];}void set(int i, const X &x){ dat[i + n] = x; }void build(){for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);}void update(int i, const X &x){i += n;dat[i] = x;while(i > 0){i >>= 1; // parentdat[i] = fx(dat[i * 2], dat[i * 2 + 1]);}}X query(int a, int b){X vl = ex;X vr = ex;int l = a + n;int r = b + n;while(l < r){if(l & 1) vl = fx(vl, dat[l++]);if(r & 1) vr = fx(dat[--r], vr);l >>= 1;r >>= 1;}return fx(vl, vr);}X operator [](int i) const {return dat[i + n];}};template <class S,S(*op)(S, S),S(*e)(),class F,S(*mapping)(F, S),F(*composition)(F, F),F(*id)()>struct LazySegTree{private:int _n, size, log;vector<S> d;vector<F> lz;void pull(int k){ d[k] = op(d[2 * k], d[2 * k + 1]); }void all_apply(int k, F f){d[k] = mapping(f, d[k]);if(k < size) lz[k] = composition(f, lz[k]);}void push(int k){all_apply(2 * k, lz[k]);all_apply(2 * k + 1, lz[k]);lz[k] = id();}public:LazySegTree() : LazySegTree(0){}LazySegTree(int n) : LazySegTree(vector<S>(n, e())){}LazySegTree(const vector<S> &v) : _n(int(v.size())){log = 0;size = 1;while(size < _n) size <<= 1, log++;d = vector<S>(2 * size, e());lz = vector<F>(size, id());for(int i = 0; i < _n; i++) d[size + i] = v[i];for(int i = size - 1; i >= 1; i--){pull(i);}}void update(int p, S x){assert(0 <= p && p < _n);p += size;for(int i = log; i >= 1; i--) push(p >> i);d[p] = x;for(int i = 1; i <= log; i++) pull(p >> i);}S get(int p){assert(0 <= p && p < _n);p += size;for(int i = log; i >= 1; i--) push(p >> i);return d[p];}S query(int l, int r){assert(0 <= l && l <= r && r <= _n);if(l == r) return e();l += size;r += size;for(int i = log; i >= 1; i--){if(((l >> i) << i) != l) push(l >> i);if(((r >> i) << i) != r) push(r >> i);}S sml = e(), smr = e();while(l < r){if(l & 1) sml = op(sml, d[l++]);if(r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_query(){ return d[1]; }void apply(int p, F f){assert(0 <= p && p < _n);p += size;for(int i = log; i >= 1; i--) push(p >> i);d[p] = mapping(f, d[p]);for(int i = 1; i <= log; i++) pull(p >> i);}void apply(int l, int r, F f){assert(0 <= l && l <= r && r <= _n);if(l == r) return;l += size;r += size;for(int i = log; i >= 1; i--){if(((l >> i) << i) != l) push(l >> i);if(((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while(l < r){if(l & 1) all_apply(l++, f);if(r & 1) all_apply(--r, f);l >>= 1;r >>= 1;}l = l2;r = r2;}for(int i = 1; i <= log; i++){if(((l >> i) << i) != l) pull(l >> i);if(((r >> i) << i) != r) pull((r - 1) >> i);}}template <bool (*g)(S)>int max_right(int l){return max_right(l, [](S x){ return g(x); });}template <class G>int max_right(int l, G g){assert(0 <= l && l <= _n);assert(g(e()));if(l == _n) return _n;l += size;for(int i = log; i >= 1; i--) push(l >> i);S sm = e();do{while(l % 2 == 0) l >>= 1;if(!g(op(sm, d[l]))){while(l < size){push(l);l = (2 * l);if(g(op(sm, d[l]))){sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while((l & -l) != l);return _n;}template <bool (*g)(S)>int min_left(int r){return min_left(r, [](S x){ return g(x); });}template <class G>int min_left(int r, G g){assert(0 <= r && r <= _n);assert(g(e()));if(r == 0) return 0;r += size;for(int i = log; i >= 1; i--) push((r - 1) >> i);S sm = e();do{r--;while(r > 1 && (r % 2)) r >>= 1;if(!g(op(d[r], sm))){while(r < size){push(r);r = (2 * r + 1);if(g(op(d[r], sm))){sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while((r & -r) != r);return 0;}};const long long INF = 1LL << 60;using S = long long;using F = long long;S op(S l, S r){return min(l, r);}S e(){return INF;}S mapping(F f, S x){return x + f;}F composition(F f, F g){return f + g;}F id(){return 0LL;}bool f(S x){return x > 0;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);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];}auto [G, root] = cartesianTree(a);HeavyLightDecomposition hld(n);for(int i = 0; i < n; i++){for(int j : G[i]){hld.add_edge(i, j);}}hld.build(root);SegTree<long long> segx(n, [](long long a, long long b){ return a + b; }, 0LL);for(int i = 0; i < n; i++){segx.update(hld.get(i), x[i]);}LazySegTree<S, op, e, F, mapping, composition, id> seg(n);vector<int> pidx(n);{long long sum = 0;auto query_sum = [&](int l, int r){sum += segx.query(l, r);};for(int i = 0; i < n; i++){for(int j : G[i]){int idx = max(hld.get(i), hld.get(j));sum = 0;pidx[j] = i;hld.subtree_query(j, query_sum);seg.update(idx, sum + L - a[i]);}}}while(q--){int t; cin >> t;if(t == 1){int a;long long b;cin >> a >> b;a--;long long d = b - segx[hld.get(a)];segx.update(hld.get(a), b);auto add_query = [&](int l, int r){seg.apply(l, r, d);};hld.path_query(root, a, add_query, false);}else{int c;cin >> c;c--;vector<pair<int, int>> path;auto query_min = [&](int l, int r){if(l == r){return;}path.emplace_back(l, r);};if(L <= min(a[c], a[c + 1])){cout << L << "\n";continue;}int s = c + 1;if(a[c] < a[c + 1]) s = c;hld.path_query(s, root, query_min, false);reverse(path.begin(), path.end());int curr = -1;for(auto [l, r] : path){if(seg.query(l, r) > 0){curr = l;}else{int x = seg.min_left<f>(r);if(l <= x && x < r){curr = x;}break;}}long long ans = L;auto query_sum = [&](int l, int r){ans += segx.query(l, r);};if(curr == -1){hld.subtree_query(s, query_sum);}else{hld.subtree_query(pidx[curr], query_sum);}cout << ans << "\n";}}}