compro-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/segment-tree/DualSegmentTree-pcq.test.cpp
- View this file on GitHub
- Last update: 2023-07-03 02:09:18+09:00
- Problem: https://judge.yosupo.jp/problem/range_affine_point_get
Depends on
FastIO
(lib/00-util/FastIO.cpp)
- ModInt
(lib/00-util/ModInt.cpp)
- DualSegmentTree - 非再帰抽象化双対セグメント木
(lib/10-segment-tree/DualSegmentTree.cpp)
- MonoidRangeFoldSumRangeOperateAffine - fold:区間和, operate:区間アフィン変換
(lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAffine.cpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_point_get"
#include <vector>
#include <iostream>
using namespace std;
#include "../../lib/00-util/FastIO.cpp"
#include "../../lib/00-util/ModInt.cpp"
#include "../../lib/10-segment-tree/DualSegmentTree.cpp"
#include "../../lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAffine.cpp"
int main(void){
cin.tie(0);ios::sync_with_stdio(false);
using Mint = ModInt<MOD_998244353>;
int N,Q;
read(N),read(Q);
DualSegmentTree<MonoidRangeFoldSumRangeOperateAffine<Mint,pair<Mint,Mint>>> seg(N);
for(int i=0;i<N;++i) {
int a; read(a);
seg.operate(i,i+1,{0,a});
}
while(Q--) {
int q; read(q);
if(q==0) {
int l,r,b,c;
read(l),read(r),read(b),read(c);
seg.operate(l,r,{b,c});
}
if(q==1) {
int i; read(i);
cout << seg.fold(i) << "\n";
}
}
return 0;
}#line 1 "test/segment-tree/DualSegmentTree-pcq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_point_get"
#include <vector>
#include <iostream>
using namespace std;
#line 1 "lib/00-util/FastIO.cpp"
/*
* @title FastIO
* @docs md/util/FastIO.md
*/
class FastIO{
private:
inline static constexpr int ch_0='0';
inline static constexpr int ch_9='9';
inline static constexpr int ch_n='-';
inline static constexpr int ch_s=' ';
inline static constexpr int ch_l='\n';
inline static void endline_skip(char& ch) {
while(ch==ch_l) ch=getchar();
}
template<typename T> inline static void read_integer(T &x) {
int neg=0; char ch; x=0;
ch=getchar();
endline_skip(ch);
if(ch==ch_n) neg=1,ch=getchar();
for(;(ch_0 <= ch && ch <= ch_9); ch = getchar()) x = x*10 + (ch-ch_0);
if(neg) x*=-1;
}
template<typename T> inline static void read_unsigned_integer(T &x) {
char ch; x=0;
ch=getchar();
endline_skip(ch);
for(;(ch_0 <= ch && ch <= ch_9); ch = getchar()) x = x*10 + (ch-ch_0);
}
inline static void read_string(string &x) {
char ch; x="";
ch=getchar();
endline_skip(ch);
for(;(ch != ch_s && ch!=ch_l); ch = getchar()) x.push_back(ch);
}
inline static char ar[40];
inline static char *ch_ar;
template<typename T> inline static void write_integer(T x) {
ch_ar=ar;
if(x< 0) putchar(ch_n), x=-x;
if(x==0) putchar(ch_0);
for(;x;x/=10) *ch_ar++=(ch_0+x%10);
while(ch_ar--!=ar) putchar(*ch_ar);
}
public:
inline static void read(int &x) {read_integer<int>(x);}
inline static void read(long long &x) {read_integer<long long>(x);}
inline static void read(unsigned int &x) {read_unsigned_integer<unsigned int>(x);}
inline static void read(unsigned long long &x) {read_unsigned_integer<unsigned long long>(x);}
inline static void read(string &x) {read_string(x);}
inline static void read(__int128_t &x) {read_integer<__int128_t>(x);}
inline static void write(__int128_t x) {write_integer<__int128_t>(x);}
inline static void write(char x) {putchar(x);}
};
#define read(arg) FastIO::read(arg)
#define write(arg) FastIO::write(arg)
#line 1 "lib/00-util/ModInt.cpp"
/*
* @title ModInt
* @docs md/util/ModInt.md
*/
template<long long mod> class ModInt {
public:
long long x;
constexpr ModInt():x(0) {}
constexpr ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {}
constexpr ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
constexpr ModInt &operator+=(const long long y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}
constexpr ModInt &operator+=(const int y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}
constexpr ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
constexpr ModInt &operator-=(const long long y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}
constexpr ModInt &operator-=(const int y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}
constexpr ModInt &operator*=(const ModInt &p) {x = (x * p.x % mod);return *this;}
constexpr ModInt &operator*=(const long long y) {ModInt p(y);x = (x * p.x % mod);return *this;}
constexpr ModInt &operator*=(const int y) {ModInt p(y);x = (x * p.x % mod);return *this;}
constexpr ModInt &operator^=(const ModInt &p) {x = (x ^ p.x) % mod;return *this;}
constexpr ModInt &operator^=(const long long y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}
constexpr ModInt &operator^=(const int y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}
constexpr ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;}
constexpr ModInt &operator/=(const long long y) {ModInt p(y);*this *= p.inv();return *this;}
constexpr ModInt &operator/=(const int y) {ModInt p(y);*this *= p.inv();return *this;}
constexpr ModInt operator=(const int y) {ModInt p(y);*this = p;return *this;}
constexpr ModInt operator=(const long long y) {ModInt p(y);*this = p;return *this;}
constexpr ModInt operator-() const {return ModInt(-x); }
constexpr ModInt operator++() {x++;if(x>=mod) x-=mod;return *this;}
constexpr ModInt operator--() {x--;if(x<0) x+=mod;return *this;}
constexpr ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
constexpr ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
constexpr ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
constexpr ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
constexpr ModInt operator^(const ModInt &p) const { return ModInt(*this) ^= p; }
constexpr bool operator==(const ModInt &p) const { return x == p.x; }
constexpr bool operator!=(const ModInt &p) const { return x != p.x; }
// ModInt inv() const {int a=x,b=mod,u=1,v=0,t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);} return ModInt(u);}
constexpr ModInt inv() const {int a=x,b=mod,u=1,v=0,t=0,tmp=0;while(b > 0) {t = a / b;a-=t*b;tmp=a;a=b;b=tmp;u-=t*v;tmp=u;u=v;v=tmp;} return ModInt(u);}
constexpr ModInt pow(long long n) const {ModInt ret(1), mul(x);for(;n > 0;mul *= mul,n >>= 1) if(n & 1) ret *= mul;return ret;}
friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}
friend istream &operator>>(istream &is, ModInt &a) {long long t;is >> t;a = ModInt<mod>(t);return (is);}
};
constexpr long long MOD_998244353 = 998244353;
constexpr long long MOD_1000000007 = 1'000'000'000LL + 7; //'
#line 1 "lib/10-segment-tree/DualSegmentTree.cpp"
/*
* @title DualSegmentTree - 非再帰抽象化双対セグメント木
* @docs md/segment-tree/DualSegmentTree.md
*/
template<class Monoid> class DualSegmentTree {
using TypeNode = typename Monoid::TypeNode;
using TypeLazy = typename Monoid::TypeLazy;
size_t length;
size_t height;
vector<TypeNode> node;
vector<TypeLazy> lazy;
void propagate(int k) {
if(lazy[k] == Monoid::unit_lazy) return;
if(k >=length) node[k-length] = Monoid::func_operate(node[k-length],lazy[k],k-length,k-length+1);
if(k < length) lazy[2*k+0] = Monoid::func_lazy(lazy[2*k+0],lazy[k]);
if(k < length) lazy[2*k+1] = Monoid::func_lazy(lazy[2*k+1],lazy[k]);
lazy[k] = Monoid::unit_lazy;
}
void build(const size_t num) {
for (length = 1,height = 0; length <= num; length *= 2, height++);
node.resize(1 * length, Monoid::unit_node);
lazy.resize(2 * length, Monoid::unit_lazy);
}
public:
//unitで初期化
DualSegmentTree(const size_t num) {
build(num);
}
// //同じinitで初期化
DualSegmentTree(const size_t num, const TypeNode init) {
build(num);
for (int i = 0; i < num; ++i) node[i] = init;
}
//vectorで初期化
DualSegmentTree(const vector<TypeNode>& vec) {
build(vec.size());
for (int i = 0; i < vec.size(); ++i) node[i] = vec[i];
}
//operate [a,b)
void operate(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] = Monoid::func_lazy(lazy[l],x), propagate(l),l++;
if(r&1) --r,lazy[r] = Monoid::func_lazy(lazy[r],x), propagate(r);
}
}
//fold [a,a+1)
TypeNode fold(int a) {
int l = a + length;
for (int i = height; 0 <= i; --i) propagate(l >> i);
return node[a];
}
void print(){
cout << "lazy" << endl;
for(int i = 1,j = 1; i < 2*length; ++i) {
cout << lazy[i] << " ";
if(i==((1<<j)-1) && ++j) cout << endl;
}
cout << "vector" << endl;
cout << "{ " << fold(0);
for(int i = 1; i < length; ++i) cout << ", " << fold(i);
cout << " }" << endl;
}
};
#line 1 "lib/99-operator/monoid-lazy/MonoidRangeFoldSumRangeOperateAffine.cpp"
/*
* @title MonoidRangeFoldSumRangeOperateAffine - fold:区間和, operate:区間アフィン変換
* @docs md/operator/monoid-lazy/MonoidRangeSumRangeAffine.md
*/
template<class T, class U> struct MonoidRangeFoldSumRangeOperateAffine {
using TypeNode = T;
using TypeLazy = U;
inline static constexpr TypeNode unit_node = 0;
inline static constexpr TypeLazy unit_lazy = {1,0};
inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
inline static constexpr TypeLazy func_lazy(TypeLazy old_lazy,TypeLazy new_lazy){return {new_lazy.first*old_lazy.first,new_lazy.first*old_lazy.second+new_lazy.second};}
inline static constexpr TypeNode func_operate(TypeNode node,TypeLazy lazy,int l, int r){return {node*lazy.first+lazy.second*(r-l)};}
inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var <= nodeVal;}
};
#line 10 "test/segment-tree/DualSegmentTree-pcq.test.cpp"
int main(void){
cin.tie(0);ios::sync_with_stdio(false);
using Mint = ModInt<MOD_998244353>;
int N,Q;
read(N),read(Q);
DualSegmentTree<MonoidRangeFoldSumRangeOperateAffine<Mint,pair<Mint,Mint>>> seg(N);
for(int i=0;i<N;++i) {
int a; read(a);
seg.operate(i,i+1,{0,a});
}
while(Q--) {
int q; read(q);
if(q==0) {
int l,r,b,c;
read(l),read(r),read(b),read(c);
seg.operate(l,r,{b,c});
}
if(q==1) {
int i; read(i);
cout << seg.fold(i) << "\n";
}
}
return 0;
}