首页 > 其他分享 >题解(教主的魔法)P2801

题解(教主的魔法)P2801

时间：2023-05-25 11:35:13浏览次数：62  
标签：ch int 题解 P2801 魔法 read 教主 身高 register

题目

教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 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$ 行每行有一个操作：

  1. 若第一个字母为 M，则紧接着有三个数字 $L, R, W$。表示对闭区间 $[L, R]$ 内所有英雄的身高加上 $W$。

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

输出格式

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

样例 #1

样例输入 #1

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

样例输出 #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≤106$，$Q≤3000$，$1≤W≤1000$，$1≤C≤109$。

$\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结果昨天想买已经过期了呜呜呜

标签：ch,int,题解,P2801,魔法,read,教主,身高,register
From： https://www.cnblogs.com/phigros/p/17430642.html

相关文章

  • 常见问题解决 --- 安卓中一个类中的匿名类和另一个类中的匿名类无法相互传值
      runOnUiThread(newRunnable(){@Overridepublicvoidrun(){//在UI线程中执行的主代码textView.setText("Hello,world!");}});将上面更新主ui放置在匿名内部类的回调方法里即可传值给属性。......
  • 《花雕学AI》语言+想象+人工智能=图像魔法：微软 Bing 图像魔法师的功能、价值和评测
    你有没有想过，如果你能够用语言来创造图像，那该有多么神奇和有趣？你有没有想过，如果你能够看到你想象中的图像，那该有多么震撼和美妙？现在，这一切都可以实现了，因为微软Bing图像魔法师来了！微软Bing图像魔法师是一款能够根据用户的描述生成图像的人工智能产品，它可以让你的语言变成视觉，......
  • AtCoder Beginner Contest 302 H. Ball Collector 题解
    AtCoderBeginnerContest302H.BallCollector题意跳过。可以视作将\(a_i,b_i\)之间连了一条边，然后\(a_i,b_i\)之间只能选一个等价于对于一条边只能选择其一个端点。那么对于只包含树的联通块而言，如果都选择儿子节点，那么会有一个根节点无法被选择上；而对于包含至少一个......
  • NOIP2014普及组试题题解
    1.珠心算测验代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=2e4+39+7;intmp[N],n,a[N],ans=0;intmain(){ cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=1;i<=n;i++){ for(intj=1;j<=n;j++)......
  • 常见问题解决 --- Failed to build android app at server - class file for android.
    问题原因  这个错误主要是LocalBroadcastManager这个类被弃用了，而在库或者sdk中使用到了。解决办法build.gradle文件中添加implementation'com.android.support:support-v4:30.4.1'gradle.properties添加android.enableJetifier=true......
  • abc260_f Find 4-cycle 题解
    Find4-cycle题意有一个\(s+t\)个点\(m\)条边的简单无向图\(G\)。点标号为\(1\cdotss+t\)，边标号为\(1\cdotsm\)。第\(i\)条边连接点\(u_i\)和\(v_i\)。如果\(G\)中包含一个大小为\(4\)的简单环，选择任意一个并按任意顺序输出环上的\(4\)个点。若不存......
  • abc260_e At Least One 题解
    AtLeastOne题意给定一个整数\(m\)和\(n\)对数\((a_i,b_i)\)，我们定义一个\(f(x)\)函数表示满足以下要求的整数序列数量：整数序列为\((1,2,3\cdotsm)\)的一个子段且序列长度为\(x\)。对于\(1\leqslanti\leqslantn\)，满足\(a_i\)或者\(b_i\)在整数序列......
  • Element 表格固定列横向滚动条无法拖动的问题解决
    在Element-UI中，当对表格列进行固定后，底部的横向滚动条就无法拖动了，主要的问题就是固定区域盖住了横向滚动条。方案一：修改el-table__body-wrapper样式的层级，随便设个层级就可::v-deep.el-table__body-wrapper{z-index:2}//加了fixed之后失效::v-deep.el-table__fi......
  • abc273_e Notebook 题解
    Notebook题意有\(q\)次操作。现在你有一个空序列\(a\)和一本\(10^9\)页的笔记本，每页纸上都有一个空序列。每次操作是以下四种中的一种：ADDx，表示在\(a\)的末尾插入一个整数\(x\)。DELETE，表示删除\(a\)的末尾的一个数，如果\(a\)序列为空则什么也不干。SAVEy，表......
  • Game on Paper 题解
    题目传送门一道模拟题。如果每涂一个格子就判断整个矩阵，那时间复杂度显然会炸。我们每涂一个格子，影响的应该只是以这个格子为中心的\(3\times3\)矩阵，判断以这些点为中心的话会不会涂出\(3\times3\)的矩阵即可。Code#include<bits/stdc++.h>#definelllonglong#d......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99