verify/LC-RangeAffineRangeSum.test.cpp

• View this file on GitHub
• Last update: 2022-12-30 01:32:33+09:00
• Problem: https://judge.yosupo.jp/problem/range_affine_range_sum
• Link: View error logs on GitHub Actions

Depends on

• data-structure/segment-tree/lazy-segment-tree.hpp
• data-structure/segment-tree/range-affine-range-sum-query.hpp
• template/template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"

#include "../template/template.hpp"
#include "../data-structure/segment-tree/range-affine-range-sum-query.hpp"

int main(){
  int N, Q;
  cin >> N >> Q;
  VL a = input(N);

  RangeAffineRangeSumQuery<ll> rsq(N, 998244353);
  REP(i,N) rsq.set(i, a[i]);
  REP(i,Q){
    int t;
    cin >> t;
    if(t == 0){
      int l, r;
      ll b, c;
      cin >> l >> r >> b >> c;
      rsq.applyRange(l, r, {b, c});
    }else{
      int l, r;
      cin >> l >> r;
      cout << rsq.query(l, r) << endl;
    }
  }
}

#line 1 "verify/LC-RangeAffineRangeSum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"

#line 1 "template/template.hpp"
#include<bits/stdc++.h>
using ll = long long;
#define REP(i, n) for(ll i = 0; (i) < ll(n); ++ (i))
#define FOR(i, m, n) for(ll i = (m); (i) <= ll(n); ++ (i))
#define REPR(i, n) for(ll i = ll(n) - 1; (i) >= 0; -- (i))
#define FORR(i, m, n) for(ll i = ll(n); (i) >= ll(m); -- (i))
#define ALL(x) x.begin(),x.end()

#define INF (int)1e9
#define LLINF (long long)1e18
#define MOD (int)(1e9+7)
#define MOD9 (int)998244353
#define PI 3.141592653589
#define PB push_back
#define F first
#define S second

#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define Yes(T) {cout<<"Yes"<<endl; if(T) return 0;}
#define No(T) {cout <<"No"<<endl; if(T) return 0;}
#define YES(T) {cout<<"YES"<<endl; if(T) return 0;}
#define NO(T) {cout <<"NO"<<endl; if(T) return 0;}

#define Graph vector<vector<int> >
#define CostGraph vector<vector<pair<int,ll> > >
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define VI vector<int>
#define VL vector<ll>
#define VVI vector<vector<int> >
#define VVL vector<vector<ll> >
#define VPII vector<pair<int,int> >
#define VPLL vector<pair<ll,ll> >

#define DDD fixed<<setprecision(10)
#define PAD setfill('0')<<right<<setw(8)

template <class T>
inline bool chmin(T &a, T b) {
  if(a > b){ a = b; return true;}
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if(a < b){a = b; return true;}
  return false;
}
struct input{
  int n;
  input() {}
  input(int n_) : n(n_){};
  template <class T>
  operator T(){
    T ret;
    std::cin >> ret;
    return ret;
  }
  template <class T>
  operator std::vector<T>() {
    std::vector<T> ret(n);
    REP(i,n) std::cin >> ret[i];
    return ret;
  }
};
template <class T>
inline void printVec(std::vector<T> v){
  REP(i,v.size()){
    if(i) std::cout << " ";
    std::cout << v[i];
  } std::cout << std::endl;
}

using namespace std;
#line 1 "data-structure/segment-tree/lazy-segment-tree.hpp"
template <typename T, typename E>
struct LazySegmentTree{
  using F = function<T(T, T)>;
  using G = function<T(T, E)>;
  using H = function<E(E, E)>;
  int n, sz, height;
  vector<T> data;
  vector<E> lazy;
  const F f;
  const G g;
  const H h;
  const T e;
  const E eLazy;

  inline void update(int k){
    data[k] = f(data[2 * k + 0], data[2 * k + 1]);
  }

  inline void all_apply(int k, const E &x) {
    data[k] = g(data[k], x);
    if(k < sz) lazy[k] = h(lazy[k], x);
  }

  inline void propagate(int k){
    if(lazy[k] != eLazy){
      all_apply(2 * k + 0, lazy[k]);
      all_apply(2 * k + 1, lazy[k]);
      lazy[k] = eLazy;
    }
  }

  // LazySegmentTree() = default;
  LazySegmentTree(int n, const F f, const G g, const H h, const T &e, const E &eLazy): n(n), f(f), g(g), h(h), e(e), eLazy(eLazy){
    sz = 1;
    height = 0;
    while(sz < n) sz <<= 1, ++height;
    data.assign(2 * sz, e);
    lazy.assign(2 * sz, eLazy);
  }

  void set(int k, const T &x){
    k += sz;
    for(int i = height; i > 0; --i) propagate(k >> i);
    data[k] = x;
    for(int i = 1; i <= height; ++i) update(k >> i);
  }

  T query(int l, int r){
    if(l >= r) return e;
    l += sz;
    r += sz;
    for(int i = height; i > 0; --i){
      if(((l >> i) << i) != l) propagate(l >> i);
      if(((r >> i) << i) != r) propagate((r - 1) >> i);
    }
    T lval = e, rval = e;
    for(; l < r; l >>= 1, r >>= 1){
      if(l & 1) lval = f(lval, data[l++]);
      if(r & 1) rval = f(data[--r], rval);
    }
    return f(lval, rval);
  }

  void apply(int k, const E &x){
    k += sz;
    for(int i = height; i > 0; --i) propagate(k >> i);
    data[k] = g(data[k], x);
    for(int i = 1; i <= height; ++i) update(k >> i);
  }

  void applyRange(int l, int r, const E &x){
    if(l >= r) return;
    l += sz;
    r += sz;
    for(int i = height; i > 0; --i){
      if(((l >> i) << i) != l) propagate(l >> i);
      if(((r >> i) << i) != r) propagate((r - 1) >> i);
    }

    int l2 = l, r2 = r;
    for(; l < r; l >>= 1, r >>= 1){
      if(l & 1) all_apply(l++, x);
      if(r & 1) all_apply(--r, x);
    }
    l = l2, r = r2;

    for(int i = 1; i <= height; ++i){
      if(((l >> i) << i) != l) update(l >> i);
      if(((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template <typename C>
  int findFirst(int l, const C &check){
    if(l >= n) return n;
    l += sz;
    for(int i = height; i > 0; --i) propagate(l >> i);
    T sum = e;
    do{
      while((l & 1) == 0) l >>= 1;
      if(check(f(sum, data[l]))){
        while(l < sz) {
          propagate(l);
          l <<= 1;
          auto nxt = f(sum, data[l]);
          if(!check(nxt)){
            sum = nxt;
            ++l;
          }
        }
        return l + 1 - sz;
      }
      sum = f(sum, data[l++]);
    }while((l & -l) != l);
    return n;
  }

  template <typename C>
  int findLast(int r, const C &check){
    if(r <= 0) return -1;
    r += sz;
    for(int i = height; i > 0; --i) propagate((r - 1) >> i);
    T sum = e;
    do{
      --r;
      while(r > 1 and (r & 1)) r >>= 1;
      if(check(f(data[r], sum))){
        while(r < sz){
          propagate(r);
          r = (r << 1) + 1;
          auto nxt = f(data[r], sum);
          if(!check(nxt)){
            sum = nxt;
            --r;
          }
        }
        return r - sz;
      }
      sum = f(data[r], sum);
    }while((r & -r) != r);
    return -1;
  }
};
#line 2 "data-structure/segment-tree/range-affine-range-sum-query.hpp"
template <typename T>
struct RangeAffineRangeSumQuery{
  using P = pair<T,T>;

  int n;
  T mod;

  function<P(P,P)> f = [&](P a, P b)->P{
    return {(a.first + b.first) % mod, (a.second + b.second) % mod};
  };

  function<P(P,P)> g = [&](P a, P b)->P{
    return {(a.first * b.first + a.second * b.second) % mod, a.second % mod};
  };

  function<P(P,P)> h = [&](P a, P b)->P{
    return {a.first * b.first % mod, (a.second * b.first + b.second) % mod};
  };

  LazySegmentTree<P, P> seg;
  RangeAffineRangeSumQuery(int n, T mod): n(n), mod(mod), seg(n, f, g, h, P({0, 0}), P({1, 0})){

  }

  void set(int k, T &x){
    seg.set(k, {x, 1});
  }

  void applyRange(int l, int r, P p){
    seg.applyRange(l, r, p);
  }

  T query(int l, int r){
    return seg.query(l, r).first;
  }
};
#line 5 "verify/LC-RangeAffineRangeSum.test.cpp"

int main(){
  int N, Q;
  cin >> N >> Q;
  VL a = input(N);

  RangeAffineRangeSumQuery<ll> rsq(N, 998244353);
  REP(i,N) rsq.set(i, a[i]);
  REP(i,Q){
    int t;
    cin >> t;
    if(t == 0){
      int l, r;
      ll b, c;
      cin >> l >> r >> b >> c;
      rsq.applyRange(l, r, {b, c});
    }else{
      int l, r;
      cin >> l >> r;
      cout << rsq.query(l, r) << endl;
    }
  }
}

Back to top page