2020牛客寒假算法基础集训营2 - 求函数 - 线段树维护组合函数

题目链接：https://ac.nowcoder.com/acm/contest/3003/J
题目大意：


思路：

#include<bits/stdc++.h>
#define LL long long
#define mid (l+r)/2
using namespace std;
const LL mod = 1e9+7;

struct Node{
    int l, r;
    LL ks, bs;
}node[5000000];

LL b[200005], k[200005];
void BT(int i, int l, int r){
    node[i].l=l; node[i].r=r;
    if(l==r){
        node[i].ks=k[l]; node[i].bs=b[l];
        return ;
    }
    BT(i<<1, l, mid); BT((i<<1)+1, mid+1, r);
    node[i].ks=node[i<<1].ks*node[(i<<1)+1].ks%mod;
    node[i].bs=(node[i<<1].bs*node[(i<<1)+1].ks%mod+node[(i<<1)+1].bs)%mod;
}

void gx(int i, int x, LL k, LL b){
    if(node[i].l==node[i].r){
        node[i].ks=k; node[i].bs=b;
        return ;
    }
    if(x<=(node[i].l+node[i].r)/2){
        gx(i<<1, x, k, b);
    }
    else{
        gx((i<<1)+1, x, k, b);
    }
    node[i].ks=node[i<<1].ks*node[(i<<1)+1].ks%mod;
    node[i].bs=(node[i<<1].bs*node[(i<<1)+1].ks%mod+node[(i<<1)+1].bs)%mod;
    //cout<<node[i].l<<" "<<node[i].r<<" "<<node[i].ks<<" "<<node[i].bs<<endl;
}

LL ansk=1, ansb=0;
void cx(int i, int l, int r){

    if(node[i].l==l&&node[i].r==r){
        ansk=ansk*node[i].ks%mod;
        ansb=(ansb*node[i].ks%mod+node[i].bs)%mod;
        return ;
    }
    if(r<=(node[i].l+node[i].r)/2) cx(i<<1, l, r);
    else if(l>(node[i].l+node[i].r)/2) cx((i<<1)+1, l, r);
    else cx(i<<1, l, (node[i].l+node[i].r)/2), cx((i<<1)+1, (node[i].l+node[i].r)/2+1, r);
}

int main(){

    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld", &k[i]);
    }
    for(int i=1; i<=n; i++){
        scanf("%lld", &b[i]);
    }
    BT(1, 1, n);
    while(m--){
        int op;
        scanf("%d", &op);
        if(op==1){
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            gx(1, x, y, z);
        }
        else{
            int x, y;
            scanf("%d%d", &x, &y);
            ansk=1; ansb=0;
            cx(1, x, y);
            printf("%lld\n", (ansk+ansb)%mod);
        }
    }

    return 0;
}