Time Limit: / MS (Java/Others)    Memory Limit: / K (Java/Others)

Total Submission(s):     Accepted Submission(s): 

Problem Description

Argestes has a lot of hobbies and likes solving query problems especially. One day Argestes came up with such a problem. You are given a sequence a consisting of N nonnegative integers, a[],a[],...,a[n].Then there are M operation on the sequence.An operation can be one of the following:

S X Y: you should set the value of a[x] to y(in other words perform an assignment a[x]=y).

Q L R D P: among [L, R], L and R are the index of the sequence, how many numbers that the Dth digit of the numbers is P.

Note: The 1st digit of a number is the least significant digit.

Input

In the first line there is an integer T , indicates the number of test cases.

For each case, the first line contains two numbers N and M.The second line contains N integers, separated by space: a[],a[],...,a[n]—initial value of array elements.

Each of the next M lines begins with a character type.

If type==S,there will be two integers more in the line: X,Y.

If type==Q,there will be four integers more in the line: L R D P.

[Technical Specification]

<=T<=

<=N, M<=

<=a[i]<= -

<=X<=N

<=Y<= -

<=L<=R<=N

<=D<=

<=P<=

Output

For each operation Q, output a line contains the answer.

Sample Input

Q

Q

Q

Q

Q

S

Q    

Sample Output

Source

BestCoder Round # (Div. )

之前用线段树一直MLE(在码之前看了下内存限制，就觉得会开不下的了),知道可以用分块做之后，就看了下大白的一道分块题，再想这道题就比较简单了

~num[b][a][b]表示第b块所有的数在第a位为b的个数，这些都可以简单预处理出来，然后只是单点修改，把原来的值和新值对比一下更新一下就好了

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + ;

const int SIZE = ;

int n, m;

int A[N];

int block[N / SIZE + ][SIZE + ];

int num[N / SIZE + ][][];

void pre(int b, int j)

{

    int *B = &block[b][];

    for(int i = ; i < j; ++i) {

        int tmp = B[i];

        int cnt = ;

        while(cnt <= ) {

            int x = tmp % ;

            tmp /= ;

            num[b][cnt][x]++;

            cnt++;

        }

    }

}

void init()

{

    memset(num, , sizeof num);

    scanf("%d%d", &n, &m);

    int j = , b = ;

    for(int i = ; i < n; ++i) {

        scanf("%d", &A[i]);

        block[b][j] = A[i];

        if(++j == SIZE) {

            pre(b, j);

            b++; j = ;

        }

    }

    if(j) { pre(b, j); ++b; }

}

int get(int x, int d) {

    int cnt = ;

    while(cnt < d) {

        x /= ;

        cnt++;

    }

    return x % ;

}

int query(int L, int R, int D, int p)

{

    int res = ;

    int lb = L / SIZE, rb = R / SIZE;

    if(lb == rb) {

        for(int i = L; i <= R; ++i) {

            if(get(A[i], D) == p) res++;

        }

    }

    else {

        for(int i = L; i < (lb + ) * SIZE; ++i) if(get(A[i], D) == p) res++;

        for(int i = rb * SIZE; i <= R; ++i) if(get(A[i], D) == p) res++;

        for(int i = lb + ; i < rb; ++i) res += num[i][D][p];

    }

    return res;

}

void modify(int x, int y)

{

    if(A[x] == y) return;

    int old = A[x], now = y, b = x / SIZE, cnt = ;

    int c1[], c2[];

    A[x] = y;

    while(cnt <= ) {

        c1[cnt] = old % ;

        c2[cnt] = now % ;

        old /= ;

        now /= ;

        cnt++;

    }

    for(int i = ; i <= ; ++i) {

        if(c1[i] != c2[i]) {

            num[b][i][ c2[i] ]++;

            num[b][i][ c1[i] ]--;

        }

    }

}

int main()

{

    int _; scanf("%d", &_);

    while(_ --)

    {

        init();

        char op[];

        int L, R, D, P;

        while(m --)

        {

            scanf("%s", op);

            if(op[] == 'Q') {

                scanf("%d%d%d%d", &L, &R, &D, &P);

                L--; R--;

                printf("%d\n", query(L, R, D, P));

            }else {

                scanf("%d%d", &D, &P);

                D--;

                modify(D, P);

            }

        }

    }

    return ;

}