题目一看就很数据结构,套路地考虑线段树。
不妨设 为
区间的答案,
为区间
中元素的乘积。
套路地考虑信息的合并,不难发现, 可以由
,
和
推得。
在线段树上直接做就可以了,单点修改和区间查询是容易的。
由于你站的 渲染好像有问题,所以公式什么的就算了。
using namespace std;
namespace sk {};
#define int long long
using ll=sk::static_modint<1145141>;
constexpr int MAXN=1e5+10;
struct SG {
#define ll(p) tr[p].l
#define rr(p) tr[p].r
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define val(p) tr[p].val
#define mul(p) tr[p].mul
struct {
int l, r; ll val, mul;
} tr[MAXN<<2];
void pushup(int p) {
val(p)=val(ls(p))+mul(ls(p))*val(rs(p));
mul(p)=mul(ls(p))*mul(rs(p));
}
void build(int l, int r, int a[], int p=1) {
ll(p)=l, rr(p)=r;
if (l==r) return val(p)=mul(p)=a[l], void();
int mid=(l+r)>>1;
build(l,mid,a,ls(p)); build(mid+1,r,a,rs(p));
pushup(p);
}
using pll=pair<ll,ll>;
pll ask(int l, int r, int p=1) {
int cl=ll(p), cr=rr(p);
if (l<=cl && cr<=r) return {val(p),mul(p)};
int mid=(cl+cr)>>1;
if (l<=mid && r>mid) {
auto [vl,ml]=ask(l,r,ls(p));
auto [vr,mr]=ask(l,r,rs(p));
return {vl+ml*vr,ml*mr};
}
if (l<=mid) return ask(l,r,ls(p));
else return ask(l,r,rs(p));
}
void change(int pos, int v, int p=1) {
int cl=ll(p), cr=rr(p);
if (cl==cr) return val(p)=mul(p)=v, void();
int mid=(cl+cr)>>1;
if (pos<=mid) change(pos,v,ls(p));
else change(pos,v,rs(p));
pushup(p);
}
} sg;