同上同上,在自己的电脑上都能过(下了第一个点是对的),但是交上去全是WA。。。
代码:
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
//P1531 I Hate it...
#define N 200005
#define len_Tree 1000005
#define ask_len 5005
#define INF 0x3f3f3f3f
using namespace std;
int read()
{
char ch = ' ', last;
int ans = 0;
while (ch < '0' || ch > '9')
last = ch, ch = getchar();
while (ch >= '0' && ch <= '9')
ans = ans * 10 + int(ch - '0'), ch = getchar();
if(last == '-' )
return -ans;
return ans;
}
//head
int n, m, dat[N], a, b, Segment_Tree[len_Tree] = { 0 }, cnt = 0;
char c;
//variable
void build(int o, int l, int r)
{
if (l == r)
Segment_Tree[o] = dat[l];
else
{
int mid = (l + r) / 2;
build(o * 2, l, mid);
build(o * 2 + 1, mid + 1, r);
Segment_Tree[o] = max(Segment_Tree[o * 2], Segment_Tree[o * 2 + 1]);
}
}
void modify(int o, int l, int r, int L, int R, int val)
{
if (L == l && R == r)
Segment_Tree[o] = max(Segment_Tree[o], val);
else
{
int mid = (l + r) / 2;
if (R <= mid)
modify(o * 2, l, mid, L, R, val);
else if (L > mid)
modify(o * 2 + 1, mid + 1, r, L, R, val);
else
modify(o * 2, l, mid, L, R, val), modify(o * 2 + 1, mid + 1, r, L, R, val);
Segment_Tree[o] = max(Segment_Tree[o * 2], Segment_Tree[o * 2 + 1]);
}
}
int ask(int o, int l, int r, int L, int R)
{
if (l >= L && r <= R)
return Segment_Tree[o];
else
{
int mid = (l + r) / 2;
if (R <= mid)
return ask(o * 2, l, mid, L, R);
else if (L > mid)
return ask(o * 2 + 1, mid + 1, r, L, R);
else
return max(ask(o * 2, l, mid, L, mid), ask(o * 2 + 1, mid + 1, r, mid + 1, R));
}
}
//functions
int main()
{
freopen("a.in", "r", stdin);//电脑上测试用的。。。
n = read(), m = read();
for (int i = 1; i <= n; i++)
dat[i] = read();
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
c = getchar(), a = read(), b = read();
if(c == 'Q')
cout << ask(1, 1, n, a, b) << endl;
if (c == 'U')
modify(1, 1, n, a, a, b);
}
return 0;
}
```
by Harmony @ 2018-02-17 14:14:53