codeforces Lucky Array

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树状数组

题意:题意很易懂就不说了吧,区间更新和区间查询。

关于这题的解法说法不一,有人说这种比较暴力的树状数组方法是水过去的,有人说不算。某牛用400ms就过了这题,但是他说可以证明,这种暴力的树状数组其实理论复杂度也是差不多的,跟用线段树是一样的。某牛400ms写的是线段树

树状数组做法很易理解

总区间是1到n,a[i]如果是lucky number那么就加1.查询[x,y]有多少lucky number,那么就是两个前缀和相减sum[y] - sum[x - 1].修改操作,如果一个a[i]从不是ln变成了ln,加1,从ln变成不是ln,减1

注意一开始的时候先预处理出1-100000这些数字哪些是ln,以后直接从标记数组中判断,否则在test 62中会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define cl memset

int a[N],c[N];
bool lucky[N];

inline int lowbit(int x){
return x & (-x);
}
inline void add(int p,int n,int m){
while(p<=n){
c[p] += m; p += lowbit(p);
}
}
inline int sum(int m){
int res = 0;
while(m){
res += c[m]; m -= lowbit(m);
}
return res;
}
inline bool check(int n){
while(n){
if(n%10 != 4 && n%10 != 7)
return false;
n /= 10;
}
return true;
}

int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
cl(c,0,sizeof(c));

cl(lucky,false,sizeof(lucky));
for(int i = 1; i <= 100000; i++)
lucky[i] = check(i);

for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
if(lucky[a[i]]) add(i,n,1);
}
while(m--){
char op[10];
int x,y,d;
scanf("%s%d%d",op,&x,&y);
if(op[0] == 'c'){
printf("%d\n",sum(y)-sum(x-1));
}
else{
scanf("%d",&d);
for(int i = x; i <= y; i++){
bool _ok = lucky[a[i]];
bool ok = lucky[a[i]+=d];
if(!_ok && ok) add(i,n,1);
if(_ok && !ok) add(i,n,-1);
}
}
}
}
return 0;
}