题解 P1531 【I Hate It】

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

————

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

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

 struct node{
     int l, r;
     int val;
 } tree[maxn * ];

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

 void Build(int l, int r, int pos) { //
     tree[pos].l = l;
     tree[pos].r = r;
     if(l == r) {
         int a;
         a = read();
         tree[pos].val = a;
     }
     else {
         int mid = (l + r) >> ;
         Build(l, mid, pos * );
         Build(mid + , r, pos *  + );
         tree[pos].val = max(tree[pos * ].val, tree[pos *  + ].val);
     }
 }

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

 void Update(int l, int r, int d, int pos) {
     if(tree[pos].l == l && tree[pos].r == r) {
         tree[pos].val = max(d, tree[pos].val);
         return ;
     }
     int mid = (tree[pos].l + tree[pos].r) >> ;
     if(r <= mid) Update(l, r, d, pos * );
     else if(l > mid) Update(l, r, d, pos *  + );
     else {
         Update(l, mid, d, pos * );
         Update(mid + , r, d, pos *  + );
     }
     tree[pos].val = max(tree[pos * ].val, tree[pos *  + ].val);
 }

区间查询函数：

其实流程和修改挺像的。

 int Query(int l, int r, int pos) {
     if(tree[pos].l == l && tree[pos].r == r) {
         return tree[pos].val;
     }
     int mid = (tree[pos].l + tree[pos].r) >> ;
     if(r <= mid) return Query(l, r, pos * );
     else if(l > mid) return Query(l, r, pos *  + );
     else {
         return max(Query(l, mid, pos * ), Query(mid + , r, pos *  + ));
     }
 }

主要处理部分：

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

 scanf("%s", &op);
         l = read(); r = read();
         if(op == 'Q') printf("%d\n", Query(l, r, ));
         else Update(l, l, r, );

emmm….大概就这么多了。

代码64ms，氧化后36ms。