题目描述

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是：每张牌上有一个点数 $v$，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相
同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）。

小杨同学现在有一个长度为 $n$ 的卡牌序列 $A$，其中每张牌的点数为 $A_i$（$1\le i\le n$）。小杨同学有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨同学会给出 $l_i,r_i$ 小杨同学想知道如果用下标在 $[l_i,r_i]$ 的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

输入格式

一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$，表示卡牌序列 $A$ 的长度。

第二行包含 $n$ 个正整数 $A_1,A_2,\dots ,A_n$，表示卡牌的点数 $A$。

第三行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$ 表示一组询问。

输出格式

对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。

输入输出样例 #1

输入 #1

1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6

输出 #1

1
1
0
2

说明/提示

样例解释

对于第一次询问，小杨同学会按照 $1,2,2$ 的顺序放置卡牌，在放置最后一张卡牌时，两张点数为 $2$ 的卡牌会被收走，因此最后队列中只剩余一张点数为 $1$ 的卡牌。

对于第二次询问，队列变化情况为：

{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}\{\}\to\{1\}\to\{1,2\}\to\{1,2,2\}\to\{1\}\to\{1,3\}\to\{1,3,1\}\to\{\}\to\{3\}{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为 $3$ 的卡牌。

数据范围

子任务	分数	$T$	$n$	$q$	$\max A_i$	特殊条件
$1$	$30$	$\le 5$	$\le 100$	$\le 100$	$\le 13$
$2$	$30$	$\le 5$	$\le 1.5\times 10^4$	$\le 1.5\times 10^4$	$\le 13$	所有询问的右端点等于 $n$
$3$	$40$	$\le 5$	$\le 1.5\times 10^4$	$\le 1.5\times 10^4$	$\le 13$

对于全部数据，保证有 $1\le T\le 5$，$1\le n\le 1.5\times 10^4$，$1\le q\le 1.5\times 10^4$，$1\le A_i\le 13$。

solution

可以记录一个每个纸牌的下一个相同纸牌的位置，这表示可以删除的一段，所以如果可以将从每一个纸牌开始可以删除的位置都记录下来，这样就好办了。但是有可能数据量太大，可以采用st表的方式，只记录 $2^i$ 级别的。

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "unordered_map"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"
#include "cstring"
#include "cmath"using namespace std;const int N = 15001;int t, n, m, a[14], f[N][20]; // a[i] : 牌 i 上一次出现的位置
// vector<int> f[N]; // f[i][j] : 第 i 张牌的可以通过 2^j 次收牌达到的位置int main() {cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++)for (int j = 0; j < 20; j++)f[i][j] = n + 1;for (int i = 1; i <= n; i++) {int x;cin >> x;if (a[x]) f[a[x]][0] = i;a[x] = i;}for (int j = 1; j < 20; j++)for (int i = 1; i <= n; i++) {if (f[i][j - 1] < n)f[i][j] = f[f[i][j - 1] + 1][j - 1];}cin >> m;while (m--) {int l, r, s = 0, flag = 0;cin >> l >> r;while (l <= r) {int x = l;for (int j = 19; j >= 0; j--) {if (f[x][j] < r)x = f[x][j] + 1;else if (f[x][j] == r) {flag = 1;break;}}if (flag) break;if (x > l) l = x;else {s++, l++;}}cout << s << endl;}// 清空 amemset(a, 0, sizeof a);}
}

结果