[BZOJ3745][COCI2015]Norma[分治]

题意

题目链接

分析

• 考虑分治，记当前分治区间为 \(l,r\) 。

• 枚举左端点，然后发现右端点无非三种情况：
  • 极大极小值都在左边;
  • 有一个在左边;
  • 极大极小值都在右边;

• 考虑递推 \(l\) 的同时递推最靠右的满足最大最小值在左边的位置 \(p_1,p_2\).

• 根据不同的情况计数即可，注意计算以 \(\rm mid\) 作为右端点的情况。

• 总时间复杂度为\((nlogn)\)。

重点：分治算法降低复杂度的原因：根据极大极小值的不同划分数据以及?

代码

#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define For for(int j=1;j<=6;++j)
typedef long long LL;
inline int gi(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=5e5 + 7;
const LL mod=1e9;
int n;
LL a[N],s[7][N],ans;
void add(LL &a,LL b){a+=b;if(a>=mod) a-=mod;}
LL s1(int x){
    return 1ll*x*(x+1)/2%mod;
}
void fz(int l,int r){
    if(l==r){ add(ans,a[l]*a[l]%mod);return ;}
    if(l>r) return;
    int mid=l+r>>1;LL mx=a[mid],mi=a[mid];
    For s[j][mid-1]=0;
    for(int i=mid;i<=r;++i){
        Min(mi,a[i]);Max(mx,a[i]);
        For s[j][i]=s[j][i-1];
        add(s[1][i],mi*mx%mod);
        add(s[2][i],(i-mid)*mi%mod*mx%mod);
        add(s[3][i],mi);
        add(s[4][i],mx);
        add(s[5][i],(i-mid)*mi%mod);
        add(s[6][i],(i-mid)*mx%mod);
    }
    mx=mi=a[mid];
    int p1=mid,p2=mid;
    for(int i=mid;i>=l;--i){
        Min(mi,a[i]);Max(mx,a[i]);
        for(;p1+1<=r&&a[p1+1]>=mi;++p1);
        for(;p2+1<=r&&a[p2+1]<=mx;++p2);
        int k1=min(p1,p2),k2=max(p1,p2);
        add(ans,(s1(k1-i+1)-s1(mid-i)+mod)*mi%mod*mx%mod);
        if(k1==p1){
            add(ans,(s[5][k2]-s[5][k1]+mod)*mx%mod);
            add(ans,(s[3][k2]-s[3][k1]+mod)*(mid-i+1)%mod*mx%mod);
        }else{
            add(ans,(s[6][k2]-s[6][k1]+mod)*mi%mod);
            add(ans,(s[4][k2]-s[4][k1]+mod)*(mid-i+1)%mod*mi%mod);
        }
        add(ans,(s[2][r]-s[2][k2]+mod)%mod);
        add(ans,(s[1][r]-s[1][k2]+mod)*(mid-i+1)%mod);
    }
    fz(l,mid-1);fz(mid+1,r);
}
int main(){
    n=gi();
    rep(i,1,n) a[i]=gi();
    fz(1,n);
    printf("%lld\n",ans);
    return 0;
}

[BZOJ3745][COCI2015]Norma[分治]

原文：https://www.cnblogs.com/yqgAKIOI/p/9800850.html