常用算法题锦——线段树

题目描述 
牛牛有n个宝石，第i个宝石的价值是w[i].
有m个操作，操作分为两种类型
? Change   x  y   把第x个宝石的价值改成 y 
? Ask          l   r   询问区间[l,r]内宝石的最大价值，和最大价值的宝石有多少个。
输入描述:
第一行两个整数 n , m (1 ≤ n,m ≤ 2e5)
第二行有n个整数 w[i]  (0 ≤ w[i] ≤ 1e9)
接下来m行，每行代表一个操作。具体见题目描述。
输出描述:
每次询问输出一行，每行两个整数 val  cnt，val代表所有宝石中的最大价值，cnt代表价值最大的宝石有多少个。
示例1
输入
复制
5 3
2 4 3 6 8
Ask 1 5
Change 2 10
Ask 1 3
输出
复制
8 1
10 1　　

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m;
int w[N];
struct Node{
  int l, r;
  int mx, cnt;
}tr[N * 4];
struct Seg_Tree{
  void pushup(Node &c, Node &a, Node &b)
  {
    if (a.mx == b.mx) c.cnt = a.cnt + b.cnt;
    else if (a.mx > b.mx) c.cnt = a.cnt;
    else c.cnt = b.cnt;
    c.mx = max(a.mx, b.mx);
  }
  void pushup(int u)
  {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
  }
  void build(int u, int l, int r)
  {
    if (l == r)
    {
      tr[u] = {l, r, w[l], 1};
      return;
    }
    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
  void change(int u, int x, int c)
  {
    if  (tr[u].l == x && tr[u].r == x)
    {
      tr[u] = {x, x, c, 1};
      return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) change(u << 1, x, c);
    if (x > mid) change(u << 1 | 1, x, c);
    pushup(u);
  }
  Node query(int u, int l, int r)
  {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else
    {
      Node left = query(u << 1, l, r);
      Node right = query(u << 1 | 1, l, r);
      Node ans;
      pushup(ans, left, right);
      return ans;
    }
  }
}t;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  t.build(1, 1, n);
  char op[10];
  int l, r;
  while (m -- )
  {
    scanf("%s", op);
    scanf("%d%d", &l, &r);
    if (*op == ‘C‘)
    {
      t.change(1, l, r);
    }
    else
    {
      Node x = t.query(1, l, r);
      printf("%d %d\n", x.mx, x.cnt);
    }
  }
  return 0;
}