夏晓光(loveJY)的博客

合并需要log的线段树

其实本质上是线段树维护单调栈,但是我们直接在某个点上记录一整个栈不太阳间

我们会发现其实有很多儿子的信息我们没有很好利用,所以我们可以考虑用儿子节点的信息拼成一个单调栈合并的信息

单调栈合并的时候需要从后面某个地方砍一刀然后把后面剩下的地方接到前面去

所以这个也是一样的,我记录了区间最大值和区间单调栈长度直接写TLE了好几发

因为我是直接递归看看右边能不能再去划分,只用最大值当做剪枝的判据

所以这个是能被卡成$O(n^2)$的qwq两边都有可能递归

不被卡成$n^2$就要只递归一边......

如果左边最大值小于V,我们直接递归右边

否则我们能根据这个区间的单调栈长度和左区间的单调栈长度算出右边区间在左边成单调栈时的长度

换句话说:右边区间的长度就是$tr[k].L-tr[ls[k]].L$

这样就只递归左边即可

$O(nlog^2n)$

code:

#include<bits/stdc++.h>
#define db double
using namespace std;
#define sort(a,b) random_shuffle(a,b)
const int MAXN = 7e5 + 7;
const db eps = 1e-11;
int n, m, x, y;
struct rec {
	db Max;
	int L;//记录最大值和单调栈长度
	rec(int L = 0, db x = 0): Max(x), L(L) {};
} tr[MAXN];
db a[MAXN];
namespace seg {
	int ls[MAXN], rs[MAXN], T, root;
#define mid ((l+r)>>1)
	inline void build(int &k, int l, int r) {
		if(!k)k = ++T;
		if(l == r) {
			tr[k].Max = 0;
			tr[k].L = 1;
			return ;
		}
		build(ls[k], l, mid);
		build(rs[k], mid + 1, r);
		tr[k].L = 1;
	}
	inline int query(int k, int l, int r, db V) {
		if(tr[k].Max <= V)return 0;
		if(a[l] > V)return tr[k].L;
		if(l == r)return a[l] > V;
		int tmp = 0;
		if(tr[ls[k]].Max <= V) {
			return query(rs[k], mid + 1, r, V);
		} else {
			return query(ls[k], l, mid, V) + tr[k].L - tr[ls[k]].L;
		}
		return tmp;
	}
	inline int pushup(int k, int l, int r) {
		//找到第一个位置
		//然后再那个位置之后的区间都提出来
		// printf("in %d!%d %d\n", k, l, r);
		if(tr[rs[k]].Max - tr[ls[k]].Max > eps) {
			return query(rs[k], mid + 1, r, tr[ls[k]].Max) + tr[ls[k]].L;
		} else {
			// printf("?%d %lf\n", tr[ls[k]].L, tr[ls[k]].Max);
			return tr[ls[k]].L;
		}
	}
	inline void modify(int &k, int l, int r, int x, db V) {
		if(!k)k = ++T;
		if(l == r) {
			tr[k].Max = V;
			tr[k].L = 1;
			return ;
		}
		if(x <= mid)modify(ls[k], l, mid, x, V);
		else modify(rs[k], mid + 1, r, x, V);
		// printf("merge !:->%d %d %d\n", k, l, r);
		tr[k].L = pushup(k, l, r);
		tr[k].Max = max(tr[ls[k]].Max, tr[rs[k]].Max);
	}
}
using namespace seg;
int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d%d", &n, &m);
	// build(root, 1, n);
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		a[x] = (1.00 * y) / (1.00 * x);
		modify(root, 1, n, x, (1.00 * y) / (1.00 * x));
		printf("%d\n", tr[root].L);
	}
	return 0;
}