数列分块入门1
时间限制: 1 Sec 内存限制: 256 MB
[命题人:admin] [ Edit] [ TestData]
题目描述
给出一个长为n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。
输入
第一行输入一个数字n。
第二行输入n个数字，第i个数字为ai，以空格隔开。
接下来输入n行询问，每行输入四个数字opt、l、r、c，以空格隔开。
若opt=0，表示将位于[l,r]的之间的数字都加c。
若opt=1，表示询问ar 的值（l和c忽略）。
输出
对于每次询问，输出一行一个数字表示答案。
样例输入 Copy
4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
样例输出 Copy
2
5
提示
n<=50000,-231<=others, ans <=231-1
思路：
分块的思路是跟卿学姐学的，可以去b站看视频。
单点查询，区间修改。
用w[i]维护每一个分块所需要加的值，相当于线段树的懒惰标记。
等到查询时某一点的数就是a[x]+w[belong[x]]
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int num,belong[maxn],block,l[maxn],r[maxn]; int w[maxn];///维护的信息 int n,a[maxn]; 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; ///for(int i=1;i<=num;i++) /// for(int j=l[i];j<=r[i];j++) /// belong[j]=i; ///预处理 for(int i=1;i<=num;i++) w[i]=0; } void update(int x,int y,int c) { if(belong[x]==belong[y]) { for(int i=x;i<=y;i++) a[i]+=c; } 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; } } int qask(int x) { return a[x]+w[belong[x]]; } void AC() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); 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(y)); } } int main() { AC(); return 0; }
