GZY的博客

P6406 [COCI2014 2015#2] Norma 题解

 题解  649  

提供一种线段树解法。

设 $\min(l,r)$ 表示 $a_l$ 至 $a_r$ 的最小值，$\max(l,r)$ 表示 $a_l$ 至 $a_r$ 的最大值。

题目要求： $$ \sum_{l=1}^n \sum_{r=l}^n (r-l+1)\min(l,r)\max(l,r) $$

考虑将其分成： $$ \sum_{l=1}^n \sum_{r=l}^n (r+1)\times\min(l,r)\max(l,r)-l\times\min(l,r)\max(l,r) $$ 即，对于每个 $r$ 求出： $$ (r+1)\times\sum _{l=1}^r \min(l,r)\max(l,r) $$ 对于每个 $l$ 求出： $$ l\times\sum _{r=l}^n \min(l,r)\max(l,r) $$ 这两个求法类似，以 $r$ 为例：

假设现在的右端点为 $r$，

考虑维护数组 $mn$ 和 $mx$，$mn_i=\min(i,r),mx_i=\max(i,r)$，

那么 $r$ 作为右端点的答案就是 $\sum_{i=1}^r mn_i\times mx_i$。

考虑将右端点向后移变为 $r+1$ 的答案，

可以发现只有部分的 $mn$ 和 $mx$ 发生了变化，

具体的，设 $p$ 为 $r+1$ 左边第一个比 $a_{r+1}$ 小的数，设 $q$ 为 $r+1$ 左边第一个比 $a_{r+1}$ 大的数。

（$p$ 和 $q$ 可以用单调栈求出）。

容易发现，$mn$ 数组从 $p+1$ 到 $r+1$ 都应变为 $a_{r+1}$，$mx$ 数组从 $q+1$ 到 $r+1$ 都应变为 $a_{r+1}$。

考虑用线段树维护这一过程，即需要支持：

  • 区间覆盖 $mn$
  • 区间覆盖 $mx$
  • 区间查询 $\sum_{i=1}^r mn_i \times mx_i$

$l$ 的贡献同理。

这题卡空间，最好只存 $5$ 个量。

代码（部分变量名和题解不同）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int N=5e5+3,p=1e9;
struct Val{
    int sa,sb,sm;
    Val(){sa=sb=sm=0;}
};
Val operator+(Val x,Val y){
    Val z;
    z.sa=(x.sa+y.sa)%p;
    z.sb=(x.sb+y.sb)%p;
    z.sm=(x.sm+y.sm)%p;
    return z;
}
struct node{
    int tga=-1,tgb=-1;
    Val v;
    void val(int ta,int tb,int l,int r){
        if(~ta){
            tga=ta;
            v.sa=(ta*1LL*(r-l+1))%p;
            v.sm=(ta*1LL*v.sb)%p;
        }
        if(~tb){
            tgb=tb;
            v.sb=(tb*1LL*(r-l+1))%p;
            v.sm=(tb*1LL*v.sa)%p;
        }
    }
}tr[(N<<2)];
void push_down(int x,int l,int r){
    tr[x<<1].val(tr[x].tga,tr[x].tgb,l,mid);
    tr[x<<1|1].val(tr[x].tga,tr[x].tgb,mid+1,r);
    tr[x].tga=tr[x].tgb=-1;
}
void push_up(int x)
    {tr[x].v=tr[x<<1].v+tr[x<<1|1].v;}
void change(int x,int l,int r,int ql,int qr,int ta,int tb){
    if(l>=ql&&r<=qr){tr[x].val(ta,tb,l,r);return;}
    if(l>qr||r<ql) return;
    push_down(x,l,r);
    change(x<<1,l,mid,ql,qr,ta,tb),
    change(x<<1|1,mid+1,r,ql,qr,ta,tb);
    push_up(x);
}
Val ask(int x,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return tr[x].v;
    if(l>qr||r<ql) return Val();
    push_down(x,l,r);
    return ask(x<<1,l,mid,l,r)+ask(x<<1|1,mid+1,r,l,r);
}
int a[N],n;
ll ans=0;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    stack<int>mn,mx;
    for(int i=1;i<=n;i++){
        while(mx.size()&&a[mx.top()]<a[i]) mx.pop();
        if(mx.size()) change(1,1,n,mx.top()+1,i,a[i],-1);
        else change(1,1,n,1,i,a[i],-1);
        mx.push(i);
        while(mn.size()&&a[mn.top()]>a[i]) mn.pop();
        if(mn.size()) change(1,1,n,mn.top()+1,i,-1,a[i]);
        else change(1,1,n,1,i,-1,a[i]);
        mn.push(i);
        auto v=ask(1,1,n,1,i);
        ans=(ans+(v.sm*1LL*(i+1))%p)%p;
    }
    while(mn.size()) mn.pop();
    while(mx.size()) mx.pop();
    change(1,1,n,1,n,0,0);
    for(int i=n;i>=1;i--){
        while(mx.size()&&a[mx.top()]<a[i]) mx.pop();
        if(mx.size()) change(1,1,n,i,mx.top()-1,a[i],-1);
        else change(1,1,n,i,n,a[i],-1);
        mx.push(i);
        while(mn.size()&&a[mn.top()]>a[i]) mn.pop();
        if(mn.size()) change(1,1,n,i,mn.top()-1,-1,a[i]);
        else change(1,1,n,i,n,-1,a[i]);
        mn.push(i);
        auto v=ask(1,1,n,i,n);
        ans=(ans-(v.sm*1LL*i)%p)%p;
    }
    cout<<(ans%p+p)%p;

}