　　Argestes and Sequence

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1279 Accepted Submission(s): 373

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[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.

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[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

Output

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

Sample Input

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

Sample Output

分块大法，降低暴力的时间复杂度

 //2016.8.13

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N = ;

 int a[N], len = , n, mi[] = {, , , , , , , , , , };

 struct node

 {

     int cnt[][];//cnt[d][p]表示每个块内第d位是p的个数

 }block[];

 bool judge(int x, int d, int p)//判断x的第d位是否为p

 {

     return x/mi[d]%==p;

 }

 int query(int l, int r, int d, int p)

 {

     int id1 = l/len, id2 = r/len, ans = ;

     if(id1==id2)//如果l,r在同一个块内，暴力枚举

     {

         for(int i = l; i <= r; i++)

               if(judge(a[i], d, p))

                   ans++;

     }else

     {

         for(int i = id1+; i <= id2-; i++)//把中间的块加起来

           ans+=block[i].cnt[d][p];

         for(int i = l; i <= (id1+)*len && i <= n; i++)//暴力最左边的块

           if(judge(a[i], d, p))

             ans++;

         for(int i = id2*len+; i <= r; i++)//暴力最右边的块

           if(judge(a[i], d, p))

             ans++;

     }

     return ans;

 }

 void update(int x, int y)

 {

     int tmp = a[x], id = (x-)/len;//这里起初x少减了个1，WA了好多次忧伤。。。

     a[x] = y;

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

     {

         block[id].cnt[i][tmp%]--;

         tmp/=;

     }

     tmp = a[x];

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

     {

         block[id].cnt[i][tmp%]++;

         tmp/=;

     }

 }

 int main()

 {

     int T, d, p, m, x, y, l, r, id;

     char cmd;

     cin>>T;

     while(T--)

     {

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

         memset(block, , sizeof(block));

         memset(a, , sizeof(a));

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

         {

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

             id = (i-)/len;

             int tmp = a[i];

             for(int j = ; j <= ; j++)//初始化块

             {

                 block[id].cnt[j][tmp%]++;

                 tmp/=;

             }

         }

         while(m--)

         {

             getchar();

             scanf("%c", &cmd);

             if(cmd == 'Q')

             {

                 int ans = ;

                 scanf("%d%d%d%d", &l, &r, &d, &p);

                 ans = query(l, r, d, p);

                 printf("%d\n", ans);

             }else

             {

                 scanf("%d%d", &x, &y);

                 update(x, y);

             }

         }

     }

     return ;

 }

巴特西

HDU5057(分块)