建站网址建设,如何成为电商,网上商城推广,青岛做网站多少钱题干#xff1a;
很多学校流行一种比较的习惯。老师们很喜欢询问#xff0c;从某某到某某当中#xff0c;分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢#xff0c;现在需要你做的是#xff0c;就是按照老师的要求#xff0c;写一个程序#xff0c;模拟老…题干
很多学校流行一种比较的习惯。老师们很喜欢询问从某某到某某当中分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢现在需要你做的是就是按照老师的要求写一个程序模拟老师的询问。当然老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试请处理到文件结束。 在每个测试的第一行有两个正整数 N 和 M ( 0N200000,0M5000 )分别代表学生的数目和操作的数目。 学生ID编号分别从1编到N。 第二行包含N个整数代表这N个学生的初始成绩其中第i个数代表ID为i的学生的成绩。 接下来有M行。每一行有一个字符 C (只取Q或U) 和两个正整数AB。 当C为Q的时候表示这是一条询问操作它询问ID从A到B(包括A,B)的学生当中成绩最高的是多少。 当C为U的时候表示这是一条更新操作要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9Hint
Huge input,the C function scanf() will work better than cin
题目大意 中文题啦不解释。
解题报告
这题跟【HDU - 1166】敌兵布阵 就不一样啦这题是单点覆盖更新也就是说很多地方的 要换成。
单点更新区间最大值查询改一下pushup即可。
AC代码
#includebits/stdc.husing namespace std;
const int MAXN 200000 5;
int n;
int a[MAXN];
struct TREE {int l,r;int val;int laz; int maxx;
} tree[4*MAXN];
void pushup(int cur) {tree[cur].val tree[2*cur].val tree[2*cur 1].val; tree[cur].maxx max(tree[2*cur].maxx, tree[2*cur 1].maxx);
}
void build(int l ,int r,int cur) {if(l r) {tree[cur].l tree[cur].r l;//写成tree[r].r 了。。 tree[cur].val a[l];tree[cur].maxx tree[cur].val;return ;//这步return必须加不然就无限递归了。这就是为什么写递归函数要将出口写在最前面就是不给他再次进入递归函数的机会 }int m (lr)/2;tree[cur].l l;tree[cur].r r;build(l,m,2*cur);build(m1,r,2*cur 1);pushup(cur);
}
//pl-pr为查询区间l和r为树种 当前cur下标
//int query2(int pl,int pr,int l,int r,int cur) {
// if(pll prr) return tree[cur].val; pushdown(cur,l,r);
// int m (lr)/2;
// int res 0;
// if(pl m) res query2(pl,pr,l,m,2*cur);
// //下面这里是if啊不是else
// if(pr m1) res query2(pl,pr,m1,r,2*cur 1);
// return res;
//}
int query(int pl,int pr,int l,int r,int cur) {if(pll pr r) return tree[cur].maxx;int m (lr)/2;int res,tmp1 0,tmp2 0;if(pl m) tmp1 query(pl,pr,l,m,2*cur);
// printf( %d tmp1 %d\n,cur,tmp1);if(pr m1) tmp2 query(pl,pr,m1,r,2*cur1);res max(tmp1,tmp2);return res;
// if(pl m) res query(pl,pr,l,m,2*cur);
// if(pr m1) res max(res,query(pl,pr,m1,r,2*cur1));
// return res;
}
void update1(int tar,int val,int l,int r,int cur) {if(l r) {tree[cur].val val;tree[cur].maxx val;
// tree[cur].laz val;return;//这步return必须加不然就无限递归了。这就是为什么写递归函数要将出口写在最前面就是不给他再次进入递归函数的机会 }int m (l r)/2;if(tarm) update1(tar,val,l,m,2*cur);else update1(tar,val,m1,r,2*cur 1);pushup(cur);
}
int main()
{int tmp1,tmp2;int mm;char op[10];while(~scanf(%d%d,n,mm) ) {for(int i 1; in; i ) {scanf(%d,a[i]);}memset(tree,0,sizeof(tree));build(1,n,1);
// printf(%d %d ,tree[1].l,tree[1].r);
// for(int i 1; i50; i) printf(%d ,tree[i].maxx);while(mm-- ) {scanf(%s,op);if(op[0] Q) {scanf(%d%d,tmp1,tmp2);
// tmp2 tmp2 - tree[tmp1].val;printf(%d\n,query(tmp1,tmp2,1,n,1));}else {scanf(%d%d,tmp1,tmp2);update1(tmp1,tmp2,1,n,1);
// for(int i 1; i50; i) printf(%d ,tree[i].maxx);}}}return 0 ;} // 5 6
//1 2 3 4 5
//Q 1 5
//U 3 6
