#1192423 (C++17) No.3763 Compress Pancakes

• 問題: No.3763 Compress Pancakes
• ユーザー: 👑 Nachia
• 提出日時: 2026-10-09 22:38:50
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 164 ms / 2,000 ms
• コード長: 4,153 bytes
• コンパイル時間: 453 ms
• コンパイル使用メモリ: 100,304 KB
• 実行使用メモリ: 47,996 KB
• 最終ジャッジ日時: 2026-10-09 22:39:00
• 合計ジャッジ時間: 5,736 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 29

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

#include <cassert>

namespace nachia{

template<
    class S,
    S op(S l, S r)
>
struct Segtree {
private:
    int N;
    std::vector<S> A;
    int xN;

    void mergev(int i){
        if(i < N) A[i] = op(A[i*2], A[i*2+1]);
    }

    template<class E>
    int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(r <= a) return a;
        if(b <= r){
            S nx = op(A[i], x);
            if(cmp(nx)){ x = nx; return a; }
        }
        if(b - a == 1) return b;
        int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1);
        if(q > (a+b)/2) return q;
        return minLeft2(r, cmp, a, (a+b)/2, i*2);
    }
    
    template<class E>
    int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(b <= l) return b;
        if(l <= a){
            S nx = op(x, A[i]);
            if(cmp(nx)){ x = nx; return b; }
        }
        if(b - a == 1) return a;
        int q = maxRight2(l, cmp, a, (a+b)/2, i*2);
        if(q < (a+b)/2) return q;
        return maxRight2(l, cmp, (a+b)/2, b, i*2+1);
    }

public:
    Segtree() : N(0) {}
    Segtree(int n, S e) : xN(n) {
        N = 1; while (N < n) N *= 2;
        A.assign(N * 2, e);
    }
    Segtree(const std::vector<S>& a, S e) : Segtree(a.size(), e){
        for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i];
        for(int i=N-1; i>=1; i--) mergev(i);
    }

    S getE() const { return A[0]; }

    void set(int p, S x){
        assert(0 <= p); assert(p < xN);
        p += N; A[p] = x;
        for(int d=1; (1<<d)<=N; d++) mergev(p>>d);
    }

    S get(int p) const {
        assert(0 <= p); assert(p < xN);
        return A[N+p];
    }

    S prod(int l, int r) const {
        assert(0 <= l); assert(r <= xN);
        l += N; r += N;
        S ql = A[0], qr = A[0];
        while(l<r){
            if(l&1) ql = op(ql, A[l++]);
            if(r&1) qr = op(A[--r], qr);
            l /= 2;
            r /= 2;
        }
        return op(ql, qr);
    }

    S allProd() const { return A[1]; }

    // bool cmp(S)
    template<class E>
    int minLeft(int r, E cmp) const {
        return minLeft2(r, cmp);
    }

    // bool cmp(S)
    template<class E>
    int maxRight(int l, E cmp) const {
        int x = maxRight2(l, cmp);
        return x > xN ? xN : x;
    }
};

} // namespace nachia

struct Node {
  ll g = 0;
  ll mod = 0;
  ll rem = 0;
  ll sum = 0;
};

Node op(Node l, Node r){
  if(l.sum == 0) return r;
  if(r.sum == 0) return l;
  Node res;
  res.sum = l.sum + r.sum;
  bool ok = 0;
  if(l.g > 0 && l.g == r.g){
    r.rem = (r.rem + l.sum) % r.mod;
    if(l.mod < r.mod) swap(l, r);
    if(l.rem % r.mod == r.rem){
      ok = 1;
      res.g = l.g;
      res.mod = l.mod;
      res.rem = l.rem;
    }
  }
  if(!ok){
    res.g = res.mod = res.rem = -1;
  }
  return res;
}
ll get_g(ll a){
  while(a%2 == 0) a /= 2;
  return a;
}

Node makeNode(ll a){
  Node res;
  res.g = get_g(a);
  res.sum = a;
  res.mod = a;
  res.rem = 0;
  return res;
}

void testcase(){
  ll N, Q; cin >> N >> Q;
  V<ll> A(N); REP(i,N) cin >> A[i];
  V<Node> init(N);
  REP(i,N) init[i] = makeNode(A[i]);
  auto ds = nachia::Segtree<Node, op>(init, Node());

  REP(qi,Q){
    ll ty; cin >> ty;
    if(ty == 1){
      ll k, x; cin >> k >> x; k--;
      ds.set(k, makeNode(x));
    } else {
      ll l, r; cin >> l >> r; l--;
      auto prod = ds.prod(l, r);
      ll g = get_g(prod.sum);
      if(prod.g == g && prod.rem == 0) cout << "Yes\n"; else cout << "No\n";
    }
  }
}

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