前言

手搓蓝色数据结构，好开心。

题意

维护序列，支持区间加、区间统计比给定值小的数的个数。

题解

先对题意做一个简单转化：区间统计小于给定值的数的个数，就是求给定值在区间内排第几。这是主席树的经典应用“求区间

k

大值”，复杂度

O(n \log n)

。由于

n

没多大，用分块的根号复杂度也能曹飞这道题。具体复杂度最后说明。

先想最暴力的

O(n^2)

做法：暴力加、暴力查找。不难发现查找可以用二分优化，但区间查之前还要先排序，最坏复杂度

O(n^2 \log n)

，考虑优化。注意到最坏情况下多次排序了同一段区间，有没有什么办法能一次排序解决所有查询呢？

有的兄弟，有的。我们先对数列分块，对每个块内部排序。但这时一块内元素的相对位置都改变了，所以我们要建一个原数组的副本，在副本上进行排序。

接着看区间加操作。我们再次注意到，对一整个已经排好序的块加上某个值，元素的相对大小不会变。这启示我们给每个块维护一个 lazy-tag，整个块加时直接对 lazy-tag 进行加减操作。而对于区间两端的散块，直接暴力单点加即可。这时我们再再次注意到，暴力单点加后两端的块中元素相对位置可能发生改变，需要再次排序。我们可以将这个块再次复制到副本上，再从副本上排序。

最后是区间查。对于整块，我们在副本上二分统计；对于两端散块，我们暴力统计即可。注意统计时不要忘记加减 lazy-tag。这里二分不需要手写，直接 lower_bound 即可。

代码

CPP

void Main(int cases){
	n=read();
	up(i,1,n) a[i]=b[i]=read();
	len=sqrt(n);
	l[0]=r[0]=0;
	up(i,1,n){
		id[i]=(i-1)/len+1;
		if(id[i]!=id[i-1]) l[id[i]]=i,r[id[i-1]]=i-1,cnt++;
	}
	r[cnt]=n;
	up(i,1,cnt){
		sort(b+l[i],b+r[i]+1);
	}
	up(i,1,n){
		ll op=read(),lt=read(),rt=read(),x=read();
		if(op==0){
			if(id[lt]==id[rt]){
				up(j,lt,rt) a[j]+=x;
				up(j,l[id[lt]],r[id[lt]]) b[j]=a[j];
				sort(b+l[id[lt]],b+r[id[lt]]+1);
			}else{
				up(j,lt,r[id[lt]]) a[j]+=x;
				up(j,l[id[lt]],r[id[lt]]) b[j]=a[j];
				sort(b+l[id[lt]],b+r[id[lt]]+1);
				
				up(j,l[id[rt]],rt) a[j]+=x;
				up(j,l[id[rt]],r[id[rt]]) b[j]=a[j];
				sort(b+l[id[rt]],b+r[id[rt]]+1);
				up(j,id[lt]+1,id[rt]-1) add[j]+=x;
			}
		}
		if(op==1){
			x=x*x;
			ll ans=0;
			if(id[lt]==id[rt]){
				up(j,lt,rt) ans+=((a[j]+add[id[j]])<x);
			}else{
				up(j,lt,r[id[lt]]) ans+=((a[j]+add[id[j]])<x);
				up(j,l[id[rt]],rt) ans+=((a[j]+add[id[j]])<x);
				up(j,id[lt]+1,id[rt]-1){
					ll tmp=lower_bound(b+l[j],b+r[j]+1,x-add[j])-(b+l[j]-1)-1;
					ans+=tmp;
				}
			}
			cout<<ans<<endl;
		}
	}
	return;
}

解释

稍微解释一下上面的代码。

其中

id_i,l_i,r_i

都是与基础分块有关，这里我懒得讲；

b

是原数组副本，用于排序；

add

是我们上面提到的 lazy-tag。

总结

本题虽说是蓝，却是一道很好的分块进阶题目，可以荣登 S 组必吃榜。此外，这题坑也比较多，尤其是 lower_bound 找不到、全都是时的特殊返回值，坑了我六七回。

通过这题的同学可以去挑战数列分块系列的后面题目了，再见！

题解：P13977 数列分块入门 2

文章操作

前言

题意

题解

代码

解释

总结

相关推荐

评论

题解：P13977 数列分块入门 2