标题

大标题大标题大标题大标题

思路

考虑暴力，对于每个方向，先求出它向正、负延伸的范围，再 $O(2^n)$ 计算向正还是负延伸。

优化，发现每一次能延伸多少只看其中最小的，而且顺序不影响答案，所以可以按向正、负延伸的范围的最小值排序，一旦后面的最小值都比当前最小值还大，再搜索没有意义，直接加上后面总共的贡献返回即可。
做完后看了一眼数据范围，$2e5$能过，奇迹啊

时间复杂度:

$O(2^n)$

十年OI一场空，不开long long见祖宗

$AC$ $Code$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
const int Mod=1e9+7;
int n,m[N],mi[N]={1};
struct node{
	int x,y;
}a[N];
int h[N];
int ans=1;
void dfs(int x,int minn){
	if(x==n+1){
		ans+=minn;
		ans%=Mod;
		return;
	}
	if(minn<=h[x]){
		ans+=minn*mi[n-x+1]%Mod;
		ans%=Mod;
		return;
	}
	dfs(x+1,min(minn,a[x].x));
	dfs(x+1,min(minn,a[x].y));
}
bool cmp(node A,node B){
	return min(A.x,A.y)<min(B.x,B.y);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		mi[i]=mi[i-1]*2%Mod;
		cin>>m[i];
	}
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a[i].x=m[i]-x;
		a[i].y=x-1;
	}
	sort(a+1,a+1+n,cmp);
	h[n+1]=1e18;
	for(int i=n;i>=1;i--){
		h[i]=min(h[i+1],min(a[i].x,a[i].y));
	}
	dfs(1,1e18);
	cout<<ans;
}

暴力卍岁！！！（佛教，申和注意一下）