题解 | 子数列求积

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
struct node {
    int l, r, sum;
} tree[4 * 100010];
const int mod = 1e9 + 7;
void slove() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    auto build = [&](auto&& build, int p, int l, int r)->void{
        tree[p].l = l, tree[p].r = r;
        if (l == r) {
            tree[p].sum = a[l] % mod;
            return ;
        }
        int mid = l + r >> 1;
        build(build, p * 2, l, mid);
        build(build, p * 2 + 1, mid + 1, r);
        tree[p].sum = (tree[p * 2].sum* tree[p * 2 + 1].sum) % mod;
    };
    build(build, 1, 1, n);
    auto qurey = [&](auto&& qurey, int p, int l, int r)->int{
        if (tree[p].l >= l && tree[p].r <= r) return tree[p].sum;
        int ans = 1LL;
        int mid = tree[p].l + tree[p].r >> 1;
        if (mid >= l) ans = (ans * qurey(qurey, p * 2, l, r)) % mod;
        if (mid < r) ans = (ans * qurey(qurey, p * 2 + 1, l, r)) % mod;
        return ans % mod;
    };
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << qurey(qurey, 1, l, r) << " ";
    }
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    //std::cin>>T;
    while (T--)    {
        slove();
    }
    return 0;
}

流口水了，写个线段树仅供参考。