9.15 腾讯笔试-技术研究T5 区间选点方案数 动态规划

大致题意是说给出位置1~n，以及m个闭区间，在每个位置上放置0或者1，要求每一个闭区间至少包含一个1，求合法的放置方案总数（）。

笔试的前面四题都很好解决，当时对第五题干想了很久没有思路，最后部分分也没骗出来。作为前ACMer感觉有点失落，又抽空花了几小时想了想，总算可以给一个解法。

首先按区间的右端点进行从小到大排序，右端点相同的情况下左端点从大到小排序。接着排除发生区间包含的情况（如果出现包含，显然只需要保留被包含的区间即可），即排序后遍历，去掉让左端点不递增的区间。于是筛选后的所有个区间，只会出现区间交叉的情况，左端点和右端点都是严格递增的。

现在我们考虑二维dp（当时一直没往二维状态上想，下意识觉得时间复杂度不够TAT）。

代表考虑前i个区间，在位置1~j上非法（即至少有一个区间都是0）的放置方案数（没有包含在的位置默认取值0）。注意这里我们把状态设置为答案的反面，最后答案用去减即可。

假设第个区间是，接下来考虑三种可能的状态转移：

情况1：，此时显然有

情况2：，此时我们做一个简单容斥，即的区间非法方案数，加上本区间全0的方案数，减去本区间全0且中至少有个全0区间的方案数： = +

情况3：，即当前区间在考虑的范围之外；当前区间一定非法，那么可以随意取值，

最终的答案为。

现在我们可以有一个复杂度的算法了，考虑到有效状态很稀疏，如果用记忆化搜索会很快，但最差的情况仍然会超时。

仔细观察递推式，发现最重要的情况2，实际上可以看作是加上了一个和无关的常数，因此情况2等价于对于对的值加上了定值，这种区间加法可以用线段树或者树状数组来优化。

对于情况1，我们发现对于每一个，我们不用求出所有的值，只需要求对应的值即可满足之后的dp需要，由于我们是按照右端点增序进行遍历的，那么每一个都暴力更新这些值，总的更新次数等于。

对于情况3，实际上我们发现由于最后的不会来自于情况3，而情况1和2的更新过程中，子问题也不会出现需要求情况3的时候（注意我们一开始处理得到左端点增序的条件，否则会涉及到情况3），所以我们可以不求的dp值。

综上这是一个数据结构优化更新的动态规划，时间复杂度为。

#include <cstdio>
#include <algorithm>

using namespace std;
using LL = long long;

constexpr int mo = 1000000007;

int quick_power(int a, int b) {
    int base = a, res = 1;
    while (b) {
        if (b & 1)
            res = (LL) res * base % mo;
        base = (LL) base * base % mo;
        b >>= 1;
    }
    return res;
}

struct SegmentTree {
    int addv[1 << 18];

#define M ((L+R)>>1)
#define kl (k<<1)
#define kr (k<<1|1)

    void build_tree(int k, int L, int R) {
        addv[k] = 0;
        if (L == R)
            return;
        build_tree(kl, L, M);
        build_tree(kr, M + 1, R);
    }

    void add(int k, int L, int R, int l, int r, int v) {
        if (l <= L && R <= r) {
            addv[k] = (addv[k] + v) % mo;
            return;
        }
        if (l <= M)
            add(kl, L, M, l, r, v);
        if (r > M)
            add(kr, M + 1, R, l, r, v);
    }

    int query(int k, int L, int R, int pos) {
        if (L == R)
            return addv[k];
        if (pos <= M)
            return query(kl, L, M, pos) + addv[k];
        else
            return query(kr, M + 1, R, pos) + addv[k];
    }
};

int n, m;
SegmentTree st;
pair<int, int> intervals[100005];

//#define DEBUG
//#define RAND_INPUT

int main() {
#ifndef RAND_INPUT
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &intervals[i].first, &intervals[i].second);
#else
    srand(time(nullptr));
    n = rand() % 29 + 1;
    m = rand() % (2 * n);
    printf("%d %d\n", n, m);
    for (int i = 1; i <= m; i++) {
        intervals[i] = {rand() % n + 1, rand() % n + 1};
        if (intervals[i].first > intervals[i].second)
            swap(intervals[i].first, intervals[i].second);
        printf("%d %d\n", intervals[i].first, intervals[i].second);
    }
#endif
    sort(intervals + 1, intervals + m + 1, [&](const pair<int, int> &x, const pair<int, int> &y) {
        return x.second < y.second || x.second == y.second && x.first > y.first;
    });
    st.build_tree(1, 1, n);
    int max_left = 0;
    for (int i = 1; i <= m; i++) {
        auto [l, r] = intervals[i];
        if (max_left < l) {
            max_left = l;
            int temp = (quick_power(2, l - 1) - (l == 1 ? 0 : st.query(1, 1, n, l - 1)) + mo) % mo;
            st.add(1, 1, n, l, r, temp);
        }
        int nxt_r = i == m ? n : intervals[i + 1].second, v = st.query(1, 1, n, r);
        for (int j = r + 1; j <= nxt_r; j++) {
            v = v * 2 % mo;
            st.add(1, 1, n, j, j, v);
        }
    }
    printf("%d\n", (quick_power(2, n) - st.query(1, 1, n, n) + mo) % mo);
#ifdef DEBUG
    int cnt = 0;
    for (int i = 0; i < 1 << n; i++) {
        bool f = true;
        for (int j = 1; j <= m && f; j++) {
            auto [l, r] = intervals[j];
            if ((i >> r) << r - l + 1 == i >> l - 1)
                f = false;
        }
        cnt += f;
    }
    printf("%d", cnt);
#endif
    return 0;
}

核心思路即80-98行。