线段树大水题
#include<cstdio>
int n,m;
long long k[200005],b[200005];
const long long Mod=1000000007ll;
struct SegTree{
long long k,b;
int l,r;
}tree[1000005];
void Pushup(int rt){
tree[rt].k=tree[rt*2].k*tree[rt*2+1].k%Mod;
tree[rt].b=(tree[rt*2+1].b+tree[rt*2+1].k*tree[rt*2].b%Mod)%Mod;
}
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].k=k[l]%Mod;tree[rt].b=b[l]%Mod;return;}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
Pushup(rt);
}
void Modify(int rt,int pos,long long k,long long b){
if(tree[rt].l==tree[rt].r){tree[rt].k=k%Mod;tree[rt].b=b%Mod;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Modify(rt*2,pos,k,b);
if(pos>mid)Modify(rt*2+1,pos,k,b);
Pushup(rt);
}
long long Query(int rt,int l,int r,long long x){
if(l<=tree[rt].l && tree[rt].r<=r){return (tree[rt].k*x%Mod+tree[rt].b)%Mod;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l>mid)return Query(rt*2+1,l,r,x)%Mod;
else if(r<=mid)return Query(rt*2,l,r,x)%Mod;
return Query(rt*2+1,l,r,Query(rt*2,l,r,x)%Mod)%Mod;
}
int main(){
freopen("4499.in","r",stdin);
freopen("4499.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld %lld",&k[i],&b[i]);
}
Build(1,1,n);
for(int i=1;i<=m;i++){
char s[5];
long long l,r,v;
scanf("%s %lld %lld %lld",s,&l,&r,&v);
if(s[0]=='M')Modify(1,(int)l,r,v);
else printf("%lld\n",Query(1,(int)l,(int)r,v));
}
return 0;
}
评论 (0)
