luogu2801 教主的魔法

分块入门题，思路简单。区间加+查询区间内大于等于x的数的个数

需要注意的一点就是，尽管分块的时候要进行块内排序，但是每次进行区间操作的时候指的还是原数组的区间。

一开始没看板子自己敲了一个鬼畜做法，就不在这里赘述了，但代码及其冗长。

被dalao点化说需要开两个数组，一个是原序列，一个是分块数组，就是排好序的。

整块的修改就不说了，打标记。零散块的修改要先改原序列，之后复制到分块数组里，再进行重构；整块的查询是用分块数组来二分，零散直接暴力查，但需要注意查的时候都要加上标记才行。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn (1000000 + 10)
using namespace std;
int a[maxn],b[maxn],bl[maxn],L[maxn],R[maxn],add[maxn];
int n,m,block;
int read(){
	char c;int r=0,f=1;
	c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		r=r*10+(c^48);
		c=getchar();
	}
	return r*f;
}
void build(){
	for (int i=1;i<=n;i++) bl[i]=(i-1)/block+1;
	for (int i=1;i<=n;i++) if (!L[bl[i]]) L[bl[i]]=i;
	for (int i=n;i>=1;i--) if (!R[bl[i]]) R[bl[i]]=i;
	for (int i=bl[1];i<=bl[n];i++) sort(b+L[i],b+R[i]+1);
}
void reset(int belong){
	for (int i=L[belong];i<=R[belong];i++) b[i]=a[i];
}
void change(int l,int r,int x){
	if (bl[l]==bl[r]){
		for (int i=l;i<=r;i++) a[i]+=x;
		reset(bl[l]);
		sort(b+L[bl[l]],b+R[bl[l]]+1);
	}
	else{
		for (int i=l;i<=R[bl[l]];i++) a[i]+=x;
		reset(bl[l]);
		sort(b+L[bl[l]],b+R[bl[l]]+1);
		for (int i=bl[l]+1;i<=bl[r]-1;i++) add[i]+=x;
		for (int i=L[bl[r]];i<=r;i++) a[i]+=x;
		reset(bl[r]);
		sort(b+L[bl[r]],b+R[bl[r]]+1);
	}
}
int lb(int x,int belong){
	int l=L[belong],r=R[belong];
	int ans=r+1;
	while (l<=r){
		int mid=(l+r)>>1;
		if (b[mid]>=x){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	return R[belong]-ans+1;
}
int query(int l,int r,int x){
	int ans=0;
	if (bl[l]==bl[r]) {
		for (int i=l;i<=r;i++) if (a[i]>=x-add[bl[l]]) ans++;
	}
	else{
		for (int i=l;i<=R[bl[l]];i++) if (a[i]>=x-add[bl[l]]) ans++;
		for (int i=bl[l]+1;i<=bl[r]-1;i++) ans+=lb(x-add[i],i);
		for (int i=L[bl[r]];i<=r;i++) if (a[i]>=x-add[bl[r]]) ans++;
	}
	return ans;
}
int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]=b[i]=read();
	block=sqrt(n);
	build();
	for (int i=1;i<=m;i++){
		char opt;int l,r,x;
		cin>>opt;
		l=read();r=read();x=read();
		if (opt=='M') change(l,r,x);
		if (opt=='A') printf("%d\n",query(l,r,x));
	}
}

P.S.

我是真心想吐槽这题。

第一遍打自己那个鬼畜做法的时候检查不出错误来，只好调出题解来对拍，结果无意间用这组数据hack掉两个题解。

10 5
39 56 58 26 89 11 86 31 84 21
M 5 9 21
A 1 7 38
M 6 8 80
M 1 2 90
A 1 1 88

然后好不容易过了，开始打正确做法，又检查不出错误来，和杜佬的对拍，又把他的给hack了。

16 2
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
M 10 11 10
A 6 16 10

据说这还是hzwer的解法……

我我我我就想hack掉一个三十分代码有那么难吗

一个三十分代码连着hack掉仨题解，emmmm……

教主的魔法解题报告

一个鬼畜的上午

luogu2801 教主的魔法

P.S.