Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF1558D Top-Notch Insertions

Posted on

dp+组合数学+线段树

学到了，学到了。

出题出$\sum m$的都是傻逼。

Solution

首先要明确的是方案数只能由最终数列的大小关系确定，中途无论怎么试着确定方案数都可能被后面几组给推翻。

首先发现最后的式子中一定存在$n-1$种大小关系，设其中有$c$个小于号，$n-c-1$个小于等于号，根据插板法，我们可以得出最后的答案为$C_{2n-c-1}^n$，详细来说就是对数组经行差分，因为最后一个数的大小小于等于$n$，所以我们强行增加一个$n+1$的位置，对于每个小于号，都必须比前面的数大一，所以我们强行给他们提前分配一个（注意，这个数列不能出现0，所以第一个数必须强制赋为1），它们就变成了小于等于号，那么答案为$C_{2n-1-c}^n$。

考虑算出$c$的个数，考虑倒序还原，如果有一个数前面插入了数，说明它前面这个符号一定是$<$，统计这样的数的个数即可（记得删除它前面的数），用线段树维护即可。

Code

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c)
    {
        if (c == '-')
            flag = 1;
        c = getchar();
    }
    while ('0' <= c && c <= '9')
        res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag)
        res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0)
        putchar('-'), res = -res;
    if (res > 9)
        write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s)
{
    while (*s)
        putchar(*s++);
}
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 2e5 + 5, mod = 998244353;
int n, m, T;
struct Node{
    int l, r, val;
    #define l(x) (x << 1)
    #define r(x) (x << 1 | 1)
}tr[N << 2];
void build(int x, int l, int r)
{
    tr[x].l = l, tr[x].r = r;
    tr[x].val = r - l + 1;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
}
inline int query(int x, int cnt)
{
    if(tr[x].l == tr[x].r) return tr[x].l;
    if(cnt > tr[l(x)].val) return query(x << 1 | 1, cnt - tr[l(x)].val);
    return query(x << 1, cnt);
}
inline void modify(int x, int l, int v)
{
    tr[x].val += v;
    if(tr[x].l == tr[x].r) return ;
    int mid = tr[x].l + tr[x].r >> 1;
    if(l <= mid) modify(x << 1, l, v);
    else modify(x << 1 | 1, l, v);
}
struct Ask{
    int x, y;
}q[N];
int a[N];
int fac[N << 1], inv[N << 1];
inline void init()
{
    fac[0] = 1;
    for(int i = 1;i < (N << 1);i ++) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[0] = inv[1] = 1;
    for(int i = 2;i < (N << 1);i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2;i < (N << 1);i ++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}
inline int C(int x, int y)
{
    if(y < 0 || x < y) return 0;
    return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int vis[N];
vector<int>s, t;
inline void work()
{
    read(n, m);
    for(int i : s) vis[i] = 0;
    for(int i : t) modify(1, i, 1);
    s.clear(), t.clear();
    for(int i = 1;i <= m;i ++) read(q[i].x, q[i].y);
    int res = 0;
    for(int i = m, l, r;i >= 1;i --)
    {
        l = query(1, q[i].y), r = query(1, q[i].y + 1);
        a[r] = 1;
        if(!vis[r]) s.push_back(r), res ++, vis[r] = 1;
        modify(1, l, -1);
        t.push_back(l);
    }
    write(C(n * 2 - res - 1, n), '\n');
}
int main()
{
    init();
    build(1, 1, N - 1);
    read(T);
    while(T --) work();
    return 0;
}