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
| #include<bits/stdc++.h> using namespace std; #define ll long long #define mid ((l + r)>> 1) #define lch rt << 1, l, mid #define rch (rt << 1) | 1, mid + 1, r typedef pair<int, int> pii; const int INF = 0x3f3f3f3f; const int maxn = 1e6 + 10; int T, n, tot; int a[maxn], tr[maxn << 2], q[maxn], lar[maxn]; ll w[maxn]; map<int, vector<int> >mp; void pushup(int rt) { tr[rt] = max(tr[rt << 1], tr[(rt << 1) | 1]); } void build(int rt, int l, int r) { if (l == r) { tr[rt] = a[l]; return; } build(lch); build(rch); pushup(rt); } int query(int ql, int qr, int rt, int l, int r) { if (ql <= l && qr >= r)return tr[rt]; int res = 0; if (ql <= mid)res = max(res, query(ql, qr, lch)); if (qr > mid)res = max(res, query(ql, qr, rch)); return res; }
int rk[maxn], tmp[maxn], k, sa[maxn], lcp[maxn]; bool compare_sa(int i, int j) { if (rk[i] != rk[j])return rk[i] < rk[j]; else { int ri = i + k <= n ? rk[i + k] : -1; int rj = j + k <= n ? rk[j + k] : -1; return ri < rj; } } void constract_sa(const int* S) { for (int i = 0; i <= n; i++) { sa[i] = i; rk[i] = i < n ? S[i] : -1; } for (k = 1; k <= n; k *= 2) { sort(sa, sa + n + 1, compare_sa); tmp[sa[0]] = 0; for (int i = 1; i <= n; i++) { tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); } for (int i = 0; i <= n; i++) { rk[i] = tmp[i]; } } } void constract_lcp(const int* S) { for (int i = 0; i <= n; i++) { rk[sa[i]] = i; } int h = 0; lcp[1] = 0; for (int i = 0; i < n; i++) { int j = sa[rk[i] - 1]; if (h > 0)h--; for (; j + h < n&&i + h < n; h++) { if (S[j + h] != S[i + h])break; } lcp[rk[i]] = h; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); scanf("%d", &T); while (T--) { mp.clear(); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); q[i] = a[i]; } sort(q, q + n); tot = unique(q, q + n) - q; for (int i = 0; i < n; i++) { a[i] = lower_bound(q, q + n, a[i]) - q; mp[a[i]].push_back(i); } stack<int>st; st.push(n); a[n] = INF; build(1, 0, n - 1); for (int i = n - 1; i >= 0; i--) { while (a[st.top()] <= a[i])st.pop(); lar[i] = st.top(); st.push(i); } w[n] = 0; w[n - 1] = q[a[n - 1]]; for (int i = n - 2; i >= 0; i--) { w[i] = (ll)q[a[i]] * (lar[i] - i) + w[lar[i]]; } constract_sa(a); constract_lcp(a); ll ans = 0; for (int i = 1; i <= n; i++) { if (lcp[i] == 0) { ans += w[sa[i]]; } else { int p = sa[i] + lcp[i] - 1; int mx = query(sa[i], p, 1, 0, n - 1); int pos; int tp = lower_bound(mp[mx].begin(), mp[mx].end(), p) - mp[mx].begin(); if (tp == mp[mx].size())pos = mp[mx][tp - 1]; else { if (mp[mx][tp] != p) pos = mp[mx][tp - 1]; else pos = mp[mx][tp]; } int ed = lar[pos]; ans += (ll)q[a[pos]] * (ed - p - 1) + w[ed]; } } printf("%I64d\n", ans); } return 0; }
|