hdu 5057 Argestes and Sequence

主要的考点是对内存的把控。由于各个十进制位上的数互不影响，所以可以将询问保存再离线处理。区间求和明显需要用到树状数组。

#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <iostream>
#include <cmath>
using namespace std;
#ifdef __GNUC__
typedef long long LL;
inline void opt64(LL a) {
    printf("%lld", a);
}
#else
typedef __int64 LL;
inline void opt64(LL a) {
    printf("%I64d", a);
}
#endif
const int MAXN = 100002;
int n, m, x, y;
int ac[MAXN], cur, ab[MAXN];
struct query
{
    int L, R, P, d, r;
} kp;
vector<query> mmp[11];
int sdd[MAXN][3];
int ten[11];
struct node
{
    int dp[10];
    void init() {
        memset(dp, 0, sizeof dp);
    }
    void cal(int a)
    {
        init();
        a /= ten[cur-1];
        ++dp[a%10];
    }
    node operator - (const node & a)
    {
        node res;
        res.init();
        for (int j = 0; j< 10; ++j)
        {
            res.dp[j] = dp[j] - a.dp[j];
        }
        return res;
    }
    node operator + (const node & a)
    {
        node res;
        res.init();
        for (int j = 0; j< 10; ++j)
        {
            res.dp[j] = dp[j] + a.dp[j];
        }
        return res;
    }
} da[MAXN], db, dc;
int low_bit(int x)
{
    return x&(-x);
}
void change(int x, node a)
{
    while (x <= n)
    {
        da[x] = da[x] + a;
        x += low_bit(x);
    }
}
int get_sum(int x, int p)
{
    int res = 0;
    while (x > 0)
    {
        res += da[x].dp[p];
        x -= low_bit(x);
    }
    return res;
}
char ss[5];
int rres[MAXN], nr;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int t, a, cnt;
    ten[0] = 1;
    for (int i = 1; i< 10; ++i) ten[i] = ten[i-1]*10;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        cnt = nr = 0;
        for (int i = 1; i<= n; ++i) scanf("%d", ac+i);
        for (int i = 0; i< 11; ++i) mmp[i].clear();
        for (int i = 1; i<= m; ++i)
        {
            scanf("%s", ss);
            if (ss[0] == 'Q')
            {
                int o;
                scanf("%d%d%d%d", &kp.L, &kp.R, &o, &kp.P);
                kp.d = i;
                kp.r = nr++;
                mmp[o].push_back(kp);
            }
            else
            {
                sdd[++cnt][0] = i;
                scanf("%d%d", &sdd[cnt][1], &sdd[cnt][2]);
            }
        }
        for (int i = 1, k; i< 11; ++i)
        {
            cur = i;
            if ((k=mmp[i].size()) == 0) continue;
            for (int j =0; j<= n; ++j) da[j].init();
            memcpy(ab, ac, sizeof ac);
            for (int j =1; j<= n; ++j)
                db.cal(ab[j]), change(j, db);
            int bg = 1;
            for (int j = 0; j< k; ++j)
            {
                query sp = mmp[i][j];
                while (bg<=cnt && sdd[bg][0] < sp.d)
                {
                    db.cal(sdd[bg][2]);
                    dc.cal(ab[sdd[bg][1]]);
                    change(sdd[bg][1], db-dc);
                    ab[sdd[bg][1]] = sdd[bg][2];
                    ++bg;
                }
                rres[sp.r] = get_sum(sp.R, sp.P) - get_sum(sp.L-1, sp.P);
            }
        }
        for (int i = 0; i< nr; ++i) printf("%d\n", rres[i]);
    }
    return 0;
}