描述

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[1],a[2],…,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.

输入格式

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[1],a[2],…,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]
1<=T<= 50
1<=N, M<=100000
0<=a[i]<=231 - 1
1<=X<=N
0<=Y<=231 - 1
1<=L<=R<=N
1<=D<=10
0<=P<=9

输出格式

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

样例

输入

1
5 7
10 11 12 13 14
Q 1 5 2 1
Q 1 5 1 0
Q 1 5 1 1
Q 1 5 3 0
Q 1 5 3 1
S 1 100
Q 1 5 3 1

输出

5
1
1
5
0
1

思路

i,j表示最大不冲突字串的首和尾。
用26个队列来存26个字母的位置，当某个队列的size大于k时，明显冲突。计算i-j之间的子串的个数。要注意算重的部分，要减去。
i更新为对应队列里front的值。特别注意的是，位置在old_i和new_i之间的字母的队列要pop掉，这个BUG卡了我两个小时，OMG…………
代码很简约，也比较易懂。

思路

开一个1000001010（i,j,k）的树状数组。可以想到这个树状数组的意思是第i个数字的第j位是k的个数。
由于内存不够，顾用一个short和char来组合表示数字。short类型的最大整数是32767，所以%32768。
小技巧：

%*c
在输入和输出类似与这种表示方式的意思是跳过一个已经读取的或者即将要输出的字符。

c++代码

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define mod 32768
#define maxn 100010
short res[maxn][10][10];
char tt[maxn][10][10];
int b[10],n,m,c[maxn];
inline int lowbit(int x)
{
    return x&(-x);
}
void desp(int x){
    memset(b,0,sizeof(b));int k=0;
    while(x){
        b[k++]=x%10;x/=10;
    }
}
void update(int pos,int v){
    int t;
    for(int i=0;i<10;i++){
        for(int j=pos;j<=n;j+=lowbit(j)){
            t=(int)res[j][i][b[i]]+v;
            res[j][i][b[i]]=t%mod;
            tt[j][i][b[i]]+=t/mod;
        }
    }
}
int querry(int pos,int bit,int v){
    int ans=0;
    for(int i=pos;i>0;i-=lowbit(i)){
        ans+=(int)res[i][bit][v]+(int)tt[i][bit][v]*mod;
    }
    return ans;
}
int main(){
    int T,x,y,bit,v,tmp;
    char p;
    cin>>T;
    while(T--){
        scanf("%d%d",&n,&m);
        memset(tt,0,sizeof(char)*n*100);
        memset(res,0,sizeof(short)*n*100);
        for(int i=1;i<=n;i++){
            scanf("%d%*c",&c[i]);
            desp(c[i]);update(i,1);
        }
        while(m--){
            scanf("%c%d%d%*c",&p,&x,&y);
            if(p=='S'){
                desp(c[x]);
                update(x,-1);
                desp(y);
                update(x,1);                
                c[x]=y;
            }
            else{
                scanf("%d%d%*c",&bit,&v);bit--;
                int ans=querry(y,bit,v)-querry(x-1,bit,v);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}