?
3745: [Coci2015]Norma
3745: [Coci2015]NormaTime Limit:?20 Sec??Memory Limit:?64 MBSubmit:?960??Solved:?426 [Submit][Status][Discuss] DescriptionInput
第1行,一个整数N;
第2~n+1行,每行一个整数表示序列a。
? Output
输出答案对10^9取模后的结果。
? Sample Input
4
2 4 1 4 Sample Output
109
【数据范围】 N <= 500000 1 <= a_i <= 10^8 HINT? 思路:分治好题!? 明显的,$O(n^2)$的算法非常容易? 由于我们要考虑所有的子区间,所以我们这里采用分治算法。?? 考虑l和r内存的子区间。?? 子区间有3种情况, 1.只在l到mid之间 这个可以递归解决 2.只在mid+1到r? ? 这个也可以递归解决 3. 左端点在左半区间,右端点在右半区间? 对3种情况就是分治里面的合并情况,最复杂。? 我们可以先把左半区间预处理好。? 比如6个数,3? 4 2? 1 5 3?? 左半区间是3 4 2? 我们可以预处理? 长度为1? 最小值是2? 最大值也是2?? 长度为2? 最小值是2? 最大值是4? 长度为3? 最小值是2? 最大值是4?? ? 然后我们考虑右边区间?? 第一个数是1,由于1的出现,使得左边的区间长度都加一,并且改变了左边3个区间的最小值。 (都变成1)? 所以1和左边3个区间的乘积和就是 2*1*2+3*1*4+4*1*4,所以这个不好算,我们需要预处理。? 我们发现式子可以写成1*(2*2+3*4+4*4) 即把共同的最小值提取出来 如果我们可以预处理前3个区间的长度*最大值的前缀和1*2+2*4+3*4? ? 那么(2*2+3*4+4*4)-(1*2+2*4+3*4? ?)=2 + 4 + 4? ?就是前3个区间最大值的前缀和(同样可以预处理),这样我们就在O(1)的时间内计算出乘积和。?? ? 右边第2个数是5,由于5的出现,区间长度又都增加了1,并且改变左边3个区间的最大值。? (都变成5)? 使得乘积和: 3*1*5+4*1*5+5*1*5 ,我们发现可以提取1*5(即共同的最大值和最小值) 1*5*(3+4+5),如何计算3+4+5呢,这明显就是高斯求和。? ? 对于最小值和最大值不变的那些区间的乘积和,我们可以通过预处理计算,方法也也类似。? 所以我们总共需要做6个预处理,也就是我定义了6个sum数组的原因。?? ? 很重要的一点,最小值变化和最大值变化具有单调性,所以合并的过程的时间复杂度是O(n)的, 总的时间复杂度:$O(nlogn)$ 1 #include<bits/stdc++.h> 2 using namespace std; 3 int const N=500000+10; 4 int const mod=1e9; 5 #define ll long long 6 ll a[N],ans,sum[N],sum1[N],sum2[N],sum3[N],sum4[N],sum5[N]; 7 ll n,mi[N],mx[N]; 8 ll inline s(ll x,ll y){ 9 return y>=x? (x+y)*(y-x+1)/2 % mod:0; 10 } 11 void dfs(int l,int r){ 12 if(l==r){ 13 ans=(ans+a[r]*a[r]) %mod; 14 return; 15 } 16 int mid=(l+r)/2; 17 dfs(l,mid); 18 dfs(mid+1,r); 19 mi[0]=1e9; 20 mx[0]=0; 21 int lnum=mid-l+1; 22 for(int i=mid;i>=l;i--) { 23 int k=mid-i+1; 24 mi[k]=min(mi[k-1],a[i]); 25 mx[k]=max(mx[k-1],a[i]); 26 sum[k]=(sum[k-1]+k*mi[k]%mod*mx[k]) % mod; 27 sum1[k]=(sum1[k-1]+mi[k]*mx[k])%mod; 28 sum2[k]=(sum2[k-1]+k*mi[k])% mod; 29 sum3[k]=(sum3[k-1]+mi[k])%mod; 30 sum4[k]=(sum4[k-1]+k*mx[k])%mod; 31 sum5[k]=(sum5[k-1]+mx[k])%mod; 32 } 33 int t1=0,t2=0; 34 ll v1=1e9,v2=0; 35 for(int j=mid+1;j<=r;j++){ 36 int k=j-mid; 37 while (t1<lnum && mi[t1+1]>a[j]) 38 t1++,v1=a[j]; 39 while (t2<lnum && mx[t2+1]<a[j]) 40 t2++,v2=a[j]; 41 v1=min(v1,a[j]); 42 v2=max(v2,a[j]); 43 int t=min(t1,t2); 44 ans=(ans+v1*v2%mod*s(1+k,k+t))%mod; 45 int p=max(t1,t2); 46 if(t1>t){ 47 ans=(ans+v1*(sum4[t1]-sum4[t]+k*(sum5[t1]-sum5[t])%mod)%mod)%mod; 48 } 49 if(t2>t){ 50 ans=(ans+v2*(sum2[t2]-sum2[t]+k*(sum3[t2]-sum3[t])%mod)%mod)%mod; 51 } 52 ans=(ans+sum[lnum]-sum[p]+k*(sum1[lnum]-sum1[p])%mod) % mod; 53 ans=(ans+mod)%mod; 54 } 55 } 56 int main(){ 57 scanf("%lld",&n); 58 for(int i=1;i<=n;i++) 59 scanf("%lld",&a[i]) ; 60 dfs(1,n); 61 cout<<ans<<endl; 62 return 0; 63 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |