http://codeforces.com/problemset/problem/121/E
题意： Petya 喜欢幸运数，幸运数只包含 4 和 7 这两个数字。例如 47，744，4 都是幸运数字，但 5,16,467 不是。
Petya 有一个 N 个数的数组，他想给这个数组执行 M 个操作，可以分为两种操作：
-
add l r d把第 l 到 第 r 个数都加上 d； -
count l r统计第 l 到第 r 个数有多少个幸运数字。
喜闻乐见的数据结构题。
更加喜闻乐见的是这题能用树状数组直接暴力跑过去。对每一个区间修改进行n次单点修改的傻狗操作竟然也可以AC这题
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = 1e5 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,tmp,K;
const int sp[] = {,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
bool check[];
int a[maxn];
int tree[maxn];
void add(int t,int x){
for(;t <= N;t += t & -t){
tree[t] += x;
}
}
int getsum(int t){
int s = ;
for(;t;t -= t & -t){
s += tree[t];
}
return s;
}
int main()
{
For(i,,) check[sp[i]] = ;
scanf("%d%d",&N,&M);
For(i,,N){
int x; Sca(x); a[i] = x;
if(check[x]) add(i,);
}
For(i,,M){
int l,r;
char op[];
scanf("%s%d%d",op,&l,&r);
if(op[] == 'a'){
int d; Sca(d);
For(j,l,r){
if(check[a[j]]) add(j,-);
a[j] += d;
if(check[a[j]]) add(j,);
}
}else{
Pri(getsum(r) - getsum(l - ));
}
}
#ifdef VSCode
system("pause");
#endif
return ;
}
当然正解肯定不是这样的
困难之处在于维护区间内幸运数字的个数。事实上确实不简单，思路和hdu多校里面的一道线段树相似。
线段树维护三个值，区间内所有数到下一个幸运数字差值的最小值，最小值的个数，lazy标记
每一次update之后要重新遍历一次线段树去寻找有没有最小值小于0的数，然后将这些减少到0的数一个个修改即可。
看起来很麻烦的操作事实上时间复杂度是很科学的正解。
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
inline LL read(){LL now=;register char c=getchar();for(;!isdigit(c);c=getchar());
for(;isdigit(c);now=now*+c-'',c=getchar());return now;}
inline void out(int x){if(x > ) out(x / ); putchar(x % + '');}
inline void out(LL x){if(x > ) out(x / ); putchar(x % + '');}
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = 1e5 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,tmp,K;
const int sp[] = {,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
struct Tree{
int l,r;
int x,y,lazy;
}tree[maxn * ];
int c[maxn];
int a[maxn];
void Pushup(int t){
if(tree[t << ].x == tree[t << | ].x){
tree[t].x = tree[t << ].x;
tree[t].y = tree[t << ].y + tree[t << | ].y;
}else if(tree[t << ].x < tree[t << | ].x){
tree[t].x = tree[t << ].x;tree[t].y = tree[t << ].y;
}else{
tree[t].x = tree[t << | ].x;tree[t].y = tree[t << | ].y;
}
}
void Build(int t,int l,int r){
tree[t].l = l; tree[t].r = r;
tree[t].lazy = ;
if(l == r){
tree[t].x = c[a[l]];
tree[t].y = ;
return;
}
int m = (l + r) >> ;
Build(t << ,l,m); Build(t << | ,m + ,r);
Pushup(t);
}
void Pushdown(int t){
if(tree[t].lazy){
tree[t << ].lazy += tree[t].lazy;
tree[t << | ].lazy += tree[t].lazy;
tree[t << ].x += tree[t].lazy;
tree[t << | ].x += tree[t].lazy;
tree[t].lazy = ;
}
}
void update(int t,int l,int r,int val){
if(l <= tree[t].l && tree[t].r <= r){
tree[t].x += val;
tree[t].lazy += val;
return;
}
Pushdown(t);
int m = (tree[t].l + tree[t].r) >> ;
if(r <= m) update(t << ,l,r,val);
else if(l > m) update(t << | ,l,r,val);
else{
update(t << ,l,m,val); update(t << | ,m + ,r,val);
}
Pushup(t);
} void rebuild(int t){
if(tree[t].x >= ) return;
if(tree[t].l == tree[t].r){
a[tree[t].l] -= tree[t].lazy;
tree[t].x = c[a[tree[t].l]];
tree[t].lazy = ;
return ;
}
Pushdown(t);
rebuild(t << ); rebuild(t << | );
Pushup(t);
}
int query(int t,int l,int r){
if(tree[t].x) return ;
if(l <= tree[t].l && tree[t].r <= r){
return tree[t].y;
}
Pushdown(t);
int m = (tree[t].l + tree[t].r) >> ;
if(r <= m) return query(t << ,l,r);
if(l > m) return query(t << | ,l,r);
else return query(t << ,l,m) + query(t << | ,m + ,r);
}
int main()
{
int cnt = ;
For(i,,1e4){
if(sp[cnt] < i) cnt++;
c[i] = sp[cnt] - i;
}
N = read(); M = read();
For(i,,N) a[i] = read();
Build(,,N);
int l,r;
char op[];
For(i,,M){
scanf("%s",op);
l = read(); r = read();
if(op[] == 'a'){
int d; d = read();
update(,l,r,-d);
rebuild();
}else{
out(query(,l,r));
puts("");
}
}
#ifdef VSCode
system("pause");
#endif
return ;
}