题解：P11214 【MX-J8-T2】黑洞

· · 题解

样例初步分析

\ 对于上图，我们可以发现有 4=2^2 条对角线，它们的格子数也是可以计算的\ 左上角: 1= min (2-1,3-1)\ 右上角: 1= min (2-1,6-3)\ 左下角: 2= min (3-1,6-2)\ 右下角: 3= min (6-2,6-3)\

8 = 1+1+2+3+1（黑洞它本身）

深度分析规律

一共 2^n 条对角线，每条对角线都要在 n 个数中找最小的，是哪 n 个数呢？\ 令 f_i=m_i-a_i,g_i=a_i-1 \ 对于 f_1, \dots, f_n 和 g_1, \dots, g_n \

## 代码细节呈现 $ 2 \le n \le 2*10^5 $，对时间复杂度是有要求的\ 我们把 $f_i$ 和 $g_i$ 小的放前，然后按照左端点排序\ 现在要考虑的就是每一轮选 $f_i$ 或 $g_i$ 后面的情况\ 因为 $f_i \le f_i \dots f_n$，所以后面 $2^j(j=n-i)$ 个情况，如果这一轮选 $f_i$ 的话，结果都为 $f_i$ \ 这对吗？\ 如果前面有一轮的 $g_j \le f_i(j \le i)$ 那后面的情况就不是 $f_i$ 了，所以还需要记录每一轮 $g_j$ 的最小值，每一轮算的也是 min $(f_i,$ min $(g_1,\dots g_i))$\ 这正好帮我们解决了每一轮选 $g_i$ 的情况！\ 至于怎么边算 $2^j(j=n-i)$ 边%，快速幂就行了\ 最后还要算上都选 $g_i$ 的情况，加上记录的变量即可\ 时间复杂度 $O(n logn) 
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 200005;
const int MOD = 1e9+7; 
int n,m[N],a[N];
struct node{
    int x,y;
}p[N];
bool cmp(node x,node y){
    if(x.x==y.x) return x.y<y.y;
    return x.x<y.x;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;b>>=1;
    }
    return res;
}
signed main(){
//  freopen("hole.in","r",stdin);
//  freopen("hole.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&m[i]);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        p[i].x=a[i]-1;p[i].y=m[i]-a[i];
        if(p[i].x>p[i].y) swap(p[i].x,p[i].y);
    }
    sort(p+1,p+n+1,cmp);
    int ans=0,mn=1e18;
    for(int i=1;i<=n;i++){
        ans=(ans+min(p[i].x,mn)*ksm(2,n-i)%MOD)%MOD;
        mn=min(mn,p[i].y);
    }
    printf("%lld\n",(ans+mn+1)%MOD);
    return 0;
}
/*
切勿抄袭
*/

后话

蒟蒻第一次发比赛题解qwq\ 最后，祝大家 CSP-J/S RP++！