洛谷 P13976：数列分块入门 1 ← 序列分块算法（区间更新、单点查询）

【题目来源】https://www.luogu.com.cn/problem/P13976【题目描述】给出一个长为 n 的数列以及 n 个操作操作涉及区间加法单点查值。【输入格式】第一行输入一个数字 n。第二行输入 n 个数字第 i 个数字为 ai以空格隔开。接下来输入 n 行询问每行输入四个数字 opt、l、r、c以空格隔开。若 opt0表示将位于 [l,r] 的之间的数字都加 c。若 opt1表示询问 ar 的值l 和 c 忽略。【输出格式】对于每次询问输出一行一个数字表示答案。【输入样例】41 2 2 30 1 3 11 0 1 00 1 2 21 0 2 0​​​​​​​【输出样例】25【数据范围】对于所有数据1≤n≤300000,−2^63≤ai,c,ans≤2^63−1。【算法分析】● “序列分块”算法的基本要素及 build() 函数的构建细节https://blog.csdn.net/hnjzsyjyj/article/details/138955263【算法代码1-based】本题推荐 1-based 写法。#include bits/stdc.h using namespace std; typedef long long LL; const int N3e55; LL a[N],le[N],ri[N]; int pos[N]; LL lazy[N]; int n; void build() { //1-based int blocksqrt(n); int cnt(nblock-1)/block; for(int i1; icnt; i) { le[i](i-1)*block1; ri[i]i*block; } ri[cnt]n; for(int i1; in; i) pos[i](i-1)/block1; } void add(int st,int ed,LL val) { if(pos[st]pos[ed]) { for(int ist; ied; i) a[i]val; return; } for(int ist; iri[pos[st]]; i) a[i]val; for(int ipos[st]1; ipos[ed]; i) lazy[i]val; for(int ile[pos[ed]]; ied; i) a[i]val; } LL query(int x) { return a[x]lazy[pos[x]]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i1; in; i) cina[i]; build(); while(n--) { int op,le,ri; LL val; cinoplerival; if(op0) { add(le,ri,val); } else { coutquery(ri)\n; } } return 0; } /* in: 4 1 2 2 3 0 1 3 1 1 0 1 0 0 1 2 2 1 0 2 0 out: 2 5 */【算法代码0-based】#include bits/stdc.h using namespace std; typedef long long LL; const int N3e55; LL a[N],le[N],ri[N]; int pos[N]; LL lazy[N]; int n; void build() { int blocksqrt(n); int cnt(nblock-1)/block; for(int i0; icnt; i) { le[i]i*block; ri[i](i1)*block-1; } ri[cnt-1]n-1; for(int i0; in; i) pos[i]i/block; } void add(int st,int ed,LL val) { if(pos[st]pos[ed]) { for(int ist; ied; i) a[i]val; return; } for(int ist; iri[pos[st]]; i) a[i]val; for(int ipos[st]1; ipos[ed]; i) lazy[i]val; for(int ile[pos[ed]]; ied; i) a[i]val; } LL query(int x) { return a[x]lazy[pos[x]]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i0; in; i) cina[i]; build(); while(n--) { int op,le,ri; LL val; cinoplerival; if(op0) { add(le-1,ri-1,val); } else { coutquery(ri-1)\n; } } return 0; } /* in: 4 1 2 2 3 0 1 3 1 1 0 1 0 0 1 2 2 1 0 2 0 out: 2 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/138955263