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

比题解好想还跑得飞快，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 快。

deepseek 创作的神秘题解，代码从洛谷拷的。

题意转化

题目要求统计区间 $[l, r]$ 的数量，使得对于每个 $i \in [1, k]$，都存在至少一个数字 $x$，它在区间内恰好出现 $i$ 次。

我们把每一个可能的区间 $[l, r]$ 看成二维平面上的一个点 $(l, r)$，其中 $1 \le l \le r \le n$。
对于某个数字 $x$，它出现恰好 $i$ 次的所有区间，在平面上会形成若干个矩形的并集。
记 $A_i$ 为“存在某个数字出现恰好 $i$ 次”的区间集合，即

$$A_i = \bigcup_{x} \bigl\{ [l,r] \mid x \text{ 在 } [l,r] \text{ 中出现恰好 } i \text{ 次} \bigr\}.$$

那么题目所求就是：

$$\left| \bigcap_{i=1}^{k} A_i \right|.$$

---

容斥原理

直接求交集比较困难，但可以用容斥转化为并集：

$$\left| \bigcap_{i=1}^{k} A_i \right| = \sum_{\varnothing \ne S \subseteq \{1,\dots,k\}} (-1)^{|S|+1} \left| \bigcup_{i \in S} A_i \right|.$$

其中每个 $\bigcup_{i \in S} A_i$ 表示：区间中存在某个数字，其出现次数属于集合 $S$。
这可以通过扫描线计算并集面积得到。

---

单个数字出现恰好 $i$ 次的矩形构造

设数字 $x$ 的出现位置为

$$p_1 < p_2 < \cdots < p_m,$$

并定义哨兵 $p_0 = 0,\ p_{m+1} = n+1$。

如果我们要让 $x$ 恰好出现 $i$ 次，就必须选中连续 $i$ 个出现位置

$$p_j, p_{j+1}, \dots, p_{j+i-1}.$$

那么区间 $[l, r]$ 要满足：

• 左端点 $l$ 必须在 $(p_{j-1}, p_j]$，即 $l \in [p_{j-1}+1,\ p_j]$；
• 右端点 $r$ 必须在 $[p_{j+i-1},\ p_{j+i})$，即 $r \in [p_{j+i-1},\ p_{j+i}-1]$。

因此在二维平面 $(l, r)$ 上，这对应一个矩形：

$$[l, r] \in [p_{j-1}+1,\ p_j] \times [p_{j+i-1},\ p_{j+i}-1].$$

---

扫描线求并集面积

我们用扫描线沿 $r$ 方向移动，维护当前 $r$ 下，有多少个左端点 $l$ 被至少一个矩形覆盖。
对每个矩形，它在 $r$ 方向上的区间是 $[p_{j+i-1},\ p_{j+i}-1]$，在 $l$ 方向上的区间是 $[p_{j-1}+1,\ p_j]$。

扫描时，当 $r = p_{j+i-1}$ 时，将 $l$ 区间加入覆盖；当 $r = p_{j+i}$ 时，将 $l$ 区间移除。

---

代码实现细节

数据结构 DS

线段树维护一个数组 $\text{cover}[l]$（当前 $r$ 下，位置 $l$ 被覆盖的次数），支持区间加（加入/移除矩形），并需要快速查询 覆盖次数为 0 的位置个数。

线段树每个节点存储：

• mn：区间内覆盖次数的最小值；
• cnt：区间内等于 mn 的位置个数。

当查询整个区间时：

• 若 mn == 0，则未被覆盖的位置数 = $n - \text{cnt}$（因为 $\text{cnt}$ 是等于 0 的位置数）；
• 若 mn > 0，则所有位置都被覆盖至少一次，贡献为 $n$。

这样就能 $O(\log n)$ 得到当前 $r$ 下被覆盖的左端点个数。

函数 solve(st)

参数 st 是一个二进制掩码，表示需要满足的出现次数集合 $S$（其中第 $i$ 位对应次数 $i$）。

它计算：

$$\left| \bigcup_{i \in S} A_i \right|.$$

实现：

1. 清空所有事件 upd。
2. 遍历每个数字 $x$（代码中用 $i$ 表示）。
3. 对于 st 中每个为 1 的位 $s$（表示次数），枚举数字 $x$ 的所有连续 $s$ 个出现位置。
   • 设出现位置数组为 $\text{occ}[x]$（包含哨兵 0 和 $n+1$）。
   • 令 $j$ 为连续 $s$ 个出现位置的结尾下标（即第 $j$ 个位置是最后出现的那一个），则这 $s$ 个位置是 $\text{occ}[x][j-s+1] \dots \text{occ}[x][j]$。
   • 构造矩形：
     • $r$ 方向区间：$[\text{occ}[x][j], \text{occ}[x][j+1)-1]$，因此事件在 $\text{occ}[x][j]$ 加入，在 $\text{occ}[x][j+1]$ 移除；
     • $l$ 方向区间：$[\text{occ}[x][j-s]+1,\ \text{occ}[x][j-s+1]]$。
   • 将加入事件存入 $\text{upd}[\text{occ}[x][j]]$，移除事件存入 $\text{upd}[\text{occ}[x][j+1]]$。
4. 扫描 $r$ 从 1 到 $n$，依次处理所有事件，用线段树动态维护覆盖情况，统计每个 $r$ 下被覆盖的左端点个数，累加得到并集大小。

主函数容斥

枚举所有非空子集：

for (int mask = 1; mask < (1 << k); mask++) {
    int res = solve(mask);
    if (__builtin_popcount(mask) & 1) ans += res;
    else ans -= res;
}

则 $ans$ 即为答案。

代码：

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

const int MAXN = 1e5 + 10;
int n, k;
long long ans;          // 最终答案，使用 long long
int a[MAXN];
vector<int> occ[MAXN];  // occ[x] 存储数字 x 在数组中的所有出现位置（含哨兵）

// 线段树命名空间，用于维护区间覆盖次数的最小值及其个数
namespace DS {
    struct INFO {
        int mn;   // 区间内覆盖次数的最小值
        int cnt;  // 区间内等于 mn 的位置个数
    } t[MAXN << 2];
    int tag[MAXN << 2]; // 懒惰标记

    // 合并两个 INFO
    INFO operator +(const INFO &A, const INFO &B) {
        INFO res;
        res.mn = min(A.mn, B.mn);
        res.cnt = 0;
        if (A.mn == res.mn) res.cnt += A.cnt;
        if (B.mn == res.mn) res.cnt += B.cnt;
        return res;
    }

    // INFO 加上一个整数（区间加）
    INFO operator +(const INFO &A, int v) {
        return {A.mn + v, A.cnt};
    }

    // 建树，初始所有位置覆盖次数为 0
    void build(int k, int l, int r) {
        tag[k] = 0;
        t[k] = {0, r - l + 1};
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
    }

    // 下传标记
    void push_down(int k, int l, int r) {
        if (tag[k] == 0) return;
        int mid = (l + r) >> 1;
        int lc = k << 1, rc = k << 1 | 1;
        tag[lc] += tag[k];
        tag[rc] += tag[k];
        t[lc] = t[lc] + tag[k];
        t[rc] = t[rc] + tag[k];
        tag[k] = 0;
    }

    // 区间加：将 [x, y] 加上 v
    void update(int k, int l, int r, int x, int y, int v) {
        if (x <= l && r <= y) {
            tag[k] += v;
            t[k] = t[k] + v;
            return;
        }
        push_down(k, l, r);
        int mid = (l + r) >> 1;
        if (x <= mid) update(k << 1, l, mid, x, y, v);
        if (y > mid) update(k << 1 | 1, mid + 1, r, x, y, v);
        t[k] = t[k << 1] + t[k << 1 | 1];
    }
}

// upd[i] 存储扫描线在 r = i 时需要处理的矩形事件
// 每个事件为 ((l1, l2), delta)，表示在 l 轴区间 [l1, l2] 上加上 delta
vector<pair<pair<int,int>, int>> upd[MAXN];

// solve(st)：计算满足出现次数属于集合 st 的区间数量（并集面积）
// st 是掩码，第 i 位为 1 表示次数 i 在集合中
long long solve(int st) {
    // 清空事件
    for (int i = 1; i <= n; i++) upd[i].clear();
    // 枚举每个数量 s
    for (int s = 1; s <= k; s++) {
        if (!(st & (1 << (s - 1)))) continue;
        // 遍历整个数组 
        for (int i = 1; i <= n; i++) {
            // 对于每个数字 i，枚举其出现位置中的连续 s 段
            // j 是连续 s 个出现位置的最后一个下标（从 0 开始，哨兵在开头）
            // 要求 j >= s，且 j+1 < occ[i].size()
            for (int j = s; j + 1 < (int)occ[i].size(); j++) {
                // 构造矩形：
                // l 方向区间：[occ[i][j-s] + 1, occ[i][j-s+1]]
                // r 方向区间：[occ[i][j], occ[i][j+1] - 1]
                // 扫描线沿 r 方向，事件在 occ[i][j] 加入，在 occ[i][j+1] 移除
                int l1 = occ[i][j - s] + 1;
                int l2 = occ[i][j - s + 1];
                int r1 = occ[i][j];
                int r2 = occ[i][j + 1]; // 移除位置（半开区间）
                upd[r1].push_back({{l1, l2}, 1});
                upd[r2].push_back({{l1, l2}, -1});
            }
        }
    }

    long long res = 0;
    DS::build(1, 1, n);  // 初始化线段树，所有位置覆盖次数为 0
    for (int r = 1; r <= n; r++) {
        // 处理所有在 r 位置的事件
        for (auto &pr : upd[r]) {
            int l1 = pr.first.first;
            int l2 = pr.first.second;
            int delta = pr.second;
            DS::update(1, 1, n, l1, l2, delta);
        }
        // 查询当前 r 下，未被任何矩形覆盖的左端点数量
        if (DS::t[1].mn == 0) {
            // 最小值为 0，则未被覆盖的个数 = n - (等于 0 的个数)
            res += n - DS::t[1].cnt;
        } else {
            // 所有位置都被覆盖，贡献为 n
            res += n;
        }
    }
    return res;
}

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

    cin >> n >> k;
    // 为每个数字加入哨兵 0
    for (int i = 1; i <= n; i++) occ[i].push_back(0);

    // 读入数组并记录出现位置
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        occ[a[i]].push_back(i);
    }

    // 为每个数字加入哨兵 n+1
    for (int i = 1; i <= n; i++) occ[i].push_back(n + 1);

    // 容斥：枚举所有非空子集
    for (int mask = 1; mask < (1 << k); mask++) {
        long long res = solve(mask);
        if (__builtin_popcount(mask) & 1) ans += res;
        else ans -= res;
    }

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

附：

容斥原理详解

公式回顾

容斥原理（Inclusion-Exclusion Principle）是组合数学中一个基本而强大的工具，它给出了多个集合的交集大小与其并集大小之间的精确关系。对于任意 $k$ 个集合 $A_1, A_2, \dots, A_k$，有：

$$\left| \bigcap_{i=1}^k A_i \right| = \sum_{\emptyset \neq S \subseteq \{1, \dots, k\}} (-1)^{|S|+1} \left| \bigcup_{i \in S} A_i \right|.$$

其中：

• $\bigcap_{i=1}^k A_i$ 表示所有 $A_i$ 的交集，即同时属于每一个 $A_i$ 的元素集合；
• 求和遍历所有非空子集 $S \subseteq \{1,\dots,k\}$；
• $|S|$ 表示子集 $S$ 的大小；
• $\bigcup_{i \in S} A_i$ 表示子集 $S$ 中所有集合的并集；
• $(-1)^{|S|+1}$ 是符号因子：当 $|S|$ 为奇数时取正，偶数时取负。

---

为什么这个公式成立？

为了理解这个公式，我们考察一个任意元素 $x$ 在右侧求和式中被计数的次数。我们希望证明：

1. 若 $x$ 属于所有 $k$ 个集合，则其在右侧的总贡献为 $1$；
2. 若 $x$ 不属于至少一个集合，则其在右侧的总贡献为 $0$。

这正是左侧交集指示函数所期望的值。

情况 1：$x$ 属于所有集合

假设 $x \in A_1 \cap A_2 \cap \dots \cap A_k$。那么对于任意非空子集 $S \subseteq \{1,\dots,k\}$，都有 $x \in \bigcup_{i \in S} A_i$。因此，在右侧求和的所有 $2^k-1$ 个非空子集中，$x$ 都会被计入一次。

按子集大小分类：大小为 $j$（$1 \le j \le k$）的子集共有 $\binom{k}{j}$ 个，每个贡献符号 $(-1)^{j+1}$。所以 $x$ 的总贡献为：

$$\sum_{j=1}^k \binom{k}{j} (-1)^{j+1} = 1 - \sum_{j=0}^k \binom{k}{j} (-1)^j = 1 - (1-1)^k = 1.$$

因此，此时 $x$ 在右侧恰好被计算一次，与左侧相等。

情况 2：$x$ 不属于至少一个集合

设 $x$ 恰好属于 $r$ 个集合，其中 $0 \le r < k$。不失一般性，设 $x$ 属于 $A_1, \dots, A_r$，而不属于 $A_{r+1}, \dots, A_k$。

那么，在右侧求和中，只有那些 $S \subseteq \{1,\dots,r\}$ 的非空子集才会使得 $x \in \bigcup_{i \in S} A_i$。对于包含任何 $>r$ 的指标的子集，$x$ 不会出现在并集中。

因此，$x$ 的总贡献为：

$$\sum_{j=1}^r \binom{r}{j} (-1)^{j+1} = 1 - \sum_{j=0}^r \binom{r}{j} (-1)^j = 1 - (1-1)^r = 0.$$

所以此时 $x$ 在右侧不被计算，与左侧一致（因为 $x \notin \bigcap_{i=1}^k A_i$）。

综上，右侧求和式恰好等于交集的大小。

---

直观理解

两个集合

对于两个集合 $A_1, A_2$，容斥原理退化为熟悉的公式：

$$|A_1 \cap A_2| = |A_1| + |A_2| - |A_1 \cup A_2|.$$

这可以通过文氏图直观验证。

三个集合

对于三个集合，公式为：

$$|A_1 \cap A_2 \cap A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cup A_2| - |A_1 \cup A_3| - |A_2 \cup A_3| + |A_1 \cup A_2 \cup A_3|.$$

这符合一般模式：所有单个集合的并集取正，所有两两并集取负，三者并集取正。

---

在算法问题中的应用

在许多计数问题中，我们需要统计同时满足多个条件的对象个数，即求多个集合的交集。直接求交集往往困难，但求并集（满足至少一个条件的对象个数）可能容易实现。此时容斥原理提供了桥梁：

1. 定义 $A_i$ 为“满足第 $i$ 个条件”的对象集合；
2. 我们要求 $\left| \bigcap_{i=1}^k A_i \right|$；
3. 对于每个非空子集 $S$，计算 $\left| \bigcup_{i \in S} A_i \right|$（即满足子集中至少一个条件的对象数）；
4. 按容斥公式进行加减，得到交集大小。

在题目 P11390 [COCI 2024/2025 #1] 教师 / Učiteljica 中，我们将“区间满足某个数字出现次数恰好为 $i$”视为集合 $A_i$。要求的是同时满足所有 $i$（$1 \le i \le k$）的区间数。利用容斥原理，将其转化为对每个子集求并集面积（即满足某些出现次数至少一个的区间数），而并集面积可以通过扫描线 + 线段树高效计算。

---

总结

容斥原理是一个强大且优雅的工具，它将交集问题转化为并集问题，适用于各种计数场景。使用时需枚举所有非空子集，并正确应用符号 $(-1)^{|S|+1}$。它在组合数学、概率论和算法设计中均有广泛应用。

P11390 [COCI 2024/2025 #1] 教师 / Učiteljica 题解

---

知识点

线段树，扫描线，容斥，状压，线段树分治。

分析

首先可以很容易的看出这题和扫描线有关，把 $[l,r]$ 转换成图形上的点即可。我们直接看到子任务 3，满足特殊性质 B：$k = 1$。

那么这个就是把每个数字单独拎出来，然后把合法的矩形并在一起，最后求矩形面积并，扫描线解决很简单。

法 1：容斥

这个解法的题解是网上最多的，对于擅长组合数学的同学们很友好。

我们从刚刚的部分分进一步推理：发现 $k>1$ 时，就是把 $k$ 不同时的矩形并再取交集，然后再算面积。那么这个“并”“交”让人想到了容斥，所以容斥把「取交集」变成多次的「求并集」解决即可。

由于其他题解讨论的都较为详细，这里不再赘述。

时间复杂度 $O(k2^kn\log_2{n})$，空间复杂度 $O(nk)$。

法 2：线段树分治+状压

对于不擅长组合数学的同学们，这个做法可能会友好一点。

我们考虑不用容斥直接「取交集」。仍然是从部分分衍生出来，发现标记下传的线段树在矩形减操作时不太方便，于是可以想到线段树分治，避免矩形减操作。

再考虑状压来存储线段树上每个节点和其子节点已经满足的 $k$，那么很容易就可以解出来：线段树上每个节点存覆盖到自己的区间矩形加的状态，开 $2^k$ 大小的数组来存子树代表的区间中每种状态的数量。

时间复杂度 $O(k2^kn\log^2_2{n})$，空间复杂度 $O(n2^k)$。可能需要卡常。

法 3：永久化标记+状压

起始思路与法 2 类似。考虑部分分的线段树实现方法，我们可以标记下传，也可以标记永久化，而标记永久化明显十分简洁，所以我们考虑在正解也用标记永久化。那么就直接正常的扫描线扫过去即可。

时间复杂度 $O(k2^kn\log_2{n})$，空间复杂度 $O(n2^k)$。

大概是因为矩形只用加一次，导致这个做法是常数最小的，翻 Luogu 的提交记录，排名在前面的我有看到的都是这么写的。

代码

这里实现了永久化标记线段树配状压的做法。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e5+10),K(4),St(1<<4);

int n,m,U,tot;
int a[N];
ll ans;
vector<int> vec[N];
struct Line {
	int x,l,r,v,k;

	friend bool operator <(Line a,Line b) { return a.x<b.x; }
} lin[N<<3];
struct SEG {
	struct node {
		int sta;
		int cnt[K],sum[St];
		node(int sta=0):sta(sta) { RCL(cnt,0,int,m),RCL(sum,0,int,U+1); }

		void down(int k,int d) {
			if(cnt[k])sta^=1<<k;
			cnt[k]+=d;
			if(cnt[k])sta^=1<<k;
		}
	} tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
	void Up(int p) {
		RCL(tr[p].sum,0,int,U+1);
		FOR(S,0,U)tr[p].sum[tr[p].sta|S]+=tr[ls].sum[S]+tr[rs].sum[S];
	}

	void Build(int p=1,int l=1,int r=n) {
		tr[p]=node(0);
		if(l==r)return tr[p].sum[0]=1,void();
		Build(ls,l,mid),Build(rs,mid+1,r),Up(p);
	}

	void Plus(int L,int R,int k,int d,int p=1,int l=1,int r=n) {
		if(L<=l&&r<=R) {
			if(l==r)tr[p].sum[tr[p].sta]=0;
			tr[p].down(k,d),(l<r?Up(p),0:tr[p].sum[tr[p].sta]=1);
			return;
		}
		if(L<=mid)Plus(L,R,k,d,ls,l,mid);
		if(mid<R)Plus(L,R,k,d,rs,mid+1,r);
		Up(p);
	}
#undef ls
#undef rs
#undef mid
} seg;

void Plus(const int k,int xa,int xb,int ya,int yb) {
	lin[++tot]= {xa,ya,yb,1,k},lin[++tot]= {xb+1,ya,yb,-1,k};
}

void Solve(vector<int> &vec,const int k) {
	FOR(i,0,(int)vec.size()-k)
		Plus(k-1,!i?1:vec[i-1]+1,vec[i],vec[i+k-1],i+k>=(int)vec.size()?n:vec[i+k]-1);
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	cin>>n>>m;
	FOR(i,1,n)cin>>a[i],vec[a[i]].push_back(i);
	U=(1<<m)-1;
	FOR(i,1,n)if(!vec[i].empty())FOR(k,1,m)Solve(vec[i],k);
	sort(lin+1,lin+tot+1),seg.Build();
	int it(1);
	FOR(i,1,n) {
		while(it<=tot&&lin[it].x<=i)seg.Plus(lin[it].l,lin[it].r,lin[it].k,lin[it].v),++it;
		ans+=seg.tr[1].sum[U];
	}
	cout<<ans<<endl;
	return 0;
}

---