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(logn)$ 级别的时间复杂度内查询，注意需要判断一下查找内容是否正确。

//...
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;
}