题解 P2801 【教主的魔法】
@xMinh:底下仨题解我hack掉俩了
qwq太强辣!
说正题
数列分块入门by hzwer一个很好的blog
一开始看见Q很小以为是差分
一看题发现不对劲
于是我们就拿分块暴力了233
@巨型方块 有人要把你分了
首先，分块是sm玩意？
根号平衡(by lxl)：
有x次操作，单次复杂度为O(a)
有y=kx次查询，单次复杂度为O(b)
在满足一定条件的题里面
可以通过提高其中一边的复杂度，降低另一边的复杂度来达到更好的效果
这时满足xa=kxb
于是分块一般都是带sqrt的
杜教筛会出来O(n^(2/3))的神奇复杂度，基于数论分块
但这里不讨论数论分块
带修改区间和问题的部分做法(还是by lxl)
如果采用x叉树，即有logx(n)层
如果采用sqrt(n)叉树，即有2层
如果采用2叉树，即有logn层
第一个是分块，第二个是线段树
这个即是一个根号平衡的例子
但这个题不能用分治结构完成(继续by lxl)
如果是单点修改，我们可以用树套树实现
但是区间修改后树套树无法快速合并信息
比如我们维护了cur的一个名次数据结构
cur的左儿子没有发生变化
cur的右儿子被整体加了
这样我们无法通过这两个儿子的名次数据结构快速维护出cur的名次数据结构
也无法直接在cur的名次数据结构上操作
所以分治结构无法在低复杂度解决这个问题
那么想到分块
分块基础(lxl)
要实现：
1.区间加
2.区间和
朴素来做，可以有O(1)修改O(n)查询以及O(n)修改O(1)查询的暴力做法
这个问题可以套用根号平衡达到O( sqrt(n) )修改O( sqrt(n) )查询
我们可以把sqrt(n)个元素放一块里面维护
我们把每次操作完整覆盖的块定义为“整块”
把每次操作没有完整覆盖的块定义为“零散块”(区间端点)
每次操作最多经过O( sqrt(n) )个整块，以及O(1)个零散块
所以我们可以O(1)维护整块信息，O( sqrt(n) )查询零散块信息
这样就达到了O( msqrt(n) )的复杂度
分块本质
一个度数为sqrt(n)，只有三层的树
每次修改只用更新:sqrt(n)个size为1的节点以及2个size为sqrt(n)的节点
注意到我们不用维护那个size为n的根节点的信息
所以如果在分治结构上很难快速合并某些信息，我们就可以利用分块来做
好了抄lxl的课件抄完了233
这个问题可以抽象成：
维护一个序列
支持区间加，区间查询>=x的数的个数
那么分块怎么做？
初始化的时候，对每个块排序
修改的时候，整块打标记，零散块重构，就是再排序一遍
查询呢？
零散块查询可以暴力，整块查询可以二分
如何二分？
假设区间的标记为y，读入的是x
那么只要把x-y作为二分的值即可
用stl的lower_bound很快
接下来是复杂度
设有x个块
修改:整块O(1),零散块O(n/x)
这里排序的方法要注意
原先这个块是有序的
区间加之后，这个区间仍然保持有序
也就是有两个有序的区间要合并
归并即可完成O(n/x)复杂度
查询:零散块O(n/x),整块O(log(n/x)*x)
于是根号平衡成为O(msqrt(nlogn))(我也不知道怎么算的)
上代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[1100000],m,bl[1100000],tag[2000],l,r,x,n,bol,a1[1100000],t[1100000],L[2000],R[2000],opt;
inline void merge(int l1,int r1,int l2,int r2)
{
register int i=l1,j=l2,k=l1;
while(i<=r1&&j<=r2)
{
if(a1[i]<a1[j])t[k++]=a1[i++];
else t[k++]=a1[j++];
}
while(i<=r1)t[k++]=a1[i++];
while(j<=r2)t[k++]=a1[j++];
for(register int i=l1;i<=r2;i++)
a1[i]=t[i];
}
inline void reset(int x,int c)
{
int r=R[x];
for(register int i=L[x];i<=r;i++)
a1[i]=a[i];
merge(L[x],c,c+1,r);
}
inline void cg(int l,int r,int x)
{
int minn=min(r,R[bl[l]]);
for(register int i=l;i<=minn;i++)
a[i]+=x;
reset(bl[l],l);
if(bl[l]!=bl[r])
{
for(register int i=L[bl[r]];i<=r;i++)
a[i]+=x;
reset(bl[r],r);
}
for(register int i=bl[l]+1;i<bl[r];i++)
tag[i]+=x;
}
inline int q(int l,int r,int x)
{
int ans=0;
int minn=min(r,R[bl[l]]);
int xx=x-tag[bl[l]];
for(register int i=l;i<=minn;i++)
if(a[i]>=xx)
ans++;
if(bl[l]!=bl[r])
{
xx=x-tag[bl[r]];
for(register int i=L[bl[r]];i<=r;i++)
if(a[i]>=xx)
ans++;
}
for(register int i=bl[l]+1;i<bl[r];i++)
{
int xx=x-tag[i];
ans+=R[i]-(lower_bound(a1+L[i],a1+R[i]+1,xx)-a1)+1;
}
return ans;
}
inline int getin()
{
register int x=0;register char ch=getchar();
while((ch<'0'||ch>'9'))ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x;
}
inline char getin1()
{
register char ch=getchar();
while(ch<'A'||ch>'M')ch=getchar();
return ch;
}
int wt[100];
inline void putout(int x)
{
if(!x)
{
putchar(48);
return;
}
register int l=0;
while(x)wt[++l]=x%10,x/=10;
while(l)putchar(wt[l--]+48);
}
int main()
{
n=getin(),m=getin();
bol=sqrt(n);
for(register int i=1;i<=n;i++)a1[i]=a[i]=getin(),bl[i]=(i-1)/bol+1;
for(register int i=1;i<=bl[n];i++)
{
L[i]=(i-1)*bol+1;R[i]=i*bol;
sort(a1+L[i],a1+R[i]+1);
}
R[bl[n]]=n;
for(register int i=1;i<=m;i++)
{
opt=getin1(),l=getin(),r=getin(),x=getin();
if(opt=='M')cg(l,r,x);
else putout(q(l,r,x)),putchar(10);
}
}PS:虽然推出来块大小应该是sqrt(nlogn),但sqrt(n)跑得最快...
分块这东西很玄学...有时候+-*/一些常数可能就能跑快点...
目前rank5
rqy太强了...不开O2跑了240ms开O2 188ms...最顶上两个是rqy的代码%%%