題目

題解

區(qū)間修改，詢問區(qū)間小于c的個數。分塊排序，用vector。至于那個塊的大小，好像要用到均值不等式 我不太會。。。就開始一個個試，發(fā)現siz=sqrt(n)/4時最快！！！明天去學一下算分塊復雜度的方法。

代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath>using namespace std; const int MAXN = 50005; const int N = 1005;inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; }vector<int> b[N];int n,siz; int a[MAXN],l[N],r[N]; int num,bl[MAXN],inc[MAXN];inline void reset(int id){b[id].clear();for(register int i=l[id];i<=r[id];i++) b[id].push_back(a[i]);sort(b[id].begin(),b[id].end()); }inline void build(){siz=sqrt(n);siz/log2(n);num=n/siz;if(n%siz) num++;for(register int i=1;i<=n;i++)bl[i]=(i-1)/siz+1; for(register int i=1;i<=num;i++){l[i]=(i-1)*siz+1;r[i]=i*siz;}r[num]=n;for(register int i=1;i<=num;i++) reset(i); }inline void update(int ql,int qr,int w){if(bl[ql]==bl[qr]){for(register int i=ql;i<=qr;i++)a[i]+=w;reset(bl[ql]);return;}for(register int i=ql;i<=r[bl[ql]];i++)a[i]+=w;reset(bl[ql]);for(register int i=bl[ql]+1;i<bl[qr];i++) inc[i]+=w;for(register int i=l[bl[qr]];i<=qr;i++)a[i]+=w;reset(bl[qr]); }inline int query(int ql,int qr,int c){int ret=0;if(bl[ql]==bl[qr]){for(register int i=ql;i<=qr;i++)ret+=(a[i]+inc[bl[i]]<c);return ret;}for(register int i=ql;i<=r[bl[ql]];i++)ret+=(a[i]+inc[bl[i]]<c);for(register int i=l[bl[qr]];i<=qr;i++)ret+=(a[i]+inc[bl[i]]<c);for(register int i=bl[ql]+1;i<bl[qr];i++){int tar=c-inc[i];ret+=lower_bound(b[i].begin(),b[i].end(),tar)-b[i].begin();}return ret; }int main(){n=rd();for(register int i=1;i<=n;i++) a[i]=rd();build();for(register int i=1;i<=n;i++){int op,L,R,k;op=rd();L=rd();R=rd();k=rd();if(op==0)update(L,R,k);elseprintf("%d\n",query(L,R,k*k));}return 0; }

轉載于:https://www.cnblogs.com/sdfzsyq/p/9677036.html

總結

以上是生活随笔為你收集整理的loj #6278. 数列分块入门 2的全部內容，希望文章能夠幫你解決所遇到的問題。

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