bzoj 3343 教主的魔法 分块

时间:2022-09-10 07:47:08

修改直接对整块打标记,两边暴力。

查询需要保证每个整块有序,所以在修改时排序就好啦

#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 教主的魔法 分块的更多相关文章

  1. BZOJ 3343&colon; 教主的魔法&lpar;分块&plus;二分查找&rpar;

    BZOJ 3343: 教主的魔法(分块+二分查找) 3343: 教主的魔法 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1172  Solved:  ...

  2. BZOJ 3343&colon; 教主的魔法 &lbrack;分块&rsqb;【学习笔记】

    3343: 教主的魔法 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1172  Solved: 526[Submit][Status][Discus ...

  3. Bzoj 3343&colon; 教主的魔法&lpar;分块&plus;二分答案&rpar;

    3343: 教主的魔法 Time Limit: 10 Sec Memory Limit: 256 MB Description 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息 ...

  4. Bzoj 3343&colon; 教主的魔法 分块&comma;二分

    3343: 教主的魔法 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 821  Solved: 364[Submit][Status][Discuss ...

  5. BZOJ——3343&colon; 教主的魔法 &vert;&vert; 洛谷—— P2801 教主的魔法

    http://www.lydsy.com/JudgeOnline/problem.php?id=3343  ||  https://www.luogu.org/problem/show?pid=280 ...

  6. BZOJ 3343教主的魔法

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

  7. bzoj 3343&colon; 教主的魔法

    Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 924  Solved: 402[Submit][Status][Discuss] Descriptio ...

  8. BZOJ 3343 教主的魔法(分块)

    题意: 有一个1e6的数组,t次操作:将[l,r]内的值增加w,或者查询[l,r]内的值大于等于add的 思路: 分块,块大小为sqrt(n),每次只需要暴力头尾两块,中间的整块打标记, 对于查询查操 ...

  9. &lbrack;bzoj&rsqb; 3343 教主的魔法 &vert;&vert; 带修改分块

    原题 长度为n的序列,有两种操作: 1.[l,r]区间每个数+w 2.询问[l,r]区间有多少个数>c 记录lazy数组即可. #include<cstdio> #include&l ...

随机推荐

  1. &lbrack;转&rsqb;maven创建自定义的archetype

    创建自己的archetype一般有两种方式,比较简单的就是create from project 1.首先使用eclipse创建一个新的maven project,然后把配置好的一些公用的东西放到相应 ...

  2. Spring整合JUnit4测试

    @RunWith(SpringJUnit4ClassRunner.class) @ContextConfiguration(locations = {"classpath:spring/ap ...

  3. struts1、ajax、jquery、json简单实例

    1.页面ajax代码,使用$.ajax,获得json对象后each $.ajax({ type:"GET", url:ctx + "/uploadImg.do" ...

  4. Javascript 原型和原型链

    先来了解一下Javascript中的原型:”原型也是一个对象,原型可以用来实现继承...“ 对于 原型,构造函数,以及实例之间的关系:“每个(构造)函数都有一个原型属性,原型对象都包含一个指向构造函数 ...

  5. 磁盘文件I&sol;O,SSD结构,局部性原理 笔记

    磁盘文件I/O过程 进程向内核发起read scene.dat请求: 内核根据inode获取对应该进程的address space,在address space查找page_cache,如果没有找到, ...

  6. pytorch模型部署在MacOS或者IOS

    pytorch训练出.pth模型如何在MacOS上或者IOS部署,这是个问题. 然而我们有了onnx,同样我们也有了coreML. ONNX: onnx是一种针对机器学习设计的开放式文件格式,用来存储 ...

  7. SDL OPENGL 在linux ubuntu示例

    gl画纹理texture /* * SDL OpenGL Tutorial. * (c) Michael Vance, 2000 * briareos@lokigames.com * * Distri ...

  8. Spring Cloud之注册中心搭建

    一.注册中心服务端搭建 1)引入相关Maven坐标 <dependency> <groupId>org.springframework.cloud</groupId&gt ...

  9. 【转】mybatis如何防止sql注入

    sql注入大家都不陌生,是一种常见的攻击方式,攻击者在界面的表单信息或url上输入一些奇怪的sql片段,例如“or ‘1’=’1’”这样的语句,有可能入侵参数校验不足的应用程序.所以在我们的应用中需要 ...

  10. linux 下安装jdk环境安装

    一.创建jdk安装目录mkdir /usr/local/java 二.将jdk解压到安装目录中,直接到java目录中,如果不是处理下不要有子目录 tar -zxvf jdk-8u91-linux-x6 ...