BZOJ-4499: 线性函数

Description

小C最近在学习线性函数，线性函数可以表示为：f(x) = kx + b。现在小C面前有n个线性函数fi(x)=kix+bi ，他对这n个线性函数执行m次操作，每次可以：
1.M i K B 代表把第i个线性函数改为：fi(x)=kx+b 。
2.Q l r x 返回fr(fr-1(...fl(x))) mod 10^9+7 。n,m<=200000

线段树维护区间一次函数的复合。注意外层复合是右区间。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 201000 
#define mod 1000000007
struct func
{
    ll k,b;
    func(ll _k=0,ll _b=0):k(_k),b(_b){}
    func operator+(const func z) {return func(k*z.k%mod,(k*z.b+b)%mod);}
    ll calc(ll x){return (k*x+b)%mod;}
}t[N<<2];
void build(int pos,int l,int r)
{
    if(l==r)
    {
        scanf("%lld%lld",&t[pos].k,&t[pos].b);
        return ;
    }
    int mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    t[pos]=t[pos<<1|1]+t[pos<<1];
}
void fix(int pos,int l,int r,int x,int k,int b)
{
    if(l==r)
    {
        t[pos].k=k; t[pos].b=b;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) fix(pos<<1,l,mid,x,k,b);
    else fix(pos<<1|1,mid+1,r,x,k,b);
    t[pos]=t[pos<<1|1]+t[pos<<1];
}
func query(int pos,int l,int r,int x,int y)
{
    if(x<=l&&y>=r) return t[pos];
    int mid=(l+r)>>1;
    if(y<=mid) return query(pos<<1,l,mid,x,y);
    else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
    else return query(pos<<1|1,mid+1,r,x,y)+query(pos<<1,l,mid,x,y);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    char sw[8]; int a,b,c;
    while(m--)
    {
        scanf("%s%d%d%d",sw,&a,&b,&c);
        if(sw[0]=='M') fix(1,1,n,a,b,c);
        else printf("%lld\n",query(1,1,n,a,b).calc(c));
    }
    return 0;
}