自动搬运

查看原文

来自洛谷，原作者为

	zhouwc 千夫诺诺，不如一士谔谔！

搬运于2025-08-24 22:12:50，当前版本为作者最后更新于2019-11-10 14:58:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

官方题解

subtask1

对于每次操作，枚举$l$，枚举$i$，判断一下。考察了循环语句和分支语句的简单应用。

时间复杂度$O(m^3)$

subtask2

记录下每次操作后每个$i$满不满足条件。

考虑在末尾加一个字符

不难发现原来的$i$变成了现在的$i+1$，再把新加入的字符对状态的影响处理一下。

再考虑在开头加一个字符

原来的状态不用变，只要把新加入的字符对状态的影响处理。

时间复杂度$O(m^2)$

subtask3

字符集非常小，答案只有在特殊情况下才存在，可能存在什么神奇的做法。

subtask4

每个位子和每种字符都是独立的，对每种字符都记录一下位子。

用$f[i]=0 or 1$表示长度为$i$的后缀可不可以，0表示可以，1表示不行。

考虑f只有0和1，可以用bitset优化，对每种字符都开一个bitset记录是不是该字符。

在末尾加一个字符时，左移后做or运算。

在开头加一个字符时，直接or上该字符出现的状态左移长度减一位。

答案就是范围内0的个数。

复杂度$O(m^2/w)$

std：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<bitset>
using namespace std;
int n,m,opt,S[1000005],dt;
bitset<35005> f,id[1005],now;
int read(){
	int ans=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch<='9'&&ch>='0'){
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	return ans;
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
		S[i]=read();
	for(int i=1;i<=m;i++)
		id[S[i]].set(i);
	now.set();
	for(int i=1;i<=m;i++){
		opt=read();
		dt=read();
		now.reset(i);
		if(opt==0)
			f=(f<<1)|id[dt];
		else
			f=f|(id[dt]<<(i-1));
		printf("%d\n",(~(f|now)).count());
	}
	return 0;
}

附录：

关于如何使用bitset

简单的来说，bitset就是压位优化的0/1数组。

定义一个长度为$len$的bitset：

bitset<len> f;

把f的每一位都改为1

f.set();

把f的第i位改为1

f.set(i);

把f的每一位都改为0

f.reset();

把f的第i位改为0

f.reset(i);

求f有几个1

f.count();

各类位运算和整数类型一样

f=f<<1;
f=f>>1;
f=f&f;
f=f|f;
f=f^f;
f=~f;