2020牛客寒假算法基础训练营Day2 - J 求函数

传送门：Day2 - J

题目描述

输入描述

第一行，两个正整数 n,m
第二行，n个整数$k_1,k_2,…k_n$
第三行，n个整数$b_1,b_2,…b_n$
接下来m行，操作格式如上
保证$1<=n,m<=2×10^5$,$0<=k_i,b_i<=10^9+7$

输出描述

对于每个求值操作，输出一行一个整数，表示答案。

思路分析

难点在于如何合并两个子节点

样例输入

2 3
1 1
1 0
1 2 114514 1919810
2 1 2
2 1 1

样例输出

2148838
2

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define int long long
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;


int ans,n,m;
int k[N],b[N];

struct node {
    int l,r,k,b;
    int mid() {
        return (l+r)/2;
    }
} tree[N*4];

void pushup(int x) {
    tree[x].k=(tree[x*2].k*tree[x*2+1].k%mod)%mod;
    tree[x].b=(tree[x*2+1].k*tree[x*2].b%mod+tree[x*2+1].b)%mod;
}

void build(int x,int l,int r) {
    tree[x].l=l;
    tree[x].r=r;
    if(l==r) {
        tree[x].k=k[l];
        tree[x].b=b[l];
        return ;
    }
    int mid=tree[x].mid();
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);

}

void update(int x,int pos,int k,int b) {
    if(tree[x].l==tree[x].r && tree[x].l==pos) {
        tree[x].k=k;
        tree[x].b=b;
        return ;
    }
    int mid=tree[x].mid();
    if(pos<=mid)
        update(x*2,pos,k,b);
    if(pos>mid)
        update(x*2+1,pos,k,b);
    pushup(x);
}

void query(int x,int l,int r) {
    if(l<=tree[x].l && tree[x].r <=r) {
        ans=(ans*tree[x].k%mod+tree[x].b)%mod;
        return ;
    }
    int mid=tree[x].mid();
    if(l<=mid)
        query(x*2,l,r);
    if(r>mid)
        query(x*2+1,l,r);

}

signed main() {
    IOS;
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>k[i];
    for(int i=1; i<=n; i++) cin>>b[i];
    build(1,1,n);
    for(int i=1; i<=m; i++) {
        int op,x,y,z;
        cin>>op;
        if(op==1) {
            cin>>x>>y>>z;
            update(1,x,y,z);
        } else {
            cin>>x>>y;
            ans=1;
            query(1,x,y);
            cout<<ans%mod<<endl;
        }
    }
    return 0;




    return 0;
}