[题解]HNOI2016序列

题目描述
给定长度为 $n$ 的序列： $a1,a2,…,an$ ，记为 $a[1:n]$ 。类似地， $a[l:r]（1 ≤ l ≤ r ≤ N）$ 是指序列： $al,al+1,…,ar- 1,ar$ 。若 $1 ≤ l ≤ s ≤ t ≤ r ≤ n$ ，则称 $a[s:t]$ 是 $a[l:r]$ 的子序列。
现在有 $q$ 个询问，每个询问给定两个数 $l$ 和 $r$ ， $1 ≤ l ≤ r ≤ n$ ，求 $a[l:r]$ 的不同子序列的最小值之和。
例如，给定序列 $5,2,4,1,3$ ，询问给定的两个数为 $1$ 和 $3$ ，那么 $a[1:3]$ 有 $6$ 个子序列 $a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]$ ，这 $6$ 个子序列的最小值之和为 $5+2+4+2+2+2=17$ 。

$Solution$
一个技巧：取最小数
先取区间 $[l,r]$ 的最小值，设下标为 $x$
首先对于左端点 $< x$ ，右端点 $> x$ 的区间，最小值都是 $a[x]$ ，所以先加上 $a[x] \times (x-l) \times (r-x)$
然后考虑左端点、右端点 $\leq x$ 的区间和左端点、右端点 $\geq x$ 的区间
我们处理一个数组 $f$ _ $pre_i$ 表示以 $i$ 为右端点，左端点 $1-i$ 的区间最小值之和
设第一个比第 $i$ 个元素小的数的下标为 $pre[i]$
显然 $f$ _ $pre[i] =$ $f$ _ $pre[pre[i]] + a[i] * (i - pre[i])$
又处理一个 $g$ _ $pre_i$ 表示 $\sum_{j=1}^{i}f$ _ $pre[j]$
那么，左端点、右端点 $> x$ 的区间，贡献为 $g$ _ $pre[r] - g$ _ $pre[x] - f$ _ $pre[x] \times (r-x)$
想一想，为什么
首先 $g$ _ $pre[r] - g$ _ $pre[x]$ 很好理解，只算右端点在 $[x + 1, r]$ 的区间
也就是说，后面一项是将右端点在 $[x + 1, r]$ 的区间，而左端点在 $[1, x]$ 的区间的贡献减掉
我们发现，这相当于每一个 $f$ _ $pre[i]$ 减去了 $f$ _ $pre[x]$
那为什么可以减呢，这本是不可以减的
注意到开头的 $a[x]$ 是 $[l, r]$ 的最小值，再回到算 $f$ _ $pre$ 的公式
我们发现，无论是哪个 $i$ ，经过若干次 $x = pre[x]$ 的迭代后，一定会变成 $x$
$f$ _ $pre[i] = f$ _ $pre[pre[i]] + (i - pre[i]) * a[i] + f$ _ $pre[pre[pre[i]]] + (pre[i] - pre[pre[i]] * a[pre[i]]) + ... + f$ _ $pre[x]$
减去之后，恰好是右端点为 $i$ ，左端点在 $x+1，i$ 区间的权值和
左半边贡献同理
于是就做完了

$Code$

#include <bits/stdc++.h>
#define ri int
#define ll long long
using namespace std;
const int Maxn=1e5;
const int Lgn=17;
stack<int>s;
int pre[Maxn+5],suf[Maxn+5],n,m;
int st[Maxn+5][Lgn+5],lg[Maxn+5];
ll f_pre[Maxn+5],g_pre[Maxn+5],f_suf[Maxn+5],g_suf[Maxn+5],a[Maxn+5];
int query(int l,int r) {
    int t=lg[r-l+1];
    if(a[st[l][t]]<a[st[r-(1<<t)+1][t]])return st[l][t];
    return st[r-(1<<t)+1][t];
}
int main() {
    scanf("%d%d",&n,&m);
    lg[0]=-1;
    for(ri i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(ri i=1;i<=n;i++)scanf("%lld",&a[i]),st[i][0]=i;
    a[0]=a[n+1]=-1e9-1;
    for(ri j=1;j<=lg[n];j++)
        for(ri i=1;i<=n-(1<<j)+1;i++) {
            int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
            if(a[x]<a[y])st[i][j]=x;
            else st[i][j]=y;
        }
    s.push(0);
    for(ri i=1;i<=n;i++) {
        while(!s.empty()&&a[s.top()]>a[i])s.pop();
        pre[i]=s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    s.push(n+1);
    for(ri i=n;i>=1;i--) {
        while(!s.empty()&&a[s.top()]>a[i])s.pop();
        suf[i]=s.top();
        s.push(i);
    }
    for(ri i=1;i<=n;i++) {
        f_pre[i]=f_pre[pre[i]]+a[i]*(i-pre[i]);
        g_pre[i]=g_pre[i-1]+f_pre[i];
    }
    for(ri i=n;i>=1;i--) {
        f_suf[i]=f_suf[suf[i]]+a[i]*(suf[i]-i);
        g_suf[i]=g_suf[i+1]+f_suf[i];
    }
    while(m--) {
        int l,r;
        scanf("%d%d",&l,&r);
        int x=query(l,r);
        printf("%lld\n",a[x]*(r-x+1)*(x-l+1)+g_pre[r]-g_pre[x]-f_pre[x]*(r-x)+g_suf[l]-g_suf[x]-f_suf[x]*(x-l));
    }
    return 0;
}