luogu P2801 教主的魔法

luogu P2801 教主的魔法

题目:P2801 教主的魔法

题目描述

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、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
2
3
4
5
6
7
8
9
5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4
输出 #1
1
2
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≤1000000,Q≤3000,1≤W≤1000,1≤C≤1,000,000,000。


分析

刚入门分块,以此作为练习。

初始化:将数组拆为 $\sqrt{n}$ 个区间,查询时,如果区间覆盖了一个块,则直接输出块的答案。显然这样做最多只有两个块需要单独操作。

查询:本题不是查询区间和,为方便查找大于 $c$ 的数目,再用另外一个数组 $t[]$ 对区间进行排序,查询时利用二分查找即可。

区间增加:对于一整个区间被覆盖的情况,用 $dlt[]$ 数组将整个区间加上 $w$。边界处暴力增加。

时间复杂度:$O(Q\sqrt{N}\log N)$。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
namespace iNx{
const int N = 1e6 + 7 ;
const int SQN = 1e3 + 7 ;
int a[N],t[N],st[SQN],ed[SQN],belong[N],size[SQN],dlt[SQN];
int n,q;
void SORT(int x){
for(int i=st[x];i<=ed[x];i++) t[i]=a[i];
sort(t+st[x],t+ed[x]+1);
}
void init(){
int num=sqrt(n);
int i,j;
for(i=0;i<num;i++){
st[i+1]=n/num * i + 1;
ed[i+1]=n/num * (i+1);
}
ed[num]=n;
for(i=1;i<=num;i++){
SORT(i);
for(j=st[i];j<=ed[i];j++) belong[j]=i;
size[i]=ed[i]-st[i]+1;
}
}
void modify(int l,int r,int c){
int x=belong[l],y=belong[r],i;
if(x==y){
for(i=l;i<=r;i++)
a[i]+=c;
SORT(x);
return ;
}
for(i=l;i<=ed[x];i++) a[i]+=c;
for(i=st[y];i<=r;i++) a[i]+=c;
for(i=x+1;i<y;i++) dlt[i]+=c;
SORT(x);
SORT(y);
}
int BF(int l,int r,int c,int x){
int ans=r+1,L=l,R=r,mid;
while(L<=R){
mid=(L+R)>>1;
if(t[mid]+dlt[x]>=c) ans=mid,R=mid-1;
else L=mid+1;
}
return (r-ans+1);
}
int answer(int l,int r,int c){
int i,ans=0;
int x=belong[l],y=belong[r];
if(x==y) return BF(l,r,c,x);
ans+=BF(l,ed[x],c,x);
ans+=BF(st[y],r,c,y);
for(i=x+1;i<y;i++) ans+=BF(st[i],ed[i],c,i);
return ans;
}
void work(){
scanf("%d%d",&n,&q);
int i,l,r,c;
char ch;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
init();
for(i=1;i<=q;i++){
ch=cin.peek();
while(ch==' '||ch=='\n'||ch=='\r'){
cin.get();
ch=cin.peek();
}
ch=cin.get();
if(ch=='A'){
scanf("%d%d%d",&l,&r,&c);
printf("%d\n",answer(l,r,c));
}
else if(ch=='M'){
scanf("%d%d%d",&l,&r,&c);
modify(l,r,c);
}
}
}
}
int main(){
iNx::work();
return 0;
}
#

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×