【线段树】【FeyatCup】——2.法法塔的奖励
首先感謝并膜拜兩位大佬 wyl8899 & 法法塔 感謝兩位的出題！
題目：
| 法法塔是很喜歡寫(xiě)程序的。所以冒著就算碼農(nóng)屌絲一輩子的風(fēng)險(xiǎn)也大無(wú)畏地寫(xiě)著程序。 輸入數(shù)據(jù)： 第一行一個(gè)數(shù)n，描述樹(shù)上節(jié)點(diǎn)的個(gè)數(shù)。 輸出數(shù)據(jù)： 一行n個(gè)數(shù)，第i個(gè)數(shù)表示法法塔選擇了以第i個(gè)節(jié)點(diǎn)為根的子樹(shù)后，他可以獲得的最多的獎(jiǎng)品個(gè)數(shù)。 數(shù)據(jù)范圍： n<=100000，每個(gè)數(shù)的權(quán)值都是1到n的正整數(shù)。 |
拆分題意，這道題是求樹(shù)上求最長(zhǎng)不下降子序列，但是如果將每一條邊單獨(dú)拿出來(lái)進(jìn)行dp是會(huì)爆空間的，所以我們考慮別的方法。
?
?
?
?
參考：
?
https://www.cnblogs.com/chhokmah/p/10550155.html
?
https://www.cnblogs.com/Mychael/p/8665589.html
https://www.luogu.org/blog/wcr20020327/xin-ren-di-di-yi-ci-blog-xian-duan-shu
?
動(dòng)態(tài)開(kāi)點(diǎn)線(xiàn)段樹(shù)&&線(xiàn)段樹(shù)合并：
顧名思義，動(dòng)態(tài)開(kāi)點(diǎn)線(xiàn)段樹(shù)就是在線(xiàn)段樹(shù)的基礎(chǔ)上實(shí)現(xiàn)動(dòng)態(tài)開(kāi)點(diǎn)，達(dá)到減小空間的方法。與原來(lái)的線(xiàn)段樹(shù)有一點(diǎn)不同，動(dòng)態(tài)開(kāi)點(diǎn)線(xiàn)段樹(shù)擁有左兒子（ls）與右兒子（rs），便于進(jìn)行線(xiàn)段樹(shù)與點(diǎn)之間的組合和更新。
舉個(gè)例子，單點(diǎn)構(gòu)造是在原有線(xiàn)段樹(shù)上開(kāi)啟新的點(diǎn)(要注意取地址符的使用)：
?
1 void change(int &o,int l,int r,int a,int b){//a=pos,b=size 2 if (!o) o=++cnt; 3 if (l==r){ 4 g[o].sum=max(g[o].sum,b); 5 return; 6 } 7 int mid=(l+r)/2; 8 if (a<=mid) change(g[o].ls,l,mid,a,b); 9 else change(g[o].rs,mid+1,r,a,b); 10 g[o].sum=max(g[g[o].ls].sum,g[g[o].rs].sum); 11 }?
其余的不再贅述，而線(xiàn)段樹(shù)合并則是將兩個(gè)線(xiàn)段樹(shù)合并在一起（廢話(huà)），參見(jiàn)代碼：
?
1 //Mychael大大的代碼 2 int merge(int u,int v){ 3 if (!u) return v;//如果沒(méi)有u點(diǎn)，則返回v做根 4 if (!v) return u;//類(lèi)似上面 5 int t = ++cnt;//如果兩邊都有，就新建t點(diǎn)作為根 6 sum[t] = sum[u] + sum[v];//融合兩個(gè)點(diǎn)，但是在這個(gè)程序中需要改為更新最大值 7 ls[t] = merge(ls[u],ls[v]);//遞歸修改 8 rs[t] = merge(rs[u],rs[v]); 9 return t; 10 }?
經(jīng)過(guò)上面兩個(gè)操作，這道題的解法應(yīng)該已經(jīng)大致明晰了呢：
我們?cè)谝粋€(gè)子樹(shù)中找到當(dāng)前最長(zhǎng)不下降子序列中的最大值，并在其基礎(chǔ)上加1即可。
?
//continue #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int head[N],cnt,num[N],rt[N],n,ans[N]; struct edge{int to,next; }e[N]; struct line{int ls,rs,sum; }tr[N<<1]; void addedge(int from,int to){e[++cnt].to=to;e[cnt].next=head[from];head[from]=cnt; } void change(int &o,int l,int r,int siz,int pos){ //動(dòng)態(tài)開(kāi)點(diǎn) if(!o) o=++cnt;if(l==r){tr[o].sum=max(tr[o].sum,siz);return;}int mid=(l+r)>>1;if(pos<=mid) change(tr[o].ls,l,mid,siz,pos);else change(tr[o].rs,mid+1,r,siz,pos);tr[o].sum=max(tr[tr[o].ls].sum,tr[tr[o].rs].sum); } int query(int o,int l,int r,int a,int b){//查詢(xún)區(qū)間最大值if(!o) return 0;if(l==a&&r==b) return tr[o].sum;int mid=(l+r)>>1;if(b<=mid) return query(tr[o].ls,l,mid,a,b);else if(a>mid) return query(tr[o].rs,mid+1,r,a,b);else return max(query(tr[o].ls,l,mid,a,mid),query(tr[o].rs,mid+1,r,mid+1,b)); } int merge(int a,int b,int l,int r){if(!a||!b) return a+b;if(l==r){tr[a].sum=max(tr[a].sum,tr[b].sum);return a;}int mid=(l+r)>>1;tr[a].ls=merge(tr[a].ls,tr[b].ls,l,mid);tr[a].rs=merge(tr[a].rs,tr[b].rs,mid+1,r);tr[a].sum=max(tr[a].sum,tr[b].sum);return a; } void dfs(int o){//遍歷整個(gè)樹(shù)，將線(xiàn)段樹(shù)合并求最大值int j=0;for(int u=head[o];u;u=e[u].next){int v=e[u].to;dfs(v);j=merge(j,rt[v],1,n);}ans[o]=query(j,1,n,1,num[o])+1;change(j,1,n,ans[o],num[o]);rt[o]=j; } int main(){scanf("%d",&n);int fa;for(int i=1;i<=n;i++){scanf("%d",&fa);if(fa!=-1)addedge(fa,i);}for(int i=1;i<=n;i++) scanf("%d",&num[i]);cnt=0;dfs(1);for(int i=1;i<=n;i++) printf("%d ",ans[i]);return 0; }?
轉(zhuǎn)載于:https://www.cnblogs.com/Nelson992770019/p/11160434.html
總結(jié)
以上是生活随笔為你收集整理的【线段树】【FeyatCup】——2.法法塔的奖励的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Nginx 之五： Nginx服务器的负
- 下一篇： 微信小程序开发--数据绑定