完美子图

时间:2020-07-11 12:27:30   收藏:0   阅读:57

完美子图 (分治 \(\star\star\star?\))

Descrption

Input

Output

Sample Input

5
1 1
3 2
2 4
5 5
4 3

Sample Output

10

Hint

分析

Code

#include <bits/stdc++.h>
const int maxn=1e5+5,Inf=0x3f3f3f3f;
typedef long long LL;
int Min[maxn],Max[maxn],cnt[maxn<<1];
int n,a[maxn];
LL ans;
void Divi(int L,int R){
    if(L==R){ans++;return;}//单独一个是完美子图
    int mid=(L+R)>>1;
    Divi(L,mid);
    Divi(mid+1,R);
    //预处理左右两边的最值
    Max[mid]=Min[mid]=a[mid];
    Max[mid+1]=Min[mid+1]=a[mid+1];
    for(int i=mid-1;i>=L;--i){
        Max[i]=std::max(Max[i+1],a[i]);
        Min[i]=std::min(Min[i+1],a[i]);
    }
    for(int i=mid+2;i<=R;++i){
        Max[i]=std::max(Max[i-1],a[i]);
        Min[i]=std::min(Min[i-1],a[i]);
    }
    for(int i=mid;i>=L;i--){//最大、最小均在左侧
        int j=Max[i]-Min[i]+i;//区间[i,j]
const int maxn=1e5+5,Inf=0x3f3f3f3f;
typedef long long LL;
int Min[maxn],Max[maxn],cnt[maxn<<1];
int n,a[maxn];
LL ans;
void Divi(int L,int R){
    if(L==R){ans++;return;}//单独一个是完美子图
    int mid=(L+R)>>1;
    Divi(L,mid);
    Divi(mid+1,R);
    //预处理左右两边的最值
    Max[mid]=Min[mid]=a[mid];
    Max[mid+1]=Min[mid+1]=a[mid+1];
    for(int i=mid-1;i>=L;--i){
        Max[i]=std::max(Max[i+1],a[i]);
        Min[i]=std::min(Min[i+1],a[i]);
    }
    for(int i=mid+2;i<=R;++i){
        Max[i]=std::max(Max[i-1],a[i]);
        Min[i]=std::min(Min[i-1],a[i]);
    }
    for(int i=mid;i>=L;i--){//最大、最小均在左侧
        int j=Max[i]-Min[i]+i;//区间[i,j]
        if(j<=R && j>mid && Max[j]<Max[i] && Min[i]<Min[j])
            ans++;
    }
    for(int i=mid+1;i<=R;++i){//都在右侧
        int j=i-Max[i]+Min[i];
        if(j<=mid && j>=L && Max[j]<Max[i] && Min[j]>Min[i])
            ans++;
    }
    int j=mid+1,k=mid+1;
    for(int i=mid;i>=L;--i){//左小右大:Min[i]-i==Max[j]-j
        while(j<=R && Min[j]>Min[i])//右边的最小值要比左边的大
            cnt[Max[j]-j+n]++,++j;//Max[j]-j有可能为负,所以+n
        while(k< j&& Max[k]<Max[i])//右边如果有从mid+1开始连续的区间的最大值比左边小--
            cnt[Max[k]-k+n]--,++k;
        ans+=(LL)cnt[Min[i]-i+n];
    }
    while(k<j)//清空cnt数组,memset也可以,但会超时
        cnt[Max[k]-k+n]--,k++;
    j=mid;k=mid;
    for(int i=mid+1;i<=R;++i){//左大右小:Min[i]+i==Max[j]+j
        while(j>=L && Min[j]>Min[i])
            cnt[Max[j]+j]++,--j;
        while(k>j && Max[k]<Max[i])
            cnt[Max[k]+k]--,--k;
        ans+=(LL)cnt[Min[i]+i];
    }
    while(k>j)//清空cnt数组,memset也可以,但会超时
        cnt[Max[k]+k]--,--k;
}
void Solve(){
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<=n;++i)
        scanf("%d%d",&x,&y),a[x]=y;
    Divi(1,n);
    printf("%lld\n",ans);
}
int main() {
    Solve();
    return 0;
}]
        if(j<=R && j>mid && Max[j]<Max[i] && Min[i]<Min[j])
            ans++;
    }
    for(int i=mid+1;i<=R;++i){//都在右侧
        int j=i-Max[i]+Min[i];
        if(j<=mid && j>=L && Max[j]<Max[i] && Min[j]>Min[i])
            ans++;
    }
    int j=mid+1,k=mid+1;
    for(int i=mid;i>=L;--i){//左小右大:Min[i]-i==Max[j]-j
        while(j<=R && Min[j]>Min[i])//右边的最小值要比左边的大
            cnt[Max[j]-j+n]++,++j;//Max[j]-j有可能为负,所以+n
        while(k<j && Max[k]<Max[i])//右边如果有从mid+1开始连续的区间的最大值比左边小--
            cnt[Max[k]-k+n]--,++k;
        ans+=(LL)cnt[Min[i]-i+n];
    }
    while(k<j)//清空,避免影响下面
        cnt[Max[k]-k+n]--,k++;
    j=mid;k=mid;
    for(int i=mid+1;i<=R;++i){//左大右小:Min[i]+i==Max[j]+j
        while(j>=L && Min[j]>Min[i])
            cnt[Max[j]+j]++,--j;
        while(k>j && Max[k]<Max[i])
            cnt[Max[k]+k]--,--k;
        ans+=(LL)cnt[Min[i]+i];
    }
    while(k>j)
        cnt[Max[k]+k]--,--k;
}
void Solve(){
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<=n;++i)
        scanf("%d%d",&x,&y),a[x]=y;
    Divi(1,n);
    printf("%lld\n",ans);
}
int main() {
    Solve();
    return 0;
}

原文:https://www.cnblogs.com/hbhszxyb/p/13283005.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!