分块例题3

题面描述

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

输入格式

第一行输入一个数字 n

第二行输入 n 个数字，第 i 个数字为a[i]，以空格隔开

接下来输入 n 行询问，每行输入四个数字 opt, l，r，c, 以空格隔开

若 opt = 0，表示将 [l,r] 的之间的数都加 c

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

输出格式

对于每次询问，输出一行一个数字表示答案

样例

我们可以把满足小于c的数全部找出了，取个最大，但是如果这样的话分块就没有意义了，我们可以把块里的数据排序，直接lower_bound一下找到那个位置，直接和暴力的出的值比较就好，这样我们使我们的分块有了意义，并不是纯暴力，是个优化的暴力。总的来说，就是在分块的时候，把每块拍一下序就好了，如果修改，清空，重新赋值，再次排序即可，这个可以用STL当中的vector去实现就好了。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int pos[510010],a[510010],l1[510010],r1[510010],add[510010],t;
vector<int>p[510010];
void qing(int x)
{
	p[x].clear();
	for(int i=l1[x];i<=r1[x];i++)
	p[x].push_back(a[i]);
	sort(p[x].begin(),p[x].end());
}
void ch(int l,int r,int d)
{
	//cout<<a[1]<<"                  "<<endl;
	for(int i=1;i<=t;i++)
	{
		if(l>r1[i]||r<l1[i])
		continue;
		if(l<=l1[i]&&r>=r1[i])
		add[i]+=d;
		else
		{
			for(int j=max(l,l1[i]);j<=min(r,r1[i]);j++)
			{
				a[j]+=d; 
			}
			qing(i);
		}
	}
 } 
 int ask(int l,int r,int c)
 {
 	int kl=-1,pw;
 	for(int i=1;i<=t;i++)
	{
		if(l>r1[i]||r<l1[i])
		continue;
		if(l<=l1[i]&&r>=r1[i])
		{
			pw=lower_bound(p[i].begin(),p[i].end(),c-add[i])-p[i].begin();
			if(pw!=0)
			kl=max(kl,p[i][pw-1]+add[i]);
		}
		else
		{
			for(int j=max(l,l1[i]);j<=min(r,r1[i]);j++)
			{
				if(a[j]+add[i]<c)
				kl=max(kl,a[j]+add[i]);
			}
		}
	}
	return kl;
 }
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	t=sqrt(n);
	for(int i=1;i<=t;i++)
	{
		l1[i]=(i-1)*sqrt(n)+1;
		r1[i]=i*sqrt(n);
	}
	if(r1[t]<n)
	{
		t++;
		l1[t]=r1[t-1]+1;
		r1[t]=n;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=l1[i];j<=r1[i];j++)
		{
			pos[j]=i;
		 } 
	}
	for(int i=1;i<=t;i++)
		qing(i);
	for(int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		scanf("%d%d%d%d",&opt,&l,&r,&c);
		if(opt==0)
		ch(l,r,c);
		if(opt==1)
		{
//			for(int i=1;i<=n;i++)
//			cout<<a[i]<<' ';
//			cout<<endl;
			printf("%d\n",ask(l,r,c));
		}
	}
}