CF2063F2 F2. Counting Is Not Fun (Hard Version)题解

F2. Counting Is Not Fun (Hard Version)

题目翻译

​ 题目给我们一个数字n，代表一个有着n个好对的括号序列，一个好对（i, j) (i < j) 满足s[i] == ‘(‘, s[j] == ‘)’同时去掉i，j两个字符，区间内剩余的子串是一个合法的平衡括号字符串，可以证明对于一个长度位2 * n的括号序列一定有n个好对。题目依次给出n个好对，我们需要计算出前i个好对确定的情况下有多少种符号要求的合法括号字符串（i从0到n）。

思路

​ 与easy版本不同的是hard版的数据到达了3e5，首先我们easy版计算长度为x的合法括号序列的复杂度我们就无法接受，考虑如何快速计算，这实际上就是卡特兰数，我们的平衡度总是大于等于0，最后等于0，相当于不穿过y = x，走到（x / 2， x / 2），我们可以世界使用卡特兰数的组合数学公式来快速计算。

​ 接着考虑如何计算每个前缀好对的可能的括号序列数，注意到easy版我们对每个都进行了重新计算，这实际上没有必要，因为我们新加入一个好对只会影响最小的覆盖其的好对，重新计算它的贡献，然后乘上新加入的好对的贡献即可。要知道最小覆盖其的好对我们可以使用一个线段树维护覆盖某个点的长度最小的对的序号即可，这实际上相当于线段树维护最小值。知道某个好对还没被覆盖的点的个数我们可以使用令一个线段树维护区间最小值和这个区间最小值的个数即可，考虑某个好对，覆盖其的好对一定不会计算到其中，之后其中的好对非区间最小值的一定被覆盖了，而区间最小值一定没有被覆盖。我们重新计算新加入好对及覆盖其的好对的贡献即可。

​ 本题实际上有一个更为简单的实现，倒着求答案，看作删除一个好对，这相当于把删除的好对和最小覆盖其的好对合并到了一起，抽象成图论可以看作缩点，其覆盖的子好对顺着转移过去即可，使用并查集维护节点，同时维护某个好对覆盖的子对长度和即可简单实现计算。

代码

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
const int N = 2e6 + 10; //注意这里要多开点
const int mod = 998244353;
ll fact[N + 1],infact[N + 1];   //  阶乘和阶乘的逆元
//取模版本快速幂
ll qmi(ll a, ll k, ll m){   //求a^k mod m
    a %= m;
    ll res = 1 % m;
    while (k)
    {
        if (k&1) res = res * a % m;//指数k为1的位乘上a^(1<<x)mod m
        a = a * a % m;//每一项是前一项的平方模m
        k >>= 1;
    }
    return res;
}
//初始化阶乘
void init(int n = N){ // 预处理阶乘取模的余数和阶乘取模余数的逆元
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        fact[i] = fact[i - 1] * i % mod;
    }
    infact[N] = qmi(fact[N], mod - 2, mod);
    for(int i = N - 1; i >= 0; i--){
        infact[i] = infact[i + 1] * (i + 1) % mod;
    }
}
//组合数A和C
//C(a, b) = !a / !(a - b) * !(b)    //a个里挑b个
//A(a, b) = !a / !(a - b)
ll C(int a,int b){
    return fact[a] * infact[a-b] % mod * infact[b] % mod;
}   

ll A(int a, int b){    
    return fact[a] * infact[a-b] % mod;
}
//求逆元
ll contary(ll now){
    return qmi(now, mod - 2, mod);
}
//暴力计算组合数C
ll burteC(int m, int k) {
    if (m < k || k < 0) return 0;
    ll ret = 1;
    for(int i = 1; i <= k; i ++) ret = ret * (m - i + 1) % mod;
    for(int i = 1; i <= k; i ++) ret = ret * qmi(i, mod - 2, mod) % mod;
    return ret;
}

ll getCn(int n){
    if(n == 0)
        return 1;
    return (C(2 * n, n) - C(2 * n, n - 1) + mod) % mod;
}

template<class T>
class SegmentTree{
private:
    int n;
    struct node{
        T minn;
        T val;
    };
    std::vector<node> tree;
    std::vector<T> tag;
    std::vector<T> a;
 
    int ls(int p){
        return p << 1;
    }
 
    int rs(int p){
        return p << 1 | 1;
    }
 
    node merge(node a, node b){
        auto res = node();
        res.minn = std::min(a.minn, b.minn);
        if(a.minn == res.minn)
            res.val += a.val;
        if(b.minn == res.minn)
            res.val += b.val;
        return res;
    }
 
    void push_up(int p){
        tree[p] = merge(tree[ls(p)], tree[rs(p)]);
    }
    
    void build(int p, int pl, int pr){
        if(pl == pr){
            tree[p] = node();
            tree[p].val = 1;
            tree[p].minn = 0;
            return;
        }
        int mid = (pl + pr) >> 1;
        build(ls(p), pl, mid);
        build(rs(p), mid + 1, pr);
        push_up(p);
    }
 
    void add(node& p, T d){
        p.minn += d;
    }
 
    void addtag(int p, int pl, int pr, T d){
        tag[p] += d;
        add(tree[p], d);
    }
 
    void push_down(int p, int pl, int pr){
        if(tag[p]){
            int mid = (pr + pl) >> 1;
            addtag(ls(p), pl, mid, tag[p]);
            addtag(rs(p), mid + 1, pr, tag[p]);
            tag[p] = 0;
        }
    }
 
    void update(int L, int R, int p, int pl, int pr, T d){
        if(L <= pl && pr <= R){
            addtag(p, pl, pr, d);
            return;
        }
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid)
            update(L, R, ls(p), pl, mid, d);
        if(R > mid)
            update(L, R, rs(p), mid + 1, pr, d);
        push_up(p);
    }
 
    node query(int L, int R, int p, int pl, int pr){
        if(L <= pl && pr <= R)
            return tree[p];
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid && R > mid)
            return merge(query(L, R, ls(p), pl, mid), query(L, R, rs(p), mid + 1, pr));
        if(L <= mid)
            return query(L, R, ls(p), pl, mid);
        if(R > mid)
            return query(L, R, rs(p), mid + 1, pr);
    }
 
public:
 
    void update(int L, int R, T d){
        update(L, R, 1, 0, n, d);
    }
 
    node query(int L, int R){
        return query(L, R, 1, 0, n);
    }
 
    SegmentTree(int len){
        n = len;
        tree.assign((n + 2) << 2, node());
        tag.assign((n + 2) << 2, 0);
        build(1, 0, n);
    }
 
    SegmentTree(std::vector<T> cur){
        //cur 是 1序列
        int len = cur.size() - 1;
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
        a = cur;
        build(1, 1, n);
    }
};


std::vector<std::pair<int, int>> cur;

template<class T>
class SegmentTreeInd{
private:
    int n;
    struct node{
        T minind;
    };
    std::vector<node> tree;
    std::vector<T> tag;
    std::vector<T> a;
 
    int ls(int p){
        return p << 1;
    }
 
    int rs(int p){
        return p << 1 | 1;
    }
 
    node merge(node a, node b){
        auto res = node();
        if(cur[a.minind].ss - cur[a.minind].ff <= cur[b.minind].ss - cur[b.minind].ff)
            res = a;
        else
            res = b;
        return res;
    }
 
    void push_up(int p){
        tree[p] = merge(tree[ls(p)], tree[rs(p)]);
    }
    
    void build(int p, int pl, int pr){
        if(pl == pr){
            tree[p] = node();
            tree[p].val = a[pl];
            return;
        }
        int mid = (pl + pr) >> 1;
        build(ls(p), pl, mid);
        build(rs(p), mid + 1, pr);
        push_up(p);
    }
 
    void add(node& p, T d){
        if(cur[p.minind].ss - cur[p.minind].ff >= cur[d].ss - cur[d].ff)
            p.minind = d;
    }
 
    void addtag(int p, int pl, int pr, T d){
        if(cur[tag[p]].ss - cur[tag[p]].ff >= cur[d].ss - cur[d].ff)
            tag[p] = d;
        add(tree[p], d);
    }
 
    void push_down(int p, int pl, int pr){
        if(tag[p]){
            int mid = (pr + pl) >> 1;
            addtag(ls(p), pl, mid, tag[p]);
            addtag(rs(p), mid + 1, pr, tag[p]);
            tag[p] = 0;
        }
    }
 
    void update(int L, int R, int p, int pl, int pr, T d){
        if(L <= pl && pr <= R){
            addtag(p, pl, pr, d);
            return;
        }
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid)
            update(L, R, ls(p), pl, mid, d);
        if(R > mid)
            update(L, R, rs(p), mid + 1, pr, d);
        push_up(p);
    }
 
    node query(int L, int R, int p, int pl, int pr){
        if(L <= pl && pr <= R)
            return tree[p];
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid && R > mid)
            return merge(query(L, R, ls(p), pl, mid), query(L, R, rs(p), mid + 1, pr));
        if(L <= mid)
            return query(L, R, ls(p), pl, mid);
        if(R > mid)
            return query(L, R, rs(p), mid + 1, pr);
    }
    
public:
    
    void update(int L, int R, T d){
        update(L, R, 1, 1, n, d);
    }
 
    node query(int L, int R){
        return query(L, R, 1, 1, n);
    }
 
    SegmentTreeInd(int len){
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
    }
 
    SegmentTreeInd(std::vector<T> cur){
        //cur 是 1序列
        int len = cur.size() - 1;
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
        a = cur;
        build(1, 1, n);
    }
};


void solve(){
    int n;
    std::cin >> n;
    cur.assign(n + 1, std::pair<int, int>());
    cur[0] = {0, 2 * n + 1};
    for(int i = 1; i <= n; i++)
        std::cin >> cur[i].ff >> cur[i].ss;
    std::vector<ll> res;
    res.push_back(getCn(n));

    auto seg = SegmentTree<int>(2 * n + 1);
    auto segid = SegmentTreeInd<int>(2 * n + 1);

    ll ans = getCn(n);


    for(int i = 1; i <= n; i++){
        ll in = seg.query(cur[i].ff, cur[i].ss).val;
        ll need = (in - 2) / 2;
        ans = ans * getCn(need) % mod;

        ll fa = segid.query(cur[i].ff, cur[i].ff).minind;
        
        ll infa = seg.query(cur[fa].ff, cur[fa].ss).val;

        ll needfa = (infa - 2) / 2;
        ll con = getCn(needfa);
        ans = ans * qmi(con, mod - 2, mod) % mod;

        seg.update(cur[i].ff, cur[i].ss, 1);
        infa = seg.query(cur[fa].ff, cur[fa].ss).val;
        needfa = (infa - 2) / 2;

        con = getCn(needfa);
        ans = ans * con % mod;

        res.push_back(ans);
        segid.update(cur[i].ff, cur[i].ss, i);
    }

    for(int i = 0; i < res.size(); i++)
        std::cout << res[i] << sendl[i == res.size() - 1];
}