题目

教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 $N$ 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 $1, 2, \ldots, N$。

每个人的身高一开始都是不超过 $1000$ 的正整数。教主的魔法每次可以把闭区间 $[L, R]$（$1≤L≤R≤N$）内的英雄的身高全部加上一个整数 $W$。（虽然 $L=R$ 时并不符合区间的书写规范，但我们可以认为是单独增加第 $L(R)$ 个英雄的身高）

CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 $[L, R]$ 内有多少英雄身高大于等于 $C$，以验证教主的魔法是否真的有效。

WD 巨懒，于是他把这个回答的任务交给了你。

输入格式

第 $1$ 行为两个整数 $N, Q$。$Q$ 为问题数与教主的施法数总和。

第 $2$ 行有 $N$ 个正整数，第 $i$ 个数代表第 $i$ 个英雄的身高。

第 $3$ 到第 $Q+2$ 行每行有一个操作：

若第一个字母为 M，则紧接着有三个数字 $L, R, W$。表示对闭区间 $[L, R]$ 内所有英雄的身高加上 $W$。
若第一个字母为 A，则紧接着有三个数字 $L, R, C$。询问闭区间 $[L, R]$ 内有多少英雄的身高大于等于 $C$。

输出格式

对每个 A 询问输出一行，仅含一个整数，表示闭区间 $[L, R]$ 内身高大于等于 $C$ 的英雄数。

样例 #1

样例输入 #1

样例输出 #1

2
3

提示

【输入输出样例说明】

原先 $5$ 个英雄身高为 $1, 2, 3, 4, 5$，此时 $[1, 5]$ 间有 $2$ 个英雄的身高大于等于 $4$。教主施法后变为 $1, 2, 4, 5, 6$，此时 $[1, 5]$ 间有 $3$ 个英雄的身高大于等于 $4$。

【数据范围】

对于 $30%$ 的数据，$N≤1000$，$Q≤1000$。

对于 $100%$ 的数据，$N≤10^{6$，$Q≤3000$，$1≤W≤1000$，$1≤C≤10}9$。

$\text{upd 2022.8.18}$：新增加一组 Hack 数据。

打个暴力先

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
inline int read(){
	int f(1),x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f*x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n,m,a[N],t,L[N],R[N];
main(void){
	n=read(),m=read();
	for(register int i=1;i<=n;i++){
		a[i]=read();
	}
	
	while(m--){
		char ch=getchar();getchar();
		int l=read(),r=read(),v=read();
		if(ch=='M'){
			for(register int i=l;i<=r;i++){
				a[i]+=v;
			}
		}
		else{
			int arc(0);
			for(register int i=l;i<=r;i++){
				if(a[i]>=v){
					arc++;
				}
			}
			write(arc),putchar('\n');
		}
	}
	return 0;
}

OJ得66分，luogu得0分

然后怎么分块呢

预处理

打个板子捏

记录每个块的左右边界和$pos[i]$记录对应位置

	n=read(),m=read();
	t=sqrt(n);
	for(register int i=1;i<=n;i++){
		a[i]=read();
	}
	for(register int i=1;i<=t;i++){
		L[i]=(i-1)*t+1;
		R[i]=i*t;
	}
	if(R[t]<n){
		t++,L[t]=R[t-1]+1,R[t]=n;
	}
	for(register int i=1;i<=t;i++){
		for(register int j=L[i];j<=R[i];j++){
			pos[j]=i;
		}
	}

查询

对于查询的时候因为不能对中间一块一个一个一个得遍历找>=v の数有多少

所以可以给这个块内的数组排个序（满足单调），用二分查找出初始点，然后用右区间减就行

例如一个块内元素有

5 2 3 4 1

我们将他升序排列

  1 2 3 4 5
L[i]     R[i]

例如找>=2的数

二分找到2是 $L[i]+1$ 然后用$R[i]-(L[i]+1)+1$

即$R[i]-$二分答案$+1$

对于不足整块即左右两边的数组可以用暴力搜索

对于$pos[l]=pos[r]$的部分特判暴力搜索就行

inline static int testify(int l,int r,int v){
	int arc(0),p=pos[l],q=pos[r];
	if(p==q){
		for(register int i=l;i<=r;i++){
			if(add[p]+a[i]>=v) arc++;
		}
		return arc;
	}
	else{
		for(register int i=l;i<=R[p];i++){
			if(add[p]+a[i]>=v) arc++;
		}
		for(register int i=L[q];i<=r;i++){
			if(add[q]+a[i]>=v) arc++;
		}
		for(register int i=p+1;i<=q-1;i++){
			int ll=L[i],rr=R[i]+1,mid(0);
			while(ll<rr){
				mid=(ll+rr)>>1;
				if(d[mid]+add[i]<v){
					ll=mid+1;
				}
				else{
					rr=mid;
				}
			}
			arc+=(R[i]+1)-ll;
		}
	}
	return arc;
}

修改

板子但是加入一个新数组$d[i]$对于原来$a[i]$的块进行$sort$升序排列

对于中间块用$add[i]$进行标记

inline void SORT(int now){
	for(register int i=L[now];i<=R[now];i++){
		d[i]=a[i];
	}
	sort(d+L[now],d+R[now]+1);
}
inline static void change(int l,int r,int v){
	int p=pos[l],q=pos[r];
	if(p==q){
		for(register int i=l;i<=r;i++){
			a[i]+=v;
		}
		SORT(p);
	}
	else{
		for(register int i=l;i<=R[p];i++){
			a[i]+=v;
		}
		SORT(p);
		for(register int i=L[q];i<=r;i++){
			a[i]+=v;
		}
		SORT(q);
		for(register int i=p+1;i<=q-1;i++){
			add[i]+=v;
		}
	}
}

完结撒花，附上$AC$代码

注意$d[i]$重排列数组要在 $main$函数初始化一下捏

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000114;
inline int read(){
	int f(1),x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f*x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n,m,a[N],t,L[N],R[N],d[N],pos[N],add[N];
inline void SORT(int now){
	for(register int i=L[now];i<=R[now];i++){
		d[i]=a[i];
	}
	sort(d+L[now],d+R[now]+1);//d+L[now]是对应块の左端点,
   //数组元素个数为R[now]-L[now]+1
   //所以d+L[now]+(R[now]-L[now]+1)=d+R[now]+1是sort的右边
}
inline static void change(int l,int r,int v){
	int p=pos[l],q=pos[r];
	if(p==q){
		for(register int i=l;i<=r;i++){
			a[i]+=v;
		}
		SORT(p);
	}
	else{
		for(register int i=l;i<=R[p];i++){
			a[i]+=v;
		}
		SORT(p);
		for(register int i=L[q];i<=r;i++){
			a[i]+=v;
		}
		SORT(q);
		for(register int i=p+1;i<=q-1;i++){
			add[i]+=v;
		}
	}
}
inline static int testify(int l,int r,int v){
	int arc(0),p=pos[l],q=pos[r];
	if(p==q){
		for(register int i=l;i<=r;i++){
			if(add[p]+a[i]>=v) arc++;
		}
		return arc;
	}
	else{
		for(register int i=l;i<=R[p];i++){
			if(add[p]+a[i]>=v) arc++;
		}
		for(register int i=L[q];i<=r;i++){
			if(add[q]+a[i]>=v) arc++;
		}
		for(register int i=p+1;i<=q-1;i++){
			int ll=L[i],rr=R[i]+1,mid(0);
			while(ll<rr){
				mid=(ll+rr)>>1;
				if(d[mid]+add[i]<v){
					ll=mid+1;
				}
				else{
					rr=mid;
				}
			}
			arc+=(R[i]+1)-ll;
		}
	}
	return arc;
}
main(void){
	n=read(),m=read();
	t=sqrt(n);
	for(register int i=1;i<=n;i++){
		a[i]=read();
	}
	for(register int i=1;i<=t;i++){
		L[i]=(i-1)*t+1;
		R[i]=i*t;
	}
	if(R[t]<n){
		t++,L[t]=R[t-1]+1,R[t]=n;
	}
	for(register int i=1;i<=t;i++){
		for(register int j=L[i];j<=R[i];j++){
			pos[j]=i;
		}
	}
	for(register int i=1;i<=t;i++){
		SORT(i);
	}
	while(m--){
		char ch;
		cin>>ch;
		int l=read(),r=read(),v=read();
		if(ch=='M'){
			change(l,r,v);
		}
		else if(ch=='A'){
			write(testify(l,r,v)),putchar('\n');
		}
	}
	return 0;
}

闲话

~~荒野大镖客2 前几日279打折67结果昨天想买已经过期了呜呜呜~~

JZTXT

题解(教主的魔法)P2801

题目

教主的魔法

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

预处理

查询

修改

完结撒花，附上$AC$代码

注意$d[i]$重排列数组要在 $main$函数初始化一下捏

闲话

JZTXT

题解(教主的魔法)P2801

题目

教主的魔法

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

预处理

查询

修改

完结撒花，附上$AC$代码

注意$d[i]$重排列数组要在 $main$函数 初始化一下捏

闲话

注意$d[i]$重排列数组要在 $main$函数初始化一下捏