NOIP2025 RP++。

小清新线段树优化计数。

最直接好做的想法就是枚举其中一条分割线，计算能被这条线分割的方案数。

注意这里的分割线仅指 $x=k+0.5$ 和 $y=k+0.5$，$0\leq k\leq n$ 共 $2n+2$ 条。

容易发现这样会算重，可能有方案有多种分割方式。

考虑经典 trick，设 $f(i)$ 是钦定 $i$ 条分割线的方案数，答案就是 $\sum_{i=1}^{2n-2} f(i)\times (-1)^{i-1}$。

看着不好算，但是可以发现有一些计算是无效的。

假如 $x$ 处钦定了至少两条分割线，设最小的为 $x=l+0.5$，最大的为 $x=r+0.5$。

那么在这两条直线中间一共 $m=r-l-1$ 条直线无论钦不钦定，得到的答案都是不变的，这是因为 $x\in [l,r]$ 的奶牛都不能选。

$m>0$ 时有 $\sum_{i=0}^{m} C_m^i\times (-1)^i=0$，所以 $r-l>1$ 时的计算都没用。

排掉这么多情况，我们只需要计算这些了：

• 只钦定一个方向的一条线。
• 只钦定一个方向的两条相邻的线。
• 钦定两个方向的线，每个方向至多两条相邻的线。
  • 此处还要枚举两队分别在一三象限还是二四象限。

前两个都容易计算，最后一个使用线段树容易解决。只考虑左边全是红右边全是蓝，最后乘 $2$ 即可。

::::info[为什么不会多算某些东西？]

• 两个队伍都没有奶牛。
  • 只钦定一个方向被算了 $2(n+1-n)$ 次。
  • 钦定两个方向的被算了 $2\times \left(-(n+1)^2+2n(n+1)-n^2 \right)$ 次。
    • 乘二是因为考虑一三或二四象限都被算了一次。
  • 加起来恰好抵消，不会多算。
• 恰好一个队伍有奶牛。
  • 设其中 $x$ 坐标最小最大分别为 $l$ 和 $n+1-r$。
  • 设其中 $y$ 坐标最小最大分别为 $d$ 和 $n+1-u$。
  • 一个方向选一条被算 $l+r+u+d$ 次。
  • 一个方向选两条被算 $-(l+r+u+d-4)$ 次。
  • 两个方向各选一条被算 $-(l+r)(u+d)$ 次。
  • $x$ 选一条 $y$ 选两条被算 $(l+r)(u+d-2)$ 次。
  • $y$ 选一条 $x$ 选两条被算 $(l+r-2)(u+d)$ 次。
  • 两个方向各选两条被算 $-(l+r-2)(u+d-2)$
  • 依然抵消，所以不会多算。

::::

::::info[该如何线段树维护？] 先考虑两个方向都只钦定一条，且分布在一三象限的情况。

考虑从左往右扫描线，$a_i$ 表示右侧 $y$ 坐标 $\geq i$ 以及左侧 $y$ 坐标 $<i$ 的点数量和。

每次把右侧的一个点删掉再加到左侧。

线段树支持区间加，区间求 $2^{a_i}$ 的和即可。

$x$ 坐标钦定两条就是删掉点后加入前计算一遍。

$y$ 坐标钦定两条就是维护的时候左右都不取等。 ::::

::::info[完整代码]

#include<bits/stdc++.h>
#define MX 200005
#define int long long
using namespace std;
const int mod=1000000007;int read();
int n,a[MX],qp[MX],nqp[MX],res,cal;
int qpow(int x,int y){
	int z=1;while(y){
		if(y&1) z=z*x%mod;
		x=x*x%mod,y>>=1;
	}return z;
}
class SegmentTree{public:
	int tr[MX*4],lz[MX*4];
	void Init(int t,int l,int r){
		tr[t]=1,lz[t]=0;if(l>=r) return;
		int mid=(l+r)>>1;
		Init(t<<1,l,mid);Init(t<<1|1,mid+1,r);
		tr[t]=r-l+1;
	}	
	void add(int t,int w){
		if(w>=0) tr[t]=tr[t]*qp[w]%mod;
		else tr[t]=tr[t]*nqp[-w]%mod;
		lz[t]+=w;
	}
	void pushdown(int t){
		add(t<<1,lz[t]);add(t<<1|1,lz[t]);lz[t]=0;}
	void Add(int t,int l,int r,int L,int R,int w){
		if(L<=l && r<=R){add(t,w);return;}
		int mid=(l+r)>>1;pushdown(t);
		if(L<=mid) Add(t<<1,l,mid,L,R,w);
		if(R>mid) Add(t<<1|1,mid+1,r,L,R,w);
		tr[t]=(tr[t<<1]+tr[t<<1|1])%mod;
	}
	int Sum(int t,int l,int r,int L,int R){
		if(L<=l && r<=R) return tr[t];
		int mid=(l+r)>>1,ret=0;pushdown(t);
		if(L<=mid) ret+=Sum(t<<1,l,mid,L,R);
		if(R>mid) ret+=Sum(t<<1|1,mid+1,r,L,R);
		return ret%mod;
	}
}T,Tr;
signed main(){
	n=read();qp[0]=nqp[0]=1;
	for(int i=1;i<=n;i++){
		qp[i]=qp[i-1]*2%mod;
		nqp[i]=qpow(qp[i],mod-2);
		int x=read();a[x]=read();}
	res=(n+1)*qpow(2,n)-n*qpow(2,n-1);
	res=((res%mod)+mod)*2%mod;
	
	T.Init(1,0,n+1);Tr.Init(1,0,n+1);
	for(int i=1;i<=n;i++){
		T.Add(1,0,n+1,0,i,1);
		Tr.Add(1,0,n+1,0,i-1,1);
	}
	cal=T.Sum(1,0,n+1,1,n+1);
	res=(res+mod-cal)%mod;
	cal=Tr.Sum(1,0,n+1,1,n);
	res=(res+cal)%mod;
	for(int i=1;i<=n;i++){
		int w=a[i];
		T.Add(1,0,n+1,0,w,-1);
		Tr.Add(1,0,n+1,0,w-1,-1);
		
		cal=T.Sum(1,0,n+1,1,n+1);
		res=(res+cal)%mod;
		cal=Tr.Sum(1,0,n+1,1,n);
		res=(res+mod-cal)%mod;
			
		T.Add(1,0,n+1,w+1,n+1,1);
		Tr.Add(1,0,n+1,w+1,n+1,1);
		cal=T.Sum(1,0,n+1,1,n+1);
		res=(res+mod-cal)%mod;
		cal=Tr.Sum(1,0,n+1,1,n);
		res=(res+cal)%mod;
	}
	
	T.Init(1,0,n+1);Tr.Init(1,0,n+1);
	for(int i=1;i<=n;i++){
		T.Add(1,0,n+1,i,n+1,1);
		Tr.Add(1,0,n+1,i+1,n+1,1);
	}
	cal=T.Sum(1,0,n+1,0,n);
	res=(res+mod-cal)%mod;
	cal=Tr.Sum(1,0,n+1,1,n);
	res=(res+cal)%mod;
	for(int i=1;i<=n;i++){
		int w=a[i];
		T.Add(1,0,n+1,w,n+1,-1);
		Tr.Add(1,0,n+1,w+1,n+1,-1);
		
		cal=T.Sum(1,0,n+1,0,n);
		res=(res+cal)%mod;
		cal=Tr.Sum(1,0,n+1,1,n);
		res=(res+mod-cal)%mod;
		
		T.Add(1,0,n+1,0,w-1,1);
		Tr.Add(1,0,n+1,0,w-1,1);
		cal=T.Sum(1,0,n+1,0,n);
		res=(res+mod-cal)%mod;
		cal=Tr.Sum(1,0,n+1,1,n);
		res=(res+cal)%mod;
	}
	res=res*2%mod;
	printf("%lld\n",res);
	return 0;
}
int read(){
	int Ca=0;char Cr=' ';int Cf=1;
	while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
	while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
	return Ca*Cf;
}

::::