meaning of the title

Title Link

Sol

Line tree board problems can not be done, it is more and more vegetables..

According to the description of the topic, a legal interval is equivalent to that the color in the interval does not appear outside the interval.

So we can count where the longest left endpoint is for each right endpoint. At first, we thought it was monotonous, but it's not..

For each color, we calculated the optimal position \ (r_i \) and the leftmost position \ (l_i \)

For a left endpoint \ (J \), if \ (r_j > I \), then \ (J \) and the point on the left cannot be selected. Here, heap + multiset can be used for maintenance.

If \ (r_j \leqslant i \), then \ ((l_j, r_j] \) cannot be selected.

Then we can assign the interval of the line tree directly

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define Fin(x) freopen(#x".in", "r", stdin);
#define Pair pair<int, int>
#define fi first
#define se second 
template<typename A, typename B> inline bool chmax(A &x, B y) {return x < y ? x = y, 1 : 0;}
template<typename A, typename B> inline bool chmin(A &x, B y) {return x > y ? x = y, 1 : 0;}
#define LL long long 
using namespace std;
const int MAXN = 2e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], r[MAXN], l[MAXN], tag[MAXN];
multiset<int> s;
priority_queue<Pair, vector<Pair>, greater<Pair> > q;
void Erase(int x) {
    auto it = s.find(x);
    s.erase(it);
}
#define ls k << 1
#define rs k << 1 | 1
int f[MAXN], sum[MAXN];
void update(int k) {
    sum[k] = sum[ls] + sum[rs];
}
void ps(int k) {
    sum[k] = 0; f[k] = 1;
}
void pushdown(int k) {
    if(!f[k]) return ;
    ps(ls); ps(rs);
    f[k] = 0;
}
void Build(int k, int l, int r) {
    f[k] = 0; 
    if(l == r) {sum[k] = 1; return ;}
    int mid = l + r >> 1;
    Build(ls, l, mid); Build(rs, mid + 1, r);
    update(k);
}
int Query(int k, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return sum[k];
    pushdown(k);
    int mid = l + r >> 1;
    if(ql > mid) return Query(rs, mid + 1, r, ql, qr);
    else if(qr <= mid) return Query(ls, l, mid, ql, qr);
    else return Query(ls, l, mid, ql, qr) + Query(rs, mid + 1, r, ql, qr);
}
void Mem(int k, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) {ps(k); return ;}
    pushdown(k);
    int mid = l + r >> 1;
    if(ql <= mid) Mem(ls, l, mid, ql, qr);
    if(qr  > mid) Mem(rs, mid + 1, r, ql, qr);
    update(k);
}
void solve() {
    N = read(); int mx = 0;
    for(int i = 1; i <= N; i++) l[i] = INF, r[i] = 0, tag[i] = 0; 
    for(int i = 1; i <= N; i++) a[i] = read(), chmax(r[a[i]], i), chmin(l[a[i]], i), chmax(mx, a[i]);
    Build(1, 1, N);
    LL ans = 0;
    for(int i = 1; i <= N; i++) {
        q.push({r[a[i]], i}); s.insert(i);
        if(r[a[i]] == i) 
            if(l[a[i]] + 1 <= i) Mem(1, 1, N, l[a[i]] + 1, i);
        int mx = 0;
        while(!q.empty() && q.top().fi <= i)
            Erase(q.top().se), q.pop();
        if(!s.empty()) {
            auto it = s.end(); it--;
            mx = (*it);
        }
        if(mx + 1 <= i) ans += Query(1, 1, N, mx + 1, i);
    }
    cout << ans << '\n';
}
signed main() {
//  Fin(a);
    for(int T = read(); T--; solve());
    return 0;
}