洛谷 P5640 【CSGRound2】逐梦者的初心题解

每日一题 day33 打卡

Analysis

这道题太难♂了，居然才是蓝的。

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

用

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

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

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

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<bitset>
 6 #define int long long
 7 #define R register
 8 #define maxn 1000000+10
 9 #define maxm 33333+10
10 #define maxnum 1000+10
11 #define rep(i,s,e) for(register int i=s;i<=e;++i)
12 using namespace std;
13 inline int read()
14 {
15     int x=0;
16     bool f=1;
17     char c=getchar();
18     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
19     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
20     if(f) return x;
21     return 0-x;
22 }
23 inline void write(int x)
24 {
25     if(x<0){putchar('-');x=-x;}
26     if(x>9)write(x/10);
27     putchar(x%10+'0');
28 }
29 int n,m;
30 int s[maxn];
31 bitset<maxm> now,ans,num[maxnum];
32 signed main()
33 {
34     n=read();m=read();
35     rep(i,1,n) s[i]=read();
36     rep(i,1,m) num[s[i]].set(i);
37     now.set();
38     rep(i,1,m)
39     {
40         int op=read(),ch=read();
41         now.reset(i);
42         if(op==0) ans=(ans<<1)|num[ch];
43         else if(op==1) ans=ans|num[ch]<<(i-1);
44         write((~(ans|now)).count());
45         putchar('
');
46     }
47     return 0;
48 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

洛谷 P5640 【CSGRound2】逐梦者的初心 题解

Analysis

洛谷 P5640 【CSGRound2】逐梦者的初心题解