求函数【线段树】【2020牛客寒假算法基础集训营2】

 

首先，这个区间很容易让人想到是区间操作，那么就是来推公式吧。

我们从中不难发现，

从两个值到四个值

可以是相当于

其中，两个“[ ]”括号中的值是不是有点相似，我们是不是可以将它放在线段树上来进行维护了？

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 2e5 + 7;
const ll mod = 1e9 + 7;
int N, Q;
ll kk[maxN], bb[maxN];
ll tree[maxN << 2], sum[maxN << 2];
inline void pushup(int rt)
{
    sum[rt] = (tree[rsn] * sum[lsn] % mod - tree[rsn] + sum[rsn] + mod) % mod;
    tree[rt] = tree[lsn] * tree[rsn] % mod;
}
void buildTree(int rt, int l, int r)
{
    if(l == r)
    {
        tree[rt] = kk[l];
        sum[rt] = (kk[l] + bb[l]) % mod;
        return;
    }
    int mid = HalF;
    buildTree(Lson); buildTree(Rson);
    pushup(rt);
}
inline void update(int rt, int l, int r, int qx, ll k, ll b)
{
    if(l == r)
    {
        tree[rt] = k;
        sum[rt] = (k + b) % mod;
        return;
    }
    int mid = HalF;
    if(qx <= mid) update(Lson, qx, k, b);
    else update(Rson, qx, k, b);
    pushup(rt);
}
#define MP(a, b) make_pair(a, b)
pair<ll, ll> query(int rt, int l, int r, int ql, int qr)
{
    if(ql <= l && qr >= r)
    {
        return MP(sum[rt], tree[rt]);
    }
    int mid = HalF;
    if(qr <= mid) return query(QL);
    else if(ql > mid) return query(QR);
    else
    {
        pair<ll, ll> ans_L, ans_R;
        ans_L = query(QL);
        ans_R = query(QR);
        return MP((ans_R.second * ans_L.first % mod - ans_R.second + ans_R.first + mod) % mod, ans_L.second * ans_R.second % mod);
    }
}
int main()
{
    scanf("%d%d", &N, &Q);
    for(int i=1; i<=N; i++) scanf("%lld", &kk[i]);
    for(int i=1; i<=N; i++) scanf("%lld", &bb[i]);
    buildTree(1, 1, N);
    int op, i, k, b, l, r;
    while(Q--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d%d", &i, &k, &b);
            update(1, 1, N, i, k, b);
        }
        else
        {
            scanf("%d%d", &l, &r);
            printf("%lld\n", query(1, 1, N, l, r).first);
        }
    }
    return 0;
}
/*
2 3
1 1
1 0
1 2 114514 1919810
2 1 2
2 1 1
*/