HDU 1754 I Hate It (线段树(指针))

发表于 更新于 分类于

Problem

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 \(N\) 和 \(M\) ( \(0<N<=200000\),\(0<M<5000\) )，分别代表学生的数目和操作的数目。

学生ID编号分别从\(1\)编到\(N\)。

第二行包含\(N\)个整数，代表这\(N\)个学生的初始成绩，其中第\(i\)个数代表ID为\(i\)的学生的成绩。

接下来有\(M\)行。每一行有一个字符 \(C\) (只取'Q'或'U') ，和两个正整数\(A\)，\(B\)。

当\(C\)为'Q'的时候，表示这是一条询问操作，它询问ID从\(A\)到\(B\)(包括\(A\),\(B\))的学生当中，成绩最高的是多少。

当\(C\)为'U'的时候，表示这是一条更新操作，要求把ID为\(A\)的学生的成绩更改为\(B\)。

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

1
2
3
4
5
6
7
8
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

1
2
3
4
5
6
5
9

Solution

线段树区间最值板子题, 这些不解释, 这题主要用来测试析构函数。

由于我只会经常写指针版的线段树, 多组数据的题目经常MLE, 所以要写一个函数来释放内存。为了方便就用析构函数(在当前变量内存空间释放时调用), 就不用写个递归函数了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <algorithm>
#include <cstdio>
class SegmentTree {
 private:
  struct Node {
    int value;
    Node *left, *right;
    int L, R;
    inline void Update() {
      if (this->left) {
        this->value = std::max(this->left->value, this->right->value);
      }
    }
    Node(const int &l, const int &r) {
      this->L = l, this->R = r;
      this->left = this->right = NULL;
      if (l == r) {
        scanf("%d", &this->value);
      } else {
        register int mid((l + r) >> 1);
        this->left = new Node(l, mid);
        this->right = new Node(mid + 1, r);
        this->Update();
      }
    }
    ~Node() { //The destructor
      if (this->left) {
        delete this->left;
        delete this->right;
      }
    }
    inline int Query(const int &l, const int &r) {
      if (this->L >= l && this->R <= r) {
        return this->value;
      } else {
        register int mid((this->L + this->R) >> 1), ret(-2147483648);
        if (l <= mid) ret = std::max(ret, this->left->Query(l, r));
        if (mid < r) ret = std::max(ret, this->right->Query(l, r));
        return ret;
      }
    }
    inline void Modify(const int &kIndex, const int &kDelta) {
      if (this->L == this->R) {
        this->value = kDelta;
      } else {
        register int mid((this->L + this->R) >> 1);
        if (kIndex <= mid)
          this->left->Modify(kIndex, kDelta);
        else
          this->right->Modify(kIndex, kDelta);
        this->Update();
      }
    }
  } * root;

 public:
  SegmentTree() { this->root = NULL; }
  inline void Clear() {
    if (this->root) {
      delete this->root;
      this->root = NULL;
    }
  }
  inline void Build(const int &l, const int &r) { this->root = new Node(l, r); }
  inline int Query(const int &l, const int &r) {
    return this->root->Query(l, r);
  }
  inline void Modify(const int &kIndex, const int &kDelta) {
    this->root->Modify(kIndex, kDelta);
  }
} T;
int n, m;
char C;
int A, B;
int main(int argc, char const *argv[]) {
  while (~scanf("%d %d", &n, &m)) {
    T.Clear();
    T.Build(1, n);
    while (m--) {
      scanf("\n%c %d %d", &C, &A, &B);
      switch (C) {
        case 'Q': {
          printf("%d\n", T.Query(A, B));
          break;
        }
        case 'U': {
          T.Modify(A, B);
          break;
        }
      }
    }
  }
  return 0;
}