传送门
分块大法好
分块
-
什么是分块
- 就是把一连串的东西分成几个部分，通常是分成√n个部分，每个部分√n个数字，然后每一块分开处理。（当然有别的情况）
-
有什么用
- 时间得到了优化，把n变成了sqrt(n)*log(sqrt(n))。这是一种优雅的暴力呢
- 主要思路？
- 每一块内按照权值排序。对于每一次操作的区间，若是中间完整的块，就用lazy处理，若是两边的不完整的块，就先按id排序，然后暴力处理，再按照value排序回去。完整的块每次操作O(1)，最多有sqrt(n)块，总共sqrt(n)；两遍的块每次操作sqrt(n)*log(sqrt(n))，最多有两块，总共是sqrt(n)*log(sqrt(n))。所以最后的一次操作时间复杂度为O(sqrt(n)*log(sqrt(n)))。
解题思路
看一下这个题，就是个板子，但是有些需要注意的事情：
- 判断区间两个端点是否在同一个块里，防止重复加或者重复计算。
- lower_bound因为是在结构体里查询，所以需要把查询的值包装成一个结构体，然后用上比较函数。
- 求块的个数以及大小时一定要sq=sqrt(n)+1，不要吝啬，即使多一个块也不能漏掉元素！！
- 要注意到零散块的边界
AC代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 const int maxn=1000005; 6 struct node{ 7 int value,id; 8 }a[maxn]; 9 int n,q,cnt,num,ans,l[maxn],r[maxn],id[maxn],sq,lazy[maxn]; 10 bool cmp_value(node a,node b){ 11 if(a.value==b.value) return a.id<b.id; 12 return a.value<b.value; 13 } 14 bool cmp_id(node a,node b){ 15 return a.id<b.id; 16 } 17 inline void add(int ll,int rr,int w){ 18 sort(a+l[id[ll]],a+r[id[ll]]+1,cmp_id); 19 for(int i=ll;i<=rr;i++) a[i].value+=w; 20 sort(a+l[id[ll]],a+r[id[ll]]+1,cmp_value); 21 } 22 inline int query(int ll,int rr,int w){ 23 int res=0; 24 sort(a+l[id[ll]],a+r[id[ll]]+1,cmp_id); 25 for(int i=ll;i<=rr;i++) if(a[i].value>=w) res++; 26 sort(a+l[id[ll]],a+r[id[ll]]+1,cmp_value); 27 return res; 28 } 29 int main() 30 { 31 cin>>n>>q; 32 for(int i=1;i<=n;i++){ 33 cin>>a[i].value; 34 a[i].id=i; 35 } 36 sq=sqrt(n)+1; 37 int now=1; 38 for(int i=1;i<=n;i++){ 39 if(cnt==sq){ 40 sort(a+l[now],a+i,cmp_value); 41 cnt=0; 42 r[now++]=i-1; 43 l[now]=i; 44 } 45 cnt++; 46 id[i]=now; 47 } 48 r[now]=n; 49 for(int i=1;i<=q;i++){ 50 char c; 51 int ll,rr,w; 52 cin>>c>>ll>>rr>>w; 53 if(c=='M'){ 54 for(int i=id[ll]+1;i<=id[rr]-1;i++) lazy[i]+=w; 55 add(ll,min(rr,r[id[ll]]),w); 56 if(id[ll]!=id[rr]) add(l[id[rr]],rr,w); 57 }else{ 58 ans=0; 59 node x; 60 x.id=0; 61 for(int i=id[ll]+1;i<=id[rr]-1;i++) x.value=w-lazy[i],ans+=a+r[i]-lower_bound(a+l[i],a+r[i]+1,x,cmp_value)+1; 62 ans+=query(ll,min(rr,r[id[ll]]),w-lazy[id[ll]]); 63 if(id[ll]!=id[rr]) ans+=query(l[id[rr]],rr,w-lazy[id[rr]]); 64 cout<<ans<<endl; 65 } 66 } 67 return 0; 68 }