luogu6406 [COCI2014-2015#2] Norma 题解

Solution

考虑分治。

对于当前处理的区间 $[L,R]$ ，枚举左端点 $l$ ，维护 $mn = \min_{i=l}^{mid} \{a_i\}$ ， $mx = \max_{i=l}^{mid} \{a_i\}$ 。

同时用 $pos_0$ 表示最靠右的 $p$ ，满足 $mn \le \min_{i=mid+1}^{p} \{a_i \}$ ， $pos_1$ 表示最靠右的 $p$ ，满足 $mx \ge \max_{i=mid+1}^{p} \{a_i \}$ 。

有了这些信息，我们就能将以 $l$ 为左端点的区间根据右端点 $r$ 的取值分为如下几类。

下面钦定 $pos_0 \le pos_1$ 。

$[mid+1,pos_0]$ 。此时贡献的最值系数相等，提出来之后就是一个等差数列求和，写出来就是
$\frac{\Big( (mid-l+1+1)+(pos_0-l+1) \Big) \times (pos_0-mid)}{2}$
$(pos_0,pos_1]$ 。这些区间的 $\min$ 不满足条件，但 $\max$ 满足条件，所以贡献是
$mx \sum_{i=pos_0+1}^{pos_1} \Big((i-l+1) \min_{j=mid+1}^{i} \{a_j\}\Big)$
考虑如何计算这个和式。首先我们可以把 $[l,i]$ 拆成 $[l,mid]$ 与 $[mid+1,i]$ ，前者仅仅是作为贡献的一个系数，后者则可以用差分快速求出。具体地，维护 $\sum_{i=mid+1}^{R} (i-mid) \times pre_i$ 与 $\sum_{i=mid+1}^{R} pre_i$ ，其中 $pre$ 是前缀 $\min$ 。
$(pos_1,R]$ 。此时与 $mn$ 和 $mx$ 均无关。
$\sum_{i=pos_1+1}^{R} (i-l+1) \min_{j=pos_1+1}^{i} \{a_j\} \max_{j=pos_1+1}^{i} \{a_j\}$
用类似的办法处理即可。

对于 $pos_0 > pos_1$ 的情况，仅仅会对第二种贡献产生影响，对称着维护一个关于前缀 $\max$ 的东西就行。

代码中的变量名与上文有所不同。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
    int a=0, f=1; char c=getchar();
17
    while(!isdigit(c)) {
18
        if(c=='-') f=-1;
19
        c=getchar();
20
    }
21
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
    return a*f;
23
}
24
const int N=5e5+5, mod=1e9;
25
int n, ans, a[N];
26
int s1[N], s2[N], s3[N], s4[N], s5[N], s6[N];
27
int calc(int i,int mid,int lim) {
28
    int l=mid+1-i+1, r=lim-i+1;
29
    return (l+r)*(lim-mid)/2%mod;
30
}
31
void solve(int l,int r) {
32
    if(l==r) { (ans+=a[l]*a[l]%mod)%=mod; return; }
33
    int mid=(l+r)>>1;
34

35
    int pmn=a[mid+1], pmx=a[mid+1];
36
    s1[mid]=s2[mid]=s3[mid]=s4[mid]=s5[mid]=s6[mid]=0;
37
    for(int i=mid+1;i<=r;++i) {
38
        pmn=min(pmn,a[i]), pmx=max(pmx,a[i]);
39
        s1[i]=(s1[i-1]+(i-mid)*pmn%mod)%mod;
40
        s2[i]=(s2[i-1]+pmn)%mod;
41
        s3[i]=(s3[i-1]+(i-mid)*pmx%mod)%mod;
42
        s4[i]=(s4[i-1]+pmx%mod)%mod;
43
        s5[i]=(s5[i-1]+(i-mid)*pmx%mod*pmn%mod)%mod;
44
        s6[i]=(s6[i-1]+pmx*pmn%mod)%mod;
45
    }
46
    int mn=a[mid], mx=a[mid], j=mid, k=mid;
47
    for(int i=mid;i>=l;--i) {
48
        mn=min(mn,a[i]), mx=max(mx,a[i]);
49
        while(j<r&&a[j+1]>mn) ++j;
50
        while(k<r&&a[k+1]<mx) ++k;
51
        int lim1=min(j,k), lim2=max(j,k);
52
        if(lim1>mid) (ans+=(mn*mx%mod*calc(i,mid,lim1)%mod)%mod)%=mod;
53
        if(j>lim1) (ans+=mn*((s3[j]-s3[lim1]+mod)%mod+(mid-i+1)*(s4[j]-s4[lim1]+mod)%mod)%mod)%=mod;
54
        if(k>lim1) (ans+=mx*((s1[k]-s1[lim1]+mod)%mod+(mid-i+1)*(s2[k]-s2[lim1]+mod)%mod)%mod)%=mod;
55
        (ans+=(s5[r]-s5[lim2]+mod)%mod+(mid-i+1)*(s6[r]-s6[lim2]+mod)%mod)%=mod;
56
    }
57
    solve(l,mid);
58
    solve(mid+1,r);
59
}
60
signed main() {
61
    n=read();
62
    rep(i,1,n) a[i]=read();
63
    solve(1,n);
64
    printf("%lld\n",ans);
65
    return 0;
66
}

Nanami^2

luogu6406 [COCI2014-2015#2] Norma 题解

Solution

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

Solution

觉得这篇文章怎么样？

分享这篇文章

评论区