刷题总结——教主的魔法(bzoj3343)
2024-08-30 12:12:29
题目:
Description
教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)
CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。
WD巨懒,于是他把这个回答的任务交给了你。
Input
第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。
Output
对每个“A”询问输出一行,仅含一个整数,表示闭区间 [L, R] 内身高大于等于C的英雄数。
Sample Input
5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4
Sample Output
2
3
3
HINT
【输入输出样例说明】
原先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。
Source
题解:
引用hwzer题解,%%%%%%%%%%:
就是每一块的个数为根号n
修改:
对于一整块,直接打add标记
头尾俩块不完整的进行暴力修改重构
查询
每一块内排序,在第i块内二分查找大等于C-add[i]的数字
头尾俩块暴力查询
自己再说些吧··以前写的都是空间为n√n的,这道题肯定不行,新学了一种利用二分节约空间的分块(虽然时间复杂度为n√n logn)
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+;
const int M=1e3+;
int n,id[N],b[N],a[N],tots,s,Right[M],Left[M],add[M],m;
bool jud[N];
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar())
f=(f<<)+(f<<)+c-'';
return f;
}
inline void update(int now)
{
for(int i=Left[now];i<=Right[now];i++) b[i]=a[i];
sort(b+Left[now],b+Right[now]+);
}
inline int find(int x,int w)
{
int l=Left[x],r=Right[x],ans=;
while(l<=r)
{
int mid=(l+r)/;
if(b[mid]>=w) ans=mid,r=mid-;
else l=mid+;
}
if(!ans) return ;
else return Right[x]-ans+;
}
inline void modify(int l,int r,int c)
{
if(r-l+<*s)
{
for(int i=l;i<=r;i++)
a[i]+=c;
update(id[l]),update(id[r]);
}
else
{
int lefts,rights;
if(l%s==) lefts=id[l];
else lefts=id[l]+;
if(jud[r]) rights=id[r];
else rights=id[r]-;
for(int i=l;i<Left[lefts];i++) a[i]+=c;
for(int i=Right[rights]+;i<=r;i++) a[i]+=c;
for(int i=lefts;i<=rights;i++) add[i]+=c;
update(id[l]),update(id[r]);
}
return;
}
inline int getans(int l,int r,int c)
{
int ans=;
if(r-l+<*s)
{
for(int i=l;i<=r;i++)
if(a[i]+add[id[i]]>=c) ans++;
return ans;
}
else
{
int lefts,rights;
if(l%==) lefts=id[l];
else lefts=id[l]+;
if(jud[r]) rights=id[r];
else rights=id[r]-;
for(int i=l;i<Left[lefts];i++)
if(a[i]+add[id[i]]>=c) ans++;
for(int i=Right[rights]+;i<=r;i++)
if(a[i]+add[id[i]]>=c) ans++;
for(int i=lefts;i<=rights;i++)
ans+=find(i,c-add[i]);
return ans;
}
} int main()
{
//freopen("a.in","r",stdin);
n=R(),m=R();s=(int)sqrt(n);
for(int i=;i<=n;i++) a[i]=R();
for(int i=;i<=n;i++)
{
if(i%s==) id[i]=++tots,Left[tots]=i;
else if(i%s==) id[i]=tots,Right[tots]=i,jud[i]=true;
else id[i]=tots;
}
Right[tots]=n,jud[n]=true;
for(int i=;i<=tots;i++) update(i);
int l,r,w;
char s[];
while(m--)
{
scanf("%s",s);
l=R(),r=R(),w=R();
if(s[]=='M')
modify(l,r,w);
else
printf("%d\n",getans(l,r,w));
}
return ;
}
最新文章
- PyChram中同目录下import引包报错的解决办法?
- ASP.NET 导出gridview中的数据到Excel表中,并对指定单元格换行操作
- loj 1030概率dp
- linux或者windows下的文件拷贝
- 文字垂直居中,水平居中 a标签水平居中只要给他的父级设置text-align=center
- 带弹出列表的EditText
- UVaLive 6608 Cabin Baggage (水题)
- hadoop深入研究:(十八)——Avro schema兼容
- 1207.1——C语言 函数
- 初识JAVA,对servlet的理解
- GlusterFS源代码解析 —— GlusterFS 简单介绍
- String类的替换方法(9)
- 我的three.js学习记录(二)
- git向码云上传代码总结
- 第k小的元素
- .Net Core ----通过XUnit进行接口单元测试(带请求头及参数)并用output输出结果
- Hibernate根据实体类自动创建表
- 写在开始前---ajax中的会话过期与重新登录
- TypeError: Fetch argument None has invalid type <;type &#39;NoneType&#39;>;
- JS弹框