题目描述
【题意】
给出N个数，两种操作：
1、C x y：修改第x个数的值为y；
2、P x y：求第x到第y个的最大值，注：x未必比y小
【输入格式】
第一行输入N和M（0<N<=200000,0<M<5000），N表示有N个数，M表示有M个操作
下来N个数
然后是M个操作。
【输出格式】
遇到P操作的时候，输出结果。
【样例输入】
5 6
1 2 3 4 5
P 1 5
C 3 6
P 3 4
P 4 5
C 2 9
P 1 5
【样例输出】
5
6
5
9
首先，看到是多次询问并操作就是线段树或树状数组。线段树的管辖范围比较广，所以此处示范线段树的模型。
#include <cstring> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <cstdlib> #define N 100010 using namespace std; int a[N]; //员工，只负责一开始表达自己的值 struct node//管理者（假设他是经理），管理者绝对不是员工，一定要分开来 //理解：有N个员工，就配有 2N-1 个管理者，用空间换时间 { int l , r , lc , rc , c;//管理的员工编号是第l个到第r个（连续），lc表示左副经理的编号，rc表示右副经理的编号 //c表示第l个员工至第r个员工的特征值：可以是和、最大值、最小值 }; node tr[N];//tr数组就是管理者数组 int len;//len表示当前申请到第几个管理者 //到此，员工有自己的编号，管理者也有自己的编号 int mymax(int x , int y) { return x > y ? x : y; } //求x、y最大值的函数 void bt(int l ,int r)//建立线段树，申请一个管理者，管理第l个员工至第r个员工 { len++; int now = len;//now记录当前管理者的编号 tr[now].l = l; tr[now].r = r; tr[now].lc = tr[now].rc = -1;//一开始当前管理者now的左右副总经理都是没人 -1 if(l == r)//l == r表示当前管理者只管1人 tr[now].c = a[l]; else //如果管的人大于1人，就有权申请两个副总经理帮忙管人 { int mid = (l + r) / 2;//mid为l和r的中间值，从中间分为两段[l , mid]和[mid + 1 , r] tr[now].lc = len + 1; bt(1 , mid);//[l , mid]给左副总经理，让他管好[l , mid] tr[now].rc = len + 1; bt(mid + 1 , r);//[mid + 1 , r]给右副总管，让他管好[mid + 1 , r] tr[now].c = mymax(tr[tr[now].lc].c , tr[tr[now].rc].c);//等左右副总经理都管好了后，问左右副总经理各自管辖的范围的最大值，作为自己管辖范围的最大值 } } void change(int now , int x , int k)//change的功能：在当前管理者now的管理范围内，把管第x员工的管理者（不知道该管理者的编号）的值改为k //理解：为什么第x个一定在now的管理范围内呢？ //注意：修改，改的是管理者，不是改员工，员工已经没用了 { if(tr[now].l == tr[now].r) { tr[now].c = k; return; } //如果now只管一个人，那么这个人编号一定为x，为什么？ int lc = tr[now].lc,rc = tr[now].rc;//找出now的左右副总分别是谁 int mid = (tr[now].l + tr[now].r) / 2;//找到now管理范围的中间位置 if(x <= mid) change(lc , x , k);//如果x在now的左副总经理的管理范围，那么修改这件事就交给左副总经理去做 else if(mid + 1 <= x) change(rc , x , k);//如果x在now的右副总经理的管理范围，那么修改这件事就交给右副总经理去做 tr[now].c = mymax(tr[lc].c , tr[rc].c);//修改完后，注意要维护，有可能最大值发生变化了 } int findmax(int now , int l , int r)//findmax的功能：在当前管理者now的管辖范围内，找出第l个员工至第r个员工的最大值 { if(l == tr[now].l && tr[now].r == r) return tr[now].c;//如果now的管辖范围刚好是[l , r]，就不用问左右副总经理了 int lc = tr[now].lc , rc = tr[now].rc; int mid = (tr[now].l + tr[now].r) / 2; if(r <= mid) return findmax(lc , l , r);//[l , r]在左副总经理的管辖范围内 else if(mid + 1 <= l) return findmax(rc , l , r);//[l , r]在右副总经理的管辖范围内 else return mymax(findmax(lc , l , mid) , findmax(rc , mid + 1 , r));//其他情况就是[l , r]一部分在左副总经理，一部分在右副总经理 } int main() { int n , m , i , x , y; char ss[10]; scanf("%d%d",&n,&m); for(i = 1 ; i <= n ; i ++) scanf("%d",&a[i]); len = 0;//初始化len为0，一开始没有一个管理者 bt(1 , n); for(i = 1 ; i <= m ; i ++) { scanf("%s%d%d",ss,&x,&y); if(ss[0] == 'C') change(1 , x , y); else { if(x > y) printf("%d ",findmax(1 , y , x)); else printf("%d ",findmax(1 , x , y)); } } return 0; }
根据题意是来维护最大值和修改值，这里的findmax和change函数可自行根据题意来修改。
这里注意要判断x和y的大小。