线段树题目记录
本来想写成线段树学习笔记的，无奈太懒了，先记录下来吧，这篇文章会不断更新的。
hdu1166敌兵布阵
线段树的入门题,更新结点，查询区间和。
hdu1754 I Hate It
入门题，更新结点，查询区间最大值
hdu 1698 Just a Hook
更新一段区间上的颜色，求值。学习了懒操作。
poj 2777 Count Color
给区间染色，求一段区间内颜色的种数。学会了线段树的新写法以及位操作。
hdu 2795 Billboard
题意：一个公告牌长为h，宽为w。每张公告的长为1，宽为wi。贴公告时优先贴最上一行，尽量往左贴。现有一批公告，请给出每个公告所在行的行号，如果不能贴，就输出-1；
解析：把公告板逆时针转90度，这时候题目就转化成从左往右找一个点，这个点的值加上wi小于等于w。给线段树的结点加一个元素Min记录当前区间最低点的高度。这样每当要插入一个公告，我们就二分区间找一个Min+wi<=w的点。如果当前区间最低点加wi都大于w，那么该区间肯定放不进这个公告。找到结点后插入，从底往上更新区间的最低点高度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <cstdio>#include <iostream>using namespace std;struct SegTree{ int left,right; int Min;}st[800000];int h,w;void Build(int l,int r,int idx){ st[idx].left=l; st[idx].right=r; st[idx].Min=0; if(l==r)return; int mid=(l+r)>>1; Build(l,mid,idx*2); Build(mid+1,r,idx*2+1);}void Insert(int l,int r,int idx,int val){ if(st[idx].left==l&&st[idx].right==r) { st[idx].Min+=val; return; } int mid=(st[idx].left+st[idx].right)>>1; if(r<=mid) Insert(l,r,idx*2,val); else if(l>mid) Insert(l,r,idx*2+1,val); else { Insert(l,mid,idx*2,val); Insert(mid+1,r,idx*2+1,val); } st[idx].Min=min(st[idx*2].Min,st[idx*2+1].Min);}int Query(int idx,int val){ if(st[idx].left==st[idx].right) { if(val+st[idx].Min<=w) return st[idx].left; else return -1; } if(st[idx].Min+val>w) return -1; if(st[idx*2].Min+val<=w) return Query(idx*2,val); else return Query(idx*2+1,val);}int main(){ int N; while(scanf("%d%d%d",&h,&w,&N)!=EOF) { int len=min(h,N); Build(1,len,1); for(int i=1,val;i<=N;i++) { scanf("%d",&val); int pos=Query(1,val); if(pos!=-1) { printf("%d\n",pos); Insert(pos,pos,1,val); } else printf("%d\n",pos); } } return 0;} |
poj 3667 Hotel
题意：模拟宾馆的开房退房过程，有点类似内存的申请，当入住时，输入人数，在空的房里从尽量少的房间号开始连续选取D个房间，输出起始房间号;当退房时，输入开始位置和要退的房间数，把这些连续的房间清空。
解析：膜拜小HH的思路，线段树的结点添加三个元素，lval,rval,tot,lval表示从线段树的左端点开始最长的空余长度，rval表示从线段的右端点开始最长的空余长度，tot表示这段区间里面最长的空余长度。每当有入住申请时，优先在左子树找空余的区间，否则看左子树的rval+右子树的lval（即区间的中间一段），否则看右子树。
1 2 3 4 5 6 7 8 | if(st[idx*2].tot>=w) return Query(w,idx*2);else if(st[idx*2].rval+st[idx*2+1].lval>=w) return st[idx*2].right-st[idx*2].rval+1;else if(st[idx*2+1].tot>=w) return Query(w,idx*2+1);else return 0; |
而插入的时候自底向上更新
1 2 3 4 5 6 7 8 9 10 11 12 | int mid=(st[idx].left+st[idx].right)>>1;if(l<=mid) Update(l,r,flag,idx*2);if(r>mid) Update(l,r,flag,idx*2+1);st[idx].tot=max(st[idx*2].rval+st[idx*2+1].lval,max(st[idx*2].tot,st[idx*2+1].tot));st[idx].lval=st[idx*2].lval;st[idx].rval=st[idx*2+1].rval;if(st[idx*2].tot==st[idx*2].dis()) st[idx].lval+=st[idx*2+1].lval;if(st[idx*2+1].tot==st[idx*2+1].dis()) st[idx].rval+=st[idx*2].rval; |
poj 1436 Horizontally Visible Segments
题意：水平可视：如果两竖直线段之间可以有一条水平线穿过，且该水平线不穿过其他线段，那么这里竖直线段是水平可视的，如果有三天边两两都是水平可视的，那么称这三条边构成triangle of segments，问给定的线段能构成多少个triangle of segments。
解析：类似区间染色，把线段一层一层盖在区间上，盖的过程中如果区间已经有颜色且区间上的颜色没有跟当前插入的颜色关联（即水平可视）就把当前颜色插入到区间颜色邻接表中。首先我们按照线段的x坐标从小到大排序，然后依次插入线段，插入前先Query。最后暴力寻找两两间可见的三个线段。