盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5057 Argestes and Sequence(树状数组+离线 OR 分块)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5057

题意

有n个数,m个询问。每个询问有两种操作,一个改变某一个数,即a[x]=y。还有一个是询问[l,r]区间内从右往左第d位为p的数字个数。
1≤n,m≤1e5, 0≤a[i]≤2^31 - 1, 1<=D<=10, 0<=P<=9

思路

第一眼想法是给每一位每一个数字种一棵树状数组。这样需要开dp[10][10][100000],然而这道题比较变态,会爆内存。(可以用char + unsigned short 来表示。刚好可以卡过。。)

比较好的方式是分块:
分成400块,每块256个数。block[i][j][x]表示x块内第i为为p的数字总数。
当修改一个数的时候,O(1)的修改块内统计信息即可。
当查询一个区间时,如果在区间在同一个块,直接找一遍。如果不在同一个块内,则单独跑左右两块,然后中间整块的直接相加。复杂度为O(sqrt(n))

还有一个用时间换空间的方式:
由于开不了3维的数组,那么我们开2维的数组,然后对每一位都算一遍所有的操作。
即把所有的操作离线下来,然后对每一位进行一次操作。不过在每次操作之前需要把数变为一开始的数。

代码

分块

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
int block[400][11][10]; //400 blocks, each 256
int dig[100100][11];
int t, n, m, l, r, d, p;
int main () {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
memset(block, 0, sizeof(block));
int u;
for (int i = 1; i <= n; i++) {
scanf("%d", &u);
int x = i >> 8;
for (int j = 1; j <= 10; j++) {
++block[x][j][dig[i][j] = u % 10];
u /= 10;
}
}
char ch;
while(m--) {
ch = getchar();
while(ch != 'S' && ch != 'Q') ch = getchar();
if (ch == 'S') {
scanf("%d%d", &l, &r);
int x = l >> 8;
for (int j = 1; j <= 10; j++) {
--block[x][j][dig[l][j]];
++block[x][j][dig[l][j] = r % 10];
r /= 10;
}
} else {
scanf("%d%d%d%d", &l, &r, &d, &p);
int bl = ((l - 1) >> 8) + 1, br = r >> 8, ans = 0;
if (bl <= br) {
int bls = bl << 8, brs = br << 8;
for (int i = l; i < bls; i++) ans += (dig[i][d] == p);
for (int i = brs; i <= r; i++) ans += (dig[i][d] == p);
for (int i = bl; i < br; i++) ans += block[i][d][p];
} else {
for (int i = l; i <= r; i++) ans += (dig[i][d] == p);
}
printf("%d\n", ans);
}
}
}
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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
const int N = 1e5 + 10;
int t, n, m;
int a[10][N];
int b[N], c[N], ans[N];
struct node {
int op;
int l, r, d, p;
}p[N];
int lowbit(int x) {
return x & -x;
}
void add(int p, int dig, int v) {
while(p <= n) {
a[dig][p] += v;
p += lowbit(p);
}
}
int get(int p, int dig) {
int res = 0;
while(p) {
res += a[dig][p];
p -= lowbit(p);
}
return res;
}
void clr() {
for (int i = 0; i < 10; i++)
for (int j = 0; j <= n; j++) a[i][j] = 0;
}
int main () {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
int u;
for (int i = 1; i <= n; i++) scanf("%d", b + i), c[i] = b[i];
char ch;
for (int i = 0; i < m; i++) {
ch = getchar();
while(ch != 'S' && ch != 'Q') ch = getchar();
if (ch == 'Q') {
p[i].op = 1;
scanf("%d%d%d%d", &p[i].l, &p[i].r, &p[i].d, &p[i].p);
p[i].d--;
} else {
p[i].op = 0;
scanf("%d%d", &p[i].l, &p[i].r);
}
}
int now = 1;
for (int i = 0; i < 10; i++) {
clr();
for (int j = 1; j <= n; j++) {
b[j] = c[j];
add(j, (b[j] / now) % 10, 1);
}
for (int j = 0; j < m; j++) {
if (p[j].op == 1) {
if (p[j].d != i) continue;
ans[j] = get(p[j].r, p[j].p) - get(p[j].l - 1, p[j].p);
} else {
int x = (b[p[j].l] / now) % 10;
add(p[j].l, x, -1);
x = (p[j].r / now) % 10;
add(p[j].l, x, 1);
b[p[j].l] = p[j].r;
}
}
now *= 10;
}
for (int i = 0; i < m; i++) if (p[i].op) printf("%d\n", ans[i]);
}
return 0;
}

更新日志

  • 14402325 2015-08-07 23:47:34 Accepted 5057 904MS 6060K 1808 B G++ SIO__Five 分块
  • 14402693 2015-08-08 01:01:00 Accepted 5057 967MS 8624K 1894 B G++ SIO__Five 树状数组+离线