线段树_总结
1.单点更新，(单点查询，区间查询)
--------------------------------------------------------------
hdu1166 敌兵布阵
一个长度为N的数组，给出了值~
四种操作：
（1）”Add i j"，表示第i个营地增加j人
（2）“Sub i j”，表示第i个营地减少j人
（3）“Query i j"，查询第i个营地到第j个营地的总人数
（4）”End“，表示命令结束。
// 减法就是加法 区间成段的改变
void PushUp(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void Pushdown(int rt,int len){ if(col[rt]){ col[rt<<1] = col[rt<<1|1] = col[rt]; col[rt] = 0; sum[rt<<1] = val[rt] * (len - (len>>1)); sum[rt<<1|1] = val[rt] * (len>>1); val[rt<<1] = val[rt<<1|1] = val[rt]; }}void build(int l,int r,int rt){ val[rt] = 0; col[rt] = 0; if(l == r){ sum[rt] = 1; return ; } int m = (l + r)/2; build(lson); build(rson); PushUp(rt);}int query(int L,int R,int l,int r,int rt){ if(L <= l && r <= R){ return sum[rt]; } Pushdown(rt , r - l + 1); int m = (l + r)/2; int ret=0; if(L <= m) ret += query(L, R, lson); if(m < R) ret += query(L, R, rson); return ret;}hdu 4578 Transformation
n个数(初始化都为0),m个操作
操作1： 区间 [ x , y ] 内都加上c
操作2： 区间 [ x , y ] 内都乘上c
操作3： 区间 [ x , y ] 内都改成c
操作4： 区间 [ x , y ] 内p次方求和 (1 <= p <= 3)
区间更新的时候，分为三种，在区间PushUp的时候，保证两个儿子节点的值都更新，就把信息传递上去，
解题报告
---------------------------------------------------------------------
hdu 4614 Vases and Flowers
给定一个区间[0,N-1](初始化都为0),
有两种操作，
1.在位置A开始寻找F(如果没有这么多，则有多少个就找多少个)个数值为0的位置，把位置上的数修改为1,并返回第一个和最后一个修改的位置
2.查询区间[A,B]内1的个数，并把区间[A,B]每个位置上的数修改为0。
解题报告
---------------------------------------------------------------------
hdu 4325 Flowers
给出n朵花的在[s,t] 时间里开花，进行m次询问，每次给出时间t,问在这个时间开几朵花。
解题报告
---------------------------------------------------------------------
hdu 4107 Gangster
长度为N的数组,进行m次操作,每次对于给定的区间,若这个区间的数比p大.则+c,否则+2*c;
解题报告
----------------------------------------------------------------------
poj 3468 A Simple Problem with Integers
N个数，M个操作
有两种类型的操作
（1）“C a b c”，表示将区间[a,b]里的数加上c
（2）“Q a b”，表示查询区间[a,b]的数的和
解题报告
----------------------------------------------------------------------
poj 2528 Mayor's posters
贴海报~经典问题
解题报告
----------------------------------------------------------------------
3.区间合并
---------------------------------------------------------------------
hdu 3308 LCIS
长度为N的数组，进行m次操作，
分为两种操作：
操作1：U A B 把位置A上的更新为B,
操作2: Q A B 输出[A,B]上的最长连续上升子序列
解题报告
---------------------------------------------------------------------
poj 3368 Frequent values
一个长度为n的数组，进行m次询问，
每次询问给出一个区间，求出这个区间中的数出现的最多的次数
解题报告
---------------------------------------------------------------------
SPOJ GSS1 Can you answer these queries I
有一个长度为n的数组，进行m次操作，
每次给出一个区间，求给出该区间的最大子段和
解题报告
---------------------------------------------------------------------
SPOJ GSS3 Can you answer these queries III
解题报告
---------------------------------------------------------------------
SPOJ GSS5 Can you answer these queries V
给定一组数，同时给出[ x1 , y1 ],[ x2 , y2]两个区间，
从一区间找出 i, 从二区间找出 j ,使得a[ i ] + a[i + 1] + a[i + 2] ........+ a[ j ] 得到最大
解题报告
---------------------------------------------------------------------
4.扫描线
---------------------------------------------------------------------
poj 1151
解题报告
---------------------------------------------------------------------
5.其他
---------------------------------------------------------------------
hdu 4417
在长度为n的数组，进行m次询问，
每次给出一个区间[ L , R ]，同时给出H,求出这个区间中不大于H的数的个数
解题报告
---------------------------------------------------------------------
hdu 4027 and SPOJ GSS4 Can you answer these queries IV
解题报告
---------------------------------------------------------------------