题意

Sol

线段树板子题都做不出来，真是越来越菜了。。

根据题目描述，一个合法区间等价于在区间内的颜色没有在区间外出现过。

所以我们可以对于每个右端点，统计最长的左端点在哪里，刚开始以为这个东西有单调性，但事实并不是这样。。

我们统计出对于每个颜色最优的位置\(r_i\)和最左的位置\(l_i\)

那么对于某个左端点\(j\)，如果\(r_j > i\)，那么\(j\)以及它左侧的点都是不能选的，这里可以用堆+multiset维护。

若\(r_j \leqslant i\)，那么\((l_j, r_j]\)都是不能选的。

然后直接线段树区间赋值就好了

// luogu-judger-enable-o2#include
    
     #define Fin(x) freopen(#x".in", "r", stdin);#define Pair pair
     
      #define fi first#define se second template
      
        inline bool chmax(A &x, B y) {return x < y ? x = y, 1 : 0;}template
       
         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
        
          s;priority_queue
         
          , greater
          
            > q;void Erase(int x) { auto it = s.find(x); s.erase(it);}#define ls k << 1#define rs k << 1 | 1int 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;}