首页 > 代码库 > hdu 5057 Argestes and Sequence (数状数组+离线处理)
hdu 5057 Argestes and Sequence (数状数组+离线处理)
题意：
给N个数。a[1]....a[N]。
M种操作：
S X Y：令a[X]=Y
Q L R D P：查询a[L]...a[R]中满足第D位上数字为P的数的个数
数据范围：
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
思路：
直接开tree[maxn][10][10]记录第i位上数字为j的个数，铁定MLE，采用离线省去一维。
枚举位置（第i位），每一次枚举，扫一下M个操作，记录。
额.. 直接看代码
代码：
#include <cstdio>#include <iostream>#include <string.h>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <map>#include <stack>using namespace std;int const uu[4] = {1,-1,0,0};int const vv[4] = {0,0,1,-1};typedef long long ll;int const inf = 0x3f3f3f3f;ll const INF = 0x7fffffffffffffffll;double eps = 1e-10;double pi = acos(-1.0);#define rep(i,s,n) for(int i=(s);i<=(n);++i)#define rep2(i,s,n) for(int i=(s);i>=(n);--i)#define mem(v,n) memset(v,(n),sizeof(v))#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define lowbit(x) (x)&(-(x))struct node1{ int kind, L, R, D, P, pos, value; //kind=0,Q操作 kind=1,S操作}O[100005];int const maxn=100005;int T,n,m;int a[maxn], aa[maxn];int C[maxn][10]; //第二维：位上的数字int ans[maxn];void update(int kind,int p,int x){ //x:位上的数字 for(int i=p;i<=n;i+=lowbit(i)){ if(kind==0) ++C[i][x]; else --C[i][x]; }}int sum(int p,int P){ int ret=0; for(int i=p;i>0;i-=lowbit(i)) ret+=C[i][P]; return ret;}int query(int L,int R,int P){ return sum(R,P)-sum(L-1,P);}int POW(int base,int k){ int ret=1; while(k--) ret*=10; return ret;}int main(){ cin>>T; while(T--){ scanf("%d%d",&n,&m); rep(i,1,n){ scanf("%d",&a[i]); aa[i]=a[i]; } char op[10]; rep(kk,1,m){ scanf("%s",op); int x,y,L,R,D,P; if(op[0]==‘S‘){ scanf("%d%d",&x,&y); O[kk].kind=1, O[kk].pos=x, O[kk].value=http://www.mamicode.com/y; }else{ scanf("%d%d%d%d",&L,&R,&D,&P); O[kk].kind=0, O[kk].L=L, O[kk].R=R, O[kk].D=D, O[kk].P=P; } } rep(i,1,10){// 第i位 mem(C,0); rep(j,1,n){ a[j]=aa[j]; int t1=a[j]/POW(10,i-1)%10; //第i位上的数字 update(0,j,t1); } rep(j,1,m){ if(O[j].kind==1){ //更改操作 int t1=a[O[j].pos]/POW(10,i-1)%10; update(1, O[j].pos, t1); int t2=O[j].value/POW(10,i-1)%10; update(0, O[j].pos, t2); a[O[j].pos]=O[j].value; }else{ if(O[j].D==i){ //查询操作 ans[j]=query(O[j].L,O[j].R,O[j].P); } } } } rep(i,1,m) if(O[i].kind==0) printf("%d\n",ans[i]); } return 0;}
hdu 5057 Argestes and Sequence (数状数组+离线处理)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。