線段樹專題
1.hud 1166 http://acm.hdu.edu.cn/showproblem.php?pid=1166 敵兵布陣
本題目涉及到了區間操作和點操作兩種操作。
區間操作(區間和)：我們采用了遞推的方法來建樹，建好了葉子結點之后，我們再回溯來建整個區間。(這個操作是關鍵)
點操作：點操作必然涉及到區間的改動，我們判定，只要這個點在一個區間上，那么我們就對這個區間操作。
View Code
#include "iostream" #include "string" #include "algorithm" using namespace std; #define maxn 50005 int len, peo[maxn], ans; typedef struct node { int l, r, m; int s; }node; node t[maxn*4]; void build(int ll, int le, int ri) { t[ll].l = le; t[ll].r = ri; t[ll].m = (le+ri)>>1; if(le==ri) t[ll].s = peo[le]; else { build(ll<<1, le, t[ll].m); build(ll<<1|1, t[ll].m+1, ri); t[ll].s = t[ll<<1].s + t[ll<<1|1].s; } } void query(int ll, int le, int ri) { if(le<=t[ll].l && ri>=t[ll].r) ans+=t[ll].s; else { if(le>t[ll].m) query(ll<<1|1, le, ri); else if(ri<=t[ll].m) query(ll<<1, le, ri); else { query(ll<<1, le, t[ll].m); query(ll<<1|1, t[ll].m+1, ri); } } } void add(int ll, int p, int v) { if(p>=t[ll].l && p<=t[ll].r) t[ll].s += v; if(t[ll].l==p && t[ll].r==p) return; if(p>t[ll].m) add(ll<<1|1, p, v); else if(p<=t[ll].m) add(ll<<1, p, v); } void sub(int ll, int p, int v) { if(p>=t[ll].l && p<=t[ll].r) t[ll].s -= v; if(t[ll].l==p && t[ll].r==p) return; if(p>t[ll].m) sub(ll<<1|1, p, v); else if(p<=t[ll].m) sub(ll<<1, p, v); } int main() { int i, j, C, le, ri; char op[10]; scanf("%d", &C); for(i=1; i<=C; i++) { printf("Case %d:\n", i); scanf("%d", &len); for(j=1; j<=len; j++) scanf("%d", peo+j); build(1, 1, len); while(scanf("%s", op)!=EOF) { if(strcmp(op, "End")==0) break; scanf("%d%d", &le, &ri); if(strcmp(op, "Query")==0) { ans = 0; query(1, le, ri); printf("%d\n", ans); } else if(strcmp(op, "Add")==0) { add(1, le, ri); } else if(strcmp(op, "Sub")==0) { sub(1, le, ri); } } } return 0; }
2.hdu 1754 http://acm.hdu.edu.cn/showproblem.php?pid=1754 I hate it
本題目涉及到了區間操作和點操作兩種操作。
區間操作(區間最值)：平常的建樹。
點操作：我們每向區間插入一個點就和當前區間的最大值比較一下，如果大于最大值，則更新。(這個操作是關鍵)
View Code
#include "iostream" #include "string" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; #define maxn 200005 typedef struct node { int l, r, m, ma; }node; int ans; node t[maxn<<2]; void Build(int ll, int l, int r) { t[ll].ma=-1; t[ll].l=l; t[ll].r=r; t[ll].m=(l+r)>>1; if(l!=r) { Build(ll<<1, l, t[ll].m); Build(ll<<1|1, t[ll].m+1, r); } } void Insert(int ll, int p, int v) { if(p>=t[ll].l && p<=t[ll].r && t[ll].ma<v) t[ll].ma=v; if(p==t[ll].l && p==t[ll].r) return; if(p<=t[ll].m) Insert(ll<<1, p, v); else if(p>t[ll].m) Insert(ll<<1|1, p, v); } int Find(int ll, int l, int r) { if(l==t[ll].l && t[ll].r==r) return t[ll].ma; if(r<=t[ll].m) Find(ll<<1, l, r); else if(l>t[ll].m) Find(ll<<1|1, l, r); else { int a=Find(ll<<1, l, t[ll].m); int b=Find(ll<<1|1, t[ll].m+1, r); return a>b?a:b; } } int main() { int n, op, i, j, v, l, r; char opp[10]; while(scanf("%d%d", &n, &op)!=EOF) { Build(1, 1, n); for(i=1; i<=n; i++) { scanf("%d", &v); Insert(1, i, v); } for(i=0; i<op; i++) { scanf("%s%d%d", opp, &l, &r); if(strcmp(opp, "Q")==0) { printf("%d\n", Find(1, l, r)); } else if(strcmp(opp, "U")==0) { Insert(1, l, r); } } } }
3.hdu 1698http://acm.hdu.edu.cn/showproblem.php?pid=1698 Just a hook
本題只涉及到了區間操作。
區間操作(全區間鍵值的改變)：在維護更新的時候我們將無用的區間屏蔽掉，這樣就可以大大提高時間效率。如何屏蔽？這個是關鍵。
View Code
#include "iostream" #include "string" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; #define maxn 100005 #define L(x) (x<<1) #define R(x) (x<<1|1) typedef struct node { int l, r, z; }node; node t[maxn<<2]; void Build(int ll, int l, int r) { t[ll].l=l; t[ll].r=r; t[ll].z=1; if(l<r) { int m=(t[ll].l+t[ll].r)>>1; Build(L(ll), l, m); Build(R(ll), m+1, r); } } void Update(int ll, int l, int r, int z) { if(l==t[ll].l && t[ll].r==r) { t[ll].z=z;//更新 return; } if(t[ll].z>0)//只要不是剛好的區間，我們就往下更新，同時將這一層的區間屏蔽掉，說具體點就是t[ll].z=-1 { t[R(ll)].z = t[ll].z; t[L(ll)].z = t[ll].z; t[ll].z=-1; } if(t[ll].l==t[ll].r) return; int m=(t[ll].l+t[ll].r)>>1; if(r<=m) Update(L(ll), l, r, z); else if(l>m) Update(R(ll), l, r, z); else { Update(L(ll), l, m, z); Update(R(ll), m+1, r, z); } } int Query(int ll, int l, int r) { if(t[ll].z>0) return (t[ll].r-t[ll].l+1)*t[ll].z; int m=(t[ll].l+t[ll].r)>>1; if(r<=m) return Query(L(ll), l, r); else if(l>m) return Query(R(ll), l, r); else return Query(L(ll), l, m)+Query(R(ll), m+1, r); } int main() { int c, n, op, i, l, r, z, j, ans; scanf("%d", &c); for(i=1; i<=c; i++) { scanf("%d%d", &n, &op); Build(1, 1, n); for(j=0; j<op; j++) { scanf("%d%d%d", &l, &r, &z); Update(1, l, r, z); } ans=Query(1, 1, n); printf("Case %d: The total value of the hook is %d.\n", i, ans); } }
4.hdu 1394http://acm.hdu.edu.cn/showproblem.php?pid=1394 Minimum Inversion Number
本題是一種類型的題目——逆序數的求法。
本題涉及到了區間操作。
但是本題的區間操作有一定的講究，也就是一邊插入一邊查找。不然等插入完了再來查找就不知道是在它前面還是后面出現的了。
其它的就和平常的線段樹一樣了。
View Code
#include "iostream" #include "string" #include "cstring" #include "algorithm" #include "cstdio" using namespace std; #define maxn 5005 #define L(x) (x<<1) #define R(x) (x<<1|1) typedef struct segtree { int l, r, s; }segtree; segtree t[maxn<<2]; int s[maxn]; void Build(int ll, int l, int r) { t[ll].l=l; t[ll].r=r; t[ll].s=0; if(l<r) { int m=(l+r)>>1; Build(L(ll), l, m); Build(R(ll), m+1, r); } } int Query(int ll, int l, int r) { if(t[ll].l==l && t[ll].r==r) return t[ll].s; int m=(t[ll].l+t[ll].r)>>1; if(r<=m) return Query(L(ll), l, r); else if(l>m) return Query(R(ll), l, r); else return Query(L(ll), l, m)+Query(R(ll), m+1, r); } void Update(int ll, int k) { t[ll].s++; if(t[ll].l==t[ll].r) return; int m=(t[ll].l+t[ll].r)>>1; if(k<=m) Update(L(ll), k); else Update(R(ll), k); } int main() { int n, i, t, ans; while(scanf("%d", &n)!=EOF) { ans=0; Build(1, 0, n-1); for(i=0; i<n; i++)//我們來求一下“輸入順序時”的逆序對數 { scanf("%d", &s[i]); ans+=Query(1, s[i], n-1);//在s[i]~n-1這個區間中有多少個數是在s[i]之前出現的，那么對于這個數而言就有多少個逆序對數，不是嗎？好好想想…… Update(1, s[i]); } t=ans; for(i=0; i<n-1; i++) { t=t+(n-1-s[i])-s[i]; if(ans>t) ans=t; } printf("%d\n", ans); } return 0; }
5. hdu 2492http://acm.hdu.edu.cn/showproblem.php?pid=2492 Ping pong
本題也是一道逆序數的題目。只不為要求兩種逆序都要算出來。也就是說A>B>C和A<B<C兩種情況。
其實仔細想想本題我們可以得到一個這樣的結論。
如果完全按照題目的描述來想算法，我們是很容易進入誤區的，
但是，如果我們將題目的意思也取反來看一下，當然這個取反和原題意是等價的，就很容易知道是什么樣的題目了。
View Code
#include "iostream" #include "string" #include "cstring" #include "algorithm" #include "cstdio" using namespace std; #define maxn 20010 #define maxs 100010 #define L(x) (x<<1) #define R(x) (x<<1|1) typedef struct segtree { int l, r, s; }segtree; segtree t[maxs<<2]; int s[maxn]; void Build(int f, int l, int r) { t[f].l=l; t[f].r=r; t[f].s=0; if(l<r) { int m=(l+r)>>1; Build(L(f), l, m); Build(R(f), m+1, r); } } int Query(int f, int l, int r) { if(t[f].l==l && t[f].r==r) return t[f].s; int m=(t[f].l+t[f].r)>>1; if(r<=m) return Query(L(f), l, r); else if(l>m) return Query(R(f), l, r); else return Query(L(f), l, m)+Query(R(f), m+1, r); } void Update(int f, int k) { t[f].s++; if(t[f].l==t[f].r) return; int m=(t[f].l+t[f].r)>>1; if(k<=m) Update(L(f), k); else Update(R(f), k); } int main() { int n, i, T, k; long long fs[maxn], fb[maxn], ss[maxn], sb[maxn]; scanf("%d", &T); for(k=0; k<T; k++) { scanf("%d", &n); memset(fs, 0, sizeof fs); memset(fb, 0, sizeof fb); memset(ss, 0, sizeof ss); memset(sb, 0, sizeof sb); Build(1, 1, maxs); for(i=0; i<n; i++)//我們來求一下“輸入順序時”的逆序對數 { scanf("%d", &s[i]); fb[i]=Query(1, s[i]+1, maxs);//big if(s[i]==1) { Update(1, s[i]); continue; } fs[i]=Query(1, 1, s[i]-1);//在s[i]~n-1這個區間中有多少個數是在s[i]之前出現的，那么對于這個數而言就有多少個逆序對數，不是嗎？好好想想…… Update(1, s[i]); } Build(1, 1, maxs); for(i=n-1; i>=0; i--) { sb[i]=Query(1, s[i]+1, maxs); if(s[i]==1) { Update(1, s[i]); continue; } ss[i]=Query(1, 1, s[i]-1);//small Update(1, s[i]); } long long ans=0; for(i=1; i<n-1; i++) { ans+=fs[i]*sb[i]; ans+=fb[i]*ss[i]; } printf("%I64d\n", ans); } return 0; }
6. hdu 3308http://acm.hdu.edu.cn/showproblem.php?pid=3308 LCIS
本題是一種類型的題目，解法有一定的套路。也就是lm,rm,m,len,lv,rv等等，具體是什么含義，看看代碼就知道了。
本題涉及到了區間操作和點的操作。
區間操作，這個比較麻煩，因為沒有記錄左右邊界，所以要小心，這只是一個不起眼的小難題。
區間的操作，難就難在up函數，和query函數上，這兩個一定要看懂。其它的就好說了。
點操作一般，就是平時的操作。
View Code
#include "iostream" #include "string" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; #define L(x) (x<<1) #define R(x) (x<<1|1) #define maxn 100005 typedef struct node { int lm, rm, m; int lv, rv, len; }node;//我們并沒有記錄l, r node t[maxn<<2]; void Up(node &f, node &l, node &r) { f.lv = l.lv; f.rv = r.rv; if(l.rv<r.lv)//是遞增的 { f.lm=(l.lm==l.len?l.lm+r.lm:l.lm);//左邊的最值就是它的區間長度那么……否則…… f.rm=(r.rm==r.len?r.rm+l.rm:r.rm);//右邊的最值就是它的區間長度那么……否則…… f.m=max(max(f.lm, f.rm), l.rm+r.lm);//l.rm+r.lm表示不包含左右端點的值 f.m=max(max(l.m, r.m), f.m); } else//如果不是遞增的 { f.lm=l.lm; f.rm=r.rm; f.m=max(l.m, r.m); } } void Build(int f, int l, int r) { t[f].len=r-l+1; if(l==r) { scanf("%d", &t[f].lv); t[f].rv = t[f].lv; t[f].lm = t[f].rm = t[f].m = 1; return; } int m=(l+r)>>1; Build(L(f), l, m); Build(R(f), m+1, r); //當建樹完成的時候我們要進行統計運算，也就是向上計算 Up(t[f], t[L(f)], t[R(f)]); } void Update(int f, int l, int r, int p, int v)//我們只需要更新它的lv, rv就可以了 { if(l==r) { t[f].lv = t[f].rv = v; return; } int m=(l+r)>>1; if(p<=m) Update(L(f), l, m, p, v);// else Update(R(f), m+1, r, p, v);//我們的目的是更新葉子結點，所以不需要更新區間 //當修改完成的時候我們要進行統計運算，也就是向上計算 Up(t[f], t[L(f)], t[R(f)]); } node Query(int f, int l, int r, int &L, int &R) { if(L<=l && r<=R) return t[f]; int m=(l+r)>>1; node t1, t2; t1.len=t2.len=0; if(L<=m) t1=Query(L(f), l, m, L, R);//往左可走，就走 if(R>m) t2=Query(R(f), m+1, r, L, R);//往右可走，就走 if(t1.len && t2.len)//都找到了，從兩邊找到了 { node tmp; Up(tmp, t1, t2); tmp.len=t1.len+t2.len;//哦哦，有可能多次更新，所以不能大意哦！！！ return tmp; } if(t1.len) return t1; return t2; } int main() { int T; scanf("%d",&T); while(T--) { int n,m,x,y; node te; char c; scanf("%d%d",&n,&m); n--; Build(1, 0,n); getchar(); while(m--) { getchar(); scanf("%c%d%d",&c,&x,&y); if(c=='Q') { te=Query(1,0,n,x,y); printf("%d\n",te.m); } else Update(1, 0, n, x, y); } } return 0; }
7.hdu 4046http://acm.hdu.edu.cn/showproblem.php?pid=4046 Panda
本題就是一道簡單的線段樹題目。
但是難就難在只有當我們經過一定的轉化之后，才可以用線段樹來做，轉化的這個過程是比較困難的。
這就是本題的難點所在。轉化 轉化 轉化 轉化 再轉化
View Code
#include "iostream" #include "string" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; #define L(x) (x<<1) #define R(x) (x<<1|1) #define maxn 50010 typedef struct node { int l, r, s; }node; node t[maxn<<2]; char str[maxn]; int a[maxn]; void build(int f, int l, int r) { t[f].l = l; t[f].r = r; if(l==r) { t[f].s=a[l]; return; } int m=(l+r)>>1; build(L(f), l, m); build(R(f), m+1, r); t[f].s=t[L(f)].s+t[R(f)].s; } void update(int f, int l, int r, int p, int v) { if(l==r) { t[f].s=v; return; } int m=(l+r)>>1; if(p<=m) update(L(f), l, m, p, v); else update(R(f), m+1, r, p, v); t[f].s=t[L(f)].s+t[R(f)].s; } int Query(int f, int l, int r, int L, int R) { if(L<=l && r<=R) return t[f].s; int m=(l+r)>>1; int ret=0; if(L<=m) ret += Query(L(f), l, m, L, R); if(R>m) ret += Query(R(f), m+1, r, L, R); return ret; } int main() { int cas,T=0,n,m,r,l,c; char st; scanf("%d",&cas); while(cas--) { scanf("%d %d",&n,&m); scanf("%s",str); memset(a,0,sizeof(a)); printf("Case %d:\n",++T); for(int i=2;i<n;i++)//標記以該下標結尾的長度為3的子串是否符合要求 { if(str[i]!='w') a[i]=0; else if(str[i-1]=='b'&&str[i-2]=='w') a[i]=1; } build(1,0,n); while(m--) { scanf("%d",&c); if(c==0) { scanf("%d %d",&l,&r); l+=2; if(l>r) printf("0\n"); else printf("%d\n",Query(1,0,n,l,r)); } else { scanf("%d %c",&l,&st); if(str[l]==st)//若要就該的字符跟原先相同，則不用修改了 continue; str[l]=st; if(l>=2&&str[l-2]=='w'&&str[l-1]=='b'&&str[l]=='w') { if(a[l]==0)//若改之前是不符合要求的串，則更新 update(1, 0,n,l,1); a[l]=1; } else if(l>=2&&a[l]==1)//若改之前是符合要求的串，則更新 { update(1, 0,n,l,0); a[l]=0; } if(l>=1&&str[l]=='b'&&str[l-1]=='w'&&str[l+1]=='w') { if(a[l+1]==0) update(1, 0,n,l+1,1); a[l+1]=1; } else if(l<n-1&&l>=1&&a[l+1]==1) a[l+1]=0,update(1, 0,n,l+1,0); if(str[l]=='w'&&str[l+1]=='b'&&str[l+2]=='w') { if(a[l+2]==0) update(1, 0,n,l+2,1); a[l+2]=1; } else if(l<n-2&&a[l+2]==1) a[l+2]=0,update(1, 0,n,l+2,0); } } } return 0; }
posted on 2012-08-21 15:54 More study needed. 閱讀(239) 評論(0) 收藏 舉報
浙公網安備 33010602011771號