hdu 5057(트 리 배열+오프라인 처리)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=5057
Argestes and Sequence
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 569 Accepted Submission(s): 144
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)

思路：做一第一遍的时候用线段树卡空间，后来网上学了别人的离线处理技巧，用树状数组做了一遍；

#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int N=1e5+1000;
using namespace std;

int a[N],c[N][12],ans[N];
int b[N];
int T,n,m;

struct node
{
 int kind,l,r,d,p,pos,value;
}op[N];

int lowbit(int x)
{
    return x&(-x);
}

void update(int kind,int x,int p)
{
 while(x<=n)
 {
   if(kind==1)
      c[x][p]++;
   else
      c[x][p]--;
   x+=lowbit(x);
 }
}

int getsum(int x,int p)
{
  int ans=0;
  while(x>0)
  {
    ans+=c[x][p];
    x-=lowbit(x);
  }
  return ans;
}

int pow(int a,int b)
{
 int ans=1;
 for(int i=1;i<=b;i++)
    ans=ans*a;
 return ans;
}

int main()
{

    scanf("%d",&T);
    while(T--)
    {
     scanf("%d%d",&n,&m);

     for(int i=1;i<=n;i++)
     {
        scanf("%d",&a[i]);
        b[i]=a[i];
     }

     for(int i=1;i<=m;i++)
     {
       char s[10];
       int l,r,d,p;
       scanf("%s",s);
       if(s[0]=='Q')
       {
        scanf("%d%d%d%d",&l,&r,&d,&p);
        op[i].kind=1;
        op[i].l=l;
        op[i].r=r;
        op[i].d=d;
        op[i].p=p;
       }
       else if(s[0]=='S')
       {
         scanf("%d%d",&l,&r);
         op[i].kind=0;
         op[i].pos=l;
         op[i].value=r;
       }
     }
     for(int i=1;i<=10;i++)
     {
       memset(c,0,sizeof(c));
       for(int j=1;j<=n;j++)
       {
        a[j]=b[j];
        int t=a[j]/pow(10,i-1)%10;

        update(1,j,t);

       }

       for(int j=1;j<=m;j++)
        {
        if(op[j].kind==0)
        {
         int t=a[op[j].pos]/pow(10,i-1)%10;
         update(0,op[j].pos,t);
             t=op[j].value/pow(10,i-1)%10;
         update(1,op[j].pos,t);
         a[op[j].pos]=op[j].value;
        }
        else
        {
          if(op[j].d==i)
                ans[j]=getsum(op[j].r,op[j].p)-getsum(op[j].l-1,op[j].p);
        }
       }
     }
     for(int i=1;i<=m;i++)
        if(op[i].kind==1)printf("%d
",ans[i]);

    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 5044 - tree - 트 리 체인 분할 + 트 리 배열

누 드 체인 으로 나 뉘 어 데이터 가 좀 큰 것 같 습 니 다.선분 트 리 로 T 를 유지 하고 읽 기 마 우 스 를 추가 하면 트 리 배열 이 지나 갈 수 있 습 니 다...........................

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 5057(트 리 배열+오프라인 처리)

좋은 웹페이지 즐겨찾기