B 一道简单题

一个ST表的题解

显然题目询问的那个东西有前缀和的性质

即$T(l,r,x)=T(l,x,x)-T(r+1,x,x)T(l,r,x)=T(l,x,x)-T(r+1,x,x)$

令$an{s}_i=T(1,i,i),f(l,r)ans\_i=T(1,i,i),f(l,r)$为区间$[l,r][l,r]$的最大值

$pospos$满足$a_{pos}=f(l-1,r)a\_\{pos\}=f(l-1,r)$

画个图计算一下贡献就知道

$T(l,r,r)T(l,r,r)$

$=an{s}_r-{\sum }_{i=1}^{l-1}f(i,r)=ans\_r-\backslash sum\_\{i=1\}^\{l-1\}f(i,r)$

$=an{s}_r-{\sum }_{i=1}^{l-1}f(i,pos)=ans\_r-\backslash sum\_\{i=1\}^\{l-1\}f(i,pos)$

$=an{s}_r-(an{s}_{pos}-{\sum }_{i=l}^{pos}f(i,pos))=ans\_r-(ans\_\{pos\}-\backslash sum\_\{i=l\}^\{pos\}f(i,pos))$

$=an{s}_r-(an{s}_{pos}-a_{pos}\times (pos-l+1))=ans\_r-(ans\_\{pos\}-a\_\{pos\}\backslash times(pos-l+1))$

这里利用了对于任意满足$f(k,r)=f(k,pos)f(k,r)=f(k,pos)$

对于任意$l\le k\le posl\backslash le\; k\backslash le\; pos$满足$f(k,pos)=a_{pos}f(k,pos)=a\_\{pos\}$

这样便实现了巧妙的转化。

用ST表维护一下区间最大值出现的位置即可

而对于$an{s}_{i}ans\_i$，可以借助优先队列在$O(nlogn)O(nlogn)$时间内预处理，大致思路就是每次弹出当前队列里面小于$a_{i}a\_i$的值，并计算相应的贡献变化，类似于Atcoder abc213F后半段的处理方法

总复杂度$O(nlogn+Q)O(nlogn+Q)$

每次查询是在线的$O(1)O(1)$，感觉比线段树的离线做法快上不少

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 2e5 + 10;
#define __cs() int T; cin >> T; while (T--)
#define endl '\n'
int n, Q, f[maxn][20];
ll ans[maxn], a[maxn], now;
priority_queue<pair<ll, ll>>q;
int ask(int l, int r)
{
    int len = log2(r - l + 1);
    return a[f[l][len]] > a[f[r + 1 - (1 << len)][len]] ? f[l][len] : f[r + 1 - (1 << len)][len];
}
void ST()
{
    for (int i = 1; i <= n; ++i)f[i][0] = i;
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i - 1 + (1 << j) <= n; ++i)
            f[i][j] = (a[f[i][j - 1]] > a[f[i + (1 << j - 1)][j - 1]] ? f[i][j - 1] : f[i + (1 << j - 1)][j - 1]);
}
ll get(int l, int r)
{
    if (l > r)return 0;
    if (l == 1)return ans[r];
    int pos = ask(l - 1, r);
    return ans[r] - (ans[pos] - a[pos] * (pos - l + 1));
}
void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        ll num = 1;
        scanf("%lld", &a[i]);
        while (!q.empty())
        {
            if (-a[i] <= q.top().first)
            {
                num += q.top().second;
                now += q.top().first * q.top().second;
                q.pop();
            }
            else break;
        }
        q.push({ -a[i],num });
        now += a[i] * num;
        ans[i] = now;
    }
    ST();
    scanf("%d", &Q);
    while (Q--)
    {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        printf("%lld", get(l, x) - get(r + 1, x));
        if (Q)putchar(' ');
    }
}
int main()
{
    solve();
    return 0;
}