P6357 [COCI 2007/2008 #3] REDOKS题目描述给定一串长度为n nn的数字数字为0 ∼ 9 0\sim 90∼9之间的任意一个下标从1 11记起。然后进行m mm次区间查询每次查找区间[ A , B ] [A,B][A,B]的区间和并在查询结束后将区间里的每一个数都 1 11。特殊地如果 1 11前的数字为9 99那么 1 11之后就变成了0 00。请输出每次查询的区间和。输入格式输入第一行包含两个整数n , m n,mn,m。第二行n nn个数字字符字符间无空格。接下来的m mm行每行两个整数A , B A,BA,B表示查询区间[ A , B ] [A,B][A,B]。输出格式输出共m mm行每行为一次查询的区间和。输入输出样例 #1输入 #14 3 1234 1 4 1 4 1 4输出 #110 14 18输入输出样例 #2输入 #24 4 1234 1 1 1 2 1 3 1 4输出 #21 4 9 16输入输出样例 #3输入 #37 5 9081337 1 3 3 7 1 3 3 7 1 3输出 #317 23 1 19 5说明/提示数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 2.5 × 10 5 1\le n\le 2.5\times 10^51≤n≤2.5×1051 ≤ m ≤ 10 5 1\le m\le 10^51≤m≤1051 ≤ A , B ≤ n 1\le A,B\le n1≤A,B≤n。说明题目译自 COCI2007-2008 CONTEST #3T6 REDOKS。C实现#includebits/stdc.husingnamespacestd;#definepl(p1)#definepr(p1|1)constintN2.5e510;intn,q,x[10],a[N],add[N2],num[N2][10];charc;voidpush_up(intp){for(inti0;i10;i)num[p][i]num[pl][i]num[pr][i];}voidupd(intp,intk){if(k){memcpy(x,num[p],sizeofx);for(inti0;i10;i)num[p][(ik)%10]x[i];}}voidpush_down(intp){if(add[p])add[pl]add[p],upd(pl,add[p]),add[pr]add[p],upd(pr,add[p]),add[p]0;}voidupdate(intl,intr,intle,intri,intp){if(llerri)returnadd[p],upd(p,1);intmidlr1;push_down(p);if(lemid)update(l,mid,le,ri,pl);if(rimid)update(mid1,r,le,ri,pr);push_up(p);}intquery(intl,intr,intle,intri,intp){if(llerri){intret0;for(inti1;i10;i)retnum[p][i]*i;returnret;}intmidlr1,ret0;push_down(p);if(lemid)retquery(l,mid,le,ri,pl);if(rimid)retquery(mid1,r,le,ri,pr);returnret;}voidbuild(intl,intr,intp){if(lr)returnnum[p][a[l]]1,void();intmidlr1;build(l,mid,pl),build(mid1,r,pr),push_up(p);}intmain(){cinnq;for(inti1;in;i)cinc,a[i]c-0;build(1,n,1);for(intl,r;q--;)cinlr,coutquery(1,n,l,r,1)\n,update(1,n,l,r,1);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容