假设已经确定顺序（且不妨假设$a_{i}
显然$a_{i}$不能为峰且峰不能相邻，因此峰数的上限是$n-1$
结论：合法当且仅当存在$k\in [0,n]$使得$\forall 1\le i
为了描述方便，称第$i$组先加入$a_{i}$再加入$b_{i}$为顺序，反之为逆序
充分性：若满足此条件，将$[1,k]$顺序加入且$(k,n]$逆序加入，根据条件不难得到$\forall i\not\in \{k,k+1\},b_{i}$均是峰，同时在$b_{k}$和$b_{k+1}$中较大的一项也总是峰（特别的，当$k\in \{0,n\}$时之前已经有$n-1$个峰）
必要性：对于$i\in [1,n)$，若$i$是顺序且$i+1$是逆序，那么$b_{i}$和$b_{i+1}$中至少有一个不为峰
特别的，若1是逆序或$n$是顺序，那么$b_{1}$或$b_{n}$不为峰（可以理解为0是顺序且$n+1$是逆序）
结合两者，即存在$k\in [0,n]$，满足$[1,k]$为顺序$,(k,n]$为逆序且$\forall i\not\in\{k,k+1\},b_{i}$均是峰，也即条件
进一步的，注意到$k$仅是确定范围，因此总可以取$k=\min_{1\le i\le n,a_{i+1}>b_{i}}i$（约定$a_{n+1}=\infty$），并判定后者是否成立
回到原问题，考虑初始将其按$b_{i}$从小到大排序，并记$U_{i}=\sum_{i
对于$k=n$的情况，考虑从后往前依次加入，第$i$个可行的位置有$U_{i}+1$个（注意$b_{i}$的单调性），因此方案数为$\prod_{i=1}^{n}(U_{i}+1)$
对于$kb_{x}$，进而显然$x
关于这个问题，用一个树状数组维护即可，时间复杂度为$o(n\log n)$，可以通过
1 #include
2 using namespace std;
3 #define N 200005
4 #define mod 1000000007
5 #define ll long long
6 struct Data{
7 int a,b;
8 bool operator < (const Data &k)const{
9 return b<k.b;
10 }
11 }a[N];
12 int n,ans,inv[N],U[N],pre[N],suf1[N],suf2[N],f[N<<1];
13 int lowbit(int k){
14 return (k&(-k));
15 }
16 void update(int k,int x){
17 while (k<=(n<<1)){
18 f[k]=(f[k]+x)%mod;
19 k+=lowbit(k);
20 }
21 }
22 int query(int k){
23 int ans=0;
24 while (k){
25 ans=(ans+f[k])%mod;
26 k-=lowbit(k);
27 }
28 return ans;
29 }
30 int main(){
31 inv[0]=inv[1]=1;
32 for(int i=2;imod;
33 scanf("%d",&n);
34 for(int i=1;i<=n;i++){
35 scanf("%d%d",&a[i].a,&a[i].b);
36 if (a[i].a>a[i].b)swap(a[i].a,a[i].b);
37 }
38 sort(a+1,a+n+1);
39 for(int i=n;i;i--){
40 U[i]=query(a[i].b);
41 update(a[i].a,1);
42 }
43 pre[0]=suf1[n+1]=suf2[n+1]=1;
44 for(int i=1;i<=n;i++)pre[i]=(ll)pre[i-1]*U[i]%mod;
45 for(int i=n;i;i--)suf1[i]=(ll)suf1[i+1]*(U[i]+1)%mod;
46 for(int i=n;i;i--)suf2[i]=(ll)suf2[i+1]*(U[i]+2)%mod*inv[U[i]+1]%mod;
47 memset(f,0,sizeof(f));
48 ans=suf1[1];
49 for(int i=n;i;i--){
50 ans=(ans+(ll)pre[i-1]*suf1[i+1]%mod*(query(n<<1)-query(a[i].b)+mod))%mod;
51 update(a[i].a,(ll)suf2[i+1]*inv[U[i]+1]%mod);
52 }
53 printf("%d\n",ans);
54 return 0;
55 }