程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5057 Argestes and Sequence

hdu 5057 Argestes and Sequence

編輯:C++入門知識

hdu 5057 Argestes and Sequence


Argestes and Sequence

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


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]<=$2^{31}$ - 1
1<=X<=N
0<=Y<=$2^{31}$ - 1
1<=L<=R<=N
1<=D<=10
0<=P<=9
Output For each operation Q, output a line contains the answer.
Sample Input
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

Sample Output
5
1
1
5
0
1

Source BestCoder Round #11 (Div. 2)
題解:

這道題有三種版本的 題解,本來題目不難,就是限制空間:1.分塊算法解決,2.離線樹狀數組,3.卡空間的樹狀數組

這裡先介紹第一種算法:

學習了一下分塊算法,其實還蠻簡單的,就是將n組元素分成m組,每組合並成一塊,查詢時,只要看元素在那幾塊,相加就行了。

#include 
#include 
#include 
#include 
using namespace std;

struct Block
{
    int nt[10][10];
}block[400];
int num[100010];

int cal(int d)
{
    int ans=1;
    for(int i=1;i<=d;i++)
    {
        ans*=10;
    }
    return ans;
}

int init(int n)
{
    int s=(int)sqrt((double)n),t=0;
    int m=n/s+1;

    memset(block,0,sizeof(block));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        s=i/m;t=num[i];
        for(int j=0;j<=9;j++)
        {
            block[s].nt[j][t%10]++;
            t/=10;
        }
    }
    return m;
}

void work(int k,int n,int m)
{
    char s[2];
    int l,r,d,p,tl,tr,td,tp,ans=0;
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='S')
        {
            scanf("%d%d",&d,&p);
            td=d;td/=k;
            for(int j=0;j<=9;j++)
            {
                block[td].nt[j][num[d]%10]--;
                num[d]/=10;
            }
            num[d]=p;tp=p;
            for(int j=0;j<=9;j++)
            {
                block[td].nt[j][tp%10]++;
                tp/=10;
            }
        }
        else
        {
           ans=0;
           scanf("%d%d%d%d",&l,&r,&d,&p);
           tl=l;tl/=k;tr=r;tr/=k;d--;
           td=cal(d);
           if(tl==tr)
           {

               for(int i=l;i<=r;i++)
               if(num[i]/td%10==p)
               {
                   ans++;
               }
               printf("%d\n",ans);
           }
           else
           {
               for(int i=tl+1;i

下面還寫一寫離線處理的代碼,隨後跟上。







  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved