Argestes and sequence

单点修改 + 区间查询

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int block[350][11][11];
int len = 350;//块大小
int a[100001],n,m;
int d1[13]={0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
bool elect(int x,int d,int p)
{
  return (x/d1[d])%10==p;                      //返回枚举的数字的对应位数是否满足条件
}
int query(int l,int r,int d,int p)
{
  int i;
  int d1 = l/len + 1, d2 = r/len + 1,sum = 0;
  if(d1 == d2)                                //全碎片
  {
    for(i = l ; i <= r ; i ++)
    {
      if(elect(a[i],d,p))
        sum ++;
    }
  }
  else{
    for(i = d1+1 ; i <= d2-1 ; i++)                      //中段整包
    {
      sum += block[i][d][p];                            //添加整块内满足条件的序列总和
    }
    for(i = l ; i/len + 1 < d1+1 && i <= n ; i++)      //左区间碎片
    {
      if(elect(a[i],d,p))
        sum++;
    }
    for(i = r ; i/len +1 > d2 - 1 ; i--)               //右区间碎片
    {
      if(elect(a[i],d,p))
        sum ++;
    }
  }
  return sum;
}
void update(int x,int y)                              //更新x为Y
{
  int d1 = x/len + 1,i,t;
  t = a[x];
  for(i = 1 ;i <= 10 ; i++)                          //移除旧数字的“十区间”
  {
    block[d1][i][t%10]--;
    t /= 10;
  }
  t = y;
  for(i = 1 ; i<= 10 ; i++)                          //添加新数字的“十区间”
  {
    block[d1][i][t%10]++;
    t /= 10;
  }
  a[x] = y;
}
int main()
{
  int i,l,r,A,B,d,p,t,id,j,T;
  char s[5];
  scanf("%d",&T);                          //测试用例
  while(T--)
  {
    memset(block,0,sizeof(block));        //block初始化为0
    scanf("%d %d",&n,&m);                 //序列长度，操作次数
    for(i = 1;i <= n ; i++)
    {
      scanf("%d",&a[i]);                 //读取序列
      id = i / len + 1;                  //id[x][y][z]的y区间可以储存350个数字
      t = a[i];
      for(j = 1; j <= 10 ; j++)         //在三维数组里标记上“十区间”的每一位数
      {
        block[id][j][t%10]++;
        t /= 10;
      }
    }
    for(i = 1; i <= m ; i++)
    {
      scanf("%s",s);
      if(s[0] == 'Q')                  //查询
      {
        scanf("%d %d %d %d",&l,&r,&d,&p);
        printf("%d\n",query(l,r,d,p));
      }
      else                            //修改
      {
        scanf("%d %d",&A,&B);
        update(A,B);
      }
    }
  }
}

笔记：定义block[i][D][P]，表示第 i 块的第 D 位是 P 个总个数，单点修改操作就是根据a[x]来更新block[][][]