修改直接對整塊打標記，兩邊暴力。

查詢需要保證每個整塊有序，所以在修改時排序就好啦

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #define N 1000005 using namespace std; int n,m,nn,be[N],lazy[1005],ans; int a[N],b[N]; void work(int x) {int l=(x-1)*nn+1,r=min(n,x*nn);for(int i=l;i<=r;i++)b[i]=a[i];sort(b+l,b+r+1); } int main() {scanf("%d%d",&n,&m);nn=(int)sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);be[i]=(i-1)/nn+1;}int tot=be[n];for(int i=1;i<=tot;i++)work(i);char ch; int l,r,c,num;while(m--){ch=getchar();while(ch!='A'&&ch!='M') ch=getchar();scanf("%d%d%d",&l,&r,&c);if(ch=='M'){if(be[l]==be[r]){for(int i=l;i<=r;i++) a[i]+=c;work(be[l]);continue;}for(int i=be[l]+1;i<be[r];i++) lazy[i]+=c;for(int i=l;i<=be[l]*nn;i++) a[i]+=c;for(int i=(be[r]-1)*nn+1;i<=r;i++) a[i]+=c;work(be[l]); work(be[r]);}else{int x; ans=0;if(be[l]==be[r]){for(int i=l;i<=r;i++)if(a[i]+lazy[be[i]]>=c)ans++;printf("%d\n",ans);continue;}for(int i=be[l]+1;i<be[r];i++){x=c-lazy[i];int L=(i-1)*nn+1,R=min(n,i*nn);num=lower_bound(b+L,b+R+1,x)-b;ans+=R-num+1;}for(int i=l;i<=be[l]*nn;i++)if(a[i]+lazy[be[i]]>=c)ans++;for(int i=(be[r]-1)*nn+1;i<=r;i++)if(a[i]+lazy[be[i]]>=c)ans++;printf("%d\n",ans);}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Ren-Ivan/p/7746749.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的bzoj 3343 教主的魔法 分块的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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