题目

题解

首先转化成到(0,0)(0,0)(0,0)的斜率。

那么就是求多少个点是前缀最大值。

做法是线段树，用gao(i,x)gao(i,x)gao(i,x)表示在iii区间内，之前最大值为xxx的答案。

然后发现gao(p→r,p→l→max)gao(p\to r,p\to l\to max)gao(p→r,p→l→max)就是gao(p,0)−gao(p→l,0)gao(p,0)-gao(p\to l,0)gao(p,0)−gao(p→l,0)，所以直接用数组存一下gao(i,0)gao(i,0)gao(i,0)。代码极短，30行。

CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

int n, m, ans[MAXN<<2];

double mx[MAXN<<2];

int query(int i, int l, int r, double v) {

	if(l == r) return mx[i] > v;

	if(mx[i] <= v) return 0;

	int mid = (l + r) >> 1;

	if(mx[i<<1] <= v) return query(i<<1|1, mid+1, r, v);

	return query(i<<1, l, mid, v) + ans[i]-ans[i<<1];

}

void mdf(int i, int l, int r, int x, double v) {

	if(l == r) { mx[i] = v; ans[i] = 1; return; }

	int mid = (l + r) >> 1;

	if(x <= mid) mdf(i<<1, l, mid, x, v);

	else mdf(i<<1|1, mid+1, r, x, v);

	mx[i] = max(mx[i<<1], mx[i<<1|1]);

	ans[i] = ans[i<<1] + query(i<<1|1, mid+1, r, mx[i<<1]);

}

int main () {

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

	int x, y;

	while(m--) {

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

		mdf(1, 1, n, x, 1.0*y/x);

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

	}

}

巴特西

Luogu P4198 楼房重建（李超线段树）

题目

题解

CODE

最新文章

热门文章

巴特西

Luogu P4198 楼房重建 （李超线段树）

题目

题解

CODE

最新文章

热门文章

Luogu P4198 楼房重建（李超线段树）