给定二维平面中的垂直于 x 轴正半轴的线段，求与原点(0,0)连线中不与任何线段相交的线条条数
线段树维护 记 cnt[rt] 为 rt 所表示的线段 [l,r] 中可见的线段条数 sum[rt] 为 rt 表示的线段 [l,r] 中最大的斜率 对于当前修改的线段，其左边的原先保存的答案依然可行 对于其右边的线段，划分成左右子区间，如果左子区间的最大斜率比更新值要小，直接统计右端点答案，否则统计左子区间的答案，再加上右子区间的答案，注意右子区间的答案为 cnt[rt]−cnt[rt<<1] (因为要加上左子区间的约束条件)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int MAXN = 100000+10; double sum[MAXN<<2]; LL cnt[MAXN<<2],n,m,x,y; LL calc(int rt,int l,int r,double h) { if(l==r) return sum[rt]>h; int mid=(l+r)>>1; if(sum[rt<<1]<=h) return calc(rt<<1|1,mid+1,r,h); return calc(rt<<1,l,mid,rt)+cnt[rt]-cnt[rt<<1]; } void updata(double val,int x,int l,int r,int rt) { if(l==r) { sum[rt]=val; cnt[rt]=1; return ; } int mid=(l+r)>>1; if(x<=mid) updata(val,x,l,mid,rt<<1); else updata(val,x,mid+1,r,rt<<1|1); sum[rt]=max(sum[rt<<1],sum[rt<<1|1]); cnt[rt]=cnt[rt<<1]+calc(rt<<1|1,mid+1,r,sum[rt<<1]); } int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { scanf("%lld%lld",&x,&y); updata( (double)y/x,x,1,n,1 ); printf("%lld\n",cnt[1]); } return 0; }