比赛 |
树形数据结构进阶(再进阶) |
评测结果 |
AAAAAAAAAAAAAAAAAAAAA |
题目名称 |
幸运数列 |
最终得分 |
100 |
用户昵称 |
OTTF |
运行时间 |
10.464 s |
代码语言 |
C++ |
内存使用 |
3.80 MiB |
提交时间 |
2025-04-19 11:24:25 |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5;
int n;
int m;
bool judge[N + 10];
int num[N + 10];
int tree[N + 10];
void fourSeven () {
for (int i = 1; i <= 10000; i++) {
int num = i;
while (num) {
if (num % 10 != 4 && num % 10 != 7) {
goto https;
}
num /= 10;
}
judge[i] = true;
https://ottfmercury.github.io
;
}
}
int lowbit (int id) {
return id & (-id);
}
void add (int id, int num) {
for (; id <= N; id += lowbit (id)) {
tree[id] += num;
}
}
int query (int id) {
int res = 0;
for (; id; id -= lowbit (id)) {
res += tree[id];
}
return res;
}
int query (int l, int r) {
return query (r) - query (l - 1);
}
void ParseIn () {
freopen ("cf121e.in", "r", stdin);
freopen ("cf121e.out", "w", stdout);
fourSeven ();
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> num[i];
if (judge[num[i]]) {
add (i, 1);
}
}
}
void CoreCWriteOut () {
string op;
int l, r, d;
for (int i = 1; i <= m; i++) {
cin >> op >> l >> r;
if (op[0] == 'a') {
cin >> d;
for (int i = l; i <= r; i++) {
if (judge[num[i]]) {
add (i, -1);
}
num[i] += d;
if (judge[num[i]]) {
add (i, 1);
}
}
}
else {
cout << query (l, r) << endl;
}
}
}
int main () {
ParseIn ();
CoreCWriteOut ();
return 0;
}