题目描述
给出一个长为 n 的数列，以及 n个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。
若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。
若 opt=1，表示询问[l,r] 中，小于 c^2 的数字的个数。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
样例输入
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2样例输出
3
0
2数据范围与提示
对于100%的数据，1<=n<=50000, -2^31<=others,ans<=2^31-1。
思路：第一题是查询一个数的，而这题是要在一个区间内找到一个比c*c小的值。暴力一个一个找
肯定是会超时的。我们可以接着第一题分块的思路查询，左右不足一块的排序暴力找就行了，而整块的
我们排序二分找就很快了。这里要再建一个数组（这里用的vector,因为二分可以用库函数lower_bound()）保存改变的值用来排序。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define inf 0x3f3f3f3f #include<vector> #include<set> #include<map> #include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=5e4+10; int n,block,a[maxn],b[maxn],pos[maxn],x,ans; vector<int>v[550]; void reset(int x)//用来不构成一整块的排序 { v[pos[x]].clear(); for(int i=(pos[x]-1)*block+1;i<=min(pos[x]*block,n);i++) v[pos[x]].push_back(a[i]); sort(v[pos[x]].begin(),v[pos[x]].end()); } void update(int l,int r,int c) { for(int i=l;i<=min(pos[l]*block,r);i++)//左边不成一整块，暴力加 a[i]+=c; reset(l); if(pos[l]!=pos[r]) { for(int i=(pos[r]-1)*block+1;i<=r;i++)//右边不成一整块的暴力加 a[i]+=c; reset(r); } for(int i=pos[l]+1;i<=pos[r]-1;i++)//中间整块的整块加，用b数组保存 b[i]+=c; } int query(int l,int r,int c)//查询答案 { int ans=0; for(int i=l;i<=min(pos[l]*block,r);i++)//左边不构成一整块的暴力查找 if(a[i]+b[pos[l]]<c) ans++; if(pos[l]!=pos[r]) { for(int i=(pos[r]-1)*block+1;i<=r;i++)//右边不构成一整块的暴力查找 if(a[i]+b[pos[r]]<c) ans++; } for(int i=pos[l]+1;i<=pos[r]-1;i++)//中间整块的二分查找 { int x=c-b[i]; ans+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin(); } return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); block=sqrt(n); for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1,v[pos[i]].push_back(a[i]);//每个数分块的序号，放入vector保存 for(int i=1;i<=pos[n];i++) sort(v[i].begin(),v[i].end());//整块排序 int opt,l,r,x; for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&opt,&l,&r,&x); if(opt==0) update(l,r,x); else printf("%d ",query(l,r,x*x)); } return 0; }
第三题和第二题思路是样的，因为是要找c的前驱，暴力找左右不完整块的比c小最大值，再二分找完整块比c小最大值，取其中最大即可。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<cmath> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; int a[maxn],b[maxn],pos[maxn],ans,flag,n,block; vector<int>v[1010]; void reset(int x)//用于对不完整块排序 { v[pos[x]].clear(); for(int i=(pos[x]-1)*block+1;i<=min(pos[x]*block,n);i++) v[pos[x]].push_back(a[i]); sort(v[pos[x]].begin(),v[pos[x]].end()); } void update(int l,int r,int c)//更新值，第一个操作 { for(int i=l;i<=min(pos[l]*block,r);i++)//暴力加 a[i]+=c; reset(l); if(pos[l]!=pos[r]) { for(int i=(pos[r]-1)*block+1;i<=r;i++)//暴力加 a[i]+=c; reset(r); } for(int i=pos[l]+1;i<=pos[r]-1;i++)//b数组储存完整块的加值 b[i]+=c; } void query(int l,int r,int x) { flag=0;//标记是否找到比c小的值 ans=-inf; for(int i=l;i<=min(pos[l]*block,r);i++)//暴力找左边不完整块 { if(a[i]+b[pos[l]]<x) { ans=max(a[i]+b[pos[l]],ans); flag=1; } } if(pos[l]!=pos[r])//暴力找右边不完整块 { for(int i=(pos[r]-1)*block+1;i<=r;i++) { if(a[i]+b[pos[r]]<x) { ans=max(ans,a[i]+b[pos[r]]); flag=1; } } } for(int i=pos[l]+1;i<=pos[r]-1;i++)//整块用二分查找 { int c=x-b[i]; int k=lower_bound(v[i].begin(),v[i].end(),c)-v[i].begin(); if(k!=0&&v[i][k-1]+b[i]<x)//不要忘了加回整块该加的值 { flag=1; ans=max(ans,v[i][k-1]+b[i]); } } if(flag) printf("%d ",ans); else printf("-1 "); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); block=sqrt(n);//块的大小 for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1,v[pos[i]].push_back(a[i]);//每个数块的序号并储存在vector for(int i=1;i<=pos[n];i++) sort(v[i].begin(),v[i].end());//整块排序 int opt,l,r,c; for(int i=0;i<n;i++) { scanf("%d%d%d%d",&opt,&l,&r,&c); if(opt==0) update(l,r,c); else query(l,r,c); } return 0; }