yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P6144 Help Yourself 题解

发表于 更新于 分类于

P6144 Help Yourself 题解

应该是第一次在学校午自习时卷OI（然后sxy走进来看了我一眼啥也没说）

题面

题目链接

解法

对于这种若干区间求值的题目，肯定先按照左端点或者右端点排个序。

不妨先来考虑对于$k=1$的情况dp状态怎么设。套路地设$dp_i$表示以$i$为当前覆盖的最右端点的联通块数目之和，下面要加入一条线段$[l,r]$，思考插入这条线段对$dp$值的影响。对于$i\lt r$的所有$dp_i$不会被影响，而对每个$0 \le i \lt l$，$dp_r$的值需加上$dp_i + 1$，对每个$l \le i \lt r$，$dp_r$的值需加上$dp_i$。最后对于$i \gt r$，显然插入这么一条线段不会影响到其右断点，但取该线段和不取该线段各有一种可能，所以要将整个区间乘上2.

分析到这里，如何维护$dp$就一目了然了：使用线段树维护单点加法和区间乘法以及区间求和即可。

接下来计算$k \neq 1$的情况。不难发现每个$dp{k,i}$都可以被表示成$\sum\limits_i{b_i^k}$的形式（$b_i$是每种子集的联通块数目）。而区间乘上2直接做，求和也直接线段树，求$\sum\limits{i=0}^{l-1}{(dp{k,i}+1)}$用二项式定理拆开得到$\sum\limits{j=0}^{k}\sum\limits{i=0}^{l-1}{\binom{k}{j} \times dp{j,i}}$即可得到答案。

所以时间复杂度$O(k^2n\log{n})$随便过。这比前面两道黑题好些多了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/**
 * @file:           P6144.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P6144
*/
// #pragma GCC optimize ("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 1e5 + 10;
const int MAXM = 2e5 + 10;
const int MAXK = 11;
const int INFL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int add(int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}
struct node {
    int l, r;
    bool operator<(const node &o) const {
        return l == o.l ? r < o.r : l < o.l;
    }
};
#define li (i << 1)
#define ri (i << 1) | 1
#define lson li, l, mid
#define rson ri, mid + 1, r
struct segment_tree {
    int sum[MAXM * 4], tag[MAXM * 4];
    void pushup(int i) {
        sum[i] = add(sum[li], sum[ri]);
    }
    void getdown(int i, int val) {
        sum[i] = sum[i] * val % MOD;
        tag[i] = tag[i] * val % MOD;
    }
    void pushdown(int i) {
        if (tag[i] != 1) {
            getdown(li, tag[i]);
            getdown(ri, tag[i]);
            tag[i] = 1;
        }
    }
    void build(int i, int l, int r, int x) {
        sum[i] = 0; tag[i] = 1;
        if (l == r)
            return void(sum[i] = x);
        int mid = (l + r) >> 1;
        build(lson, x), build(rson, x);
        pushup(i);
    }
    void update(int i, int l, int r, int q, int val) {
        if (l == r)
            return void(sum[i] = add(sum[i], val));
        int mid = (l + r) >> 1;
        pushdown(i);
        if (q <= mid)
            update(lson, q, val);
        else
            update(rson, q, val);
        pushup(i);
    }
    void modify(int i, int l, int r, int ql, int qr, int val) {
        if (ql > qr)
            return;
        if (ql <= l && r <= qr)
            return getdown(i, val);
        int mid = (l + r) >> 1;
        pushdown(i);
        if (ql <= mid)
            modify(lson, ql, qr, val);
        if (qr > mid)
            modify(rson, ql, qr, val);
        pushup(i);
    }
    int query(int i, int l, int r, int ql, int qr) {
        if (ql > qr)
            return 0;
        if (ql <= l && r <= qr)
            return sum[i];
        int mid = (l + r) >> 1, ret = 0;
        pushdown(i);
        if (ql <= mid)
            ret = add(ret, query(lson, ql, qr));
        if (qr > mid)
            ret = add(ret, query(rson, ql, qr));
        return ret;
    }
};
int n, m, k, c[MAXK][MAXK];
node a[MAXN];
segment_tree tr[MAXK];
signed main() {
    read(n), read(k), m = n * 2;
    for (int i = 1; i <= n; ++i)
        read(a[i].l), read(a[i].r);
    sort(a + 1, a + n + 1);
    c[0][0] = 1;
    for (int i = 1; i <= k; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j)
            c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
    }
    for (int i = 0; i <= k; ++i)
        tr[i].build(1, 0, m, 0);
    tr[0].update(1, 0, m, 0, 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = k; j >= 0; --j) {
            int sum = 0;
            for (int l = 0; l <= j; ++l)
                sum = add(sum, c[j][l] * tr[l].query(1, 0, m, 0, a[i].l - 1) % MOD);
            sum = add(sum, tr[j].query(1, 0, m, a[i].l, a[i].r));
            tr[j].update(1, 0, m, a[i].r, sum);
            tr[j].modify(1, 0, m, a[i].r + 1, m, 2);
        }
    }
    write(tr[k].query(1, 0, m, 1, m)), putchar('\n');
    return 0;
}