九月算法竞赛选题（三）

[[ slider_text ]]

[[ item.c ]]

九月算法竞赛选题（三）

发布时间 2025-09-26 作者：秋千月 来源：算法小站

二维数点

## AtCoder Beginner Contest 424
### D
**[D - 2x2 Erasing 2](https://atcoder.jp/contests/abc424/tasks/abc424_d)**
给定$$n \times m$$的列，每一列都是`.`或者是`#`，其中`.`表示合法格子，是白色的
而`#`表示非法格子，是黑色的，一次操作，你可以将任何一个黑色格子改成白色的
现在问，最少几次操作，可以使得$$(i, j), (i+1, j), (i, j+1), (i+1, j+1)$$至少有一个是白色的

**算法分析**
注意到这个问题，$$n, m \leqslant 7$$，考虑**状态压缩 dp**
> 首先，每一行可以改成哪些状态

注意到，假设说一行的状态是`sta`，`.`记为`1`，`#`记为`0`
原来为`1`的位，改之后只能是`1`，原来是`0`的位，改之后`{0, 1}`都可以
换句话说，能够到达的`mask`，必须满足`mask & sta == sta`，符合这样条件的`mask`才可以到达
可以打表`valid(i) = {....}`

> 再来看，从`sta -> mask`，需要多少次操作？

如果`sta[i] = 1 and mask[i] = 1`，这一位不需要操作，当且仅当`sta[i] = 0 and mask[i] = 1`才需要操作
所以这里就用`popcnt( mask & ~sta )`，就是操作次数，当然暴力检查每一位也没有问题

> 接着考虑按行`dp`

```bash
for cur, last 枚举不同的 mask 状态
	当且仅当 last, cur 能够成为合法的相邻行, trans(last, cur) = true
	ndp(cur) = max( dp(last) + cost( init[i] 第 i 行起始状态 --> 变成 cur 需要的修改次数 ) )
```
怎么判断`last, cur`能否成为相邻行呢？打表，预处理即可，分别检查`last, cur 的第 j 位，第 j+1 位`
然后暴力判断即可

## CodeTON Round 7
### C
**[C. Matching Arrays](https://codeforces.com/contest/1896/problem/C)**
给定两个长度是`n`的数组`a, b`，定义数组的美丽度是满足$$a_i > b_i$$的下标`i`的数量
给定`x`，判断能不能通过重排`b`，使得数组的美丽度**恰好是**$$x$$，如果可以，输出方案

**算法分析**
> 特殊情况，$$x = 0$$的时候怎么做？

此时要求每一个位置都要$$a_i \leqslant b_i$$，那么对`a`排序，给`a[0]`配最小的`minb`
如果这样配，还不能满足的话，那么`minb`就必须放在位置$$i$$，那么$$a_0 \leqslant a_i$$
而`a[0] > minb`，所以`a[i] >= a[0] > minb`，`minb`放在之后的任何一个位置都不满足

所以最优策略就是对`a, b`分别从小到大排序，然后每个位置依次配对

> 考虑$$x > 0$$，剩下的$$y = n - x$$个元素，可以按之前的特殊情况`x = 0`处理

不难发现，对`b`**从小到大**排序，为每一个`b`找配对，前面的必须满足$$b_i < a_i$$
后面的必须满足$$b_i \geqslant a_i$$

也就是说，留给`[x, n)`的**候选`a`**，值越小越好，那么要尝试在前面$$x$$次$$b_i < a_i$$的匹配中
把**最大的`x`个**$$a$$给消耗掉，同时为了满足
```math
b_0 \leqslant \cdots b_i  \cdots \leqslant b_{x-1}
```
的限制，贪心地让`b[x-1], b[x-2], ...., b[0]`，依次匹配最大的`a`，这里候选`a`按**大根堆**维护

接着就是剩下的元素，后半部分，$$n - x$$个，按之前的**特殊情况**处理即可

## Codeforces Round 907
### C
**[Smilo and Monsters](https://codeforces.com/contest/1891/problem/C)**
有`n`个怪兽，每个怪兽血量是$$a_i$$，目标要消灭所有怪兽，有`2`种攻击方式
第一种，普攻，扣除血量`1`，连击点数$$x + 1$$
第二种，大招，选择血量$$\geqslant x$$（当前连击点数）的怪兽，血量`-= x`，并且让连击点数归`0`
一次大招记为一次攻击，普攻也作为一次攻击，请问消灭所有怪兽，最少的攻击次数

**算法分析**
> 大招一共能打的血量是多少？

假设说打了$$k$$次大招，那么$$x_1 + x_2 + \cdots + x_k = big$$是大招打掉的血量
另外能打这些大招的前提条件是，$$x_1 + x_2 + \cdots + x_k +(?)$$次的普攻
从而$$tot = 2(x_1 + x_2 + \cdots + x_k) + rem$$，$$rem = \\{0, 1\\}$$

> **贪心策略**

注意到，假设只有一个怪物，血量是`val`，那么$$2x \leqslant val$$，需要打的攻击次数$$x + 1$$
如果对$$x$$进行拆分，$$x = 2y$$，那么能打的血量是`{y + y}, {y + y}`，需要的攻击次数$$2(y+1) = 2y + 2$$
而$$2y = x$$，所以**拆分不优**，能够用大招，就尽量一次性秒杀

> 方法一，大招能够消耗的血量，$$big = \lfloor tot / 2 \rfloor$$

按血量从大到小排序，如果当前的`big >= a[i]`，直接`res += 1`，否则剩下的只能打普攻

> 方法二，直接模拟

直接模拟也可以做，就是**从小到大排序，双指针**，假设说当前积攒了$$cur$$次普攻
如果`cur + a[i] < a[j]`，那么当前大招还不足以击杀`a[j]`，`i += 1`
否则，当前大招可以击杀`a[j]`，但是不需要`a[i]`次普攻这么多，实际上只缺少了`extra = a[j] - cur`次
只需要在`a[i] -= extra`，先用`extra`次普攻扣除`a[i]`血量，然后再一次大招消除`j`，`j -= 1`

> 边界情况

最后假设说还剩下一个元素，已经有了`cur`次普攻了，我们仍希望一次普攻能够消灭`a[i]`，怎么办？
假设说还要`?`次普攻，那么这次普攻扣除的血量是`?`，还剩下`rem = a[i] - ?`这么多血量
而已经积攒的大招，能扣除的血量是`del = cur + ?`，要求`cur + ? <= a[i] - ?`
所以$$? = \lfloor \dfrac{a_i - cur}{2} \rfloor$$，那么这样就可以用一次大招击杀了

`res += ? + 1`，同时这个过程中扣除的血量是`? + (? + cur), a[i] -= cur + 2?`，看一下余数是多少？
要么是`0`，要么还剩下`1`的血，暴力普攻最后一次

## CodeTON Round 7
### D
**[D. Ones and Twos](https://codeforces.com/contest/1896/problem/D)**
给定一个序列，**每个数都是`1 or 2`**，给定`q`个查询
查询`1 S`，判断是否存在子数组，子数组必须连续，使得它的和为`S`
`2 i v`，单点修改，`a[i] = v`，其中`v = {1 or 2}`

**算法分析**
如果只有有限个询问，怎么做？
可以对每个点$$i$$开始，线段树二分，二分找到第一个$$\geqslant S$$的$$r$$
如果$$\sum [i, r] = S$$，那么答案就是`[i, r]`就是满足条件的区间，找到一个这样的区间即可

但询问很多的话，这样做会超时，因为题目中给出不是`1`就是`2`，形如`2k + 1, 2k`
考虑从`S`的奇偶性入手，另外题中不要求求出具体的值，只需要判断是否存在

> 考虑到已经存在和为$$sum$$的子序列了，问是否存在$$S$$的子序列

如果$$sum \geqslant S$$，并且`sum, S`同奇偶，那么一定存在，分为以下几种情况
如果`sum 形如 [1....1]`，那么去掉首尾两个`1`，就一定能构造出`sum - 2`
如果`sum 形如 [2...1] or [1...2]`，那么只需要去掉`2`，就一定能构造出`sum -2`

> 现在只要考虑`sum, S`不同奇偶，同时要令`sum`尽可能大

只要维护**第一个`1`出现的位置**$$L$$，以及**最后一个`1`出现的位置**$$R$$
```math
\displaystyle
\max \left(\sum_{i = L+1}^{n} a_i, \sum_{i = 1}^{R-1}a_i \right) = sum
```
如果存在`sum > S`，并且`sum 和 S 不同奇偶`，可以在`sum`中加入一个`1`，改变其奇偶性
这样就转换成同奇偶的情况来解决了

### E
**[E. Permutation Sorting](https://codeforces.com/contest/1896/problem/E)**
给定一个`n 的排列 a`，下标`i`是好的，当且仅当$$a_i = i$$，每经过一秒钟，将不是好的下标向右循环移位
比如`[3, 2, 4, 1, 5]`，其中`2, 5`是好的，`[3, 4, 1]`，向右循环移位，`[1, 3, 4]`
从而`[1, 2, 3, 4, 5]`，每个元素都是好的

现在输出，每个**下标**第一次变成好的时刻

**算法分析**
循环移位，对可操作的序列`[s1, s2, ..., sk]`，我们有$$s(i) = s(i \bmod k + 1)$$

> 首先考虑，如果没有**跳过好位置**的操作，怎么做？

对于位置$$i$$，位置上的值是$$a_i$$，那么`i 这个位置，a[i] 这个数`，**期望的合法位置是哪里呢？**
不妨用`to[i]`来表示

因为存在向右的**循环移位**，可以考虑复制一倍的链，然后考虑每个数`expect`的位置

对于$$a_i \geqslant i$$，只要正常去到`a[i]`即可，所以`to[i] = a[i]`
另外，对应地复制一半，有`to[n+i] = to[n + a[i]]`

而对于$$a_i < i$$，原本理应往左走，但是规定只能往右走，所以先走到`n`，然后再走`a[i]`步
所以`to[i] = n + a[i]`

这样，每个位置的移动路径就对应`[i, to[i]]`，即`i --> to[i]`
如果没有跳过好位置的限制，那么每个数对应的答案是确定的
`ans[ a[i] ] = to[i] - i`

> 在移动过程中，一些位置会变好，实际上并不需要移动这么多步，如果存在`1`个位置变好
那么`ans -= 1`

什么样的位置会变好呢？
```math
\displaystyle
\begin{cases}
i < j < to(i) \\
i < to(j) < to(i)
\end{cases}
```
满足上述条件的$$j$$会变好，计算`i`的答案的时候，要扣除有多少个符合条件的$$j$$
而这又是关于$$(j, to(j))$$的**二维数点**问题

封装成事件
```bash
对应 i = 1...2n 个添加事件
(x, y) = (i, to[i])

对应 i = 1...2n 个查询事件
[xl, xr] = [i, to[i]]
[yl, yr] = [i, to[i]]
```

> 优化

直接做，卡了空间，实际上不需要`4`个事件，`1 个添加事件，2 个查询事件就够了`
因为$$xr = yr, xl = yl$$，所以实际上只需要`2`个查询事件
```bash
(xr, yl) and (xl, yr)

evts.emplace_back(arr{xr, 2, yl, i});
evts.emplace_back(arr{xl, 1, yr, i});
```

接下来就是正常的二维数点，添加操作照旧，而对于查询操作
```bash
本来应该是 4 个事件
[xr, 2, yr, i]
[xl, 2, yl, i]
[xr, 1, yl, i]
[xl, 1, yr, i]

现在我们为了节省空间，只存了 2 个事件，因为 xr = yr
所以只存 (xr, yl), (xl, yr)

这样的话
[_x, type, _y, i] 就蕴含两个事件

事件1: yr = _x, type = 2
事件2: yl = _y, type = 1

对这两种事件，按照普通的二维数点进行处理即可
```

#### 算法实现
**事件添加部分**
```bash
// [y, type, x, i]
for (int j = 1; j <= N; j++) {
	auto x = j;
	auto y = to[j];

evts.emplace_back(arr{x, 0, y, j});
}

for (int i = 1; i <= N; i++) {
	int xl = i, xr = to[i];
	int yl = i, yr = to[i];

evts.emplace_back(arr{xr, 2, yl, i});
	evts.emplace_back(arr{xl, 1, yr, i});

// evts.emplace_back(arr{xr, 2, yr, i});
	// evts.emplace_back(arr{xl, 2, yl, i});

// evts.emplace_back(arr{xr, 1, yl, i});
	// evts.emplace_back(arr{xl, 1, yr, i});
}
```

**事件查询部分**
```bash
sort(evts.begin(), evts.end());

Fenwick<int> tr(N+5);
vector<int> ans(n+1, 0);

for (auto [x, type, _y, i] : evts) {
	// 这里 +1 是因为，树状数组下标要从 1 开始

int y = _y + 1;
	if (type == 0) {
		tr.add(y, 1);
	}
	else {
		auto yr = x + 1;
		int res = tr.sum(yr);
		
		// 这里类型 2 原本对应的是事件 +，但是本例中，这些点是要扣除的代价
		// 因为这些点在中途变好了，不再需要耗费这么多代价了
		if (i <= n) ans[a[i]] -= res;

auto yl = y;
		res = tr.sum(yl);
		if (i <= n) ans[a[i]] += res;
	}
}

for (int i = 1; i <= n; i++) {
	ans[a[i]] += to[i] - i;
}
```

## Codeforces Round 1052 (Div. 2)
### D
**[D1. Max Sum OR (Easy Version)](https://codeforces.com/contest/2146/problem/D1)**
**问题描述**
给定$$l, r$$，现在两个序列，其中$$n = r - l + 1$$，两个序列都有`n`个数
其中`b`序列是确定的，`b = [l, l+1, ..., r]`，`a`序列一开始和`b`一样，但是你要打乱`a`序列
需要最大化$$\sum\_{i = 1}^{n} (a_i \mid b_i)$$

**算法分析**
> 对于问题 D1，因为$$l = 0$$，所以从高位到低位，可以尽可能做到`0, 1错开`，**尽量不会浪费`1`**

这可以用 **01-trie** 解决，把所有数都插入 trie 中，然后为每个数找匹配，如果这一位有`1`，就尽量找`0`跟他配
从高位到低位贪心，找到这样的匹配后，将其从 trie 中删除即可

> 问题 D2，一定会有浪费的位，比如`l 和 r 的最高几位都是 1，都相同`，那么$$[l, r]$$中间所有数这几个高位都是`1`，浪费了

此时如果还用`01-trie`贪心，发现过不了样例，比如
```bash
最优解
3 4 5 6
4 3 6 5

而求出的 01-trie 的解
3 4 5 6
4 5 6 3

为什么呢？
对于 6 = 110，配对 3 = 011，这个时候 i = 1 位上的 1 冗余了，(011, 1) 表示 011 在 1th 位上有冗余贡献
对于 5 = 101，配对 6 = 110，这个时候 i = 2 位上的 1 冗余了，(110, 2) 有冗余贡献
对于 4 = 100，配对 5 = 101，这个时候 i = 2 上冗余，但是 i = 1 这个位上呢？只能配 0
如果配对 3 = 011 呢？

(6, 5), (4, 3)
(110, 101) and (100, 011)，不难发现这样更优，也就是最高位的 1 一定会冗余的话，就不要管他
低位先尽量不要浪费

也就是说，贪心的时候，6 第一步不应该选择最高位是 0 的 3，而应该考虑 5
```

> 考虑分治

![](/media/content_img/CF1052D.png)

可以用分治，高位到低位单独考虑，假设当前考虑的位是$$j$$，对于$$i = l \to r$$
这一位一定是前缀都是`0`，然后从`m`开始，后缀都变成`1`

可以从$$[l, r]$$中，暴力找到这样的位$$m$$，使得`第 j 位`，$$[l, m-1]^j = 0, [m, r]^j = 1$$
然后两个指针，`tl = m-1 downto l,   tr = m to r`，令`a[tl] = tr, a[tr] = tl`，即`tl, tr`配对即可
等到一边指针为空的时候，递归
```bash
solve(l, r, j): then
	找 tl，tr 匹配
	solve(l, tl-1, j-1)
	solve(tr+1, r, j-1)
```

> 01-trie 实现

根据上面的分析，不难发现，$$[l\to r]$$可能会存在高位都是相同的，都是`1`的情况
此时高位一定会出现浪费的`1`，我们只要**从低位到高位贪心**，就可以处理这种情况，为什么呢？

因为考虑$$l \to r$$，要想不浪费`1`，即`(1, 0)`配对，最早出现这种情况的一定是在低位
而**从低位到高位，从小到大 for**，越往后，高位就越倾向于出现`1`，而高位有`1`，配什么数其实都没有限制

也就是说，**高位不一定要优先**满足`1 配 0`，否则的话，你把较小的数用掉了，比如`1..010`
把`0..100`给匹配掉了之后，`0...100`是不能再提供低位的`1`了，这样你`?...010`之后低位就没法补`1`了
而`1..010`如果配`1...000`，在高位浪费`1`是无所谓的，只要保住低位就可以了

> 证明

如果`l > 0`，在处理`[l, r]`配对的时候，会存在`1`的位**被浪费**，怎么样减小浪费？
假设说考虑为`x`找配对，对于某个高位`k,  x(k) = 1`，那么`k`这个位在答案中一定会贡献出`1`
这时候它配上`0 or 1`都是可以的，但是具体配什么，**取决于更低的位的`1`有没有互补？有没有浪费？**
很自然地考虑**从低位到高位，从小到大**在 01-trie 中贪心插入，查询

> 那可能有疑问，就是如果先满足低位，比如`(1 ? ? ? 1 0) and (1 ? ? ? 0 1)`这样互补
最高位的`1`会不会浪费？本来它应该和`0`配的？

这个问题，我们仍然可以从小到大，为每个元素找配对，考虑`y = (00..0) (10...010)`
记`t = topbit(y)`，`t`更低的位我们都尽量互补了，`t`往上更高的位，我们仍然需要找`1`

> 更进一步地思考

从$$[l \to r]$$，考虑它们**最高的位**`tl = topbit(l), tr = topbit(r)`，假设说$$tl < tr$$
那么就一定存在这样的数
```bash
0 0 1 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1
```
也意味着，最高是`1`的位，往更高位移动的过程中，一定会在这一位贡献出一组`(0, 1)`
同时，因为进位的关系，更低的位（后缀），一定是**先发生若干次进位**，然后再向高位进位，不断让高位填满`1`
而更低的位的**进位**，会产生一组`(0, 1)`，就可以类似进位一样，先处理这些**一定会发生的配对**
然后再处理高位

#### 算法实现
```bash
void solve(int cas) {
    int l, r;
    cin >> l >> r;

int n = r - l + 1;
    vector<int> A(n+5, 0);
    
    // let B = [l, l+1, ..., r], A = unordered {l, l+1, ..., r}
    // maximize sum (A[i] | B[i])

auto get = [&](const int x, int j) -> int {
        return x >> j & 1;
    };

auto dfs = [&](auto &dfs, int le, int ri, int j) -> void {
        if (le > ri) return;
        if (le == ri) {
            A[le-l] = ri;
            return;
        }

int m = le;
        while (m + 1 <= ri && get(m+1, j) == get(m, j)) {
            m += 1;
        }

if (m == ri) {
            dfs(dfs, le, ri, j-1);
            return;
        }

// [le, m] [m+1, ri]
        int tl = m + 1, tr = m;

while (tl - 1 >= le && tr + 1 <= ri) {
            tl--, tr++;
            A[tl - l] = tr, A[tr - l] = tl;
        }

dfs(dfs, le, tl-1, j-1);
        dfs(dfs, tr+1, ri, j-1);
        return;
    };

dfs(dfs, l, r, LOG);

i64 ans = 0;
    for (int x = l; x <= r; x++) {
        ans += (A[x - l] | x);
    }

cout << ans << "\n";
    for (int i = 0; i < n; i++) cout << A[i] << " ";
    cout << "\n";
}
```

## CodeTON Round 7
### F
**[F.CodeTON Round 7](https://codeforces.com/contest/1896/problem/F)**
给定一个长度是`2n`的二进制串`s`，需要用括号序列来把`s`变成全`0`串，操作如下
选择一个长度是`2n`的平衡括号序列`b`，对于每个下标$$i$$，如果$$b_i$$是左括号
令$$p_i$$是最小的下标，使得`b[i, p[i]]`是一个平衡括号序列，对`s`执行一次区间反转操作
不超过`10`次操作，使得`s`全`0`
```bash
1 1 1 1 1 0 0 1
() () ( () ) 会使得上述序列变成 0
```
**算法分析**
> 观察样例

不难猜测，对于`1001`，可以选择括号序列`( ( ) )`
对于`1111`，选择括号序列`() ()`，什么时候无解

**从 01 串的角度来看**
如果`1`的个数是奇数个，肯定无解

**从括号序列的角度来看**，第一个位置一定是`(`，它一定会被改
最后一个位置一定是`)`，它不会被其他`(...)`所包含，也一定会被改，`str[1] != str[2n]`无解

> 构造简单情况

对于相邻的`1`，他们中间，如果有偶数个`0`，认为这样的`01 串`是好的
对于好的`01 串`，形如`1 0 0 0 0 1`，可以构造`(   中间若干 ()   ) `，这样就做完了

> 现在只要考虑不是简单情况怎么做？

如果有偶数个连续的`0`？那么很简单`() () ... ()`即可
如果有奇数个连续的`0`，那么形如`0 0 0 1`这样，怎么办？能不能转化成好串的形式？

> 好串的结构

**第一种**
若干个`11`是好串

**第二种**
每`2`个相邻的一组，`10 00 00 ... 00 ... 01`，一段好串左端点是`10`，中间部分是若干`00`
右端点是`01`，这样的结构构成了**一段好串**
如果整个序列都能拆分成好串，那么答案一定是可以的，在相邻的`1`放上`()`，中间放若干`()()...()`即可

> 不是好串，能不能转成好串？

答案是可以的，不是好串，就意味着相邻的`1`之间，有奇数个`0`，换句话说，有形如以下结构
```bash
10 00 ... 00 ... 00 10
10 00 ... 00 ... 00 11
```
针对第一种，`10 00 ... 00 ... 00 [10]`，翻转`[10]`，`10 00 ... 00 ... 00 [01]`，这就变成了好串
而针对第二种，同样翻转`10 00 ... 00 ... 00 [11] --> 10 00 ... 00 ... 00 [00] ...`
一直进行下去，要么是`10 00 .... 0`后缀都是`0`，而这种情况不会发生，因为有奇数个`1`是无解的
也就是说，这样变换下去，一定会遇到一个`1`
那么如果是`10 ... 00 ... [01]`，那么目标达成，否则`10 ... 00 ... [10]`，还需要一次变换
将末尾的`[10] -> [01]`，然后再用一次变换达成好串

> 第一步，构造形式`(10 ...00 ... 01)  (11)`的串

具体来说，如果遇到`[10]`或者翻转出`[10]`，那么`tag += 1`，遇到`[01]`或者翻转出`[01]`，`tag -= 1`
当`tag > 0`的时候，出现的段都必须是`[00] or [01]`的，否则要翻转
当`tag = 0`的时候，出现的段要么是`[11]`，要么是`10`，否则翻转
这样能构造出若干由`[11] and [10 ... 00 ... 01]`拼接而成的段

具体怎么构造括号序列呢？其实也不难，注意到`a[1], a[2n]`**一定会翻转**
可以**忽略首尾两个字符**，首尾一定是`( ...... )`

> 能不能维护$$i \in [2, 2n-1]$$括号序列的前缀和尽量保持`+1`呢？

如果不需要翻转`(i, i+1)`，那么添加`( )`即可，这样可以保证每一个需要翻转的位置处理完之后，
前缀和不变，仍然是`+1`，不影响其他位置，需要翻转的情况已经维护好了

只需要考虑第一个需要翻转的位置，添加`) (`，一定可以完成`(i, i+1)`的翻转
在`i`位置添加了`)`，前缀和变为`0`，而在`i+1`位置添加了`(`，前缀和又变回了`+1`
那么在`[i+1.....2n-1]`之后的位置，翻转情况**就完全是一个子问题**，和从`i = 2`开始考虑是一样的

综上所述，这样构造总是可以完成目标

> 第二步，此时相邻的`1`之间必有偶数个`0`，形如`10 00 ... 00 ... 01`

这个时候需要构造`( ...  中间若干 () () ...  )`，这个用栈，或者用一个标记`sgn`
左括号就`+1`，右括号`-1`之类的，很容易实现

> 第三步，最后形如`0 111 ... 111 0`或者`1 111 ... 111 1`

如果是`1 111 ... 111 1`，考虑`() () () .... ()`即可一步到位

否则，`0 111 ... 111 0`需要一步变成`1 111 ... 111 1`，然后再变成全`0`
这个也不难，头尾放`( ... )`，中间放`() () ... ()`即可

## Codeforces Round 1054
### E
**[E. Hidden Knowledge of the Ancients](https://codeforces.com/contest/2149/problem/E)**
给定序列$$K, l, r$$，找到有多少个二元组$$(b, c)$$，满足$$1 \leqslant b \leqslant c \leqslant n$$
另外，`a[b], a[b+1], ..., a[c]`恰好有`K`个不同的数，$$1 \leqslant c-b+1 \leqslant r$$

**算法分析**
恰有$$K$$个的计数问题，可以考虑计算$$calc(\leqslant K) - calc(\leqslant K-1)$$
而关于`calc( <= K )`的问题，很典型的滑动窗口，右端点有一个取值范围，`[lo, hi]`，`res += hi - lo + 1`即可

上一篇：九月算法竞赛选题（二）已经是最后一篇啦

看完文章有啥想法