CodeForces121E 线段树上线段果

109 阅读 0 评论 72 点赞

我是靠谱客的博主甜甜电话，这篇文章主要介绍CodeForces121E 线段树上线段果，现在分享给大家，希望可以做个参考。

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这题

复制代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#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;
}

View Code

当然正解肯定不是这样的

困难之处在于维护区间内幸运数字的个数。事实上确实不简单，思路和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;
}

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#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;
}