题目描述

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 。

Input

第一行两个整数n, m (1 <= n, m <= 200,000)。
接下来n行，每行两个整数ki, bi。
接下来m行，每行的格式为M i K B或者Q l r x。

Output

对于每个Q操作，输出一行答案。

Sample Input

5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4

Sample Output

1825
17
978
98

HINT

1 <= n, m <= 200,000，0 <= k, b, x < 1000,000,007

题目分析

随便指定一个l,r 展开fr(fr-1(...fl(x)))后发现 这玩意能用线段树分两部分维护
然后就是裸线段树了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
typedef long long ll;
ll mod=1000000007,k[200100],b[200100];
struct your
{
    int x,y;
    long long k,b;
}a[200100*4];
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy) 
    {
        a[num].k=k[dx]%mod,a[num].b=b[dx]%mod;
        return ;
    }
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
    a[num].k=a[num<<1].k*a[num<<1|1].k%mod;
    a[num].b=(a[num<<1].b*a[num<<1|1].k%mod+a[num<<1|1].b)%mod;
}
void update(int dx,ll c,ll v,int num)
{
    if(a[num].x==dx&&a[num].y==dx)
    {
        a[num].k=c%mod,a[num].b=v%mod;
        return ;
    }
    int mid=(a[num].x+a[num].y)>>1;
    if(dx<=mid) update(dx,c,v,num<<1);
    else update(dx,c,v,num<<1|1);
    a[num].k=a[num<<1].k*a[num<<1|1].k%mod;
    a[num].b=(a[num<<1].b*a[num<<1|1].k%mod+a[num<<1|1].b)%mod;
}
char s[10];
your ask(int dx,int dy,int num)
{
    if(a[num].x==dx&&a[num].y==dy) return a[num];
    int mid=(a[num].x+a[num].y)>>1;
    if(dy<=mid) return ask(dx,dy,num<<1);
    else if(dx>mid) return ask(dx,dy,num<<1|1);
    else
    {
        your tmp=ask(dx,mid,num<<1);
        your nmp=ask(mid+1,dy,num<<1|1);
        tmp.k=tmp.k*nmp.k%mod;
        tmp.b=(tmp.b*nmp.k%mod+nmp.b)%mod;
        return tmp;
    }
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&k[i],&b[i]);
    build(1,n,1);
    for(int x,y,i=1;i<=m;i++)
    {
        long long c,v;
        scanf("%s",&s[0]);      
        if(s[0]=='M') scanf("%d%lld%lld",&x,&c,&v),update(x,c,v,1);
        else
        {
            scanf("%d%d%lld",&x,&y,&c);
            your tmp=ask(x,y,1);
            long long sum=(c%mod*tmp.k%mod+tmp.b)%mod;
            printf("%lld\n",sum);
        }
    }
    return 0;
}