CodeForces121E 线段树上线段果

http://codeforces.com/problemset/problem/121/E

题意： Petya 喜欢幸运数，幸运数只包含 4 和 7 这两个数字。例如 47，744，4 都是幸运数字，但 5,16,467 不是。

Petya 有一个 N 个数的数组，他想给这个数组执行 M 个操作，可以分为两种操作：

1. add l r d 把第 l 到 第 r 个数都加上 d； 
2. 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("%dn", x)
#define Prl(x) printf("%lldn",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-9;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,tmp,K;
const int sp[30] = {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,};
bool check[10010];
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 = 0;
for(;t;t -= t & -t){
s += tree[t];
}
return s;
}
int main()
{
For(i,0,29) check[sp[i]] = 1;
scanf("%d%d",&N,&M);
For(i,1,N){
int x; Sca(x); a[i] = x;
if(check[x]) add(i,1);
}
For(i,1,M){
int l,r;
char op[20];
scanf("%s%d%d",op,&l,&r);
if(op[0] == 'a'){
int d; Sca(d);
For(j,l,r){
if(check[a[j]]) add(j,-1);
a[j] += d;
if(check[a[j]]) add(j,1);
}
}else{
Pri(getsum(r) - getsum(l - 1));
}
}
#ifdef VSCode
system("pause");
#endif
return 0;
}

当然正解肯定不是这样的

困难之处在于维护区间内幸运数字的个数。事实上确实不简单，思路和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("%dn", x)
#define Prl(x) printf("%lldn",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=0;register char c=getchar();for(;!isdigit(c);c=getchar());
for(;isdigit(c);now=now*10+c-'0',c=getchar());return now;}
inline void out(int x){if(x > 9) out(x / 10); putchar(x % 10 + '0');}
inline void out(LL x){if(x > 9) out(x / 10); putchar(x % 10 + '0');}
typedef vector<int> VI;
const double eps = 1e-9;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,tmp,K;
const int sp[31] = {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,44444};
struct Tree{
int l,r;
int x,y,lazy;
}tree[maxn * 4];
int c[maxn];
int a[maxn];
void Pushup(int t){
if(tree[t << 1].x == tree[t << 1 | 1].x){
tree[t].x = tree[t << 1].x;
tree[t].y = tree[t << 1].y + tree[t << 1 | 1].y;
}else if(tree[t << 1].x < tree[t << 1 | 1].x){
tree[t].x = tree[t << 1].x;tree[t].y = tree[t << 1].y;
}else{
tree[t].x = tree[t << 1 | 1].x;tree[t].y = tree[t << 1 | 1].y;
}
}
void Build(int t,int l,int r){
tree[t].l = l; tree[t].r = r;
tree[t].lazy = 0;
if(l == r){
tree[t].x = c[a[l]];
tree[t].y = 1;
return;
}
int m = (l + r) >> 1;
Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);
Pushup(t);
}
void Pushdown(int t){
if(tree[t].lazy){
tree[t << 1].lazy += tree[t].lazy;
tree[t << 1 | 1].lazy += tree[t].lazy;
tree[t << 1].x += tree[t].lazy;
tree[t << 1 | 1].x += tree[t].lazy;
tree[t].lazy = 0;
}
}
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) >> 1;
if(r <= m) update(t << 1,l,r,val);
else if(l > m) update(t << 1 | 1,l,r,val);
else{
update(t << 1,l,m,val); update(t << 1 | 1,m + 1,r,val);
}
Pushup(t);
}
void rebuild(int t){
if(tree[t].x >= 0) 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 = 0;
return ;
}
Pushdown(t);
rebuild(t << 1); rebuild(t << 1 | 1);
Pushup(t);
}
int query(int t,int l,int r){
if(tree[t].x) return 0;
if(l <= tree[t].l && tree[t].r <= r){
return tree[t].y;
}
Pushdown(t);
int m = (tree[t].l + tree[t].r) >> 1;
if(r <= m) return query(t << 1,l,r);
if(l > m) return query(t << 1 | 1,l,r);
else return query(t << 1,l,m) + query(t << 1 | 1,m + 1,r);
}
int main()
{
int cnt = 0;
For(i,1,1e4){
if(sp[cnt] < i) cnt++;
c[i] = sp[cnt] - i;
}
N = read(); M = read();
For(i,1,N) a[i] = read();
Build(1,1,N);
int l,r;
char op[20];
For(i,1,M){
scanf("%s",op);
l = read(); r = read();
if(op[0] == 'a'){
int d; d = read();
update(1,l,r,-d);
rebuild(1);
}else{
out(query(1,l,r));
puts("");
}
}
#ifdef VSCode
system("pause");
#endif
return 0;
}