Can You Solve the Harder Problem?(后缀数组+单调栈)

描述

传送门:2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest - Problem H

You are given a sequence $\textbf{a}$ denoted by $(a_1, a_2, \cdots, a_n)$. A query with $1 \leq l \leq r \leq n$ is defined as
$Q_{max}(l, r) = \max\lbrace a_l, a_{l + 1}, \cdots, a_r\rbrace$.
An easy problem may ask you to calculate the sum of answers for all queries with integers $1 \leq l \leq r \leq n$, but we would like to show you a harder one.

Define a classifier as a container that stores unique elements. Each element in the classifier has two values, named the key value and the mapped value. The key value of each element is a consecutive subsequence of $\textbf{a}$ and the mapped value of that element is an integer indicating the maximum value in the subsequence. The classifier only stores elements with distinct key values, which means extra duplicated elements (with the same key value) would be removed from the classifier.

Denote $S(l, r)$ as $(a_l, a_{l + 1}, \cdots, a_r)$, a consecutive subsequence of $\textbf{a}$ meeting the condition that $l$ and $r$ are integers with $1 \leq l \leq r \leq n$. Now we intend to use a classifier $\textbf{CA}$ to store all the consecutive subsequences $S(l, r)$ of $\textbf{a}$ with their $Q_{max}(l, r)$. You are asked to determine the sum of mapped values in $\textbf{CA}$.

Actually, what we defined above is a map of the form map<vector<int>, int> in C++ or Map<ArrayList<Integer>, Integer> in Java, so if you are seasoned using these data structures, you may realize that what we intend to do is to insert all possible elements $(S(l, r), Q_{max}(l, r))$ with integers $1 \leq l \leq r \leq n$ into the classifier $\textbf{CA}$ and then ask you to calculate the sum of mapped values in it.

Input

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $1000$.

For each test case, the first line contains an integer $n$ indicating the number length of the given sequence $\textbf{a}$, where $1 \leq n \leq 2 \times 10^5$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$ describing the sequence $\textbf{a}$, where $1 \leq a_i \leq 10^6$.

We guarantee that there are at most $10$ test cases with $n > 1000$.

Output

For each test case, output a line containing the sum of mapped values in $\textbf{CA}$.

Example

Input

1
2
3
4
5
2
3
1 2 3
3
2 3 3

Output

1
2
14
14

Note

In the first sample case, the sum of mapped values in $\textbf{CA}$ is equal to $1 + 2 + 3 + 2 + 3 + 3$.

In the second sample case, the sum of mapped values in $\textbf{CA}$ is equal to $2 + 3 + 3 + 3 + 3$.

思路

  • 题意就是求所有本质不同的子段的最大值的和。
  • 如果要求所有的子段,只需要用单调栈处理出每个数作为最大值的贡献即可。
  • 考虑如何去除重复的子段:
    • 用后缀数组把后缀排个序,利用 height 数组去重。
    • 和求本质不同子串数量一样的思路,答案就是每个后缀的所有前缀的最大值的和减去相邻两个后缀的公共前缀的最大值的和
  • 把后缀数组中的查询离线掉,逆序枚举左端点 $L$,用线段树维护到某个右端点 $R$ 的最大值。
  • 这样就可以在线段树上区间求和得到某个后缀的前若干个前缀的最大值的和。
  • 单调栈预处理右边第一个比它大的数的位置就可以在线段树上区间更新了。

代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1 << 20;
namespace Suffix_Array
{
int s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], rank[maxn], height[maxn];
void build_sa(int m, int n)
{
n++;
int *x = t, *y = t2;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; ~i; i--) sa[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (int i = n - k; i < n; i++) y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k) y[p++] = sa[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 0; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (int i = 1; i < n; i++)
x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
if (p >= n) break;
m = p;
}
n--;
int k = 0;
for (int i = 0; i <= n; i++) rank[sa[i]] = i;
for (int i = 0; i < n; i++)
{
if (k) k--;
int j = sa[rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
height[rank[i]] = k;
}
}
} // namespace Suffix_Array
typedef long long ll;

namespace Segment_Tree
{
#define lson o << 1
#define rson o << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson

ll sum[maxn << 2], setv[maxn << 2];

inline void pushup(int o)
{
sum[o] = sum[lson] + sum[rson];
}

inline void pushdown(int o, int m)
{
if (!setv[o]) return;
setv[lson] = setv[rson] = setv[o];
sum[lson] = setv[lson] * (m - (m >> 1));
sum[rson] = setv[rson] * (m >> 1);
setv[o] = 0;
}

void build(int l, int r, int o)
{
if (l == r)
{
sum[o] = 0;
return;
}
const int m = l + r >> 1;
build(Lson);
build(Rson);
pushup(o);
}

void update(int L, int R, int v, int l, int r, int o)
{
if (L <= l && r <= R)
{
setv[o] = v;
sum[o] = 1LL * v * (r - l + 1);
return;
}
pushdown(o, r - l + 1);
const int m = l + r >> 1;
if (L <= m) update(L, R, v, Lson);
if (m < R) update(L, R, v, Rson);
pushup(o);
}
ll query(int L, int R, int l, int r, int o)
{
if (L > R) return 0;
if (L <= l && r <= R) return sum[o];
pushdown(o, r - l + 1);
const int m = l + r >> 1;
ll ans = 0;
if (L <= m) ans += query(L, R, Lson);
if (m < R) ans += query(L, R, Rson);
return ans;
}

} // namespace Segment_Tree

using namespace Suffix_Array;
using namespace Segment_Tree;
int R[maxn];
int ask[maxn];

void solve(int* a, int n)
{
stack<int> s;
for (int i = 0; i < n; i++)
{
while (!s.empty() && a[i] > a[s.top()]) R[s.top()] = i - 1, s.pop();
s.push(i);
}
while (!s.empty()) R[s.top()] = n, s.pop();
ll ans = 0;
build(0, n - 1, 1);
for (int i = n - 1; ~i; i--)
{
update(i, R[i], a[i], 0, n - 1, 1);
ll x = query(i, n - 1, 0, n - 1, 1);
ll y = query(i, ask[i], 0, n - 1, 1);
ans += x, ans -= y;
}
printf("%lld\n", ans);
}

void solveTask()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &s[i]);
s[n] = 0;
int m = *max_element(s, s + n) + 1;
build_sa(m, n);
for (int i = 1; i <= n; i++) ask[sa[i]] = sa[i] + height[i] - 1;
solve(s, n);
}

int main()
{
int T;
scanf("%d", &T);
while (T--) solveTask();
return 0;
}
捐助作者
0%