泉暖涵窗镜(Mirror) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const long long MOD = 1000000007LL;

struct SegTree {
    int n;
    vector<long long> tree, lz;
    SegTree(int n_val) : n(n_val), tree(4 * n_val + 5, 0), lz(4 * n_val + 5, 1) {}
    void apply(int node, long long mul) {
        tree[node] = (tree[node] * mul) % MOD;
        lz[node] = (lz[node] * mul) % MOD;
    }
    void push(int node) {
        if (lz[node] != 1) {
            apply(node << 1, lz[node]);
            apply(node << 1 | 1, lz[node]);
            lz[node] = 1;
        }
    }
    void range_mul(int node, int l, int r, int ql, int qr, long long mul) {
        if (ql <= l && r <= qr) {
            apply(node, mul);
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        if (ql <= mid) range_mul(node << 1, l, mid, ql, qr, mul);
        if (qr > mid) range_mul(node << 1 | 1, mid + 1, r, ql, qr, mul);
        tree[node] = (tree[node << 1] + tree[node << 1 | 1]) % MOD;
    }
    void point_add(int node, int l, int r, int idx, long long val) {
        if (l == r) {
            tree[node] = (tree[node] + val) % MOD;
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        if (idx <= mid) point_add(node << 1, l, mid, idx, val);
        else point_add(node << 1 | 1, mid + 1, r, idx, val);
        tree[node] = (tree[node << 1] + tree[node << 1 | 1]) % MOD;
    }
    long long point_query(int node, int l, int r, int idx) {
        if (l == r) return tree[node];
        push(node);
        int mid = (l + r) >> 1;
        if (idx <= mid) return point_query(node << 1, l, mid, idx);
        else return point_query(node << 1 | 1, mid + 1, r, idx);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> b(m + 1);
    for (int i = 1; i <= m; ++i) cin >> b[i];
    SegTree seg(m);
    for (int x : a) {
        auto it = lower_bound(b.begin() + 1, b.end(), x);
        int pos = (int)(it - b.begin());
        long long add_val = 0;
        bool match = (pos <= m && b[pos] == x);
        if (match) {
            add_val = (pos == 1) ? 1LL : seg.point_query(1, 1, m, pos - 1);
        }
        if (pos <= m) {
            seg.range_mul(1, 1, m, pos, m, 2LL);
        }
        if (match) {
            seg.point_add(1, 1, m, pos, add_val);
        }
    }
    cout << seg.point_query(1, 1, m, m) << "\n";
    return 0;
}