P10264 [GESP202403 八级]接竹竿题解

### 题目大意

接竹竿游戏规则为按顺序依次加入一个牌堆，如果发现牌堆中有一对相同的牌，则将两张牌中间的牌（包含两张牌）全部拿出，求最终牌堆有多少牌。

有一个序列 $a$，有 $q$ 次询问，每次询问给出 $l,r$，求出 $[l,r]$ 的接竹竿结果。

### 题目分析

考虑直接模拟。我们先预处理出每个 $a_i$ 的后面最近出现相同值的下标，定为 $z$。

对于每次询问：

- 如果 $z_i \leq r$，那么直接跳转到 $z_i+1$。

- 否则计数器加一，很明显 $a_i$ 最近的相同位置都大于 $r$ 了，就再也没有机会消掉了。随后跳转到 $i+1$。

最终输出计数器就可以了。

可算极限复杂度为 $\mathcal {O}(Tqn)$，极限运算次数会达到 $5\times (1.5 \times 10^4)^2=1.1\times 10^9$。然而由于 $a_i \leq 13$，所以相同会出现的很密集，在一次次的跳过中省去了很多次运算，所以可以通过。

[提交记录](https://www.luogu.com.cn/record/152799535)。

### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int z[maxn];
int pos[maxn];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		pos[i]=0,z[i]=0; 
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			z[pos[a[i]]]=i;
			pos[a[i]]=i;
		}
		int q;
		cin>>q;
		while(q--)
		{
			int l,r,ans=0;
			scanf("%d%d",&l,&r);
			if(l>r) swap(l,r);
			for(int i=l;i<=r;i++)
			{
				if(z[i]!=0&&z[i]<=r) i=z[i];
				else ans++;
			}
			cout<<ans<<"\n";
		}
	}
}
```

正在渲染内容...

P10264 [GESP202403 八级]接竹竿 题解

P10264 [GESP202403 八级]接竹竿题解