首页 > 代码库 > 【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