题解 P1531 【I Hate It】

斯茂 · 2018-06-02 16:57:00 · 题解

模拟是个好东西

有人说这题线段树？树状数组？

其实模拟就能过了，此方法时间复杂度O(mn)，但是过了，可能是数据太水了吧......

下面是代码：

#include <iostream>
using namespace std;
struct stu
{
  int n, s;
};
stu s[200005];
int find(int l, int r)
{
  int i, max = -1;
  for(i = l; i <= r; i++)
    if(s[i].s > max)
      max = s[i].s;
  return max;
}
int main(int argc, char** argv) {
    int m, n, i;
    char t;
    int t1, t2;
    cin >> n >> m;
    for(i = 1; i <= n; i++)
    {
      cin >> s[i].s;
      s[i].n = i;
    }
    while(m--)
    {
      cin >> t >> t1 >> t2;
      if(t == 'Q')
        cout << find(t1, t2) << endl;
      else
        if(s[t1].s < t2)
          s[t1].s = t2;
    }
    return 0;
}