Chlience

【题解】LOJ 2051 「HNOI2016」序列
Problem给定一个序列 $a$ ,有 $q$ 个询问,对于每次询问求出 $[l,r]$ 中子序列最小值之和Th...
扫描右侧二维码阅读全文
09
2019/02

【题解】LOJ 2051 「HNOI2016」序列

Problem

给定一个序列 $a$ ,有 $q$ 个询问,对于每次询问求出 $[l,r]$ 中子序列最小值之和

Thought

$$ \sum_{i=l}^r\sum_{j=i}^{r}\min\{a_i\} $$

这道题妙得很啊

首先,区间子串问题一般来说还是会用到莫队算法的,那么只需要考虑区间之间的转移
考虑从区间 $[l,r]$ 转移到 $[l,r+1]$

那么将会多出 $r-l+2$ 个子串,分别为 $[l,r+1],[l+1,r+1],\cdots,[r+1,r+1]$
也就是说需要求出从 $r+1$ 为右端点,左端点在区间 $[l,r+1]$ 内的所有子串的最小值之和

$$ \sum_{i=l}^{r+1}\min\{a[i,r+1]\} $$

设 $f[l][r]$ 为右端点为 $r$ ,左端点在 $[l,r]$ 之间的所有子串的最小值之和,设 $pre[r]$ 为比 $r$ 要小的前一个位置,那么显然有

$$ \begin{cases} f[l][r]=(r-pre[r])*a[r]+f[l][pre[r]] & (l \leq pre[r])\\ f[l][r]=(r-l+1)*a[r] & (l > pre[r]) \end{cases} $$

那么之前的式子就能直接用 $f[l][r+1]$ 替代
问题是 $f$ 需要 $n^2$ 的时间求得,有办法优化么?

如果将左端点固定为 $1$ ,那么这个式子显然就可以降到 $O(n)$ 级别

也就是说设 $f[pos]$ 为以 $pos$ 为右端点, $[1,pos]$ 为左端点的所有子串的最小值之和,那么有

$$ f[pos]=(pos-pre[pos])*a[pos]+f[pre[pos]]\\ $$

注意到, $f[pos]-f[pre[pos]]$ 相当于是 $pos$ 这个位置能做出的贡献,也就是说,是左端点在 $(pre[pos],pos]$ 右端点在 $pos$ 的所有子串最小值之和

显然这样的转移可以形成一个树状结构,假设 $a$ 位置是 $b$ 位置树上的祖先,那么 $f[b]-f[a]$ 就是以 $(a,b]$ 为左端点, $b$ 为右端点的子串最小值之和

如果我们求出 $\min\{a[l,r+1]\}$ 为 $a[p]$

显然,$a[p]$ 一定小于等于 $a[r+1]$ ,也就是说,该点一定是 $r+1$ 在树上的祖先
那么 $\sum_{i=p+1}^{r+1}\min\{a[i,r+1]\}=f[r+1]-f[p]$

那么剩下的 $\sum_{i=l}^{p}\min\{a[i,r+1]\}$ 显然等于 $a[p]*(p-l+1)$

这样就转移完成了!
删除和向右转移同理,总时间复杂度 $O(m\sqrt n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
int n, m, sqr;
int pre[N], nxt[N], sta[N], top;
ll a[N], f[N], g[N], ANS;
ll ans[N];
int L, R;
struct Query {
    int l, r, id;
    bool operator < (const Query a) const {
        if((l / sqr) == (a.l / sqr))
            return r < a.r;
        else
            return l < a.l;
    }
}q[N];
struct ST {
    int st[N][22], bin[22], _log[N];
    void build() {
        bin[0] = 1;
        for(int i = 1; i <= 20; ++ i)
            bin[i] = bin[i - 1] << 1;
        _log[0] = - 1;
        for(int i = 1; i <= n; ++ i)
            _log[i] = _log[i >> 1] + 1;
        for(int i = 1; i <= n; ++ i)
            st[i][0] = i;
        for(int j = 1; j <= 20; ++ j)
            for(int i = 1; i + bin[j] - 1 <= n; ++ i)
                st[i][j] = a[st[i][j - 1]] < a[st[i + bin[j - 1]][j - 1]] ? st[i][j - 1] : st[i + bin[j - 1]][j - 1];
    }
    int query(int l, int r) {
        int len = _log[r - l + 1];
        return a[st[l][len]] < a[st[r - bin[len] + 1][len]] ? st[l][len] : st[r - bin[len] + 1][len];
    }
}st;
void movel(int flag) {
    int p = st.query(L, R);
    ANS += (g[L] - g[p] + a[p] * (R - p + 1)) * flag;
}
void mover(int flag) {
    int p = st.query(L, R);
    ANS += (f[R] - f[p] + a[p] * (p - L + 1)) * flag;
}
void slove() {
    L = 1; R = 0;
    for(int i = 1; i <= m; ++ i) {
        while(L > q[i].l) {-- L; movel(1);}
        while(R < q[i].r) {++ R; mover(1);}
        while(L < q[i].l) {movel(- 1); ++ L;}
        while(R > q[i].r) {mover(- 1); -- R;}
        ans[q[i].id] = ANS;
    }
}
int main() 
    n = read(); m = read();
    sqr = sqrt(3 * n);
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    st.build();
    for(int i = 1; i <= n; ++ i) {
        while(top && a[sta[top]] > a[i]) sta[top --] = 0;
        pre[i] = sta[top];
        f[i] = a[i] * (i - pre[i]) + f[pre[i]];
        sta[++ top] = i;
    }
    while(top) sta[top --] = 0;
    for(int i = n; i >= 1; -- i) {
        while(top && a[sta[top]] > a[i]) sta[top --] = 0;
        nxt[i] = sta[top];
        g[i] = a[i] * (nxt[i] - i) + g[nxt[i]];
        sta[++ top] = i;
    }
    for(int i = 1; i <= m; ++ i) {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    slove();
    for(int i = 1; i <= m; ++ i)
        printf("%lld\n", ans[i]);
    return 0;
}
Last modification:February 9th, 2019 at 03:45 pm

Leave a Comment