Algoogle

Algorithm for Programming Contest

Codeforces 121 E Lucky Array

Category: Codeforces Tag: sqrt-decomposition

Lucky Array

問題概要


4か7だけでできてる数をラッキーナンバーという.
長さn(<=10^5)の数列があって以下のクエリをm(<=10^5)回実行する.

  • 区間[l,r]の数列の要素にそれぞれdを加える
  • 区間[l,r]にラッキーナンバーがいくつあるかを返す

解法


平方分割でやる.
各区間に対して, その区間に加えられた合計とその区間にある数の分布を持つ.
各クエリで, 完全に分割された区間をカバーする場合はその区間全体で足したり数を数えたりする.
ちょろっとはみ出た部分はそのままやる.

TLEが厳しめ. 分割の大きさを適当に変えてsubmitしたら通った.
テストケース70ぐらいまでいってたら通ったことにしてもいい気がする.

コード


(121E.cpp) download
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
#include <string.h>
#include <math.h>
#include <stdio.h>

int n, m, seq[100010], i, j;
bool islucky[10010];
int lucky[] = {4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777};
struct sqdiv{
    int N, M;
    int cnt[500][10010], sum[500];
    sqdiv(int n){
        N = n;
        M = 500;
        memset(sum, 0, sizeof(sum));
        memset(cnt, 0, sizeof(cnt));
    }
    // add d for [l,r)
    void add(int l, int r, int d){
        while(l%M and l < r) {
            cnt[l/M][seq[l]]--;
            seq[l] += d;
            cnt[l/M][seq[l]]++;
            ++l;
        }
        while(r%M and l < r) {
            --r;
            cnt[r/M][seq[r]]--;
            seq[r] += d;
            cnt[r/M][seq[r]]++;
        }
        for(i = l/M; i < r/M; i++) sum[i] += d;
    }
    // count lucky [l,r)
    int count(int l, int r){
        int ret = 0;
        while(l%M and l < r) ret += islucky[seq[l]+sum[l++/M]];
        while(r%M and l < r) ret += islucky[seq[--r]+sum[r/M]];
        for(i = l/M; i < r/M; i++)
            for(j = 0; j < 30; j++)
                if(lucky[j] >= sum[i])
                    ret += cnt[i][lucky[j]-sum[i]];
        return ret;
    }
};

int main(void){
    for(i = 0; i < 30; i++)
        islucky[lucky[i]] = 1;
    scanf("%d%d", &n, &m);
    sqdiv sd(n);
    for(i = 0; i < n; i++){
        scanf("%d", seq+i);
        sd.cnt[i/sd.M][seq[i]]++;
    }
    while(m--){
        char s[8]; scanf("%s", s);
        int l, r, d; scanf("%d%d", &l, &r); l--;
        if(!strcmp(s,"count")) printf("%d\n", sd.count(l,r));
        else{
            scanf("%d", &d);
            sd.add(l,r,d);
        }
    }
    return 0;
}

Comments