Description

题目传送门：P10264 [GESP202403 八级] 接竹竿

思维题，考虑倍增。

Analysis

  • $30pts$ 模拟，$1\le a_i\le13$，根据题意，队列中不会存在两个相同的点数，所以队列的最大长度为 $13$，对于每一个 $(l,r)$，模拟加队列的过程，每添加一个牌从队列头开始查找有无相同的点数，如有则从队列中删除所有后续的元素。复杂度为 $O(T\times q\times N\times13)$。
  • $100pts$ 倍增，一共 $13$ 个点数，由题意，从自身出发，到下一个相同点数，这样的整段都可以被取走。每个点都可以维护下一个相同点数的位置。\
    但是这样的跳跃速度还是太慢了，通过倍增来加速。$nxt[i][j]$ 表示从 $i$ 出发的，第 $2\land j$ 个段的结尾位置。可知 $nxt[i][j+1]=nxt[nxt[i][j]+1][j]$。\
    复杂度 $O(T\times q\times \log N)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Reprinted from gesp.ccf.org
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int a[N];
int nxt[N][30], pos[20];
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		memset(pos, 0, sizeof pos);

		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			for (int j = 0; j <= 20; j++)nxt[i][j] = n + 1;
		}
		for (int i = n; i >= 1; i--) {
			if (!pos[a[i]]) {
				nxt[a[i]][0] = n + 1;
				pos[a[i]] = i;
			} else {
				nxt[i][0] = pos[a[i]];
				pos[a[i]] = i;
			}
		}
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= 20; j++) {
				if (nxt[i][j - 1] + 1 <= n)
					nxt[i][j] = nxt[nxt[i][j - 1] + 1][j - 1];
			}
		}
		int q;
		cin >> q;
		while (q--) {
			int l, r;
			cin >> l >> r;
			int ii = l;
			int ans = 0;
			while (ii <= r) {
				while (ii <= r && nxt[ii][0] > r) {
					ii++;
					ans++;
				}
				if (ii > r)break;
				for (int j = 20; j >= 0; j--) {
					if (nxt[ii][j] <= r) {
						ii = nxt[ii][j];
						break;
					}
				}
				ii++;
			}
			cout << ans << "\n";
		}
	}
}