##### 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.

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

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

#### 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
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.