首页 > 代码库 > 【HDOJ】5057 Argestes and Sequence
【HDOJ】5057 Argestes and Sequence
树状数组,其实很简单。只是MLE。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 #define MAXN 100005 7 8 short sum[10][10][MAXN]; 9 char bit[10][10][MAXN];10 int a[MAXN];11 int t, n, m;12 int d, p;13 const int MOD = 32768;14 15 int lowbit(int x) {16 return x & -x;17 }18 19 int getSum(int x, int d, int p) {20 int ret = 0;21 while (x > 0) {22 ret += (int)sum[d][p][x] + ((int)bit[d][p][x]) * MOD;23 x -= lowbit(x);24 }25 return ret;26 }27 28 void update(int x, int d, int p, int r) {29 int tmp;30 while (x <= n) {31 tmp = (int)sum[d][p][x] + r;32 sum[d][p][x] = tmp%MOD;33 bit[d][p][x] += tmp/MOD;34 x += lowbit(x);35 }36 }37 38 int query(int l, int r) {39 return getSum(r, d-1, p) - getSum(l-1, d-1, p);40 }41 42 void insert(int x, int i, int delta) {43 int j;44 for (j=1; j<=10; ++j) {45 update(i, j-1, x%10, delta);46 x /= 10;47 }48 }49 50 int main() {51 int i, j, ans;52 int x, y;53 char cmd[3];54 55 scanf("%d", &t);56 while (t--) {57 scanf("%d %d", &n, &m);58 for(i=0; i<10; i++) {59 for(j=0; j<10; j++) {60 memset(sum[i][j], 0, sizeof(short)*(n+1));61 memset(bit[i][j], 0, sizeof(char)*(n+1));62 }63 }64 for (i=1; i<=n; ++i) {65 scanf("%d", &a[i]);66 insert(a[i], i, 1);67 }68 while (m--) {69 scanf("%*c%s %d %d", cmd, &x, &y);70 if (cmd[0] == ‘S‘) {71 insert(a[x], x, -1);72 a[x] = y;73 insert(a[x], x, 1);74 } else {75 scanf("%d %d", &d, &p);76 ans = query(x, y);77 printf("%d\n", ans);78 }79 }80 }81 82 return 0;83 }
【HDOJ】5057 Argestes and Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。