HDU-1754 I Hate It （树状数组模板题——单点更新，区间查询最大值）

• 2020 年 2 月 24 日
• 筆記

ac代码(注意字符读入前需要注意回车的影响)

#include<iostream>  #include<cstdio>  #include<cstring>  #include<algorithm>  #include<bitset>  #include<cassert>  #include<cctype>  #include<cmath>  #include<cstdlib>  #include<ctime>  #include<deque>  #include<iomanip>  #include<list>  #include<map>  #include<queue>  #include<set>  #include<stack>  #include<vector>  #define mp make_pair  #define pi acos(-1)  #define pii pair<int, int>  #define pll pair<long long , long long>  #define ll long long  #define ld long double  #define MEMS(x) memset(x, -1, sizeof(x))  #define MEM(x) memset(x, 0, sizeof(x))  const int inf = 0x3f3f3f3f;  const int maxn = 200005;  using namespace std;  int N, M;  int s, c[maxn], d[maxn];  char order;  int lowbit(int x)  {      return x & (-x);  }  void update(int x)  {      while(x <= N)      {          d[x] = c[x];          int lx = lowbit(x);          for(int i = 1; i < lx; i <<= 1)              d[x] = max(d[x], d[x - i]);          x += lowbit(x);      }  }  int getmax(int l, int r)  {      int ans = 0;      while(r >= l)      {          ans = max(ans, c[r]);          --r;          while(r - lowbit(r) >= l)          {              ans = max(ans, d[r]);              r -= lowbit(r);          }      }      return ans;  }  int main()  {  //    freopen("input.txt", "r", stdin);  //    freopen("output.txt", "w", stdout);      while(scanf("%d %d", &N, &M) != EOF)      {          memset(d, 0, sizeof(d));          for(int i = 1; i <= N; i++)          {              scanf("%d", &c[i]);              update(i);          }          int a, b;          while(M--)          {              getchar();              scanf("%c %d %d", &order, &a, &b);              if(order == 'U')              {                  c[a] = b;                  update(a);              }              else if(order == 'Q')                  printf("%dn", getmax(a, b));          }      }  }