えびちゃんありがとうの章
可換性を必要とします
f(s,node[--r]);をf(node[--r],s);に変えると可換性を要求せずにすむらしいです(凄い)
可換性、不要...https://t.co/2yP0kCqrNP
— えびちゃん (@rsk0315_h4x) February 21, 2020
気持ち
確かに上手く行きそう
実装
非再帰です/可換性を要求しません
segment.cpp
template<typename T>
struct segment{
vector<T> node;
int n;
segment(int n):n(n){node.assign(n*2,e);}
T get(int l,int r){
l+=n;r+=n;
T s=e,t=e;
while(l<r){
if(l&1)s=f(s,node[l++]);
if(r&1)t=f(node[--r],t);
l/=2;r/=2;
}
return f(s,t);
}
void update(int t,T x){
t+=n;
node[t]=f(node[t],x);
while(t>1)t/=2,node[t]=f(node[t*2],node[t*2+1]);
}
void change(int t,T x){
t+=n;
node[t]=x;
while(t>1)t/=2,node[t]=f(node[t*2],node[t*2+1]);
}
T e={1,0};
T f(const T& s,const T& t){
return {t.first*s.first,t.first*s.second+t.second};
}
};