修改直接对整块打标记,两边暴力。
查询需要保证每个整块有序,所以在修改时排序就好啦
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 1000005
using namespace std;
int n,m,nn,be[N],lazy[1005],ans;
int a[N],b[N];
void work(int x)
{
int l=(x-1)*nn+1,r=min(n,x*nn);
for(int i=l;i<=r;i++)
b[i]=a[i];
sort(b+l,b+r+1);
}
int main()
{
scanf("%d%d",&n,&m);
nn=(int)sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
be[i]=(i-1)/nn+1;
}
int tot=be[n];
for(int i=1;i<=tot;i++)work(i);
char ch; int l,r,c,num;
while(m--)
{
ch=getchar();
while(ch!='A'&&ch!='M') ch=getchar();
scanf("%d%d%d",&l,&r,&c);
if(ch=='M'){
if(be[l]==be[r]){
for(int i=l;i<=r;i++) a[i]+=c;
work(be[l]);
continue;
}
for(int i=be[l]+1;i<be[r];i++) lazy[i]+=c;
for(int i=l;i<=be[l]*nn;i++) a[i]+=c;
for(int i=(be[r]-1)*nn+1;i<=r;i++) a[i]+=c;
work(be[l]); work(be[r]);
}
else{
int x; ans=0;
if(be[l]==be[r]){
for(int i=l;i<=r;i++)
if(a[i]+lazy[be[i]]>=c)
ans++;
printf("%d\n",ans);
continue;
}
for(int i=be[l]+1;i<be[r];i++){
x=c-lazy[i];
int L=(i-1)*nn+1,R=min(n,i*nn);
num=lower_bound(b+L,b+R+1,x)-b;
ans+=R-num+1;
}
for(int i=l;i<=be[l]*nn;i++)
if(a[i]+lazy[be[i]]>=c)
ans++;
for(int i=(be[r]-1)*nn+1;i<=r;i++)
if(a[i]+lazy[be[i]]>=c)
ans++;
printf("%d\n",ans);
}
}
return 0;
}
bzoj 3343 教主的魔法 分块的更多相关文章
-
BZOJ 3343: 教主的魔法(分块+二分查找)
BZOJ 3343: 教主的魔法(分块+二分查找) 3343: 教主的魔法 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1172 Solved: ...
-
BZOJ 3343: 教主的魔法 [分块]【学习笔记】
3343: 教主的魔法 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1172 Solved: 526[Submit][Status][Discus ...
-
Bzoj 3343: 教主的魔法(分块+二分答案)
3343: 教主的魔法 Time Limit: 10 Sec Memory Limit: 256 MB Description 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息 ...
-
Bzoj 3343: 教主的魔法 分块,二分
3343: 教主的魔法 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 821 Solved: 364[Submit][Status][Discuss ...
-
BZOJ——3343: 教主的魔法 || 洛谷—— P2801 教主的魔法
http://www.lydsy.com/JudgeOnline/problem.php?id=3343 || https://www.luogu.org/problem/show?pid=280 ...
-
BZOJ 3343教主的魔法
Description 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的 ...
-
bzoj 3343: 教主的魔法
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 924 Solved: 402[Submit][Status][Discuss] Descriptio ...
-
BZOJ 3343 教主的魔法(分块)
题意: 有一个1e6的数组,t次操作:将[l,r]内的值增加w,或者查询[l,r]内的值大于等于add的 思路: 分块,块大小为sqrt(n),每次只需要暴力头尾两块,中间的整块打标记, 对于查询查操 ...
-
[bzoj] 3343 教主的魔法 || 带修改分块
原题 长度为n的序列,有两种操作: 1.[l,r]区间每个数+w 2.询问[l,r]区间有多少个数>c 记录lazy数组即可. #include<cstdio> #include&l ...
随机推荐
-
[转]maven创建自定义的archetype
创建自己的archetype一般有两种方式,比较简单的就是create from project 1.首先使用eclipse创建一个新的maven project,然后把配置好的一些公用的东西放到相应 ...
-
Spring整合JUnit4测试
@RunWith(SpringJUnit4ClassRunner.class) @ContextConfiguration(locations = {"classpath:spring/ap ...
-
struts1、ajax、jquery、json简单实例
1.页面ajax代码,使用$.ajax,获得json对象后each $.ajax({ type:"GET", url:ctx + "/uploadImg.do" ...
-
Javascript 原型和原型链
先来了解一下Javascript中的原型:”原型也是一个对象,原型可以用来实现继承...“ 对于 原型,构造函数,以及实例之间的关系:“每个(构造)函数都有一个原型属性,原型对象都包含一个指向构造函数 ...
-
磁盘文件I/O,SSD结构,局部性原理 笔记
磁盘文件I/O过程 进程向内核发起read scene.dat请求: 内核根据inode获取对应该进程的address space,在address space查找page_cache,如果没有找到, ...
-
pytorch模型部署在MacOS或者IOS
pytorch训练出.pth模型如何在MacOS上或者IOS部署,这是个问题. 然而我们有了onnx,同样我们也有了coreML. ONNX: onnx是一种针对机器学习设计的开放式文件格式,用来存储 ...
-
SDL OPENGL 在linux ubuntu示例
gl画纹理texture /* * SDL OpenGL Tutorial. * (c) Michael Vance, 2000 * briareos@lokigames.com * * Distri ...
-
Spring Cloud之注册中心搭建
一.注册中心服务端搭建 1)引入相关Maven坐标 <dependency> <groupId>org.springframework.cloud</groupId> ...
-
【转】mybatis如何防止sql注入
sql注入大家都不陌生,是一种常见的攻击方式,攻击者在界面的表单信息或url上输入一些奇怪的sql片段,例如“or ‘1’=’1’”这样的语句,有可能入侵参数校验不足的应用程序.所以在我们的应用中需要 ...
-
linux 下安装jdk环境安装
一.创建jdk安装目录mkdir /usr/local/java 二.将jdk解压到安装目录中,直接到java目录中,如果不是处理下不要有子目录 tar -zxvf jdk-8u91-linux-x6 ...