计数

Posted on Edited on In

题目大意：给你一个随机生成的1~n的排列。

并定义区间[l,r]的价值为\(C_{l,r} = max(a_i-a_j|l \leq i,j \leq j)\)

部分分很好拿，但是正解并不容易做，有很多种做法，单调栈，单调队列，ST表都可以做，几乎只要是可以维护最大值最小值的数据结构都可以做

这里只介绍ST表的做法，一个\(O(nlogn)\)预处理，\(O(1)\)查询的数据结构

先预处理ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void pres_dou()
{
    int i, j;
    for (i = 1; i <= n; ++ i) f[i][0] = a[i], g[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (j = 1; j < t; ++ j)
    {
        for (i = 1; i <= n - (1 << j) + 1; ++ i)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    }
    return;
}

查询的时候，考虑求出一个最大的\(k\)，使得\(l \leq 2^k\leq r\)， 有重叠也无妨

1
2
3
4
5
inline int query_maxv(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

题目分析：

1
2
3
回到这个题，我们求出每一个数的最小贡献，与最大贡献，并使之加和，答案就是最大贡献与最小贡献的差
其中，在求答案的时候，考虑这个数左右两边的端点
显然他左边的，他都可以贡献，他右边的，他也可以贡献，并且跨越他的区间，他也会贡献

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 66;

int n, res_minv, res_maxv;
int a[N], pos[N];
int f[N][66], g[N][66];

inline void pres_dou()
{
    int i, j;
    for (i = 1; i <= n; ++ i) f[i][0] = a[i], g[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (j = 1; j < t; ++ j)
    {
        for (i = 1; i <= n - (1 << j) + 1; ++ i)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    }
    return;
}

inline int query_maxv(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

inline int query_minv(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return min(g[l][k], g[r - (1 << k) + 1][k]);
}

inline void fuck_maxv(int l, int r)
{
    if (l > r || l == r) return;
    int maxv = query_maxv(l ,r);
    res_maxv += 1ll * (1ll * (pos[maxv] - l) * (r - pos[maxv]) + (1ll * pos[maxv] - l) + (r - pos[maxv])) * maxv;	
    fuck_maxv(l, pos[maxv] - 1);
    fuck_maxv(pos[maxv] + 1, r);
    return;
}

inline void fuck_minv(int l, int r)
{
    if (l > r || l == r) return;
    int minv = query_minv(l ,r);
    res_minv += 1ll * (1ll * (pos[minv] - l) * (r - pos[minv]) + (1ll * pos[minv] - l) + (r - pos[minv])) * minv;
    fuck_minv(l, pos[minv] - 1);
    fuck_minv(pos[minv] + 1, r);
    return;
}

signed main()
{
    int T = read(), i;
    while (T --)
    {
        memset(f, 0, sizeof f), memset(g, 0x3f, sizeof g);
        res_maxv = res_minv = 0;
        n = read();
        for (i = 1; i <= n; ++ i) a[i] = read(), pos[a[i]] = i;
        pres_dou();
        fuck_maxv(1, n), fuck_minv(1, n);
        put(res_maxv - res_minv);
    }
    return 0;
}