定制网站开发哪里好,网站建设导向,网站被k十大原因,宠物网站设计案例luogu 楼房重建problemsolutioncodeproblem
洛谷链接
solution
非常巧妙的一道题#xff0c;对线段树的运用很灵活。
显然这个与原点的连线可以想到将每个点转化为与原点连线形成的直线斜率。
答案其实就是#xff1a;从第一个点开始选#xff0c;后一个斜率比前面大的…
luogu 楼房重建problemsolutioncodeproblem
洛谷链接
solution
非常巧妙的一道题对线段树的运用很灵活。
显然这个与原点的连线可以想到将每个点转化为与原点连线形成的直线斜率。
答案其实就是从第一个点开始选后一个斜率比前面大的必须选否则即小于等于则必须不选的选择个数。
区间是固定的且左边的一些信息影响右边每次还要单点修改可以联想到线段树。
这个线段树没有懒标记自然也没有下放标记操作。唯一的难点就是在于合并操作的实现。
线段树区间 [l,r][l,r][l,r] 维护从 lll 开始选按照答案的规则选出的个数答案。
最终输出线段树节点 111 表示 [1,n][1,n][1,n] 区间的答案即可。
显然一段区间的第一个一定被选一段区间中的最大值也一定被选。
而一段区间的最大值会影响后面区间的可选值所以还要维护一个区间 [l,r][l,r][l,r] 中最大的斜率。
考虑左右儿子具体怎么合并给父亲。
首先左儿子合并上去后做的是开头部分所以左儿子的答案一定贡献。
其次左儿子一定会选其区间内的斜率最大值而右儿子的斜率都必须大于这个最大值。
这里我们采取递归实现合并方式pushup(now,l,r,k) 表示要求线段树 nownownow 节点代表的区间 [l,r][l,r][l,r] 选择的斜率必须大于 kkk 的答案。
一开始是要求右儿子选择整体要大于左儿子的斜率最大值的。
t[now].ans t[lson].ans pushup( rson, mid 1, r, t[lson].Max );然后开始递归考虑右儿子的子树即具体的 pushup 实现。 如果节点内的最大值都不超过要求的斜率直接返回。 if( t[now].Max k ) return 0;如果左区间的最大值都不超过要求的斜率那么直接找右区间即可。 if( t[lson].Max k ) return pushup( rson, mid 1, r, k );否则就要去找左区间的答案。左区间既然有些要被选那么就没有影响右区间的开始直接统计右区间的答案。 而右区间的答案不是 t[rson].ans 而是 t[now].ans-t[lson].ans。 因为右区间可能有些会被左区间挡住不能选就只能换一种方法表示了。 return pushup( lson, l, mid, k ) t[now].ans - t[lson].ans;走到叶子节点就直接判断是否大于要求的斜率即可。 if( l r ) return t[now].Max k;trick 可以记录一下横坐标为 lll 的点与原点形成直线的斜率。 如果这个斜率就一定大于要求值的话那么就相当于从 lll 开始按照规则选的个数。 即线段树上 [l,r][l,r][l,r] 区间维护的信息那么直接返回就不用再往下操作了。 if( g[l] k ) return t[now].ans;code
#include bits/stdc.h
using namespace std;
#define maxn 100005
struct node { double Max; int ans; }t[maxn 2];
double g[maxn];#define lson now 1
#define rson now 1 | 1
#define mid ( ( l r ) 1 )int pushup( int now, int l, int r, double k ) {if( t[now].Max k ) return 0;if( k g[l] ) return t[now].ans;if( l r ) return t[now].Max k;if( t[lson].Max k ) return pushup( rson, mid 1, r, k );else return pushup( lson, l, mid, k ) t[now].ans - t[lson].ans;
}void modify( int now, int l, int r, int x, int y ) {if( l r ) { t[now].Max 1.0 * y / x, t[now].ans 1; return; }if( x mid ) modify( lson, l, mid, x, y );else modify( rson, mid 1, r, x, y );t[now].Max max( t[lson].Max, t[rson].Max );t[now].ans t[lson].ans pushup( rson, mid 1, r, t[lson].Max );
}int main() {int n, m, x, y;scanf( %d %d, n, m );while( m -- ) {scanf( %d %d, x, y );g[x] 1.0 * y / x;modify( 1, 1, n, x, y );printf( %d\n, t[1].ans );}
}
