c/c++语言开发共享洛谷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; }