洛谷 P4198 楼房重建

思路

此题可转化为以下模型

给定序列(a[1…n]),支持单点修改,每次求区间单调大小

(n,Qle 10^5)

区间单调栈是什么呢?对于一个区间,建立一个栈,首先将第一个元素入栈,从左往右扫,如果当前元素大于等于栈顶元素,就将其入栈,由此形成的栈即为单调不减的区间单调栈。

转化一下,其实就是求区间内满足(a[i]=maxlimits_{j=1}^ia[j])(a[i])的个数。

一个自然的想法是维护单调栈的大小(siz),那么如何去进行区间的合并呢?

合并两个子区间时,假设左子区间为(L),右子区间为(R),考虑合并之后的单调栈的组成部分:

  • 第一部分:(L)的单调栈

    因为单调栈是从左往右做的,所以(L)的单调栈必然是大区间单调栈的一部分

  • 剩余部分

    设出函数(calc(now,pre))(now)表示当前节点,(pre)表示当前单调栈的栈顶,(calc)函数计算剩余部分的单调栈的大小

总的单调栈大小(siz)就是(L_{siz}+calc(R,L_{max}))

calc的实现

现在有(calc(now,pre))(l)表示(now)的左子树,(r)表示(now)的右子树

  • 如果(pre>l_{max}),说明整个左子区间都不用考虑了,此时答案就变成了(calc(r,pre))
  • 如果(prele l_{max}),此时(l)是有贡献的,他对(siz)的贡献就是(calc(l,pre)),右子树的贡献为(calc(r,l_{max})),总贡献就是(calc(l,pre)+calc(r,l_{max}))

至此(calc)就推完了,但是我们发现如果仅仅是这样的话,在最坏的情况下,复杂度会爆炸,那么怎么优化呢?

观察(calc(r,l_{max})),发现它就等于(siz-l_{siz}),所以第二种情况就可以变成(calc(l,pre)+siz-l_{siz}),其中(siz)都是可以处理好的

这样我们就可以在(O(log n))的时间里完成一次合并

总时间复杂度(O(Qlog^2 n))

代码

/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;

const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

double val;
int n, m, ans, pos;
struct node { double maxn; int siz; } a[A << 2];

void build(int rt, int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(lson, l, mid), build(rson, mid + 1, r);
}

inline int calc(int rt, int l, int r, double h) {
  if (l == r) return a[rt].maxn > h;
  int mid = (l + r) >> 1;
  if (a[lson].maxn <= h) return calc(rson, mid + 1, r, h);
  return calc(lson, l, mid, h) + a[rt].siz - a[lson].siz;
}

inline void update(int rt, int l, int r) {
  if (l == r) {
    a[rt].maxn = val, a[rt].siz = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) update(lson, l, mid);
  else update(rson, mid + 1, r);
  a[rt].maxn = max(a[lson].maxn, a[rson].maxn);
  a[rt].siz = a[lson].siz + calc(rson, mid + 1, r, a[lson].maxn);
}

int main() {
  n = read(), m = read();
  build(1, 1, n);
  while (m--) {
    int x = read(), y = read();
    pos = x, val = (double) y / x;
    update(1, 1, n);
    cout << a[1].siz << 'n';
  }
}
本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 洛谷 P4198 楼房重建

发表评论

免登录下载网,提供全网最优质的资源集合!