AtCoder Library Practice Contest K問題 - Range Affine Range Sum

Source

AtCoder Library Practice Contest
問題文

問題概要

省略

解法

省略

cLay（version 20201018-1）のコード

C++に変換後のコードはこちら

#define MD 998244353

struct segval{ Modint x, s; };
struct segfun{ Modint a, b; };

segval segtree_rh_apply(segfun f, segval a){
  a.x = a.x * f.a + a.s * f.b;
  return a;
}

segval segtree_rh_merge(segval a, segval b){
  segval res;
  res.x = a.x + b.x;
  res.s = a.s + b.s;
  return res;
}

segfun segtree_rh_compose(segfun f, segfun g){
  segfun res;
  res.a = f.a * g.a;
  res.b = f.a * g.b + f.b;
  return res;
}

int N, Q, A[5d5], T, L, R;
{
  segtree_rh<segval, segfun> t;
  segfun f;

  rd(N,Q,A(N));
  t.malloc(N);
  t.setN(N, 0, 0);
  rep(i,N){
    t[i].x = A[i];
    t[i].s = 1;
  }
  t.build();
  rep(Q){
    rd(T, L, R);
    if(T==0){
      rd(f.a, f.b);
      t.change(L, R, f);
    } else {
      wt(t.get(L, R).x);
    }
  }
}

cLay（version 20200916-1）のコード

C++に変換後のコードはこちら

#define MD 998244353

struct segval{ Modint x, s; };
struct segfun{ Modint a, b; };

void segtree_rg_id(segfun &res){
  res.a = 1;
  res.b = 0;
}

void segtree_rg_func(segval &res, segfun f, segval a){
  res.x = a.x * f.a + a.s * f.b;
}

void segtree_rg_func(segval &res, segval a, segval b){
  res.x = a.x + b.x;
  res.s = a.s + b.s;
}

void segtree_rg_func(segfun &res, segfun f, segfun g){
  res.a = f.a * g.a;
  res.b = f.a * g.b + f.b;
}

int N, Q, A[5d5], T, L, R;
{
  segtree_rg<segval, segfun> t;
  segfun f;

  rd(N,Q,A(N));
  t.malloc(N);
  t.setN(N, 0, 0);
  rep(i,N){
    t[i].x = A[i];
    t[i].s = 1;
  }
  t.build();
  rep(Q){
    rd(T, L, R);
    if(T==0){
      rd(f.a, f.b);
      t.change(L, R, f);
    } else {
      wt(t.get(L, R).x);
    }
  }
}

Current time: 2024年04月26日13時24分48秒
Last modified: 2020年10月18日05時44分41秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)