hdu5057 分块法

本文主要是介绍hdu5057 分块法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：n个数，n<=100000，单点修改，区间询问一段内第D位为P的数的个数。内存卡的很死，树状数组会超内存。分块大法好。

每一块为256个数字，(i>>8)即为i所在的块。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100005;
int n,m;
int digit[maxn][10];
int block[400][10][10];
int X,Y,L,R,D,P;
int main()
{int x;char str[10];int t;scanf("%d",&t);while(t--) {scanf("%d%d",&n,&m);memset(block,0,sizeof(block));for(int i=1;i<=n;i++) {scanf("%d",&x);int b=(i>>8);for(int j=1;j<=10;j++) {digit[i][j]=x%10;block[b][j][x%10]++;x/=10;}}for(int i=0;i<m;i++) {scanf("%s",str);if(str[0]=='S') {scanf("%d%d",&X,&Y);int b=(X>>8);for(int j=1;j<=10;j++) {block[b][j][digit[X][j]]--;digit[X][j]=Y%10;block[b][j][Y%10]++;Y/=10;}}else {scanf("%d%d%d%d",&L,&R,&D,&P);int bl=((L-1)>>8)+1,br=((R+1)>>8)-1;int ans=0;if(bl<=br) {for(int i=bl;i<=br;i++)ans+=block[i][D][P];for(int i=L;i<(bl<<8);i++)ans+=(digit[i][D]==P);for(int i=((br+1)<<8);i<=R;i++)ans+=(digit[i][D]==P);}else {for(int i=L;i<=R;i++) {ans+=(digit[i][D]==P);}}printf("%d\n",ans);}}}return 0;
}

这篇关于hdu5057 分块法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---