hdu1754我讨厌他(线段树,区间最大值)

    xiaoxiao2024-11-30  6

    这个就是和那个之前做的区间最大和是一样的。就是那个敌兵布阵的那个sum改成区间最大值,更新的时候不要忘了用max。就是这样婶儿。

    #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MaxN = 200000; int sum[MaxN * 4 + 5]; void PushUp(int rt) { sum[rt] = max(sum[rt << 1] , sum[rt << 1 | 1]); } void buildT(int l , int r , int rt) { if(l == r){ scanf("%d",&sum[rt]); return; } int m = (l + r) >> 1; buildT(l , m , rt << 1); buildT(m + 1 , r ,rt << 1 | 1); PushUp(rt); } void UpDate(int p , int add , int l , int r , int rt) { if(l == r){ sum[rt] = add; return; } int m = (l + r) >> 1; if(p <= m) UpDate(p , add , l , m , rt << 1); else UpDate(p , add , m + 1 , r , rt << 1 | 1); PushUp(rt); } int query(int ll ,int rr ,int l , int r , int rt) { if(ll <= l && rr >= r) return sum[rt]; int m = (l + r) >> 1; int ret = 0; if(ll <= m) ret = max(ret ,query(ll ,rr , l , m , rt << 1)); if(rr > m) ret = max(ret ,query(ll , rr , m + 1 , r , rt << 1 | 1)); return ret; } int main() { int n , m , c , b; char a[3]; while(~scanf("%d%d", &n , &m)){ buildT(1 , n , 1); for(int i = 0 ; i < m ; i++){ scanf("%s",a); scanf("%d%d",&b , &c); if(a[0] == 'Q') printf("%d\n",query(b , c , 1 , n , 1)); else if(a[0] == 'U') UpDate(b , c , 1 , n , 1); } } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-1294113.html
    最新回复(0)