考场做法，不用状压，不用矩形交并模型转换。

比题解好想还跑得飞快，lg 最优解。

做得时候完全没想起来扫描线，只是按自己的理解优化了普通线段树，所以你看我的题解不用特意学扫描线。

1.导入

求区间数量，我们应该立刻想到固定左 / 右端点，然后对另一个可选端点计数。 本题我们枚举 $1$ 到 $n$ 作为右端点。

2.分类

先解决 $K = 1$ 的情况，也就是保证区间内恰好有一个值为 $x$ 的。

当前右端点 $R$ 来说，值为 $a[R]$。

设上一个值为 $a[R]$ 的位置是 $p1$，上上个值为 $a[R]$ 的位置是 $p2$。

对于右端点 $r$，$[p2 + 1, p1]$ 这一段里的左端点选了就会有两个值为 $a[R]$ 的位置。也就是对于值 $a[R]$ 来说这一段的贡献 $-1$。

而这一段 $[p1 + 1, i]$ 里的的左端点是绝对可以选的，无论别的值，$a[R]$ 就只有一个，所以贡献 $+1$。

答案就很简单了，统计区间 $[1,R]$ 里不为 $0$ 的点数量。$0$ 就代表没有值出现数量刚好为 1 次的。

3.算法

区间修改区间查询，考虑线段树。但一般线段树查询不了区间内不为 $0$ 的个数，怎么办？

猫娘这里打了个不在查询范围符合时马上返回的 query 函数。

同时线段树维护区间最小值 $mn$ 和区间最大值 $mx$ 进行剪枝，当 $mn > 0$ 直接返回区间大小，当 $mx <= 0$ 直接返回 $0$。

这是 $K = 1$ 的 42 分考场代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define lc (p << 1)
#define rc ((p << 1) | 1)
const int N = 1e5 + 10;

int n, K;
int a[N], pre[N], las[N];

struct Node {
    int l, r;
    LL mn, mx, lazy;   // 最小值和最大值
} tr[N << 2];

void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
}

void pushup(int p) {
    tr[p].mn = min(tr[lc].mn, tr[rc].mn);
    tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}

void pushdown(int p) {
    if (tr[p].lazy) {
        LL c = tr[p].lazy;
        for (int ch : {lc, rc}) {
            tr[ch].mn += c;
            tr[ch].mx += c;
            tr[ch].lazy += c;
        }
        tr[p].lazy = 0;
    }
}

void change(int p, int l, int r, LL c) {
    if (r < tr[p].l || tr[p].r < l) return;
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].mn += c;
        tr[p].mx += c;
        tr[p].lazy += c;
        return;
    }
    pushdown(p);
    change(lc, l, r, c);
    change(rc, l, r, c);
    pushup(p);
}

LL query(int p, int l, int r) {
    if (r < tr[p].l || tr[p].r < l) return 0;
    if (l <= tr[p].l && tr[p].r <= r) {
        if (tr[p].mn > 0) return tr[p].r - tr[p].l + 1;   // 全部有效
        if (tr[p].mx <= 0) return 0;                      // 全部无效
    }
    pushdown(p);
    return query(lc, l, r) + query(rc, l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> K;
    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(las, 0, sizeof(las));
    for (int i = 1; i <= n; i++) {
        pre[i] = las[a[i]];
        las[a[i]] = i;
    }

    build(1, 1, n);
    LL ans = 0;

    for (int r = 1; r <= n; r++) {
        int p1 = pre[r];       
        int p2 = pre[p1];      

        change(1, p1 + 1, r, 1);
        if (p1) change(1, p2 + 1, p1, -1);

        ans += query(1, 1, r);
    }

    cout << ans << "\n";
    return 0;
}

4.正解

有了 $K = 1$ 的方法，那其实我们可以通过调整 $p1$ 和 $p2$ 是 $a[R]$ 前缀链上的位置，来达到恰好 1 个相同值、恰好 2 个相同值、恰好 3 个相同值和恰好 4 个相同值的效果。

我们给每个线段树节点开四倍，分别维护恰好 1 个相同值、恰好 2 个相同值、恰好 3 个相同值和恰好 4 个相同值，所对应的线段树区间。

当且仅当该查询区间里的线段树四个值都不为 $0$ 时，该区间才成立。

说着可能不好懂，我给你们放代码：

#include<bits/stdc++.h>
using namespace std;

#define lc (p << 1)
#define rc ((p << 1) | 1)
const int N = 1e5 + 10;

int n, K;
int a[N], pre[N], las[N];

struct Node {
    int l, r;
    int mn[6], mx[6], lazy[6];
} tr[N << 2];

inline void build(int p, int l, int r) {
	tr[p].l = l; tr[p].r = r;
    memset(tr[p].mn, 0, sizeof tr[p].mn);
    memset(tr[p].mx, 0, sizeof tr[p].mx);
    memset(tr[p].lazy, 0, sizeof tr[p].lazy);
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
}

inline void pushup(int p) {
	for (int i = 1; i <= K; i ++) {
	    tr[p].mn[i] = min(tr[lc].mn[i], tr[rc].mn[i]);
	    tr[p].mx[i] = max(tr[lc].mx[i], tr[rc].mx[i]);
	}
}

inline void pushdown(int p) {
	for (int i = 1; i <= K; i ++) {
	    if (tr[p].lazy[i]) {
	        int c = tr[p].lazy[i];
	        for (int ch : {lc, rc}) {
	            tr[ch].mn[i] += c;
	            tr[ch].mx[i] += c;
	            tr[ch].lazy[i] += c;
	        }
	        tr[p].lazy[i] = 0;
	    }
	}
}

inline void change(int p, int l, int r, int id, int c) {
    if (r < tr[p].l || tr[p].r < l) return;
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].mn[id] += c;
        tr[p].mx[id] += c;
        tr[p].lazy[id] += c;
        return;
    }
    pushdown(p);
    change(lc, l, r, id, c);
    change(rc, l, r, id, c);
    pushup(p);
}

inline int query(int p, int l, int r) {
    if (r < tr[p].l || tr[p].r < l) return 0;
    if (l <= tr[p].l && tr[p].r <= r) {
		bool fx = 1;
    	for (int i = 1; i <= K; i ++) {
    		if (tr[p].mx[i] <= 0) {  
			// 强劲剪枝！如果恰好组里有一个不合法，整个区间不合法 
    			fx = 0;
    			break;
			}
		}
		if (fx == 0) return 0;                      // 全部无效
    	bool fn = 1;
    	for (int i = 1; i <= K; i ++) {
    		if (tr[p].mn[i] <= 0) {
    			fn = 0;
    			break;
			}
		}
		if (fn == 1) return tr[p].r - tr[p].l + 1;   // 全部有效
    }
    pushdown(p);
    return query(lc, l, r) + query(rc, l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> K;
    for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}

    memset(las, 0, sizeof(las));
    for (int i = 1; i <= n; i ++) {
        pre[i] = las[a[i]];
        las[a[i]] = i;
    }

    build(1, 1, n);
    long long ans = 0;

    int pp[10]; 
    for (int r = 1; r <= n; r ++) {
        pp[0] = r;
        for (int i = 1; i <= K + 1; i ++) {
            pp[i] = pre[pp[i - 1]];  // 层数前缀链 
        }

        // 左端点区间 (p[1], r] 的 cnt[1] 加 1
        // 因为在这个区间里你给 a[r] 的数量从 0 变成 1
		// 所以恰好 1 的贡献要集体加 1  
        if (pp[1] + 1 <= r)
            change(1, pp[1] + 1, r, 1, 1);

        // 左端点区间 (p[t+1], p[t]] 的 cnt[t] 减 1，cnt[t+1] 加 1
        // 同理这个区间内，你给 a[r] 的数量 + 1
		// a[r] 的数量从 t 变成 t + 1
        for (int t = 1; t <= K - 1; t ++) {
            int L = pp[t + 1] + 1;
            int R = pp[t];
            if (L <= R) {
                change(1, L, R, t, -1);
                change(1, L, R, t + 1, 1);
            }
        }

        // 区间 (p[K+1], p[K]] 的 cnt[K] 减 1
        // 同理，因为我们不在意 cnt[K + 1]，所以没有那么公整的结构  
        int L = pp[K + 1] + 1;
        int R = pp[K];
        if (L <= R) {
            change(1, L, R, K, -1);
        }

        ans = ans + 1ll * query(1, 1, r);
    }

    cout << ans << "\n";
    return 0;
}

5.时间复杂度

总修改是 $O(NKlogN)$，但总查询最坏是 $O(N^2)$。

那为什么还跑得比双 log 快？

因为 $mn/mx$ 数组维护的是每个位置左侧最近出现次数（类似滑动窗口统计），随着区间向右扩展，mn[i] 和 mx[i] 具有单调性。

实际运行中，大部分区间会在节点级别被直接剪枝，不需要递归到叶子。

所以总查询近似 $O(NlogN)$，当然比双 log 快。