数列分块入门 2
时间限制: 3 Sec 内存限制: 256 MB
[命题人:admin] [ Edit] [ TestData]
题目描述
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。
输入
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。
接下来输入 n 行询问，每行输入四个数字opt 、l、r、c，以空格隔开。
若opt=0，表示将位于[l,r]的之间的数字都加c。
若opt=1，表示询问中[l,r]小于c2的数字的个数。
输出
对于每次询问，输出一行一个数字表示答案。
样例输入 Copy
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
样例输出 Copy
3
0
2
提示
n<=50000, -231<=others, ans<=231-1
思路：
每一块内实行sort排序，二分查找个数，对于开始和结尾不是完整块的，遍历得到个数。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int n,a[maxn];///本题的信息 int num,block,belong[maxn],l[maxn],r[maxn]; int w[maxn];///维护的信息 vector<int>v[510]; void build() { block=sqrt(n); num=n/block;if(n%block) num++; for(int i=1;i<=num;i++) { l[i]=(i-1)*block+1; r[i]=i*block; } r[num]=n; for(int i=1;i<=n;i++) { belong[i]=(i-1)/block+1; v[belong[i]].push_back(a[i]); } for(int i=1;i<=belong[n];i++) sort(v[i].begin(),v[i].end()); } void resort(int u){ v[u].clear(); for(int i=l[u];i<=r[u];i++) v[u].push_back(a[i]); sort(v[u].begin(),v[u].end()); } void update(int x,int y,int c) { if(belong[x]==belong[y]) { for(int i=x;i<=y;i++) a[i]+=c; resort(belong[x]); } else { for(int i=x;i<=r[belong[x]];i++) a[i]+=c; for(int i=belong[x]+1;i<belong[y];i++) w[i]+=c; for(int i=l[belong[y]];i<=y;i++) a[i]+=c; resort(belong[x]);resort(belong[y]); } } int qask(int x,int y,int c) { int res=0; if(belong[x]==belong[y]) { for(int i=x;i<=y;i++) if(a[i]+w[belong[i]]<c) res++; } else { for(int i=x;i<=r[belong[x]];i++) if(a[i]+w[belong[i]]<c) res++; for(int i=belong[x]+1;i<belong[y];i++) { int tmp=c-w[i]; res+=lower_bound(v[i].begin(),v[i].end(),tmp)-v[i].begin(); } for(int i=l[belong[y]];i<=y;i++) if(a[i]+w[belong[i]]<c) res++; } return res; } void AC() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),w[i]=0; build();///初始化分块所需要的数组等 for(int i=1;i<=n;i++) { int op,x,y,c; scanf("%d%d%d%d",&op,&x,&y,&c); if(op==0) update(x,y,c); else printf("%d\n",qask(x,y,c*c)); } puts(""); } int main() { AC(); return 0; }
