深圳电子商务网站有哪些,网站建设与更新,企业展厅设计公司盛世笔特,网站总体设计方案我一开始没有想到用线段树#xff0c;是我学得太僵了... 我们要记录每段的最大高度#xff0c;而且要组织成区间信息#xff0c;这要用到线段树 怎么用呢#xff1f; 线段树维护区间最大值#xff1b;对于每个线段#xff0c;先二分至其包含区间#xff0c;如果最大值是我学得太僵了... 我们要记录每段的最大高度而且要组织成区间信息这要用到线段树 怎么用呢 线段树维护区间最大值对于每个线段先二分至其包含区间如果最大值就能把这个区间赋值 优化如果最小值即可返回 这道题算是一个线段树的小魔改吧... 我们发现对于线段树查询和修改两个操作是可以合在一起的找区间也不是固定的可以根据区间信息二分至我们目标的区间 #includeiostream
#includecstdio
#includecstringusing namespace std;const int N1e53,V1e53;struct line{int l,r,h;
}a[N];struct sgt{int mn,mx;int st;
}R[V2];int gl;
void push_down(int o,int l,int r){if(R[o].st){R[o1].mxR[o1|1].mxR[o1].mnR[o1|1].mnR[o].st;R[o1].stR[o1|1].stR[o].st;R[o].st0;}
}
void push_up(int o,int l,int r){R[o].mxmax(R[o1].mx,R[o1|1].mx);R[o].mnmin(R[o1].mn,R[o1|1].mn);
}
int modify(int o,int l,int r)
{if(a[gl].lla[gl].rr){if(R[o].mxa[gl].h){R[o].mxR[o].mna[gl].h;R[o].sta[gl].h;return r-l1;}else if(R[o].mna[gl].h)return 0; }push_down(o,l,r);int mid(lr)1,ret0;if(a[gl].lmid)retmodify(o1,l,mid);if(a[gl].rmid)retmodify(o1|1,mid1,r);push_up(o,l,r);return ret;
}int main()
{int T;scanf(%d,T);while(T--){int n;scanf(%d,n);int bd0;for(int i1;in;i)scanf(%d%d%d,a[i].l,a[i].r,a[i].h),a[i].r--,bdmax(bd,a[i].r);int ans0;memset(R,0,sizeof R);for(int i1;in;i){gli;ansmodify(1,1,bd);}printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/mgnfcnt/p/9464389.html
