#1196729 (C++23) No.2861 Slime Party

• 問題: No.2861 Slime Party
• ユーザー: noya2
• 提出日時: 2026-11-03 18:12:25
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 514 ms / 4,000 ms
• コード長: 8,648 bytes
• コンパイル時間: 7,185 ms
• コンパイル使用メモリ: 365,892 KB
• 実行使用メモリ: 75,496 KB
• 最終ジャッジ日時: 2026-11-03 18:13:26
• 合計ジャッジ時間: 50,319 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 78

ソースコード

#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    rep(i, 0, a.size()) os << (i ? " " : "") << a[i];
    return os;
}

void dump(auto ...vs){
    ((cerr << vs << ' '), ...) << endl;
}

// no max_right, min_left ... hash: c3a262
template<class S, auto op, auto e, class F, auto mapp, auto comp, auto id> struct lazyseg {
  int n, sz, lg;
  vector<S> d;
  vector<F> lz;
  void upd(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
  void all_apply(int k, F f) {
    d[k] = mapp(f, d[k]);
    if(k < sz) lz[k] = comp(f, lz[k]);
    // if(d[k].fail) push(k), upd(k);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = id();
  }
  bool tail(int p, int i) { return ((p >> i) << i) != p; }
  lazyseg(int _n = 0) : lazyseg(vector<S>(_n, e())) {}
  lazyseg(vector<S> v) : n(v.size()) {
    sz = bit_ceil<uint32_t>(n);
    lg = countr_zero<uint32_t>(sz);
    d.assign(2 * sz, e());
    lz.assign(sz, id());
    rep(i, 0, n) d[sz + i] = v[i];
    for(int i = sz - 1; i >= 1; i--) upd(i);
  }
  S prod(int l, int r) {
    if(l == r) return e();
    l += sz, r += sz;
    for(int i = lg; i >= 1; i--) {
      if(tail(l, i)) push(l >> i);
      if(tail(r, i)) 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);
  }
  void set(int p, S x) {
    p += sz;
    for(int i = lg; i >= 1; i--) push(p >> i);
    d[p] = x;
    for(int i = 1; i <= lg; i++) upd(p >> i);
  }
  S get(int p) {
    p += sz;
    for(int i = lg; i >= 1; i--) push(p >> i);
    return d[p];
  }
  void apply(int l, int r, F f) {
    if(l == r) return;
    l += sz, r += sz;
    for(int i = lg; i >= 1; i--) {
      if(tail(l, i)) push(l >> i);
      if(tail(r, i)) 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 <= lg; i++) {
      if(tail(l, i)) upd(l >> i);
      if(tail(r, i)) upd((r - 1) >> i);
    }
  }
  int max_right(int l, auto g) {
    if(l == n) return n;
    l += sz;
    for(int i = lg; i >= 1; i--) push(l >> i);
    S sm = e();
    do {
      while(l % 2 == 0) l >>= 1;
      if(!g(op(sm, d[l]))) {
        while(l < sz) {
          push(l);
          l <<= 1;
          if(g(op(sm, d[l]))) { sm = op(sm, d[l++]); }
        }
        return l - sz;
      }
      sm = op(sm, d[l++]);
    } while((l & -l) != l);
    return n;
  }
  int min_left(int r, auto g) {
    if(r == 0) return 0;
    r += sz;
    for(int i = lg; 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 < sz) {
          push(r);
          r = (2 * r + 1);
          if(g(op(d[r], sm))) {
            sm = op(d[r--], sm);  // r--
          }
        }
        return r + 1 - sz;
      }
      sm = op(d[r], sm);
    } while((r & -r) != r);
    return 0;
  }
};

// g : 両向きの辺を入れる
// 頂点 v の位置は ord[v] (seg.set(ord[v], A[v]))
struct hld {
  vector<int> par, sub, ord, nxt;
  hld (int n, vector<vector<int>> g, int root) : par(n), sub(n,1), ord(n), nxt(n){
    auto dfs = [&](auto sfs, int v) -> void {
      for (int &u : g[v]){ // &
        g[u].erase(find(all(g[u]),v));
        sfs(sfs,u);
        par[u] = v;
        sub[v] += sub[u];
        if (sub[g[v][0]] < sub[u]) swap(g[v][0],u);
      }
    };
    dfs(dfs,root);
    int t = 0;
    auto efs = [&](auto sfs, int v, int top) -> void {
      ord[v] = t++;
      nxt[v] = top;
      if (g[v].empty()) return ;
      sfs(sfs,g[v][0],top);
      for (int u : g[v] | views::drop(1)){
        sfs(sfs,u,u);
      }
    };
    efs(efs,root,root);
  }
  int lca(int u, int v){
    if (ord[u] > ord[v]) swap(u, v);
    if (ord[v] < ord[u] + sub[u]) return u;
    while (ord[u] < ord[v]) v = par[nxt[v]];
    return v;
  }
  // u -> lca は呼び出し順. f(a,b) : rev [b, a)
  // lca -> v は呼び出し逆順. f(a,b) : [a, b)
  // edge : 辺の情報を乗せているか？
  // f には空の区間 f(l,l) が呼ばれることがある
  // S sml = e(), smr = e();
  // path_query(u,v,false,[&](int l, int r){
  //     if (l < r) smr = op(seg.prod(l,r),smr);
  //     else sml = op(sml, revseg.prod(r,l));
  // });
  // S ans = op(sml, smr);
  void path_query(int u, int v, bool edge, auto f){
    while (nxt[u] != nxt[v]){
      if (ord[u] < ord[v]){
        f(ord[nxt[v]], ord[v] + 1);
        v = par[nxt[v]];
      }
      else {
        f(ord[u] + 1, ord[nxt[u]]);
        u = par[nxt[u]];
      }
    }
    bool big = ord[u] < ord[v];
    f(ord[u] + (edge||!big), ord[v] + (edge||big));
  }
  void subtree_query(int v, bool edge, auto f){
    f(ord[v] + edge, ord[v] + sub[v]);
  }
};

// 17:27~

void solve(){
    int n, q; cin >> n >> q;
    ll lv; cin >> lv;
    vector<ll> a(n), b(n);
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) cin >> b[i];
    vector<vector<int>> gg(n);
    vector<int> par(n,-1);
    vector<ll> sub(n);
    int root = -1;
    {
        using pli = pair<ll,int>;
        lazyseg<pli,[](pli a, pli b){ return max(a,b); }, [](){ return pli(-(1LL<<60),0); },
            bool, [](bool, pli x){ return x; }, [](bool, bool){ return false; }, [](){ return false; }> seg([&]{
                vector<pli> c(n);
                rep(i,0,n){
                    c[i] = {a[i],i};
                }
                return c;
            }());
        auto dfs = [&](auto sfs, int l, int r) -> int {
            if (r - l <= 0) return -1;
            auto [mi, m] = seg.prod(l,r);
            int lch = sfs(sfs,l,m);
            int rch = sfs(sfs,m+1,r);
            sub[m] = b[m];
            if (lch != -1){
                gg[m].emplace_back(lch);
                gg[lch].emplace_back(m);
                par[lch] = m;
                sub[m] += sub[lch];
            }
            if (rch != -1){
                gg[m].emplace_back(rch);
                gg[rch].emplace_back(m);
                par[rch] = m;
                sub[m] += sub[rch];
            }
            return m;
        };
        root = dfs(dfs,0,n);
    }
    hld tr(n,gg,root);
    vector<int> tour(n);
    rep(i,0,n){
        tour[tr.ord[i]] = i;
    }
    lazyseg<ll,[](ll a, ll b){ return min(a,b); },[](){ return 1LL<<60; },
        ll,[](ll f, ll x){ return f + x; },[](ll f, ll g){ return f + g; },[](){ return 0LL; }> seg([&]{
            vector<ll> c(n);
            rep(v,0,n){
                if (v == root) continue;
                int p = par[v];
                c[tr.ord[v]] = sub[v] + lv - a[p];
            }
            return c;
        }());
    lazyseg<ll,[](ll a, ll b){ return a + b; },[](){ return 0LL; },
        bool,[](bool, ll x){ return x; },[](bool, bool){ return false; },[](){ return false; }> subsum([&]{
            vector<ll> c(n);
            rep(v,0,n){
                c[tr.ord[v]] = b[v];
            }
            return c;
        }());
    auto query = [&](int pos) -> ll {
        int v = (a[pos] < a[pos+1] ? pos : pos+1);
        if (a[v] >= lv){
            return lv;
        }
        int cut = root;
        tr.path_query(v,root,true,[&](int l, int r){
            assert(l >= r);
            swap(l,r);
            if (cut != root) return ;
            if (seg.prod(l,r) > 0){
                return ;
            }
            int nl = seg.min_left(r,[](ll x){
                return x > 0;
            });
            // dump("path",l,r,nl);
            assert(nl-1 >= l);
            cut = tour[nl-1];
        });
        // dump("query",v,pos,cut);
        return lv + subsum.prod(tr.ord[cut],tr.ord[cut]+tr.sub[cut]);
    };
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int v; cin >> v; v--;
            ll x; cin >> x;
            subsum.set(tr.ord[v],x);
            x -= b[v];
            tr.path_query(v,root,true,[&](int l, int r){
                if (l > r) swap(l,r);
                seg.apply(l,r,x);
            });
            b[v] += x;
        }
        else {
            int pos; cin >> pos; pos--;
            assert(0 <= pos && pos+1 < n);
            cout << query(pos) << '\n';
        }
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
}