题目大意:维护 N 个数组成的序列,支持两种操作:区间加、区间查询某个值的前驱(小于该值的最大值,若无前驱,输出-1)。
题解1:可以像分块2一样,维护每个块内元素的一个有序序列,每次查询时二分查找即可。
代码如下
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int maxn=1e5+10;
const int maxb=1010;
const int inf=0x3f3f3f3f;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
int n,m,a[maxn];
struct node{
int l,r,add;
}b[maxb];
int tot,bl[maxn];vector<int> v[maxb];
void make_block(){
tot=sqrt(n);
for(int i=1;i<=tot;i++)b[i].l=b[i-1].r+1,b[i].r=i*tot;
if(b[tot].r<n)++tot,b[tot].l=b[tot-1].r+1,b[tot].r=n;
for(int i=1;i<=tot;i++){
for(int j=b[i].l;j<=b[i].r;j++)bl[j]=i,v[i].pb(a[j]);
sort(all(v[i]));
}
}
inline void rebuild(int p){
v[p].clear();
for(int i=b[p].l;i<=b[p].r;i++)v[p].pb(a[i]);
sort(all(v[p]));
}
void modify(int l,int r,int c){
int x=bl[l],y=bl[r];
if(x==y){
for(int i=l;i<=r;i++)a[i]+=c;
rebuild(x);
}else{
for(int i=x+1;i<=y-1;i++)b[i].add+=c;
for(int i=l;i<=b[x].r;i++)a[i]+=c;
for(int i=b[y].l;i<=r;i++)a[i]+=c;
rebuild(x),rebuild(y);
}
}
int query(int l,int r,int c){
int x=bl[l],y=bl[r],res=-inf;
if(x==y){
for(int i=l;i<=r;i++){
int u=a[i]+b[x].add;
if(u<c)res=max(res,u);
}
}else{
for(int i=x+1;i<=y-1;i++){
auto u=lower_bound(all(v[i]),c-b[i].add);
if(u!=v[i].begin())res=max(res,*(--u)+b[i].add);
}
for(int i=l;i<=b[x].r;i++){
int u=a[i]+b[x].add;
if(u<c)res=max(res,u);
}
for(int i=b[y].l;i<=r;i++){
int u=a[i]+b[y].add;
if(u<c)res=max(res,u);
}
}
return res==-inf?-1:res;
}
int main(){
n=m=read();
for(int i=1;i<=n;i++)a[i]=read();
make_block();
while(m--){
int opt=read(),l=read(),r=read(),c=read();
if(opt==0)modify(l,r,c);
else if(opt==1)printf("%d\n",query(l,r,c));
}
return 0;
}
题解2:可以在每个块内维护一个平衡树,支持插入删除操作,且平衡树具有自动排序功能,每次插入时将原来的值删除,并插入修改后的数值。不过常数较大,比第一种方法慢了一倍。QAQ
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
int n,q,a[maxn],pos[maxn],tot;
struct node{
int l,r,add;
set<int> st;
}b[1000];
void make_block(){
tot=(int)sqrt(n);
for(int i=1;i<=tot;i++)b[i].l=(i-1)*tot+1,b[i].r=i*tot;
if(b[tot].r<n)++tot,b[tot].l=b[tot-1].r+1,b[tot].r=n;
for(int i=1;i<=tot;i++)
for(int j=b[i].l;j<=b[i].r;j++)
pos[j]=i,b[i].st.insert(a[j]);
}
void read_and_parse(){
n=read(),q=n;
for(int i=1;i<=n;i++)a[i]=read();
make_block();
}
void modify(int l,int r,int val){
int x=pos[l],y=pos[r];
if(x==y){
for(int i=l;i<=r;i++)b[x].st.erase(a[i]),a[i]+=val,b[x].st.insert(a[i]);
}else{
for(int i=x+1;i<=y-1;i++)b[i].add+=val;
for(int i=l;i<=b[x].r;i++)b[x].st.erase(a[i]),a[i]+=val,b[x].st.insert(a[i]);
for(int i=b[y].l;i<=r;i++)b[y].st.erase(a[i]),a[i]+=val,b[y].st.insert(a[i]);
}
}
int query(int l,int r,int val){
int x=pos[l],y=pos[r],ans=-inf;
if(x==y){
for(int i=l;i<=r;i++){
int v=a[i]+b[x].add;
if(v<val&&v>ans)ans=v;
}
}else{
for(int i=x+1;i<=y-1;i++){
set<int>::iterator it=b[i].st.lower_bound(val-b[i].add);
if(it==b[i].st.begin())continue;
ans=max(ans,*--it+b[i].add);
}
for(int i=l;i<=b[x].r;i++){
int v=a[i]+b[x].add;
if(v<val&&v>ans)ans=v;
}
for(int i=b[y].l;i<=r;i++){
int v=a[i]+b[y].add;
if(v<val&&v>ans)ans=v;
}
}
return ans==-inf?-1:ans;
}
void solve(){
int opt,l,r,val;
while(q--){
opt=read(),l=read(),r=read(),val=read();
if(opt==0)modify(l,r,val);
else if(opt==1)printf("%d\n",query(l,r,val));
}
}
int main(){
read_and_parse();
solve();
return 0;
}
【LOJ#6279】数列分块3的更多相关文章
-
LOJ #6279. 数列分块入门 3-分块(区间加法、查询区间内小于某个值x的前驱(比其小的最大元素))
#6279. 数列分块入门 3 内存限制:256 MiB时间限制:1500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计测试数据讨论 3 题目描述 给 ...
-
LOJ 6279 数列分块入门3
嗯... 题目链接:https://loj.ac/problem/6279 这道题在分块的基础上用vc数组记录,然后最后分三块,两边暴力枚举找前驱,中间lower_bound找前驱. AC代码: #i ...
-
LOJ#6279. 数列分块入门 3
区间加值还是正常的操作,查找前驱的时候用lower_bound查找,然后范围所在位置的值 #include<map> #include<set> #include<cti ...
-
LOJ——#6277. 数列分块入门 1
~~推荐播客~~ 「分块」数列分块入门1 – 9 by hzwer 浅谈基础根号算法——分块 博主蒟蒻,有缘人可直接观摩以上大佬的博客... #6277. 数列分块入门 1 题目大意: 给出一个长为 ...
-
loj 6278 6279 数列分块入门 2 3
参考:「分块」数列分块入门1 – 9 by hzwer 2 Description 给出一个长为\(n\)的数列,以及\(n\)个操作,操作涉及区间加法,询问区间内小于某个值\(x\)的元素个数. 思 ...
-
LOJ 6277-6280 数列分块入门 1-4
数列分块是莫队分块的前置技能,练习一下 1.loj6277 给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值. 直接分块+tag即可 #include <bits/stdc++.h ...
-
LOJ #6285. 数列分块入门 9-分块(查询区间的最小众数)
#6285. 数列分块入门 9 内存限制:256 MiB时间限制:1500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计测试数据讨论 2 题目描述 给 ...
-
LOJ #6284. 数列分块入门 8-分块(区间查询等于一个数c的元素,并将这个区间的所有元素改为c)
#6284. 数列分块入门 8 内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计测试数据讨论 2 题目描述 给出 ...
-
LOJ #6283. 数列分块入门 7-分块(区间乘法、区间加法、单点查询)
#6283. 数列分块入门 7 内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计测试数据讨论 2 题目描述 给出 ...
-
LOJ #6282. 数列分块入门 6-分块(单点插入、单点查询、数据随机生成)
#6282. 数列分块入门 6 内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计测试数据讨论 1 题目描述 给出 ...
随机推荐
-
[platform]Device和Driver注册顺序
1. 设备和驱动注册,无论谁先谁后,都可以通过查询总线进行匹配 设备挂接到总线上时,与总线上的所有驱动进行匹配(用bus_type.match进行匹配),如果匹配成功,则调用bus_type.prob ...
-
在Salesforce中实现对Object的增删改查操作
1): Insert Statement http://www.salesforce.com/us/developer/docs/apexcode/index_Left.htm#CSHID=ap ...
-
SAP增强总结-第二代增强(SMOD、CMOD)【转载】
第二代增强比第二代增强安全性提高了很多,第一代增强毕竟是在原标准程序中修改,大部分传递参数都可以直接使用,第二代增强做了一些封装,对用户可以修改的参数做了限制. 1.增强点查找方法 首先根据事物码找到 ...
- MyEclipse build path修改问题
-
unity3d shader之实时室外光线散射(大气散射)渲染
散射需要:吸收,内散射,外散射分为瑞利散射Rayleigh Scattering和米氏散射 Mie Scattering 后面会详细讲解 大气中散射由多种原因产生,微粒,尘埃,水蒸气等等 阳光由于散 ...
-
iOS远程消息推送自我整理版
@interface AppDelegate () <UIApplicationDelegate> @end @implementation AppDelegate - (BOOL)app ...
-
【转】SqlLite .Net 4.0 System.IO.FileLoadException”类型的未经处理的异常出现在XXX
原文地址:http://www.csharpcity.com/2010/sqlite-ado-net-c-4-0/ ---------------------- 解决方法: Paste the fol ...
-
java-关于java_home配置,classpath配置和javac,java命令,javac编译器,和java虚拟机之间的关系
在每个人学习java的第一步,都是安装jdk ,jre,配置java_home,classpath,path. 为什么要做这些?在阅读java-core的时候,看到了原理,p141. 一 关于类的共享 ...
-
C# 如何获取SQL Server 中指定数据表的所有字段名和字段类型
如何获取指定数据表的所有字段名和字段类型.SqlConnection.GetSchema方法有2个重载形式,获取指定数据表的所有字段名和字段类型的秘密就在GetSchema (String, Stri ...
-
C语言进阶--DAY3
主要讲解数组和指针有关问题 1. 数组名的本质是一个常量指针 2. 内存编址的最小单位是字节,对于变量来说,一个变量可以取1.2.4.8等字节,对变量取地址来说,取的是低位字节的地址,在32位机中其对 ...