『单调栈·动态规划·ST表·莫队』「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。

题解

题目大意：给定若干个区间，求解每一个区间内，所有子区间最小值之和。

题目中需要求解若干个区间查询问题，且没有强制在线的要求，我们思考一下是否可以使用离线的莫队算法解决。我们思考如何从区间$[l,r]$转移到区间$[l,r+1]$。

我们设$p$为区间$[l,r+1]$的最小值，则新增加的答案可以分成两部分：

• 1.左端点在$[l,p]$的答案。此时贡献是：$a[p]?(p?l+1)$.涉及区间最值，p直接用ST表求解即可。
• 2.左端点在$[p+1,r]$的答案。这一部分的计算方式比较复杂。

我们设状态f[i]表示在序列$[1,i]$中，右端点r的贡献。令$pr{e}_i$表示第$i$个位置前第一个比$a[i]$小的数。

有状态转移方程：$$f[i]=f[pr{e}_i]+(r?pr{e}_i)?a[r]$$

如果我们需要求解$[p+1,r+1]$的答案，我们发现一定存在$$f[r+1]=(r?pr{e}_r)?a[r]+...+(x?p)?a[x]+f_p(pr{e}_x=p)$$

存在这种情况是基于$p$为$[1,r+1]$中的最小值；因此求解对应区间的数值只需要$f[r]?f[p].$

我们需要用一个单调递增的单调栈来维护这一个$pre$值。

这样，对于$[l,r]\to [l,r+1]$来说，新增加的贡献是：$f[r]?f[p]+a[p]?(p?l+1).$

相反的，我们可以再用反向的单调栈和DP处理一个g数组。

具体如下：

代码如下：

#include <cmath>
#include <cstdio>
#include <iostream> 
#include <algorithm>#define int long longusing namespace std;int n,m,top,ans,T,l,r;
int f[200000];
int g[200000];
int a[200000];
int st[200000];
int Ans[200000];
int lg2[200000];
int Min[200000][100];
struct node
{
    int l, r, id, p;friend bool operator < (node p1, node p2){
    if (p1.p == p2.p) return p1.r < p2.r;return p1.p < p2.p; }
} ;
node q[200000];inline int read(void)
{
    int s = 0, w = 1;char c = getchar();while (c < '0' || c > '9') {
     if (c == '-') w = -1; c = getchar();}while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w * s;
}void Get_Max(void)
{
    int T = log2(n);for (int i=1;i<=n;++i) Min[i][0] = i;for (int j=1;j<=T;++j)for (int i=1;i+(1<<j)-1<=n;++i){
    if (a[Min[i][j-1]] < a[Min[i+(1<<j-1)][j-1]])Min[i][j] = Min[i][j-1];else Min[i][j] = Min[i+(1<<j-1)][j-1];}for (int i=1;i<=n;++i) lg2[i] = log2(i);return;
}int ask(int l,int r)
{
    int t = lg2[r-l+1];int p1 = Min[l][t], p2 = Min[r-(1<<t)+1][t];return a[p1] > a[p2] ? p2 : p1;
}void Get_DP(void)
{
    top = 0;for (int i=1;i<=n;++i){
    while (a[st[top]] >= a[i] && top > 0) top --;int pre = st[top];top ++, st[top] = i;f[i] = f[pre] + (i-pre) * a[i];} top = 0;for (int i=n;i>=1;--i){
    while (a[st[top]] >= a[i] && top > 0) top --;int pre = st[top];top ++, st[top] = i;g[i] = pre != 0 ? g[pre] + (pre-i) * a[i] : a[i] * (n-i+1);}
}void ins1(int l,int r)
{
    int p = ask(l,r);ans += a[p] * (r-p+1) + g[l] - g[p];return;
}void ins2(int l,int r)
{
    int p = ask(l,r);ans += a[p] * (p-l+1) + f[r] - f[p];return;
}void del1(int l,int r)
{
    int p = ask(l,r);ans -= a[p] * (r-p+1) + g[l] - g[p];return;
}void del2(int l,int r)
{
    int p = ask(l,r);ans -= a[p] * (p-l+1) + f[r] - f[p];return;
}signed main(void)
{
    freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);n = read();m = read();for (int i=1;i<=n;++i) a[i] = read();Get_Max();Get_DP();T = sqrt(n);for (int i=1;i<=m;++i) {
    q[i].l = read();q[i].r = read();q[i].id = i;q[i].p = (q[i].l+T-1) / T;}sort(q+1, q+m+1);l = 1, r = 0, ans = 0;for (int i=1;i<=m;++i){
    while (l > q[i].l) ins1(--l, r);while (r < q[i].r) ins2(l, ++r);while (l < q[i].l) del1(l++, r);while (r > q[i].r) del2(l, r--);Ans[q[i].id] = ans;}for (int i=1;i<=m;++i) printf("%lld\n", Ans[i]);return 0;
}