洛谷P4198 楼房重建

题意：给定序列，每次修改一个值，求前缀最大值的个数。

解：线段树经典应用。

每个节点维护最大值和该区间前缀最大值个数。

发现我们不用下传标记，只需要合并区间。

需要实现一个函数int ask([l r] lm)求出区间[l r]中前一个数是lm时前缀最大值个数。

那么当lm >= large[ls]时，return ask([mid r] lm)

这个很好理解，左子区间的所有数都不会成为前缀最大值。

当lm < large[ls]时，return ask([l mid] lm) + (sum[o] - sum[ls])

这个注意，不是sum[rs]因为sum[rs]的意义是从0开始，而这个的前面会有large[ls]挡着，所以是sum[o] - sum[ls]

修改的时候先一路到底把large值改了。然后return的时候把沿途区间都更新。

具体来说就是sum[o] = ask([l r] 0)...等等，好像有问题。

lm < large[ls]的时候，求值是要调用sum[o]的，这不就循环调用导致出错了吗？

所以写成sum[o] = sum[ls] + ask([mid r] large[ls])即可。

本题不用建树。需要建树的时候就跟修改类似的写法即可。

 #include <cstdio>

 #include <algorithm>

 const int N = ;

 double a[N], large[N << ];

 int n, sum[N << ];

 int ask(int l, int r, int o, double lm) {

     if(l == r) {

         return (lm < a[r]);

     }

     int mid = (l + r) >> ;

     if(lm > large[o << ]) {

         return ask(mid + , r, o <<  | , lm);

     }

     else {

         return sum[o] - sum[o << ] + ask(l, mid, o << , lm);

     }

 }

 void change(int p, double v, int l, int r, int o) {

     if(l == r) {

         large[o] = v;

         sum[o] = ;

         return;

     }

     int mid = (l + r) >> ;

     if(p <= mid) {

         change(p, v, l, mid, o << );

     }

     else {

         change(p, v, mid + , r, o <<  | );

     }

     large[o] = std::max(large[o << ], large[o <<  | ]);

     sum[o] = sum[o << ] + ask(mid + , r, o <<  | , large[o << ]);

     return;

 }

 int main() {

     int m;

     scanf("%d%d", &n, &m);

     for(int i = , x, y; i <= m; i++) {

         scanf("%d%d", &x, &y);

         a[x] = (double)(y) / x;

         change(x, a[x], , n, );

         printf("%d\n", sum[]);

     }

     return ;

 }

AC代码

巴特西

洛谷P4198 楼房重建

最新文章

热门文章