【JZOJ5231】【NOIP2017模拟A組模拟8.5】序列問題

Description

Data Constraint

對于30%的資料，n<=5000

對于60%的資料，n<=50000

對于100%的資料，n<=500000,0<=A[i]<=10^9

Solution

這道題有很多種解法，我這裡主要講講分治和線段樹兩種解法。

分治：我們對于每一次二分出來的mid，我們考慮4種情況：最大值最小值在同一邊且跨過mid(左右)，最大值最小值不在同一邊且跨過mid(左右)。

我們設mx[i]表示mid到i的最大值。mi[i]同理。

對于最大值最小值在同一邊且跨過mid的情況:我們可以枚舉一邊，另一邊用一個指針單調移動，強制要求maxi>maxj&&mini

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=e5+,mo=e9+;
ll a[maxn],d[maxn],mx[maxn],mi[maxn],sum[maxn];
ll n,i,t,j,k,x,y,z,num,ans;
void dg(int l,int r){
    if (l==r){
        ans=(ans+a[l]*a[l]%mo)%mo;return;
    }
    if (l>r) return;int mid=(l+r)/;
    mi[mid+]=mx[mid+]=a[mid+];mi[mid]=mx[mid]=a[mid];
    for (i=mid+;i<=r;i++)
        mi[i]=min(mi[i-],a[i]),mx[i]=max(mx[i-],a[i]);
    for (i=mid-;i>=l;i--)
        mi[i]=min(mi[i+],a[i]),mx[i]=max(mx[i+],a[i]);
    sum[l-]=;
    for (i=l;i<=mid;i++)
        sum[i]=sum[i-]+mi[i];
    j=mid;
    for (i=mid+;i<=r;i++){
        while (mi[j]>=mi[i] && mx[j]<=mx[i] && j>=l) j--;
        ans=(ans+mx[i]*mi[i]%mo*(mid-j)%mo)%mo;
    }
    j=mid+;
    for (i=mid;i>=l;i--){
        while (mi[j]>=mi[i] && mx[j]<=mx[i] && !(mi[j]==mi[i] && mx[j]==mx[i])&& j<=r) j++;
        ans=(ans+mx[i]*mi[i]%mo*(j-mid-)%mo)%mo;
    }
    j=mid;k=mid;
    for (i=mid+;i<=r;i++){
        while (mx[j]<mx[i] && j>=l)j--;
        while (mi[k]>=mi[i] && k>=l) k--;
        if (j+<=k)ans=(ans+(sum[k]-sum[j])%mo*mx[i]%mo)%mo;
    }
    j=mid;k=mid;
    for (i=l;i<=mid;i++)
        sum[i]=sum[i-]+mx[i];
    for (i=mid+;i<=r;i++){
        while (mx[j]<=mx[i] && j>=l)j--;
        while (mi[k]>mi[i] && k>=l) k--;
        if (k+<=j)ans=(ans+(sum[j]-sum[k])%mo*mi[i]%mo)%mo;
    }
    dg(l,mid);dg(mid+,r);
}
int main(){
    freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);
    scanf("%lld",&n);
    for (i=;i<=n;i++)
        scanf("%lld",&a[i]);
    dg(,n);
    printf("%lld\n",ans);
}