(线段树)HUD1754IHateIt

1754 I Hate It

题目链接http://acm.hdu.edu.cn/showproblem.php?pid&＃61;1754
挺多自己粗心大意的地方&＃xff0c;下面都备注了


#include
#include
#include
#include
using namespace std;
typedef struct Node {int l, r;int m;//Node(int ll, int rr, int mm):l(ll),r(rr),m(mm){}
}node;
int a[200010];
node tr[200010*4];//注意要扩展四倍即<<2;
void pushup(int u) {tr[u].m &＃61; max(tr[u << 1].m, tr[u << 1 | 1].m);
}
void build(int u, int l, int r) {node te;te.l &＃61; l; te.r &＃61; r;tr[u] &＃61; te;if (l &＃61;&＃61; r) {tr[u].m &＃61; a[l];}else {int mid &＃61; (l &＃43; r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid &＃43; 1, r);pushup(u);}}
void change(int u,int x,int score) {//改变就是找到最底层的点,然后依次向上修改最大值。if(tr[u].r&＃61;&＃61;tr[u].l){tr[u].m &＃61; score;return;}int mid &＃61; (tr[u].l &＃43; tr[u].r)>>1;if(x<&＃61;mid){change(u<<1, x, score);}else {change(u<<1|1, x, score);}pushup(u);}
int query(int u,int x, int y) {int temp &＃61; 0;if (tr[u].l >&＃61; x && tr[u].r <&＃61; y) {//查询&＃xff0c;只需要某段在x,y之间即可temp &＃61;tr[u].m;}else {int mid &＃61; tr[u].r &＃43; tr[u].l >> 1;if (x <&＃61; mid) temp &＃61; max(temp, query(u << 1, x, y));//原理和上面的解释一样if (y > mid) temp &＃61; max(temp, query(u << 1 | 1, x, y));}return temp;
}
int main() {int n, m;while (~scanf("%d %d", &n, &m) ) {//cout<memset(a,0,sizeof a);//如果下面build,query ,change的函数n换成200010&＃xff0c;则要加上这两个置0。memset(tr,0,sizeof tr);for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)//因为学生编号是1~n,所以i初值不能为0scanf("%d", &a[i]);build(1, 1,n);char ch;int x, y;for (int i &＃61; 0; i < m; i&＃43;&＃43;) {scanf("%*c%c %d %d",&ch,&x,&y);//习惯了cin,cout&＃xff0c;scanf这里要处理\n的影响//cout<if (ch&＃61;&＃61; &＃39;Q&＃39;) {printf("%d\n", query(1, x, y));}else {change(1,x, y);}}}return 0;
}