Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Codeforces 121E - Lucky Array

問題文 : Lucky Array

解法 :
いつぞや誰かから「"Lucky Array"はセグメント木で解けるよ」 と聞いて, 問題を見つけたので挑戦したらそのLucky Array は別の問題だったらしい.
セグメント木じゃ解けなさそうなんだよなあと思いつつ, 解法をみて勉強しようとしたらO(MN) 近くかかりそうなソースが通っているのをみて戦慄.
ということでO(MN) かかるケースがあるソースを書いた所, 2sec くらいでAC. 最早説明するまでもない.
もうどう考えても平方分割が正当な気がするので, 気が向いたら平方分割で書き直します.

ソース :

#include <cstdio>
#include <vector>

using namespace std;

int bit[100001];
vector<int> lucky;

void add(int pos, int val)
{
	while (pos <= 100000){
		bit[pos] += val;
		pos += pos & -pos;
	}
}

int sum(int pos)
{
	int ret = 0;
	while (pos){
		ret += bit[pos];
		pos &= (pos - 1);
	}
	return (ret);
}

void gen(int x)
{
	if (x >= 10000) return;
	if (x) lucky.push_back(x);
	gen(x * 10 + 4); gen(x * 10 + 7);
}

int main()
{
	int n, m;
	int a[100000];
	bool check[100001] = {false};
	
	gen(0);
	
	for (int i = 0; i < lucky.size(); i++) check[lucky[i]] = true;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++){
		scanf("%d", a + i);
		if (check[a[i]]) add(i + 1, 1);
	}
	
	for (int i = 0; i < m; i++){
		char qtype[32];
		scanf("%s", qtype);
		
		if (qtype[0] == 'a'){
			int l, r, v;
			scanf("%d %d %d", &l, &r, &v);
			for (int i = l - 1; i < r; i++){
				if (check[a[i]]) add(i + 1, -1);
				a[i] += v;
				if (check[a[i]]) add(i + 1, 1);
			}
		}
		else {
			int l, r;
			scanf("%d %d", &l, &r);
			printf("%d\n", sum(r) - sum(l - 1));
		}
	}
	
	return (0);
}