LOJ #6279 数列分块入门3 题解

本文主要是介绍LOJ #6279 数列分块入门3 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\text{Part \# -1. 前言}$

重要的事情说三遍
先初始化，后输入！
先初始化，后输入！
先初始化，后输入！

蒟蒻就是这样错的（

$\text{Part \# 0.} 题目$

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）。

第一行输入一个数字 $n$ 。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $\mathrm{opt}、l、r、c$ ，以空格隔开。

若 $\mathrm{opt} = 0$ ，表示将位于 $[l, r]$ 的之间的数字都加 $c$ 。

若 $\mathrm{opt} = 1$ ，表示询问 $[l, r]$ 中 $c$ 的前驱的值（不存在则输出 -1）。

$\text{Part \# 1. } 解法$

这道题目是一个很显然的区间查询，区间加。

区间加操作的话和分块和上道题一样，在查询的时候需要满足一个块内的数据有序，所以每一次对散块进行更改的时候都要重新排序一遍，如下：

vector<int> v[maxn];
//...
inline void update(int x)
{v[x].clear();forz(i,st[x],ed[x]) v[x].push_back(a[i]);sort(v[x].begin(),v[x].end());
}
//...
if(block[l]==block[r]) 
{forz(i,l,r) a[i]+=c;update(block[l]);
}
else
{forz(i,l,ed[block[l]]) a[i]+=c;update(block[l]);forz(i,block[l]+1,block[r]-1) fk[i]+=c;forz(i,st[block[r]],r) a[i]+=c;update(block[r]);
}
//...

区间查询，同样分为整块和散块来查询。

对于散块，枚举每一个数即可，注意加上这个数所在的块的标记。
对于整块，可以用 lower_bound 在 $O (l o g n)$ 级别的时间复杂度内查询，注意需要判断一下查找内容是否正确。

//...
int ans=-1;
if(block[l]==block[r])
{forz(i,l,r) if(a[i]+fk[block[i]]<c) ans=max(ans,a[i]+fk[block[i]]);
}
else
{forz(i,l,ed[block[l]]) if(a[i]+fk[block[i]]<c) ans=max(ans,a[i]+fk[block[i]]);forz(i,block[l]+1,block[r]-1){int f=c-fk[i];auto it=lower_bound(v[i].begin(),v[i].end(),f);if(it==v[i].begin()) continue;ans=max(ans,*--it+fk[i]);}forz(i,st[block[r]],r) if(a[i]+fk[block[i]]<c) ans=max(ans,a[i]+fk[block[i]]);
}
write(ans);
putchar('\n');
//...

注意 if 的优先级的问题

$\text{Part \# 2. Code}$

完整 code 如下：

/*
1. sqrt(m*2/3)
*/
#include <bits/stdc++.h>using namespace std;#define int long long
#define fi first
#define se second
#define rg register
#define il inline
#define forz(i,a,b) for(register int i((a));i<=(b);++i)
#define forn(i,a,b) for(register int i((a));i>=(b);--i)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}const int maxn=1e5+100;
const int mod=993244853;
const int inf=9e18;int a[maxn];
int lenn[maxn];
int st[maxn],ed[maxn];
int block[maxn],fk[maxn];
int num,len;vector<int> v[maxn];inline void init(int n)
{len=sqrt(n);num=n%len?n/len+1:n/len;forz(i,1,num){st[i]=(i-1)*len+1;ed[i]=min(i*len,n);lenn[i]=ed[i]-st[i]+1;}forz(i,1,num) forz(j,st[i],ed[i]) block[j]=i;
}inline void update(int x)
{v[x].clear();forz(i,st[x],ed[x]) v[x].push_back(a[i]);sort(v[x].begin(),v[x].end());
}inline void solve()
{int n=read();init(n);forz(i,1,n) a[i]=read(),v[block[i]].push_back(a[i]);forz(i,1,num) sort(v[i].begin(),v[i].end());
//	n--;while (n--){int op=read(),l=read(),r=read(),c=read();if(op==0){if(block[l]==block[r]) {forz(i,l,r) a[i]+=c;update(block[l]);}else{forz(i,l,ed[block[l]]) a[i]+=c;update(block[l]);forz(i,block[l]+1,block[r]-1) fk[i]+=c;forz(i,st[block[r]],r) a[i]+=c;update(block[r]);}}else{int ans=-1;if(block[l]==block[r]){forz(i,l,r) if(a[i]+fk[block[i]]<c) ans=max(ans,a[i]+fk[block[i]]);}else{forz(i,l,ed[block[l]]) if(a[i]+fk[block[i]]<c) ans=max(ans,a[i]+fk[block[i]]);forz(i,block[l]+1,block[r]-1){int f=c-fk[i];auto it=lower_bound(v[i].begin(),v[i].end(),f);if(it==v[i].begin()) continue;ans=max(ans,*--it+fk[i]);}forz(i,st[block[r]],r) if(a[i]+fk[block[i]]<c) ans=max(ans,a[i]+fk[block[i]]);}write(ans);putchar('\n');}}putchar('\n');
}signed main()
{
//    IOS;int _=1;while (_--) solve();return 0;
}