【BZOJ3343】【洛谷P2801】—教主的魔法（分块）

BZOJ传送门（权限题）

洛谷传送门

分块水题

考虑到要查询大于等于$c$的数

我们把每个块单独$sort$一下

每次修改整块打一个标记

散块暴力修改后重构

复杂度$O(nlogsqrt n+qsqrt nlogsqrt n)$

因为$q<=3000$所以能过

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res*f;
}
const int N=1000005;
const int M=1005;
int tag[M],a[N],b[N],plc[N],L[M],R[M],blo,cnt,n,m,q;
char ch[5];
inline void reset(int p){
	for(int i=L[p];i<=R[p];i++)a[i]=b[i];
	sort(a+L[p],a+R[p]+1);
}
inline void modify(int l,int r,int c){
	if(plc[r]-plc[l]>1){
		for(int i=plc[l]+1;i<=plc[r]-1;i++)tag[i]+=c;
	}
	if(plc[l]==plc[r]){
		for(int i=l;i<=r;i++)b[i]+=c;
		reset(plc[l]);return;
	}
	for(int i=l;i<=R[plc[l]];i++)b[i]+=c;
	reset(plc[l]);
	for(int i=L[plc[r]];i<=r;i++)b[i]+=c;
	reset(plc[r]);
}
inline int find(int l,int r,int c){
	return lower_bound(a+l,a+r+1,c)-a;
}
inline int query(int l,int r,int c){
	int res=0;
	if(plc[r]-plc[l]<=1){
		for(int i=l;i<=r;i++)if(b[i]+tag[plc[i]]>=c)++res;
		return res;
	}
	for(int i=plc[l]+1;i<=plc[r]-1;i++){
		res+=(R[i]-find(L[i],R[i],c-tag[i])+1);
	}
	for(int i=l;i<=R[plc[l]];i++)if(b[i]+tag[plc[i]]>=c)++res;
	for(int i=L[plc[r]];i<=r;i++)if(b[i]+tag[plc[i]]>=c)++res;
	return res;
}
int main(){
	n=read(),q=read();
	blo=sqrt(n),cnt=(n-1)/blo+1;
	for(int i=1;i<=n;i++)plc[i]=(i-1)/blo+1;
	for(int i=1;i<=cnt;i++)L[i]=(i-1)*blo+1,R[i]=min(i*blo,n);
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=cnt;i++)reset(i);
	for(int i=1;i<=q;i++){
		scanf("%s",ch);
		int l=read(),r=read(),c=read();
		if(ch[0]=='M'){
			modify(l,r,c);
		}
		else cout<<query(l,r,c)<<'
';
	}
}