題目鏈接

/* 如果用線段樹，每個(gè)節(jié)點(diǎn)要再開k的空間，顯然不行。但是分塊可以(雖然空間依舊爆炸)分塊。用bloans[i][j]表示 第i塊 模k為j 的有多少個(gè) 對(duì)于不是整塊的，查詢時(shí)應(yīng)判斷 A[i]+tag[belong[i]] ==k || ==0 對(duì)于整塊，維護(hù)兩個(gè)tag，一個(gè)是整塊的加標(biāo)記，另一個(gè)是整塊的mod數(shù)標(biāo)記tag2，初始時(shí)tag2為0 當(dāng)整塊+v時(shí)，tag2 -=v。因?yàn)椴樵兊膽?yīng)是 模k=0 的數(shù)的個(gè)數(shù)，整塊+v后，這塊要查的就是 模k=k-v ((k-v+v)%k=0)的個(gè)數(shù) 這樣就很巧妙地將整塊加變成了改詢問(wèn) */ #include<cmath> #include<cstdio> #include<cctype> #include<algorithm> using namespace std; const int N=2e5+5,MAXSZ=460;int n,m,k,size,A[N],belong[N],bloans[MAXSZ][N],tag[MAXSZ],tag2[MAXSZ];inline int read() {int now=0,f=1;register char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-') f=-1;for(;isdigit(c);now=now*10+c-'0',c=getchar());return now*f; }void Update(int p,int v) {--bloans[belong[p]][A[p]];A[p]+=v;if(A[p]>=k) A[p]-=k;++bloans[belong[p]][A[p]]; } void Add(int l,int r,int v) {int t=min(r,belong[l]*size);for(int i=l; i<=t; ++i)Update(i,v);if(belong[l]!=belong[r])for(int i=(belong[r]-1)*size+1; i<=r; ++i)Update(i,v);for(int i=belong[l]+1; i<belong[r]; ++i){tag[i]+=v, tag2[i]-=v;if(tag[i]>=k) tag[i]-=k;if(tag2[i]<0) tag2[i]+=k;} } int Query(int l,int r) {int res=0, t=min(r,belong[l]*size);for(int i=l; i<=t; ++i)if(A[i]+tag[belong[l]]==k || !(A[i]+tag[belong[l]]))++res;if(belong[l]!=belong[r])for(int i=(belong[r]-1)*size+1; i<=r; ++i)if(A[i]+tag[belong[r]]==k || !(A[i]+tag[belong[r]]))//beblong[l] belong[r]別寫反了 ++res;for(int i=belong[l]+1; i<belong[r]; ++i)res+=bloans[i][tag2[i]];return res; }int main() {n=read(),m=read(),k=read();size=sqrt(n);for(int i=1;i<=n;++i){A[i]=read()%k, belong[i]=(i-1)/size+1;if(A[i]<0) A[i]+=k;++bloans[belong[i]][A[i]];}char opt[9];int l,r,v;while(m--){scanf("%s",opt);l=read(),r=read();if(opt[0]=='a')v=read(), Add(l,r,(v%k+k)%k);elseprintf("%d\n",Query(l,r));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/8435078.html

總結(jié)

以上是生活随笔為你收集整理的CODEVS.5037.线段树练习4加强版(分块 区间k的倍数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。