題目描述

小楊同學想用卡牌玩一種叫做“接竹竿”的游戲。

游戲規則是：每張牌上有一個點數 $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);}
}

結果