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;
}