【题目来源】https://www.luogu.com.cn/problem/P1816【题目描述】老管家是一个聪明能干的人。他为财主工作了整整 10 年。财主为了让自己账目更加清楚要求管家每天记 k 次账。由于管家聪明能干因而管家总是让财主十分满意。但是由于一些人的挑拨财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚。他把每次的账目按 1,2,3,… 编号然后不定时地问管家这样的问题在 a 到 b 号账中最少的一笔是多少为了让管家没时间作假他总是一次问多个问题。【输入格式】第一行输入两个数 m,n表示有 m 笔账和 n 个问题。第二行输入 m 个数分别表示账目的钱数 xi。接下来 n 行分别输入 n 个问题每行 2 个数字分别表示开始的账目编号 a 和结束的账目编号 b。【输出格式】第一行输出每个问题的答案每个答案中间以一个空格分隔。【输入样例】10 31 2 3 4 5 6 7 8 9 102 73 91 10【输出样例】2 3 1【数据范围】对于 100% 的数据1≤m≤10^51≤n≤10^50≤xi≤10^5。【算法分析】● “序列分块”算法的基本要素及 build() 函数的构建细节https://blog.csdn.net/hnjzsyjyj/article/details/138955263● 由于“洛谷 P1816忠诚”只有查询没有修改所以分块结构建好后就不需要再更新。所以“洛谷 P1816忠诚”还可以用 ST 表稀疏表来做预处理 O(nlog n)查询 O(1)比分块更快。ST算法详见https://blog.csdn.net/hnjzsyjyj/article/details/152514708【算法代码】#include bits/stdc.h using namespace std; const int N1e55; const int INFINT_MAX; int a[N],le[N],ri[N]; int block_min[N]; int pos[N]; int n,m; 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; //Calculate the min value for each block for(int i0; icnt; i) { block_min[i]INF; for(int jle[i]; jri[i]; j) { block_min[i]min(block_min[i],a[j]); } } } int query(int st,int ed) { int resINF; //st and ed are in the same block if(pos[st]pos[ed]) { for(int ist; ied; i) resmin(res,a[i]); return res; } /*Process the scattered blocks on the left (from st to the right boundary of the block where st is located)*/ for(int ist; iri[pos[st]]; i) { resmin(res,a[i]); } //Deal with the entire middle block for(int ipos[st]1; ipos[ed]; i) { resmin(res,block_min[i]); } /*Process the scattered block on the right (from the left boundary of the block where ed is located to ed)*/ for(int ile[pos[ed]]; ied; i) { resmin(res,a[i]); } return res; } int main() { ios::sync_with_stdio(0); cin.tie(0); cinnm; for(int i0; in; i) cina[i]; build(); while(m--) { int le,ri; cinleri; le--; ri--; coutquery(le,ri) ; } return 0; } /* in: 10 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10 out: 2 3 1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/138903837https://blog.csdn.net/hnjzsyjyj/article/details/152514708https://blog.csdn.net/hnjzsyjyj/article/details/138863063
【题目来源】https://www.luogu.com.cn/problem/P1816【题目描述】老管家是一个聪明能干的人。他为财主工作了整整 10 年。财主为了让自己账目更加清楚要求管家每天记 k 次账。由于管家聪明能干因而管家总是让财主十分满意。但是由于一些人的挑拨财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚。他把每次的账目按 1,2,3,… 编号然后不定时地问管家这样的问题在 a 到 b 号账中最少的一笔是多少为了让管家没时间作假他总是一次问多个问题。【输入格式】第一行输入两个数 m,n表示有 m 笔账和 n 个问题。第二行输入 m 个数分别表示账目的钱数 xi。接下来 n 行分别输入 n 个问题每行 2 个数字分别表示开始的账目编号 a 和结束的账目编号 b。【输出格式】第一行输出每个问题的答案每个答案中间以一个空格分隔。【输入样例】10 31 2 3 4 5 6 7 8 9 102 73 91 10【输出样例】2 3 1【数据范围】对于 100% 的数据1≤m≤10^51≤n≤10^50≤xi≤10^5。【算法分析】● “序列分块”算法的基本要素及 build() 函数的构建细节https://blog.csdn.net/hnjzsyjyj/article/details/138955263● 由于“洛谷 P1816忠诚”只有查询没有修改所以分块结构建好后就不需要再更新。所以“洛谷 P1816忠诚”还可以用 ST 表稀疏表来做预处理 O(nlog n)查询 O(1)比分块更快。ST算法详见https://blog.csdn.net/hnjzsyjyj/article/details/152514708【算法代码】#include bits/stdc.h using namespace std; const int N1e55; const int INFINT_MAX; int a[N],le[N],ri[N]; int block_min[N]; int pos[N]; int n,m; 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; //Calculate the min value for each block for(int i0; icnt; i) { block_min[i]INF; for(int jle[i]; jri[i]; j) { block_min[i]min(block_min[i],a[j]); } } } int query(int st,int ed) { int resINF; //st and ed are in the same block if(pos[st]pos[ed]) { for(int ist; ied; i) resmin(res,a[i]); return res; } /*Process the scattered blocks on the left (from st to the right boundary of the block where st is located)*/ for(int ist; iri[pos[st]]; i) { resmin(res,a[i]); } //Deal with the entire middle block for(int ipos[st]1; ipos[ed]; i) { resmin(res,block_min[i]); } /*Process the scattered block on the right (from the left boundary of the block where ed is located to ed)*/ for(int ile[pos[ed]]; ied; i) { resmin(res,a[i]); } return res; } int main() { ios::sync_with_stdio(0); cin.tie(0); cinnm; for(int i0; in; i) cina[i]; build(); while(m--) { int le,ri; cinleri; le--; ri--; coutquery(le,ri) ; } return 0; } /* in: 10 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10 out: 2 3 1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/138903837https://blog.csdn.net/hnjzsyjyj/article/details/152514708https://blog.csdn.net/hnjzsyjyj/article/details/138863063
