Codeforces 121 E. Lucky Array

問題

各桁の数字が全て4または7である数をlucky numberという。
例えば（4,7,477など）

n項の数列に対してm個のクエリに答えよ。

• add l r x 区間[l,r]の項全てにxを加算する
• count l r 区間[l,r]の項のうちlucky numberである数の個数を出力する

制約条件

n,m≦10^5
加算の後で数列の各項は10^4を超えない

方針

平方分割。
√nくらいのバケットに区切っておいて、
区間に一様に加算される値を管理する。
また、区間ごとに、（一様に加算される値を除いたときの）値の分布を配列でもっておく。

更新およびカウントのクエリは、
バケットからはみでる部分と、バケットに完全に含まれる部分に分けて処理できる。
バケットからはみ出る部分はナイーブに更新して、
バケットに含まれる部分は一括して更新する。

すると、カウントがO((lucky numberの数)*√n)くらいで、更新がO(√n)できる。

ソースコード

const int SZ=400;
int n,m,a[100000],sum[400];
int cnt[400][10000];
bool lucky[10000];
vi vv;
void gen(int c){
  if(c)vv.pb(c);
  if(c*10+4<10000)gen(c*10+4);
  if(c*10+7<10000)gen(c*10+7);
}
int query(int l,int r){
  int res=0;
  while(l<r&&l%SZ!=0)res+=lucky[a[l]+sum[l/SZ]], l++;
  while(l<r&&r%SZ!=0)r--, res+=lucky[a[r]+sum[r/SZ]];
  l/=SZ; r/=SZ;
  for(;l<r;l++)rep(i,vv.size())res+=(sum[l]<=vv[i]?cnt[l][vv[i]-sum[l]]:0);
  return res;
}
void add(int l,int r,int x){
  while(l<r&&l%SZ!=0){
    cnt[l/SZ][a[l]]--;
    a[l]+=x;
    cnt[l/SZ][a[l]]++;
    l++;
  }
  while(l<r&&r%SZ!=0){
    r--;
    cnt[r/SZ][a[r]]--;
    a[r]+=x;
    cnt[r/SZ][a[r]]++;
  }
  l/=SZ; r/=SZ;
  for(;l<r;l++)sum[l]+=x;
}

void run(){
  vv.clear();
  gen(0);
  rep(i,vv.size())lucky[vv[i]]=1;
  
  cin>>n>>m;
  rep(i,n){
    cin>>a[i];
    cnt[i/SZ][a[i]]++;
  }
  rep(i,m){
    int l,r,x;
    string op; cin>>op>>l>>r;
    if(op[0]=='c')cout<<query(l-1,r)<<endl;
    else{
      cin>>x;
      add(l-1,r,x);
    }
  }
}