题解 P5640 【【CSGRound2】逐梦者的初心】
zhouwc
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：
```cpp
#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;
```