2023.8.6

yduck / 2023-08-06 / 原文

日常做题

1. P4198 楼房重建

非常离谱的线段树题，反正我当时看了标签是想不出来怎么线段树的。题意就是求斜率单调上升的序列长度（以下简称该序列为答案序列）。好，我们尽力地去想一下线段树怎么做。同样记左区间、右区间节点为 \(p1, p2\) ，我们考虑维护区间的答案长度，记为 \(len\) 。很快就会发现，合并起来非常难搞，貌似只有O(n)的复杂度做法。这时，我们就尝试着再多维护一个值：区间斜率最大值，记为 \(v\) 。同时我们也可以观察到，显然，两个区间合并时，左区间的答案序列必定是会保留的。那么，我们现在处理右区间就好了。若右区间的最大值小于等于左区间的最大值，那么很明显，右区间的答案序列必然无法对总的答案产生贡献。而当右区间的最大值大于左区间的最大值时，我们就试着递归处理, 求出右区间可以保留的答案序列（此时以下的区间均为目前区间的子区间，即意味着的以下的 \(v, len\)均已知）：

传入左区间最大值，记为 \(lmax\)。

当 \(l == r\) 时，直接返回 \(v > lmax\) 的值即可。
当当前区间的左区间最大值小于等于 \(lmax\) 时，直接在右区间递归即可。
当当前区间的左区间最大值大于 \(lmax\) 时，这个时候，右区间的答案我们就可以直接O(1)算出来了：\(len - p1.len\)。既然左区间的 \(v\) 已经大于 \(lmax\) ，那么右区间的答案序列不就都可以保留嘛，那么它的长度就是 \(len - p1.len\) 。因此只需再在左区间递归即可。

容易证明，此操作的复杂度为 \(O(log n)\)，加上线段树查询的复杂度，最后就是 \(O(n log^2n)\) 。

code:

点击查看代码

#include<bits/stdc++.h>
using namespace std;

#define N 100010
#define p1 p * 2
#define p2 p * 2 + 1
#define tl tree[p].l
#define tr tree[p].r

struct xds{
  int l, r;
  double v;
  int len;
}tree[N * 4];

int n, m;

int l(int p, double mv){                            //查找区间p中斜率大于mv的单调上升序列长度
  if(tree[p].v <= mv) return 0;
  if(tl == tr){
    return tree[p].v > mv;
  }
  if(tree[p1].v <= mv) return l(p2, mv);           
  return l(p1, mv) + tree[p].len - tree[p1].len;
}

void pushup(int p){
  tree[p].v = max(tree[p1].v, tree[p2].v);
  tree[p].len = tree[p1].len + l(p2, tree[p1].v);
}

void build(int p, int l, int r){                    //建树
  tl = l, tr = r;
  if(l == r){tree[p] = {l, r, 0, 0}; return ;}      //注意：刚开始区间长度不能设为1
  int mid = l + r >> 1;
  build(p1, l, mid);
  build(p2, mid + 1, r);
  pushup(p);
}

void change(int p, int x, int y){                       //修改的同时返回答案
  // cout << p << " " << x << " " << y << endl;
  if(tl == tr){tree[p].v = (double) y / x, tree[p].len = 1; return ;}     //直到修改时才能把区间长度设为1
  int mid = tl + tr >> 1;
  if(x <= mid) change(p1, x, y);
  else change(p2, x, y);
  pushup(p);
  // cout << p << " " << x << " " << y << " " << tree[p].v << " " << tree[p].len << endl;
}

int main(){
  freopen("shuju.in", "r" ,stdin);
  freopen("shuju.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  build(1, 1, n);
  while(m--){
    int x, y;
    cin >> x >> y;
    change(1, x, y);
    cout << tree[1].len << endl;
  }
  return 0;
}