且听疯吟

【google】 google

2022-11-20

Google mock view

前段时间做了一下google的mock interview,其中有道题目印象深刻。

1. 区间查询

题目

给定长度为n的数组A，给定组数$[i,j]$，求以下结果:
$$
query(i,j) = \prod_{k=1}^{j-i+1}(A_{i+k-1}^{k})
$$
所求结果对$10^{9} + 7$取模, 其中满足以下：

  • $i \le j$
  • $1 \le n \le 10^{5}$
  • $0 \le A[i] \le 10^{9}$

地址

https://leetcode-cn.com/problems/truncate-sentence

题意

线段树

解题思路

  1. 首先看到类似的求区间的数列我们首先想到的就是用线段树。我们首先用数学分解的方法来将公式进行分解和变换：
    $$
    A[i,j] = \prod_{k=i}^{j}(A_{k}^{k-i+1}) \
    = \prod_{m=i}^{s-1}(A_{m}^{m+1-i}) * \prod_{n=s}^{j}(A_{n}^{n+1-i}) \
    = \prod_{m=i}^{s-1}(A_{m}^{m+1-i}) * \prod_{n=s}^{j}(A_{n}^{n+1-s})*(\prod_{n=s}^{j}A_{n})^{s-i} \
    $$
    由上述变换我们就可以知道如何通过线段树对其进行分解，我们设线段树的每个非叶子节点，包含的范围为$(i,j)$,且包含两个值：
    $$
    prod_{(i,j)} = \prod_{k=i}^{j}A_{k}\
    val_{(i,j)} = \prod_{k=i}^{j}A_{k}^{k+1-i}\
    $$
    有了上述变换以后我们可以知道线段树的变化，假如本次我们需要查询的区间为$(i,j)$,假设线段从$mid$处断开分为两个子节点，则我们可以知道如下的求和公式：
    $$
    prod_{(i,j)} = \prod_{k=i}^{j}A_{k} = \prod_{k=i}^{mid}A_{k}*\prod_{k=mid+1}^{j}A_{k} \
    = prod_{(i,mid)}prod_{(mid+1,j)} \
    $$
    而$val$可以变换如下：
    $$
    val_{(i,j)} = \prod_{k=i}^{j}A_{k}^{k+1-i} = \prod_{k=i}^{mid}(A_{k}^{k+1-i}) * \prod_{k=mid+1}^{j}(A_{k}^{k+1-i}) \
    = \prod_{k=i}^{mid}(A_{k}^{k+1-i}) * \prod_{k=mid+1}^{j}(A_{k}^{k+1-(mid+1)})    (\prod_{k=mid+1}^{j}A_{k})^{mid+1-i} \
    = val_{(i,mid)}val_{(mid+1,j)}(prod_{(mid+1,j)})^{mid+1-i}
    $$
    根据以上变换，我们则可以轻易的用线段树可以在$lg(n)$的时间复杂度内求出所有的查询。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
long long MOD = 1e9 + 7;
const long long MAXN = 2000000;
struct segTreeNode{
    long long val;
    long long prod;
    int l;
    int r;
};

#define CHL(x) (x*2)
#define CHR(x) (x*2+1)
segTreeNode tree[MAXN];

long long fastpow(long long x,long long y,long long mod){
    long long ret = 1;
    for(int i = y; i != 0; i >>= 1){
        if(i&1) ret = (ret*x)%mod;
        x = (x*x)%mod;
    }
    return ret;
}

bool pushUpTree(int idx){
    int mid = (tree[idx].l + tree[idx].r)>>1;
    int d = mid - tree[idx].l + 1;
    long long pl = tree[CHL(idx)].prod;
    long long pr = tree[CHR(idx)].prod;
    tree[idx].prod = pl*pr%MOD;
    tree[idx].val = tree[CHL(idx)].val*tree[CHR(idx)].val*fastpow(pr,d,MOD)%MOD;
    return true;
}

bool buildTree(int l,int r,vector<int> & arr,int idx){
    if(l > r) return false;
    tree[idx].l = l;
    tree[idx].r = r;
    tree[idx].val = 1;
    tree[idx].prod = 1;
    if(l == r){
        tree[idx].val = arr[l];
        tree[idx].prod = arr[l];
        return true;
    }

    int mid = (l+r)>>1;
    buildTree(l,mid,arr,CHL(idx));
    buildTree(mid+1,r,arr,CHR(idx));
    pushUpTree(idx);
    return true;
}

long long queryTree(int l,int r,int idx){
    if(tree[idx].r < l || tree[idx].l > r) return 1;
    if(l <= tree[idx].l &&  tree[idx].r <= r){
        long long d = tree[idx].l - l;
        return tree[idx].val*fastpow(tree[idx].prod,d,MOD)%MOD;
    }

    int mid = (tree[idx].l + tree[idx].r)>>1;
    if(l > mid){
        return queryTree(l,r,CHR(idx));
    }else if(r <= mid){
        return queryTree(l,r,CHL(idx));
    }else{
        long long lval = queryTree(l,r,CHL(idx));
        long long rval = queryTree(l,r,CHR(idx));
        return lval*rval%MOD;
    }
}

int main(){
    int n;
    int t;
    int l,r;
    memset(tree,0,sizeof(tree));
    cin>>n;
    vector<int> arr = vector<int>(n);
    for(int i = 0; i < n; ++i) cin>>arr[i];
    buildTree(0,n-1,arr,1);
    cin>>t;
    for(int i = 0; i < t; ++i){
        cin>>l>>r;
        l--;
        r--;
        cout<<queryTree(l,r,1)<<endl;
    }
    return 0;
}

欢迎关注和打赏，感谢支持！

Tags: 算法
← 【kickstart】 kick start 2021 roundB 【kick start】 2021 google kickstart round H →

扫描二维码，分享此文章