HDU 6044 Limited Permutation

/ 0评 / 0

人生第一场多校全程挂机QYQ太菜了

Multi-University Training Team 1-1012虚建笛卡尔树

Time Limit: 4000/2000 MS (Java/Others)

As to a permutation $p_1,p_2,⋯,p_n$ from $1$ to $n$, it is uncomplicated for each $1≤i≤n$ to calculate $(l_i,r_i)$ meeting the condition that $min(p_L,p_{L+1},⋯,p_R)=pi$ if and only if $l_i≤L≤i≤R≤r_i$ for each $1≤L≤R≤n$.

Given the positive integers $ n$, $ (li,ri) (1≤i≤n)$, you are asked to calculate the number of possible permutations $ p_1,p_2,⋯,p_n$ from $ 1 $to $ n$, meeting the above condition.
The answer may be very large, so you only need to give the value of answer modulo $ 10^9+$7.

Input:

The input contains multiple test cases.
For each test case:
The first line contains one positive integer $ n$, satisfying $ 1≤n≤10^6$.
The second line contains $ n$ positive integers $ l_1,l_2,⋯,l_n$, satisfying $ 1≤l_i≤i$ for each$ 1≤i≤n$.

The third line contains n positive integers $ r_1,r_2,⋯,r_n$, satisfying $ i≤r_i≤n$ for each $ 1≤i≤n$.

It's guaranteed that the sum of n in all test cases is not larger than $3⋅10^6$.

Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.
size_t fread(void *buffer, size_t size, size_t count, FILE *stream); // reads an array of count elements, each one with a size of size bytes, from the stream and stores them in the block of memory specified by buffer; the total number of elements successfully read is returned.

Output :

For each test case, output "Case #x: y" in one line (without quotes), where $ x$ indicates the case number starting from $ 1$ and $ y$ denotes the answer of corresponding case.

Sample Input

Sample Output

Source

2017 Multi-University Training Contest - Team 1
查看官方题解

题解:

题意捉急给出$ n$组$ [l_i,r_i]$ 代表$ p_i$在这个区间内最小,求出目前满足该$ n$个要求的排列总共有多少?
对于每个区间$ [l_i, r_i]$来说如果$ p_i$为其中的最小那么由$ [l_i, i-1]$ $ [i+1,r_i]$中的最小值{$ p_j,p_k$} $ >pi$而且满足$ pi>$ $ p_{l_i-1},p_{r_i+1}$
虚拟的建立笛卡尔树先按左区间升序,右区间降序,然后按照树的先序遍历把区间放上去也就建立了笛卡尔树时间最优复杂度为基数排序+线性建树=$ O(n)$。
找到$ p_i$点控制的区间$ [L,R]$划分区间为$ [L,i-1]$和$ [i+1,R]$设子树大小为$ s(v_1),s(v_2)$
子树对应的方案数为$ f(v_1),f(v_2)$ 则$ p_i$对应的方案数为$ c(s(v_1),s(v_1) + s(v_2) ) * f(v_1) * f(v_2) $

Code

发表评论

电子邮件地址不会被公开。 必填项已用*标注