这题如果用bitset后缀差分,在什么情况下答案会为负数
查看原帖
这题如果用bitset后缀差分,在什么情况下答案会为负数
483966
一粒夸克楼主2021/8/6 08:46

一开始我是这么写的

#include<bits/stdc++.h>
using namespace std;
int q;
bitset<100005> mp[26];
char s[100005],c[100005];
int main(){
	scanf("%s%d",s+1,&q);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)mp[s[i]-'a'][i]=1;
	while(q--){
		int op,x,y;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%s",&x,c);
			mp[s[x]-'a'][x]=0;mp[c[0]-'a'][x]=1;
			s[x]=c[0];
		}
		else {
			scanf("%d%d%s",&x,&y,c);
			int len=strlen(c);
			bitset<100005> ans;ans.set();
			for(int i=0;i<len;i++)ans&=(mp[c[i]-'a']>>i);
			printf("%d\n",(ans>>x).count()-(ans>>(y-len+2)).count());
		}
	}

	return 0;
} 

第二十六个测试点答案为 0 ,我输出的是 -204

我以为是有的区间不合法,然后特判了一下,输出的仍然是 -204

			scanf("%d%d%s",&x,&y,c);
            if(x>y){
                puts("0");
                continue;
            }
			int len=strlen(c);
			bitset<100005> ans;ans.set();

把答案和 0 取 max 才能过

#include<bits/stdc++.h>
using namespace std;
int q;
bitset<100005> mp[26];
char s[100005],c[100005];
int main(){
	scanf("%s%d",s+1,&q);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)mp[s[i]-'a'][i]=1;
	while(q--){
		int op,x,y;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%s",&x,c);
			mp[s[x]-'a'][x]=0;mp[c[0]-'a'][x]=1;
			s[x]=c[0];
		}
		else {
			scanf("%d%d%s",&x,&y,c);
			int len=strlen(c);
			bitset<100005> ans;ans.set();
			for(int i=0;i<len;i++)ans&=(mp[c[i]-'a']>>i);
			printf("%d\n",max(0,(int)(ans>>x).count()-(int)(ans>>(y-len+2)).count()));
		}
	}

	return 0;
} 
2021/8/6 08:46
加载中...