luogu P4198 楼房重建
这道题就是用线段树维护一个斜率"强制"递增序列元素个数 其他的都不必多说,主要难点在于在pushup时怎样更新个数 当时我脑残就直接用vector保存下序列,然后二分更新,实测只有10分 其实完全不必记录序列,只要把区间内最大值记录下来即可 但这样面临的问题就是没有办法二分,于是通过看题解便想到了递归处理 具体来说增加一个count函数,用来找一个区间内的满足条件的序列元素个数 最初只需进入右区间,count(p*2+1,mx[p*2]),同时要满足限制必须大于左区间的最大值; 分几种情况: 当l(p)==r(p)时,递归入边界,return mx(p)>k; (k是最开始传入的mx[p*2]); 当mx(p*2)<=k时,只需进入右区间,return count(p*2+1,k); else return len(p)-len(p*2)+count(p*2,k); (当mx[p*2]>k时,右区间内都满足条件,进入左区间递归,注意考虑左区间的遮挡,而不是len(p*2+1) ); (太难了,想不到) 上代码: #include<iostream> #include<cstdio> using namespace std; int n,m; struct Node{ int l,r,len; double mx; #define l(x) t[x].l #define r(x) t[x].r #define len(x) t[x].len #define mx(x) t[x].mx }t[400010]; void build(int p,int l,int r){ l(p)=l;r(p)=r; if(l==r){ return; } int mid=(l+r)>>1; build(p*2,l,mid);build(p*2+1,mid+1,r); } int count(int p,double k){ if(l(p)==r(p)) return mx(p)>k; if(mx(p*2)<=k) return count(p*2+1,k); else return len(p)-len(p*2)+count(p*2,k); } void change(int p,int x,double k){ if(l(p)==r(p)){ mx(p)=k;len(p)=1; return; } int mid=(l(p)+r(p))>>1; if(x<=mid) change(p*2,x,k); else change(p*2+1,k); mx(p)=max(mx(p*2),mx(p*2+1)); len(p)=len(p*2)+count(p*2+1,mx(p*2)); } int main(){ scanf("%d%d",&n,&m); build(1,1,n); while(m--){ double x,y;scanf("%lf%lf",&x,&y);double tan=y/x; change(1,tan);printf("%dn",len(1)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |