CP_library
This documentation is automatically generated by online-judge-tools/verification-helper
test/lazy_segtree.test.cpp
- View this file on GitHub
- Last update: 2024-02-15 14:50:41+09:00
- Problem: https://judge.yosupo.jp/problem/range_affine_range_sum
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#include "../data_structure/lazy_segtree.hpp"
#include "../math/mint998.hpp"
using mint=modint<998244353>;
struct Info {
using typeNode=mint;
using typeLazy=pair<mint,mint>;
typeNode unitNode = 0;
typeLazy unitLazy = make_pair(1,0);
typeNode funcNode(typeNode l,typeNode r){return l+r;}
typeLazy funcLazy(typeLazy l,typeLazy r){return make_pair(r.first*l.first,r.first*l.second+r.second);}
typeNode funcMerge(typeNode l,typeLazy r,int len){return r.first*l+r.second*len;}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll N,Q;cin>>N>>Q;
vector<mint> a(N);
for(ll i=0;i<N;i++) {
ll A;cin>>A;
a[i]=A;
}
LazySegmentTree<Info> seg(a);
for(ll i=0;i<Q;i++) {
ll t;cin>>t;
if(t==0) {
ll l,r,b,c;cin>>l>>r>>b>>c;
seg.update(l,r,make_pair(b,c));
}
else {
ll l,r;cin>>l>>r;
cout<<seg.get(l,r)<<endl;
}
}
}#line 1 "test/lazy_segtree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#line 1 "data_structure/lazy_segtree.hpp"
template<class Operator> class LazySegmentTree {
Operator Op;
using typeNode = decltype(Op.unitNode);
using typeLazy = decltype(Op.unitLazy);
size_t num;
size_t length;
size_t height;
vector<typeNode> node;
vector<typeLazy> lazy;
vector<pair<size_t,size_t>> range;
public:
//unitで初期化
LazySegmentTree(const size_t num) : num(num) {
for (length = 1,height = 0; length < num; length *= 2, height++);
node.resize(2 * length, Op.unitNode);
lazy.resize(2 * length, Op.unitLazy);
for (int i = 0; i < num; ++i) node[i + length] = Op.unitNode;
for (int i = length - 1; i >= 0; --i) node[i] = Op.funcNode(node[(i<<1)+0],node[(i<<1)+1]);
range.resize(2 * length);
for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
}
// //同じinitで初期化
LazySegmentTree(const size_t num, const typeNode init) : num(num) {
for (length = 1,height = 0; length < num; length *= 2, height++);
node.resize(2 * length, Op.unitNode);
lazy.resize(2 * length, Op.unitLazy);
for (int i = 0; i < num; ++i) node[i + length] = init;
for (int i = length - 1; i >= 0; --i) node[i] = Op.funcNode(node[(i<<1)+0],node[(i<<1)+1]);
range.resize(2 * length);
for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
}
//vectorで初期化
LazySegmentTree(const vector<typeNode>& vec) : num(vec.size()) {
for (length = 1,height = 0; length < vec.size(); length *= 2, height++);
node.resize(2 * length, Op.unitNode);
lazy.resize(2 * length, Op.unitLazy);
for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i];
for (int i = length - 1; i >= 0; --i) node[i] = Op.funcNode(node[(i<<1)+0],node[(i<<1)+1]);
range.resize(2 * length);
for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1);
for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second);
}
void propagate(int k) {
if(lazy[k] == Op.unitLazy) return;
node[k] = Op.funcMerge(node[k],lazy[k],range[k].second-range[k].first);
if(k < length) lazy[2*k+0] = Op.funcLazy(lazy[2*k+0],lazy[k]);
if(k < length) lazy[2*k+1] = Op.funcLazy(lazy[2*k+1],lazy[k]);
lazy[k] = Op.unitLazy;
}
//update [a,b)
void update(int a, int b, typeLazy x) {
int l = a + length, r = b + length - 1;
for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i);
for(r++; l < r; l >>=1, r >>=1) {
if(l&1) lazy[l] = Op.funcLazy(lazy[l],x), propagate(l),l++;
if(r&1) --r,lazy[r] = Op.funcLazy(lazy[r],x), propagate(r);
}
l = a + length, r = b + length - 1;
while ((l>>=1),(r>>=1),l) {
if(lazy[l] == Op.unitLazy) node[l] = Op.funcNode(Op.funcMerge(node[(l<<1)+0],lazy[(l<<1)+0],range[(l<<1)+0].second-range[(l<<1)+0].first),Op.funcMerge(node[(l<<1)+1],lazy[(l<<1)+1],range[(l<<1)+1].second-range[(l<<1)+1].first));
if(lazy[r] == Op.unitLazy) node[r] = Op.funcNode(Op.funcMerge(node[(r<<1)+0],lazy[(r<<1)+0],range[(r<<1)+0].second-range[(r<<1)+0].first),Op.funcMerge(node[(r<<1)+1],lazy[(r<<1)+1],range[(r<<1)+1].second-range[(r<<1)+1].first));
}
}
//get [a,b)
typeNode get(int a, int b) {
int l = a + length, r = b + length - 1;
for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i);
typeNode vl = Op.unitNode, vr = Op.unitNode;
for(r++; l < r; l >>=1, r >>=1) {
if(l&1) vl = Op.funcNode(vl,Op.funcMerge(node[l],lazy[l],range[l].second-range[l].first)),l++;
if(r&1) r--,vr = Op.funcNode(Op.funcMerge(node[r],lazy[r],range[r].second-range[r].first),vr);
}
return Op.funcNode(vl,vr);
}
//return [0,length]
int PrefixBinarySearch(typeNode var) {
int l = length, r = 2*length - 1;
for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i);
if(!Op.funcCheck(node[1],var)) return num;
typeNode ret = Op.unitNode;
size_t idx = 2;
for(; idx < 2*length; idx<<=1){
if(!Op.funcCheck(Op.funcNode(ret,Op.funcMerge(node[idx],lazy[idx],range[idx].second-range[idx].first)),var)) {
ret = Op.funcNode(ret,Op.funcMerge(node[idx],lazy[idx],range[idx].second-range[idx].first));
idx++;
}
}
return min((idx>>1) - length,num);
}
//range[l,r) return [l,r]
int BinarySearch(size_t l, size_t r, typeNode var) {
if (l < 0 || length <= l || r < 0 || length < r) return -1;
for (int i = height; 0 < i; --i) propagate((l+length) >> i), propagate((r+length-1) >> i);
typeNode ret = Op.unitNode;
size_t off = l;
for(size_t idx = l+length; idx < 2*length && off < r; ){
if(range[idx].second<=r && !Op.funcCheck(Op.funcNode(ret,Op.funcMerge(node[idx],lazy[idx],range[idx].second-range[idx].first)),var)) {
ret = Op.funcNode(ret,Op.funcMerge(node[idx],lazy[idx],range[idx].second-range[idx].first));
off = range[idx++].second;
if(!(idx&1)) idx >>= 1;
}
else{
idx <<=1;
}
}
return off;
}
};
#line 3 "math/mint998.hpp"
using namespace std;
using ll =long long;
ll INF=2e18;
template<int mod>
class modint {
long long x;
public:
modint(long long x=0) : x((x%mod+mod)%mod) {}
modint operator-() const {
return modint(-x);
}
modint& operator+=(const modint& a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
modint& operator-=(const modint& a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
modint& operator*=(const modint& a) {
(x *= a.x) %= mod;
return *this;
}
modint operator+(const modint& a) const {
modint res(*this);
return res+=a;
}
modint operator-(const modint& a) const {
modint res(*this);
return res-=a;
}
modint operator*(const modint& a) const {
modint res(*this);
return res*=a;
}
modint pow(ll t) const {
if (!t) return 1;
modint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
modint inv() const {
return pow(mod-2);
}
modint& operator/=(const modint& a) {
return (*this) *= a.inv();
}
modint operator/(const modint& a) const {
modint res(*this);
return res/=a;
}
bool operator==(const modint &a) const {
modint res(*this);
return res.x==a.x;
}
bool operator!=(const modint &a) const {
modint res(*this);
return res.x!=a.x;
}
friend ostream& operator<<(ostream& os, const modint& m){
os << m.x;
return os;
}
};
#line 13 "test/lazy_segtree.test.cpp"
using mint=modint<998244353>;
struct Info {
using typeNode=mint;
using typeLazy=pair<mint,mint>;
typeNode unitNode = 0;
typeLazy unitLazy = make_pair(1,0);
typeNode funcNode(typeNode l,typeNode r){return l+r;}
typeLazy funcLazy(typeLazy l,typeLazy r){return make_pair(r.first*l.first,r.first*l.second+r.second);}
typeNode funcMerge(typeNode l,typeLazy r,int len){return r.first*l+r.second*len;}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll N,Q;cin>>N>>Q;
vector<mint> a(N);
for(ll i=0;i<N;i++) {
ll A;cin>>A;
a[i]=A;
}
LazySegmentTree<Info> seg(a);
for(ll i=0;i<Q;i++) {
ll t;cin>>t;
if(t==0) {
ll l,r,b,c;cin>>l>>r>>b>>c;
seg.update(l,r,make_pair(b,c));
}
else {
ll l,r;cin>>l>>r;
cout<<seg.get(l,r)<<endl;
}
}
}