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