codeforce 121E

　　10^4以内只由4和7构成的数字只有31种，那么做法就很简单了，求出每个数字与其最接近的幸运数的差值，然后建立线段树，线段树维护区间最小值和最小值个数，如果操作过程中最小值<0，那么就去对差值进行暴力修改，直到区间差值>=0，很明显线段树每个叶子节点不会被修改超过31次，询问操作的话差值=0的数字就是幸运数了。复杂度O(31nlogn)

　　代码

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstring>
  5 #include <vector>
  6 #include <cstdio>
  7 #include <string>
  8 #include <set>
  9 #include <map>
 10 #include <queue>
 11 #include <bitset>
 12 using namespace std;
 13 const int N = 1010101;
 14 int n,m,a[N],b[N],tot,i,j,id[N],v[N];
 15 int s[N],cnt[N];
 16 char str[10];
 17 int q1,q2,q3;
 18 void dfs(int x)
 19 {
 20     if (x>=10000) return;
 21     if (x!=0) b[++tot]=x;
 22     dfs(x*10+4);
 23     dfs(x*10+7);
 24 }
 25 void updata(int x)
 26 {
 27     if (s[2*x]<s[2*x+1])
 28     {
 29         s[x]=s[2*x];
 30         cnt[x]=cnt[2*x];
 31     }
 32     else
 33     if (s[2*x]>s[2*x+1])
 34     {
 35         s[x]=s[2*x+1];
 36         cnt[x]=cnt[2*x+1];
 37     }
 38     else
 39     {
 40         s[x]=s[2*x];
 41         cnt[x]=cnt[2*x]+cnt[2*x+1];
 42     }
 43 }
 44 void build(int x,int l,int r)
 45 {
 46     if (r-l==1)
 47     {
 48         s[x]=a[r];
 49         cnt[x]=1;
 50     }
 51     else
 52     {
 53         int m=(l+r)>>1;
 54         build(2*x,l,m);
 55         build(2*x+1,m,r);
 56         updata(x);
 57     }
 58 }
 59 void clean(int x)
 60 {
 61     if (v[x])
 62     {
 63         s[x]-=v[x];
 64         v[2*x]+=v[x];
 65         v[2*x+1]+=v[x];
 66         v[x]=0;
 67     }
 68 }
 69 int query(int x,int a,int b,int l,int r)
 70 {
 71     clean(x);
 72     if ((a<=l)&&(r<=b))
 73     {
 74         if (s[x]==0) return cnt[x];else return 0;
 75     }
 76     int m=(l+r)>>1,ans=0;
 77     if (a<m) ans+=query(2*x,a,b,l,m);
 78     if (m<b) ans+=query(2*x+1,a,b,m,r);
 79     return ans;
 80 }
 81 void gao(int x,int l,int r)
 82 {
 83     clean(x);
 84     if (s[x]>=0) return;
 85     if (r-l==1)
 86     {
 87         while (s[x]<0)
 88         {
 89             s[x]+=b[id[r]+1]-b[id[r]];
 90             id[r]++;
 91         }
 92     }
 93     else
 94     {
 95         int m=(l+r)>>1;
 96         gao(2*x,l,m);
 97         gao(2*x+1,m,r);
 98         updata(x);
 99     }
100 }
101 void change(int x,int a,int b,int l,int r,int c)
102 {
103     clean(x);
104     if ((a<=l)&&(r<=b))
105     {
106         v[x]+=c;
107         gao(x,l,r);
108         return;
109     }
110     int m=(l+r)>>1;
111     if (a<m) change(2*x,a,b,l,m,c);
112     if (m<b) change(2*x+1,a,b,m,r,c);
113     clean(2*x);clean(2*x+1);
114     updata(x);
115 }
116 int main()
117 {
118     scanf("%d%d",&n,&m);
119     for (i=1;i<=n;i++)
120     scanf("%d",&a[i]);
121     dfs(0);
122     sort(b+1,b+1+tot);b[tot+1]=100000;
123     for (i=1;i<=n;i++)
124     {
125         for (j=1;j<=tot;j++)
126         if (b[j]>=a[i]) break;
127         id[i]=j;
128         a[i]=b[j]-a[i];
129     }
130     build(1,0,n);
131     for (i=1;i<=m;i++)
132     {
133         scanf("%s",str);
134         if (str[0]=='c')
135         {
136             scanf("%d%d",&q1,&q2);
137             printf("%d
",query(1,q1-1,q2,0,n));
138         }
139         else
140         {
141             scanf("%d%d%d",&q1,&q2,&q3);
142             change(1,q1-1,q2,0,n,q3);
143         }
144     }
145 }