人生第一场多校全程挂机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

[cpp]
3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5
[/cpp]

Sample Output

[cpp]
Case #1: 2
Case #2: 3
[/cpp]

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

[cpp]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = ll(1e9+7);
namespace fastIO {
#define BUF_SIZE 100000
//fread -> read
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pend == p1) {
IOerror = 1;return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ‘ ‘ || ch == ‘\n’ || ch == ‘\r’ || ch == ‘\t’;
}
inline void read(ll &x) {
char ch;
while(blank(ch = nc()));
if(IOerror)return;
for(x = ch – ‘0’; (ch = nc()) >= ‘0’ && ch <= ‘9’; x = x * 10 + ch – ‘0’);
}
#undef BUF_SIZE
};
using namespace fastIO;
const int maxn = int(1e6+7);
struct seg{
ll l,r,id;
}a[maxn];
bool cmp(const seg &a, const seg &b) {
return a.l==b.l?a.r>b.r:a.l<b.l;
}
ll jc[maxn];
ll power(ll x,ll n) {//此处用费马小定理处理逆元
ll ret =1;
while(n) {
if(n&1) ret = ret * x % mod;
x = x * x % mod;
n>>=1;
}
return ret;
}
bool mark;
ll cnt;

ll C(ll n,ll m) {//计算组合数 n>=m
ll ret=1;
if(n==m) return 1;
ret = ret * jc[n] power(jc[m]jc[n-m]%mod,mod-2) % mod;
return ret;
}
ll dfs(ll l,ll r) {
if(l>r) return 1LL;
seg now = a[cnt++];
if(now.l != l || now.r != r || mark) {
mark=1;
return 0LL;
}
if(l==r) return 1LL; //res = f(v1)f(v2)C(sz(v1),sz(v1)+sz(v2))
ll res = C(now.r-now.l, now.id-now.l)dfs(now.l, now.id-1)%mod;
res = res *dfs(now.id+1, now.r)%mod;
return res;
}
int main() {
ll n;int kase=1;
jc[0]=1;
for(int i=1;i<maxn;i++) jc[i]=jc[i-1]
(ll)i%mod;
for(;read(n),!fastIO::IOerror;) {
for(int i=1;i<=n;i++) read(a[i].l);
for(int i=1;i<=n;i++) read(a[i].r), a[i].id=i;
sort(a+1,a+n+1,cmp);
printf(“Case #%d: “,kase++);
mark=0;cnt=1;
printf(“%lld\n”,dfs(1,n));
}
}
[/cpp]


发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.