正題

題目鏈接:https://www.luogu.com.cn/problem/P2801

---

題目大意

$n$個數字，要求支持

區間加上一個數字$w$

詢問一個區間內不小于$w$的數的個數

---

解題思路

考慮分塊，對于塊內我們維護一個排序后的數組，查詢時直接在整個塊中二分答案即可。修改就暴力修改然后排序。

時間復雜度$O(Q\sqrt{n}\log n)$

---

$code$

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=1e6+10; int n,m,T,a[N],v[N],pos[N]; int L[N],R[N],lazy[N]; void Reset(int x){for(int i=L[x];i<=R[x];i++)a[i]+=lazy[x],v[i]=a[i];sort(v+L[x],v+R[x]+1);lazy[x]=0;return; } void seq_qer(){for(int i=1;i<=T;i++)L[i]=R[i-1]+1,R[i]=i*T;if(R[T]!=n)L[++T]=R[T]+1,R[T]=n;for(int i=1;i<=T;i++)for(int j=L[i];j<=R[i];j++)pos[j]=i;for(int i=1;i<=T;i++)Reset(i); } int Ask(int l,int r,int w){int q=pos[l],p=pos[r],ans=0;if(q==p){for(int i=l;i<=r;i++)ans+=(a[i]+lazy[p]>=w);return ans;}for(int i=l;i<=R[q];i++)ans+=(a[i]+lazy[q]>=w);for(int i=L[p];i<=r;i++)ans+=(a[i]+lazy[p]>=w);for(int i=q+1;i<p;i++){if(v[R[i]]+lazy[i]<w)ans+=R[i]-L[i]+1;else ans+=R[i]+1-(lower_bound(v+L[i],v+R[i]+1,w-lazy[i])-v);}return ans; } void Change(int l,int r,int w){int q=pos[l],p=pos[r],ans=0;if(q==p){for(int i=l;i<=r;i++)a[i]+=w;Reset(p);return;}for(int i=l;i<=R[q];i++)a[i]+=w;Reset(q);for(int i=L[p];i<=r;i++)a[i]+=w;Reset(p);for(int i=q+1;i<p;i++)lazy[i]+=w;return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);T=sqrt(n);seq_qer();while(m--){printf("%d ",n);for(int i=1;i<=n;i++)printf("%d ",v[i]);char op[3];int l,r,w;scanf("%s %d %d %d",op,&l,&r,&w);if(op[0]=='M')Change(l,r,w);else printf("%d\n",Ask(l,r,w));}return 0; }

總結

以上是生活随笔為你收集整理的P2801-教主的魔法【分块,二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。