#174

#174

Description

老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。 

     在询问过程中账本的内容可能会被修改 

Input

输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。 

第二行为m个数,分别是账目的钱数. 

接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y 

当p=1 则查询x,y区间 

当p=2 则改变第x个数为y 

Output

输出文件中为每个问题的答案。具体查看样例。 

Sample Input

10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10

Sample Output

2 0

可以说是线段树模板题之一.

#include <iostream> // scanf(), printf() 等各种函数都需要 (Dev-C++ 可以, 但是洛谷提交一定要加上一句 : #include <cstdio> !!!)#define SIZE 400010 // 数组大小,在线段树问题中一般是数据个数的四倍
#define INF 2e+09 // 用一个很大的数 (如 2e+09, 或2 000 000 000) 来表示无穷大using namespace std; // 使用标准 (std) 命名空间int res[SIZE]; // 存储区间的最小值,下标是对应节点的代号void buildtree(int pos, int l, int r) // 建一颗线段树
// pos : 当前节点的代号
// l : 当前区间的左端
// r : 当前区间的右端
// 该函数的时间复杂度 : O (n)
{int mid;if (l == r) // 此区间只有一个数!{scanf("%d", &res[pos]); // 直接把这个数据给输入了return; // 直接溜走}mid = l + r >> 1; // 得到区间的中间点midbuildtree(pos << 1, l, mid); // 建造表示该区间左半段的树buildtree((pos << 1) + 1, mid + 1, r); // 建造表示该区间右半段的树res[pos] = min(res[pos<<1], res[(pos<<1)+1]); // 当前区间最小值取该区间左半段和该区间右半段最小值的最小值return;
}void update(int pos, int l, int r, int x, int y) // 更新一个点的值
// pos : 当前节点的代号
// l : 当前区间的左端
// r : 当前区间的右端
// x : 要改变的数的下标
// y : 要把那个数改为y
// 该函数的时间复杂度 : O (log2 n)
{int mid;if (l == r) // 该区间只有一个数,也就是说找到了要改变的那个数!{res[pos] = y; // 直接改变该数的值return; // 直接溜了}mid = l + r >> 1; // mid表示该区间的中间点if (x <= mid) // 如果要改变的点在该区间的左半段{update(pos << 1, l, mid, x, y); // 那么,就在该区间的左半段寻找要改变的数}else // 否则,要改变的点在该区间的右半段{update((pos << 1) + 1, mid + 1, r, x, y); // 那么,就在该区间的右半段寻找要改变的数}res[pos] = min(res[pos<<1], res[(pos<<1)+1]); // 由于这个区间的左半段或者右半段的最小值已经被改变,需要更新该区间的最小值return;
}int query(int pos, int l, int r, int x, int y) // 询问区间 [x, y] 中的最小值
// pos : 当前节点的代号
// l : 当前区间的左端
// r : 当前区间的右端
// x : 要查询最小值的区间的左端
// y : 要查询最小值的区间的右端
// 该函数时间复杂度 : O (log2 n)
{int t1, t2, mid;if ((r < x) || (l > y)) // 此区间和要询问的最小值的区间 [x, y] 没有重合部分{return INF; // 直接开溜}if ((x <= l) && (y >= r)) // 此区间完全包含在要询问最小值的区间 [x, y] 中{return res[pos]; // 直接返回}mid = l + r >> 1; //  mid表示该区间的中间点t1 = t2 = INF; // 这样做是为了不符合下一步递归条件的值设为无穷大 (INF)if (x <= mid) // 如果该区间的左半段 [l, mid] 和要询问最小值的区间 [x, y] 有重合部分{t1 = query(pos << 1, l, mid, x, y); // 在该区间的左半段 [l, mid] 寻找答案}if (y > mid) // 如果该区间的右半段 [mid + 1, r] 和要询问最小值的区间 [x, y] 有重合部分{t2 = query((pos << 1) + 1, mid + 1, r, x, y); // 在该区间的右半段 [mid + 1, r] 寻找答案}return min(t1, t2); // 返回该区间的左半段的答案和右半段的答案的最小值
}int main(void) // 终于到主函数了!
{int n, m, p, x, y;scanf("%d%d", &n, &m); // 输入数据数目以及操作个数buildtree(1, 1, n); // 建一颗线段树,顺便输入数据while (m--){scanf("%d%d%d", &p, &x, &y); // 输入操作编号和操作参数if (p == 1){printf("%d ", query(1, 1, n, x, y)); // 询问区间的最小值}else{update(1, 1, n, x, y); // 更新一个数据}}return 0;
}