题解 P1531 【I Hate It】

这道题明明是裸的线段树，蒟蒻却80分了五六次。。。

------------

根据题意，显然是维护一棵单点修改区间查询的线段树，于是直接套区间修改的代码。。。

结构体，即为树上的节点。

1 struct node{
2     int l, r;
3     int val;
4 } tree[maxn * 4];

建树，注意：将读入放到这里来！！原本是在main里面读入然后储存到stu数组中，结果就一直80分！!

 1 void Build(int l, int r, int pos) { //
 2     tree[pos].l = l;
 3     tree[pos].r = r;
 4     if(l == r) {
 5         int a;
 6         a = read();
 7         tree[pos].val = a;
 8     }
 9     else {
10         int mid = (l + r) >> 1;
11         Build(l, mid, pos * 2);
12         Build(mid + 1, r, pos * 2 + 1);
13         tree[pos].val = max(tree[pos * 2].val, tree[pos * 2 + 1].val);
14     }
15 }

区间修改函数：
1. 如果直接是要求的区间，直接修改即可。
2. 反之则分配到左右子树上面去。
3. 回溯。

 1 void Update(int l, int r, int d, int pos) {
 2     if(tree[pos].l == l && tree[pos].r == r) {
 3         tree[pos].val = max(d, tree[pos].val);
 4         return ;
 5     }
 6     int mid = (tree[pos].l + tree[pos].r) >> 1;
 7     if(r <= mid) Update(l, r, d, pos * 2);
 8     else if(l > mid) Update(l, r, d, pos * 2 + 1);
 9     else {
10         Update(l, mid, d, pos * 2);
11         Update(mid + 1, r, d, pos * 2 + 1);
12     }
13     tree[pos].val = max(tree[pos * 2].val, tree[pos * 2 + 1].val);
14 }

区间查询函数：

其实流程和修改挺像的。

 1 int Query(int l, int r, int pos) {
 2     if(tree[pos].l == l && tree[pos].r == r) {
 3         return tree[pos].val;
 4     }
 5     int mid = (tree[pos].l + tree[pos].r) >> 1;
 6     if(r <= mid) return Query(l, r, pos * 2); 
 7     else if(l > mid) return Query(l, r, pos * 2 + 1); 
 8     else {
 9         return max(Query(l, mid, pos * 2), Query(mid + 1, r, pos * 2 + 1));
10     }
11 }

主要处理部分：

read()是快速读入函数，然后要注意因为本题是单点修改，所以Update函数的l,r两个参数其实是一样的。

1 scanf("%s", &op);
2         l = read(); r = read();
3         if(op == 'Q') printf("%d
", Query(l, r, 1));
4         else Update(l, l, r, 1);

emmm....大概就这么多了。

代码64ms，氧化后36ms。