题目链接：https://loj.ac/problem/6279
推荐博客：https://blog.csdn.net/qq_36038511/article/details/79725027
这题区间查询某个数字x的前驱（区间里比x小的最大的数），我用的是二分，自己手写二分的时候一直用的是没有排序的数组，好无语，后面又用set做了一遍，熟系一下set。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 50005*2
/*struct point{
int u,w;
};
bool operator <(const point &s1,const point &s2)
{
if(s1.w!=s2.w)
return s1.w>s2.w;
else
return s1.u>s2.u;
}*/
int n,m,k,t,block;
int a[maxn],tag[maxn],lump[maxn];
vector<int>ve[];
void update(int x)
{
ve[x].clear();//把第x块原来的值清除
for(int i=(x-)*block+;i<=min(x*block,n);i++)//这里要加min，因为第x块可能是最后一块并且是不完整的
ve[x].push_back(a[i]);//把增加了的值重新压入
sort(ve[x].begin(),ve[x].end());//排序
}
void add(int l,int r,int c)
{
for(int i=l;i<=min(lump[l]*block,r);i++)//暴力更新左边不完整的块
a[i]+=c;
update(lump[l]);//更新值并且重新排序
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*block+;i<=r;i++)//暴力更新右边不完整的块
a[i]+=c;
update(lump[r]);
}
for(int i=lump[l]+;i<=lump[r]-;i++)
tag[i]+=c;
}
int binary_search(int x,int w)
{
int l=,r=ve[x].size()-;
int pos=-INF;
while(l<=r)
{
int mid=(l+r)/;
if(ve[x][mid]>=w)
{
r=mid-;
pos=r;
}
else
{
l=mid+;
pos=mid;
}
}
if(pos>=&&pos<ve[x].size()&&ve[x][pos]<w)
return ve[x][pos];
else
return INF;
}
int find(int l,int r,int c)
{
int ans=-;
for(int i=l;i<=min(lump[l]*block,r);i++)//在左边不完整的块里查找
{
if(a[i]+tag[lump[l]]<c)
ans=max(ans,a[i]+tag[lump[l]]);
}
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*block+;i<=r;i++)//在右边的不完整的块里查找
{
if(a[i]+tag[lump[r]]<c)
ans=max(ans,a[i]+tag[lump[r]]);
}
}
for(int i=lump[l]+;i<=lump[r]-;i++)//在中间的完整的并且有序的块里二分查找
{
int t=c-tag[i];
/*int s=lower_bound(ve[i].begin(),ve[i].end(),t)-ve[i].begin();
if(s!=0&&tag[i]+ve[i][s-1]<c)
ans=max(ve[i][s-1]+tag[i],ans);*/
int s=binary_search(i,t);
if(s+tag[i]<c)
ans=max(ans,s+tag[i]);
}
return ans;
}
int main()
{
scanf("%d",&n); fill(tag,tag+maxn-,);
for(int i=;i<=n;i++)
ve[i].clear();
block=sqrt(n); for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
lump[i]=(i-)/block+;
ve[lump[i]].push_back(a[i]);
}
for(int i=;i<=lump[n];i++)//把每一块的值进行排序
sort(ve[i].begin(),ve[i].end()); for(int j=;j<=n;j++)
{
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==)
add(l,r,c);
else
{
int ans=find(l,r,c);
printf("%d\n",ans);
}
}
return ;
}
用set的代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 50005*2
/*struct point{
int u,w;
};
bool operator <(const point &s1,const point &s2)
{
if(s1.w!=s2.w)
return s1.w>s2.w;
else
return s1.u>s2.u;
}*/
int n,m,k,t,block;
int a[maxn],tag[maxn],lump[maxn];
set<int>se[];
void add(int l,int r,int c)
{
for(int i=l;i<=min(lump[l]*block,r);i++)//暴力更新左边不完整的块
{
se[lump[l]].erase(a[i]);
a[i]+=c;
se[lump[l]].insert(a[i]);
}
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*block+;i<=r;i++)//暴力更新右边不完整的块
{
se[lump[r]].erase(a[i]);
a[i]+=c;
se[lump[r]].insert(a[i]);
}
}
for(int i=lump[l]+;i<=lump[r]-;i++)
tag[i]+=c;
}
int find(int l,int r,int c)
{
int ans=-;
for(int i=l;i<=min(lump[l]*block,r);i++)//在左边不完整的块里查找
{
if(a[i]+tag[lump[l]]<c)
ans=max(ans,a[i]+tag[lump[l]]);
}
if(lump[l]!=lump[r])
{
for(int i=(lump[r]-)*block+;i<=r;i++)//在右边的不完整的块里查找
{
if(a[i]+tag[lump[r]]<c)
ans=max(ans,a[i]+tag[lump[r]]);
}
}
for(int i=lump[l]+;i<=lump[r]-;i++)//在中间的完整的并且有序的块里二分查找
{
int t=c-tag[i];
set<int>::iterator it=se[i].lower_bound(t);
if(it==se[i].begin())
continue;
it--;
ans=max(ans,tag[i]+(*it));
}
return ans;
}
int main()
{
scanf("%d",&n); fill(tag,tag+maxn-,);
for(int i=;i<=;i++)
se[i].clear();
block=sqrt(n); for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
lump[i]=(i-)/block+;
se[lump[i]].insert(a[i]);
}
for(int j=;j<=n;j++)
{
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==)
add(l,r,c);
else
{
int ans=find(l,r,c);
printf("%d\n",ans);
}
}
return ;
}