[HNOI 2016]序列

时间：2023-01-03 15:11:06

Description

题库链接

给你一个长度为 \(n\) 的序列 \(A\) ，给出 \(q\) 组询问。每次询问 \([l,r]\) ，求该区间内所有的子序列中最小值的和。

\(1\leq n,q\leq 100000,|A_i|\leq 10^9\)

Solution

考虑把右端点右移时，会产生 \(r-l+1\) 个新的区间，我们可以来统计这 \(r-l+1\) 个区间的最小值和。

记 \(pre_i\) 为从第 \(i\) 位往左走第一个值比 \(A_i\) 小的位置。

显然在 \(l'\in(pre_r,r]\) 的区间 \([l',r]\) 中的最小值为 \(A_r\) 。

我们可以用这个性质做一遍前缀。记 \(sum_i\) 为右端点为 \(i\) 时，左端点在 \([1,i]\) 这段区间内所有区间中最小值的和。很容易用单调栈预处理出来。

那么对于移动右端点时，我们记 \(loc\) 为这段区间内的最小值所在的位置，显然移动右端点产生的贡献为 \(sum_r-sum_{loc}+A_{loc}\cdot(loc-l+1)\) 。

查询最小值可以用 \(st\) 表来解决。

对于移动左端点也类似，从右往左处理就好了。其余的就用莫队来实现。

Code

//It is made by Awson on 2018.2.12

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const int N = 100000;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

#define log2 LOG

int n, q, lim, block, a[N+5], log2[N+5], pre[N+5], nex[N+5], f[N+5][20], bin[25];

LL suml[N+5], sumr[N+5], ans[N+5];

int s[N+5], top;

struct tt {

    int l, r, id;

    bool operator < (const tt &b) const {return l/block == b.l/block ? r < b.r : l < b.l; }

}qry[N+5];

int query(int l, int r) {int lim = log2[r-l+1]; return a[f[l][lim]] < a[f[r-bin[lim]+1][lim]] ? f[l][lim] : f[r-bin[lim]+1][lim]; }

LL movel(int l, int r) {int loc = query(l, r); return sumr[l]-sumr[loc]+1ll*a[loc]*(r-loc+1); }

LL mover(int l, int r) {int loc = query(l, r); return suml[r]-suml[loc]+1ll*a[loc]*(loc-l+1); }

void work() {

    read(n), read(q); for (int i = 1; i <= n; i++) read(a[i]), f[i][0] = i;

    log2[0] = -1; for (int i = 1; i <= n; i++) log2[i] = log2[i>>1]+1;

    bin[0] = 1; for (int i = 1; i <= 20; i++) bin[i] = bin[i-1]<<1;

    lim = log2[n], block = sqrt(n);

    for (int i = 1; i <= n; i++) {

        while (top != 0 && a[s[top]] >= a[i]) --top;

        pre[i] = top == 0 ? 0 : s[top]; s[++top] = i;

    }

    s[top = 0] = 0;

    for (int i = n; i >= 1; i--) {

        while (top != 0 && a[s[top]] >= a[i]) --top;

        nex[i] = top == 0 ? n+1 : s[top]; s[++top] = i;

    }

    for (int i = 1; i <= n; i++) suml[i] = suml[pre[i]]+1ll*(i-pre[i])*a[i];

    for (int i = n; i >= 1; i--) sumr[i] = sumr[nex[i]]+1ll*(nex[i]-i)*a[i];

    for (int i = 1; i <= lim; i++) for (int j = 1; j <= n; j++) {

        if (j+bin[i-1] > n) break;

        f[j][i] = a[f[j][i-1]] < a[f[j+bin[i-1]][i-1]] ? f[j][i-1] : f[j+bin[i-1]][i-1];

    }

    for (int i = 1; i <= q; i++) read(qry[i].l), read(qry[i].r), qry[i].id = i;

    sort(qry+1, qry+1+q);

    int curl = 1, curr = 0; LL now = 0;

    for (int i = 1; i <= q; i++) {

        int l = qry[i].l, r = qry[i].r;

        while (curr < r) ++curr, now += mover(curl, curr);

        while (curl > l) --curl, now += movel(curl, curr);

        while (curr > r) now -= mover(curl, curr), --curr;

        while (curl < l) now -= movel(curl, curr), ++curl;

        ans[qry[i].id] = now;

    }

    for (int i = 1; i <= q; i++) writeln(ans[i]);

}

int main() {

    work(); return 0;

}

相关文章