JZOJ 5231. 【NOIP2017模拟A组模拟8.5】序列问题
题目:
题意:
求
其中表示到中的最大值
其中表示到中的最小值
分析:
分治好题:
然后我们对于、、分类讨论
而当在后面时同理
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<ctime>
#include<iomanip>
#include<string>
#include<bitset>
#include<deque>
#include<set>
#define LL long long
#define mo 1000000007
using namespace std;
inline LL read(){
LL d=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
return d*f;
}
LL x[500005],minx[500005],maxx[500005],ans=0;
LL mins[500005],maxs[500005],s[500005];
void dac(LL l,LL r)
{
if(r<l) return;
if(l==r) {(ans+=x[l]*x[r])%=mo;return;}
LL mid=(l+r)>>1;
dac(l,mid);dac(mid+1,r);
minx[mid]=0x7fffffff;
maxx[mid]=0;
mins[mid]=0;
maxs[mid]=0;
s[mid]=0;
for(LL i=mid+1;i<=r;i++)
{
maxx[i]=max(maxx[i-1],x[i]);
minx[i]=min(minx[i-1],x[i]);
mins[i]=mins[i-1]+minx[i];
maxs[i]=maxs[i-1]+maxx[i];
s[i]=(s[i-1]+maxx[i]*minx[i])%mo;
}
LL mini=mid,maxi=mid,ma=0,mi=0x7fffffff;
for(LL i=mid;i>=l;i--)
{
mi=min(mi,x[i]);ma=max(ma,x[i]);
while(mini<r&&minx[mini+1]>=mi) mini++;
while(maxi<r&&maxx[maxi+1]<=ma) maxi++;
if(mini<maxi)
(ans+=mi%mo*ma%mo*(mini-mid)%mo+(s[r]-s[maxi])%mo+(mins[maxi]-mins[mini])%mo*ma%mo)%=mo;
else
(ans+=mi%mo*ma%mo*(maxi-mid)%mo+(s[r]-s[mini])%mo+(maxs[mini]-maxs[maxi])%mo*mi%mo)%=mo;
}
return;
}
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
LL n=read();
for(LL i=1;i<=n;i++) x[i]=read();
ans=0;
dac(1,n);
cout<<ans;
return 0;
}