這類題目會詢問區間中滿足條件的連續最長區間,所以PushUp的時候需要對左右兒子的區間進行合并（這里最難理解）

hdu 3308?http://acm.hdu.edu.cn/showproblem.php?pid=3308

題意：

給定n個數，下標從0-n-1,給出兩種操作Q x,y詢問區間[x,y]中的最長上升子序列(LCIS)， U x,y 將下表為x的值替換成y（單點更新）。輸出每次詢問的值。

思路：

U操作的單點更新就不必多說了，這里關鍵理解的是區間的合并；

節點信息：

struct node {int l,r;//記錄該節點的左右邊界int lm,rm,sm;//分別對應該點包括最左點的LCIS//包括最右點的LCIS，整個區間的LCIS }p[4*maxn];

　區間的合并發生在左孩子區間的最右點<右孩子區間的最左點 ?這樣兩個區間就可以發生合并了。

lm=（lm==左孩子的長度）？左孩子的lm+右孩子的lm：左孩子的lm;

rm= (rm==?右孩子的長度)?？右孩子的rm+左孩子的rm：右孩子的rm;

sm=max(max（左孩子的sm,右孩子的sm）,左孩子rm+右孩子的lm)

View Code #include<cstdio> #include<iostream> #define maxn 100007 using namespace std;struct node {int l,r;//記錄該節點的左右邊界int lm,rm,sm;//分別對應該點包括最左點的LCIS//包括最右點的LCIS，整個區間的LCIS }p[4*maxn]; int val[maxn];void pushup(int rt) {//如果不存在區間合并的話正常的更新p[rt].lm = p[rt<<1].lm;p[rt].rm = p[rt<<1|1].rm;p[rt].sm = max(p[rt<<1].sm,p[rt<<1|1].sm);int m = (p[rt].l + p[rt].r)>>1;//存在可合并的區間if (val[m] < val[m + 1]){int L = m - p[rt].l + 1;int R = p[rt].r - m;if (p[rt<<1].lm == L) p[rt].lm += p[rt<<1|1].lm;if (p[rt<<1|1].rm == R) p[rt].rm += p[rt<<1].rm;p[rt].sm = max(p[rt].sm,p[rt<<1].rm + p[rt<<1|1].lm);} } void build(int l,int r,int rt) {p[rt].l = l; p[rt].r = r;p[rt].lm = p[rt].rm = p[rt].sm = 1;if (l == r){scanf("%d",&val[l]);return ;}int m = (l + r)>>1;build(l,m,rt<<1);build(m + 1,r,rt<<1|1);pushup(rt); } void update(int pos,int sc,int rt) {if (p[rt].l == p[rt].r){val[p[rt].l] = sc;return ;}int m = (p[rt].l + p[rt].r)>>1;if (pos <= m) update(pos,sc,rt<<1);else update(pos,sc,rt<<1|1);pushup(rt);}int query(int L,int R,int rt) {if (p[rt].l >= L && p[rt].r <= R) return p[rt].sm;int m = (p[rt].l + p[rt].r)>>1;int res = 0;if (L <= m) res = max(res,query(L,R,rt<<1));if (R > m) res = max(res,query(L,R,rt<<1|1));//分出的兩個小區間可以合并，記住這里有L，R左右臨界的限制。if (val[m] < val[m + 1])res = max(res,min(m - L + 1,p[rt<<1].rm) + min(R - m,p[rt<<1|1].lm));return res; }/*int query(int l,int r,int rt) {if(p[rt].l==l&&p[rt].r==r) return p[rt].sm;int m=(p[rt].l+p[rt].r)>>1;if(r<=m) return query(l,r,rt<<1);if(l>m) return query(l,r,rt<<1|1);int hhm=max(query(l,m,rt<<1),query(m+1,r,rt<<1|1));if(val[m]<val[m+1])hhm=max(hhm,min(m-l+1,p[rt<<1].rm)+min(r-m,p[rt<<1|1].lm));return hhm; }*/int main() {//freopen("3308.txt","r",stdin);int t,x,y,n,q;char op[2];scanf("%d",&t);while (t--){scanf("%d%d",&n,&q);build(0,n - 1,1);while (q--){scanf("%s%d%d",op,&x,&y);if (op[0] == 'Q')printf("%d\n",query(x,y,1));elseupdate(x,y,1);}}return 0; }

?

uestc 1425?http://acm.uestc.edu.cn/problem.php?pid=1425?

代碼還沒提交，指引本oj今天打不開

題意：

和上題題意一樣不同的是這里不是單純的更新一個點了，而是更新一段區間。就相當于區間合并+成段更新（上題是區間合并+單點更新）

思路：

同上，只不過在處理區間合并的判斷條件時有所不同，上題因為每次都能更新到葉節點所以不必擔心lz標記還沒更新下來這一說。而這里lz大多數情況下不能更新到葉節點也就導致在判斷區間合并的條件時產生了難點，才開始的時候我記錄了每個樹上節點總共加了多少add[rt]，樣例過了可是老是wa無語了，后來想了想，如果我的子區間被更新后那么我只記錄了子區間加了多少，而區間沒有被更新，所以add記錄的就是錯誤的信息了。

這里我們記錄每個區間的左右點的值，每次更新的時候往上更新就好了，這樣就保證了每個區間的左右端點值的正確性，因為我們在區間合并時需要的只是端點。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll long long #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 100007 #define N 100007 using namespace std;struct node{int lm,rm,sm;int l,r;int al,ar;//這里記錄左右端點信息int mid(){return (l + r)>>1;} }tre[N<<2]; int val[N],lz[N<<2],add[N<<2];void pushup(int rt,int Ls,int Rs,int m){tre[rt].lm = tre[rt<<1].lm;tre[rt].rm = tre[rt<<1|1].rm;tre[rt].sm = max(tre[rt<<1].sm,tre[rt<<1|1].sm);tre[rt].al = tre[rt<<1].al; tre[rt].ar = tre[rt<<1|1].ar;if (tre[rt<<1].ar < tre[rt<<1|1].al){if (tre[rt].lm == Ls) tre[rt].lm += tre[rt<<1|1].lm;if (tre[rt].rm == Rs) tre[rt].rm += tre[rt<<1].rm;tre[rt].sm = max(tre[rt].sm,tre[rt<<1].rm + tre[rt<<1|1].lm);} } void pushdown(int rt){if (lz[rt] != 0){lz[rt<<1] += lz[rt];lz[rt<<1|1] += lz[rt];tre[rt<<1].al += lz[rt];tre[rt<<1].ar += lz[rt];tre[rt<<1|1].al += lz[rt];tre[rt<<1|1].ar += lz[rt];lz[rt] = 0;} } void build(int l,int r,int rt){lz[rt] = 0;tre[rt].l = l; tre[rt].r = r;tre[rt].ar = tre[rt].al = 0;if (l == r){tre[rt].lm = tre[rt].rm = tre[rt].sm = 1;scanf("%d",&tre[rt].al);tre[rt].ar = tre[rt].al;return ;}int m = tre[rt].mid();build(lc);build(rc);pushup(rt,m - l + 1,r - m,m); } void update(int L,int R,int sc,int rt){if (tre[rt].l >= L && tre[rt].r <= R){lz[rt] += sc;tre[rt].al += sc;tre[rt].ar += sc;return ;}int m = tre[rt].mid();pushdown(rt);if (L <= m) update(L,R,sc,rt<<1);if (R > m) update(L,R,sc,rt<<1|1);pushup(rt,m - tre[rt].l + 1,tre[rt].r - m,m); } int query(int L,int R,int rt){if (tre[rt].l >= L && tre[rt].r <= R){return tre[rt].sm;}pushdown(rt);int res = 0;int m = tre[rt].mid();if (L <= m) res = max(res,query(L,R,rt<<1));if (R > m) res = max(res,query(L,R,rt<<1|1));if (tre[rt<<1].ar < tre[rt<<1|1].al){res = max(res,min(m - L + 1,tre[rt<<1].rm) + min(R - m,tre[rt<<1|1].lm));}pushup(rt,m - tre[rt].l + 1,tre[rt].r - m,m);return res; }int main(){//freopen("data.in","r",stdin);int cas = 1;int T,n,q;char op[3];int x,y,z;scanf("%d",&T);while (T--){printf("Case #%d:\n",cas++);scanf("%d%d",&n,&q);build(1,n,1);while (q--){scanf("%s%d%d",op,&x,&y);if (op[0] == 'a'){scanf("%d",&z);update(x,y,z,1);}else{printf("%d\n",query(x,y,1));}}}return 0; }

?

?

?

pku 3667?http://poj.org/problem?id=3667

題意：

旅游團入住旅館，旅館的房間在這里形式化為X正半軸上的點，來到的團隊必須住在連續的房間內，有兩種操作1 x就是旅游團入住在連續的x個房間內，2 ?xi di 旅游團將房間xi - xi + di - 1的房間退掉；求每次入住連續的x個房間時的起始房間號。

思路：

這里入住的話肯定是連續的房間，也即連續的點。線段樹區間的合并問題，這里節點記錄該區間的最大連續節點數，每次入住就是一個查詢滿足條件區間的過程，這里注意左右孩子區間合并時滿足的條件。向上更新時也是要判斷區間的合并。

View Code #include <iostream> #include <cstring> #include <cstdio> #define maxn 50007 using namespace std;int msum[4*maxn], lsum[4*maxn],rsum[4*maxn]; int lz[4*maxn];void pushup(int rt,int m) {lsum[rt] = lsum[rt<<1];rsum[rt] = rsum[rt<<1|1];msum[rt] = max(msum[rt<<1],msum[rt<<1|1]);//注意區間的合并if (lsum[rt<<1] == m - (m>>1)) lsum[rt] += lsum[rt<<1|1];if (rsum[rt<<1|1] == (m>>1)) rsum[rt] += rsum[rt<<1];msum[rt] = max(msum[rt],rsum[rt<<1] + lsum[rt<<1|1]); }void pushdown(int rt,int m) {if (lz[rt] != -1){lz[rt<<1] = lz[rt<<1|1] = lz[rt];msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = lz[rt] == 0? 0 : m - (m>>1);msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = lz[rt] == 0? 0: (m>>1);lz[rt] = -1;} }void build(int l,int r,int rt) {lz[rt] = -1;if (l == r){msum[rt] = lsum[rt] = rsum[rt] = 1;return ;}int m = (l + r)>>1;build(l,m,rt<<1);build(m + 1,r,rt<<1|1);pushup(rt,r - l + 1); }void update(int L,int R,int mk,int l,int r,int rt) {if (l >= L && r <= R){lz[rt] = mk;msum[rt] = lsum[rt] = rsum[rt] = mk == 0? 0: (r - l + 1);return ;}pushdown(rt,r - l + 1);int m = (l + r)>>1;if (L <= m) update(L,R,mk,l,m,rt<<1);if (R > m) update(L,R,mk,m + 1,r,rt<<1|1);pushup(rt,r - l + 1); }int query(int sc,int l,int r,int rt) {if (l == r) return l;pushdown(rt,r - l + 1);int m = (l + r)>>1;if (sc <= msum[rt<<1]) return query(sc,l,m,rt<<1);else if (rsum[rt<<1] + lsum[rt<<1|1] >= sc) return m - rsum[rt<<1] + 1;//注意合并區間時滿足的情況return query(sc,m + 1,r,rt<<1|1); }int main() {//freopen("d.in","r",stdin);int n,m,x,y,z;scanf("%d%d",&n,&m);build(1,n,1);while (m--){scanf("%d%d",&x,&y);if (x == 1){if (msum[1] < y) puts("0");else{int r = query(y,1,n,1);//找到起點update(r,r + y - 1,0,1,n,1);//然后將該區間更新printf("%d\n",r);}}else{scanf("%d",&z);update(y,y + z - 1,1,1,n,1);//更新該區見 }}return 0; }

?

pku 3368?Frequent values?http://poj.org/problem?id=3368

本來結束了線段樹的刷題去做rmq來看到了這道題目，rmq沒想出來可能是最近做線段樹的題目比較多吧，想到了線段樹解法。

題意：

給定長度為n的不降序列，求詢問區間[s,e]內出現頻率最高的頻率；

思路：

典型的區間合并做法，只有合并時的條件val[m] = val[m + 1]只滿足這一條件還不夠，只有lsum = L rsum = ?R 時才能進行合并 ，還有在query求值時寫錯了，是求最大值不是求左右值。

這題看解題報告大多數都是先離散化后再用rmq或者線段樹做的，我直接就區間合并了，少了離散化的處理，不過效率可能有點低。

View Code #include <cstdio> #include <cstring> #include <iostream> #include <cmath> #define maxn 100007 using namespace std;int msum[4*maxn],lsum[4*maxn],rsum[4*maxn]; int val[maxn];void pushup(int rt,int m,int len) {lsum[rt] = lsum[rt<<1];rsum[rt] = rsum[rt<<1|1];msum[rt] = max(msum[rt<<1],msum[rt<<1|1]);if (val[m] == val[m + 1]){int L = len - (len>>1);int R = len>>1;if (lsum[rt] == L)//第一個錯誤點，掉下了這個條件lsum[rt] += lsum[rt<<1|1];if (rsum[rt] == R)rsum[rt] += rsum[rt<<1];msum[rt] = max(msum[rt],rsum[rt<<1] + lsum[rt<<1|1]);}} void build(int l,int r,int rt) {if (l == r){scanf("%d",&val[l]);msum[rt] = lsum[rt] = rsum[rt] = 1;return ;}int m = (l + r)>>1;build(l,m,rt<<1);build(m + 1,r,rt<<1|1);pushup(rt,m,r - l + 1); } int query(int L,int R,int l,int r,int rt) {if (l >= L && r <= R){//printf("%d %d\n",l,r);return msum[rt];}int res = 0;int m = (l + r)>>1;if (L <= m) res = max(res,query(L,R,l,m,rt<<1));//第二個錯誤點掉下max函數了if (R > m) res = max(res,query(L,R,m +1,r,rt<<1|1));if (val[m] == val[m + 1])res = max(res,min(m - L + 1,rsum[rt<<1]) + min(R - m,lsum[rt<<1|1]));return res; } void set(int l,int r,int rt) {printf("%d %d %d %d %d\n",l,r,msum[rt],lsum[rt],rsum[rt]);if (l == r){return ;}int m = (l + r)>>1;set(l,m,rt<<1);set(m + 1,r,rt<<1|1); } int main() {//freopen("d.txt","r",stdin);int n,q;int s,e;while (~scanf("%d",&n)){if (!n) break;scanf("%d",&q);build(1,n,1);while (q--){scanf("%d%d",&s,&e);printf("%d\n",query(s,e,1,n,1));}//set(1,n,1); }return 0; }

?

?pku?Tunnel Warfare?http://poj.org/problem?id=2892?&&　hdu 1540 ?http://acm.hdu.edu.cn/showproblem.php?pid=1540

題意：

在抗日戰爭時期的地道戰，很是出名，這里給出n個地道，他們是相互連同在一條通道上的，然后給出q個操作，分別有

D x經編號為x的地道摧毀, Q x 詢問x可以連同的地道數目 R恢復前一個被摧毀的地道。

思路：

這里主要是記錄每個點對應的lsum rsum難點在于Q詢問時的操作，以前做的都是區間里面的詢問這里是對點的詢問，對點的詢問時，我們只要找到

pos >= m - rsum[rt<<1] + 1 && pos <= m + lsum[rt<<1|1] ?區間[m - rsum[rt<<1] + 1，pos <= m + lsum[rt<<1|1] 即可返回該區間的長度；

View Code #include <cstdio> #include <cstring> #include <cstdlib> #include <map> #define maxn 50005 using namespace std;int lsum[4*maxn],rsum[4*maxn]; int stack[maxn],top;void pushup(int rt,int m) {lsum[rt] = lsum[rt<<1];rsum[rt] = rsum[rt<<1|1];if (lsum[rt] == (m - (m>>1))) lsum[rt] += lsum[rt<<1|1];if (rsum[rt] == (m>>1)) rsum[rt] += rsum[rt<<1]; } void build(int l,int r,int rt) {lsum[rt] = rsum[rt] = r - l + 1;if (l == r) return ;int m = (l + r)>>1;build(l,m,rt<<1);build(m + 1,r,rt<<1|1); } void update(int pos,int sc,int l,int r,int rt) {if (l == r){lsum[rt] = rsum[rt] = sc;return ;}int m = (l + r)>>1;if (pos <= m) update(pos,sc,l,m,rt<<1);else update(pos,sc,m + 1,r,rt<<1|1);pushup(rt,r - l + 1); } int query(int pos,int l,int r,int rt) {if (l == r) return 0;int m = (l + r)>>1;if (pos >= m - rsum[rt<<1] + 1 && pos <= m + lsum[rt<<1|1])return rsum[rt<<1] + lsum[rt<<1|1];if (pos <= m) return query(pos,l,m,rt<<1);else return query(pos,m + 1,r,rt<<1|1); } int main() {//freopen("d.txt","r",stdin);int n,q;int x;char op[3];while (~scanf("%d%d",&n,&q)){top = 0;build(1,n,1);while (q--){scanf("%s",op);if (op[0] == 'D'){scanf("%d",&x);stack[++top] = x;update(x,0,1,n,1);}else if (op[0] == 'Q'){scanf("%d",&x);printf("%d\n",query(x,1,n,1));}else{if (top){int pos = stack[top--];update(pos,1,1,n,1);}}}}return 0; }

?

轉載于:https://www.cnblogs.com/E-star/archive/2012/07/26/2609475.html

總結

以上是生活随笔為你收集整理的线段树练习——区间合并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。