资源描述：
《acm数据结构部分模版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构：增加栈#pragmacomment(linker,"/STACK:1024000000,1024000000")二维树状数组#include#include#include#definemaxn130usingnamespacestd;intxt[maxn][maxn][maxn];intadd,z,n;intlow(intx){returnx&(-x);}//二维树状数组，第三维枚举voidup(intx,inty){inti,j;for(i=x;i<=maxn;i+=low(i))fo
2、r(j=y;j<=maxn;j+=low(j)){xt[z][i][j]+=add;if(xt[z][i][j]<0)xt[z][i][j]=0;}}intsum(intx,inty){inti,ans=0;for(i=x;i>0;i-=low(i))for(intj=y;j>0;j-=low(j)){ans+=xt[z][i][j];}returnans;}intmain(){intx,y,a;intx1,y1,z1,z2;intx2,y2,ans;while(cin>>n){memset(xt,0,sizeof(xt));while(scanf("
3、%d",&a)&&a!=3){ans=0;if(a==1){scanf("%d%d%d%d",&x,&y,&z,&add);x+=2;y+=2;z+=2;up(x,y);}elseif(a==2){scanf("%d%d%d",&x1,&y1,&z1);scanf("%d%d%d",&x2,&y2,&z2);//树状数组必须大于0，而且是整数x1+=2;x2+=2;y1+=2;y2+=2;z1+=2;z2+=2;for(z=z1;z<=z2;z++){//求矩阵（x1,y1）(x2,y2)（对角）的和公式//sum(x2,y2)-sum(x1-1,y2
4、)-sum(x2,y1-1)+sum(x1-1,y1-1)ans+=(sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1));}printf("%d",ans);}}线段树成段更新voiddown(into,intL,intR){if(add[o]!=0){sum[o]+=add[o]*(R-L+1);}}voidupdate(intL,intR,into){if(L>=ql&&qr>=R){add[o]+=v;sum[o]+=v*(R-L+1);return;}intmid=(L+R)>>1;if
5、(ql<=mid)update(L,mid,o<<1);if(qr>mid)update(mid+1,R,o<<1
6、1);sum[o]=sum[o<<1]+sum[o<<1
7、1];down(o,L,R);}voidfind(intL,intR,into,LL_add){if(L>=ql&&qr>=R){v+=sum[o];v+=_add*(R-L+1);return;}intmid=(L+R)>>1;if(ql<=mid)find(L,mid,o<<1,_add+add[o]);if(qr>mid)find(mid+1,R,o<<1
8、1,_add+ad
9、d[o]);}voidpush(into){intlc=o*2;intrc=o*2+1;if(set[o]>=0)//往下更新{set[lc]=set[rc]=set[o];set[o]=-1;//记得标记}}voidupdate(into,intL,intR){intlc=o*2,rc=o*2+1;if(x1<=L&&x2>=R){set[o]=v;}else{push(o);//把之前没有更新的一起带下去更新intmid=(L+R)/2;if(x1<=mid)update(lc,L,mid);if(x2>mid)update(rc,mid+1,R)
10、;}}//求居间不同数个数voidfind(into,intL,intR){if(set[o]!=-1){if(set[o]>0&&!vi[set[o]]){vi[set[o]]=1;mun++;}//如果当前有标记则不再往下找return;}if(L==R)return;intmid=(L+R)>>1;find(o*2,L,mid);find(o*2+1,mid+1,R);}KMP：voidget(){inti,j=-1;f[0]=-1;for(i=1;i=0&&p[j+1]!=p[i])j=f[j];if(p[j+1
11、]==p[i])j++;f[i]=j;}}voidfind(){inti,j=-1;get()
