接⽵竿

题目描述

⼩杨同学想⽤卡牌玩⼀种叫做“接⽵竿”的游戏。 游戏规则是：每张牌上有⼀个点数 ，将给定的牌依次放⼊⼀列牌的末端。若放⼊之前这列牌中已有与这张牌点数相 同的牌，则⼩杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本⾝）。 ⼩杨同学现在有⼀个长度为 的卡牌序列 ，其中每张牌的点数为 （ ）。⼩杨同学有 次询问。第 次 （ ）询问时，⼩杨同学会给出 ，⼩杨同学想知道如果⽤下标在 的所有卡牌按照下标顺序玩“接⽵ 竿”的游戏，最后队列中剩余的牌数。

输入格式

第⼀⾏包含⼀个正整数 ，表⽰测试数据组数。 对于每组测试数据，第⼀⾏包含⼀个正整数 ，表⽰卡牌序列 的长度。 第⼆⾏包含 个正整数 ，表⽰卡牌的点数 。 第三⾏包含⼀个正整数 ，表⽰询问次数。 接下来 ⾏，每⾏两个正整数 ，表⽰⼀组询问。

输出格式

对于每组数据，输出 ⾏。第 ⾏（ ）输出⼀个⾮负整数，表⽰第 次询问的答案。 3.2.4 样例1 1 1 2 6 3 1 2 2 3 1 3 4 4 5 1 3 6 1 6 7 1 5 8 5 6 1 1 2 1 3 0 4 2 3.2.5 样例解释 对于第⼀次询问，⼩杨同学会按照 的顺序放置卡牌，在放置最后⼀张卡牌时，两张点数为 的卡牌会被收 ⾛，因此最后队列中只剩余⼀张点数为 的卡牌。 对于第⼆次询问，队列变化情况为： 。因此最后队列中只剩余⼀张点数为 的卡 牌。 3.2.6 数据范围 子任务编号 数据点占比 特殊条件 1 2 所有询问的右端点等于 3 对于全部数据，保证有 ， ， ， 。 3.2.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int N = 1e5+10; 5 int a[N]; 6 int nxt[N][30],pos[20]; 7 int main(){ 8 int t; 9 cin>>t; 10 while(t--){ 11 int n; 12 cin>>n; 13 memset(pos,0,sizeof pos); 14 for(int i=1;i<=n;i++){ 15 cin>>a[i]; 16 for(int j=0;j<=20;j++)nxt[i][j]=n+1; 17 } 18 for(int i=n;i>=1;i--){ 19 if(!pos[a[i]]){ 20 nxt[a[i]][0]=n+1; 21 pos[a[i]]=i; 22 }else{ 23 nxt[i][0]=pos[a[i]]; 24 pos[a[i]]=i; 25 } 26 } 27 for(int i=n;i>=1;i--){ 28 for(int j=1;j<=20;j++){ 29 if(nxt[i][j-1]+1<=n) 30 nxt[i][j]=nxt[nxt[i][j-1]+1][j-1]; 31 } 32 } 33 int q; 34 cin>>q; 35 while(q--){ 36 int l,r; 37 cin>>l>>r; 38 int ii=l; 39 int ans=0; 40 while(ii<=r){ 41 42 while(ii<=r&&nxt[ii][0]>r){ 43 ii++; 44 ans++; 45 } 46 if(ii>r)break; 47 for(int j=20;j>=0;j--){ 48 if(nxt[ii][j]<=r){ 49 ii=nxt[ii][j]; 50 break; 51 } 52 } 53 ii++; 54 } 55 cout<<ans<<"\n"; 56 } 57 } 58 }

样例输入 #1

1 1
2 6
3 1 2 2 3 1 3
4 4
5 1 3
6 1 6
7 1 5
8 5 6
1 1
2 1
3 0
4 2

样例输出 #1

样例解释 #1

对于第⼀次询问，⼩杨同学会按照 的顺序放置卡牌，在放置最后⼀张卡牌时，两张点数为 的卡牌会被收 ⾛，因此最后队列中只剩余⼀张点数为 的卡牌。 对于第⼆次询问，队列变化情况为： 。因此最后队列中只剩余⼀张点数为 的卡 牌。

数据范围

子任务编号 数据点占比 特殊条件 1 2 所有询问的右端点等于 3 对于全部数据，保证有 ， ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。