洛谷P4065 [JXOI2017]颜色(线段树)

题意

题目链接

sol

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

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

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

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

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

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

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

// 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;
}