本文主要是介绍The LCIS on the Tree HDU - 4718，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=4718
链上LCIS 用区间合并解决 线段树每次查询都带回该区间内的左值 右值 左连续段 右连续段 最大连续段 然后和该链上的上一次查询合并 这里直接当做线段树区间合并的法子写的 uv两点顺着两条链向上爬 会师后特殊处理即可
7000+的代码 debug一天。。 爬链时开了很多没用的变量 反正多了没错。。
#include <bits/stdc++.h>
using namespace std;
#define N 0x3f3f3f3fstruct node1
{int v;int next;
};struct node2//0 up 1 down
{int l;int r;int lval;int rval;int left0;int right0;int all0;int left1;int right1;int all1;
};node1 edge[200010];
node2 tree[400010];
int val[100010],first[100010],fa[100010],deep[100010],sum[100010],son[100010],top[100010],mp1[100010],mp2[100010];
int n,q,num;void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}void dfsI(int cur)
{int i,v;sum[cur]=1,son[cur]=-1;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[cur]){fa[v]=cur,deep[v]=deep[cur]+1;dfsI(v);sum[cur]+=sum[v];if(son[cur]==-1||sum[son[cur]]<sum[v]){son[cur]=v;}}}
}void dfsII(int cur,int tp)
{int i,v;num++;top[cur]=tp,mp1[cur]=num,mp2[num]=cur;if(son[cur]==-1) return;dfsII(son[cur],tp);for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[cur]&&v!=son[cur]){dfsII(v,v);}}
}void pushup(int cur)
{tree[cur].lval=tree[2*cur].lval,tree[cur].rval=tree[2*cur+1].rval;tree[cur].left0=tree[2*cur].left0;if(tree[cur].left0==tree[2*cur].r-tree[2*cur].l+1&&tree[2*cur].rval<tree[2*cur+1].lval) tree[cur].left0+=tree[2*cur+1].left0;tree[cur].right0=tree[2*cur+1].right0;if(tree[cur].right0==tree[2*cur+1].r-tree[2*cur+1].l+1&&tree[2*cur].rval<tree[2*cur+1].lval) tree[cur].right0+=tree[2*cur].right0;tree[cur].all0=max(tree[2*cur].all0,tree[2*cur+1].all0);if(tree[2*cur].rval<tree[2*cur+1].lval) tree[cur].all0=max(tree[cur].all0,tree[2*cur].right0+tree[2*cur+1].left0);tree[cur].left1=tree[2*cur].left1;if(tree[cur].left1==tree[2*cur].r-tree[2*cur].l+1&&tree[2*cur].rval>tree[2*cur+1].lval) tree[cur].left1+=tree[2*cur+1].left1;tree[cur].right1=tree[2*cur+1].right1;if(tree[cur].right1==tree[2*cur+1].r-tree[2*cur+1].l+1&&tree[2*cur].rval>tree[2*cur+1].lval) tree[cur].right1+=tree[2*cur].right1;tree[cur].all1=max(tree[2*cur].all1,tree[2*cur+1].all1);if(tree[2*cur].rval>tree[2*cur+1].lval) tree[cur].all1=max(tree[cur].all1,tree[2*cur].right1+tree[2*cur+1].left1);
}void build(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;if(l==r){tree[cur].lval=val[mp2[l]];tree[cur].rval=val[mp2[l]];tree[cur].left0=1;tree[cur].right0=1;tree[cur].all0=1;tree[cur].left1=1;tree[cur].right1=1;tree[cur].all1=1;return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}void queryII(int pl,int pr,int op,int &lval,int &rval,int &left,int &right,int &all,int cur)
{int llval,lrval,lleft,lright,lall;int rlval,rrval,rleft,rright,rall;//printf("%d %d %d %d\n",pl,pr,tree[cur].l,tree[cur].r);if(pl==tree[cur].l&&tree[cur].r==pr)//{lval=tree[cur].lval;rval=tree[cur].rval;if(op==0){left=tree[cur].left0;right=tree[cur].right0;all=tree[cur].all0;}else{left=tree[cur].left1;right=tree[cur].right1;all=tree[cur].all1;}//printf("gou: %d %d %d %d\n",pl,pr,lval,rval);return;}if(pr<=tree[2*cur].r){queryII(pl,pr,op,lval,rval,left,right,all,2*cur);}else if(pl>=tree[2*cur+1].l){queryII(pl,pr,op,lval,rval,left,right,all,2*cur+1);}else{queryII(pl,tree[2*cur].r,op,llval,lrval,lleft,lright,lall,2*cur);queryII(tree[2*cur+1].l,pr,op,rlval,rrval,rleft,rright,rall,2*cur+1);lval=llval,rval=rrval;left=lleft;if(op==0&&left==tree[2*cur].r-pl+1&&lrval<rlval) left+=rleft;else if(op==1&&left==tree[2*cur].r-pl+1&&lrval>rlval) left+=rleft;right=rright;if(op==0&&right==pr-tree[2*cur+1].l+1&&lrval<rlval) right+=lright;else if(op==1&&right==pr-tree[2*cur+1].l+1&&lrval>rlval) right+=lright;all=max(lall,rall);if(op==0&&lrval<rlval) all=max(all,lright+rleft);else if(op==1&&lrval>rlval) all=max(all,lright+rleft);}
}int queryI(int u,int v)
{int res;int lval0,rval0,left0,right0,all0,plval0,prval0,pleft0,pright0,pall0,tlval0,trval0,tleft0,tright0,tall0;int lval1,rval1,left1,right1,all1,plval1,prval1,pleft1,pright1,pall1,tlval1,trval1,tleft1,tright1,tall1;res=0,plval1=N,plval0=-N,pleft0=0,pleft1=0;while(top[u]!=top[v]){if(deep[top[u]]>deep[top[v]]){queryII(mp1[top[u]],mp1[u],1,lval1,rval1,left1,right1,all1,1);//printf("#1u %d %d\n",mp1[top[u]],mp1[u]);//printf("#1u %d %d %d %d %d\n",lval1,rval1,left1,right1,all1);res=max(res,all1);if(rval1>plval1) res=max(res,right1+pleft1);if(left1==mp1[u]-mp1[top[u]]+1&&rval1>plval1) pleft1=left1+pleft1;else pleft1=left1;res=max(res,pleft1);plval1=lval1;u=fa[top[u]];}else{queryII(mp1[top[v]],mp1[v],0,lval0,rval0,left0,right0,all0,1);//printf("#1v %d %d\n",mp1[top[v]],mp1[v]);//printf("#1v %d %d %d %d %d\n",lval0,rval0,left0,right0,all0);res=max(res,all0);if(rval0<plval0) res=max(res,right0+pleft0);if(left0==mp1[v]-mp1[top[v]]+1&&rval0<plval0) pleft0=left0+pleft0;else pleft0=left0;res=max(res,pleft0);plval0=lval0;v=fa[top[v]];}}if(deep[u]>deep[v]){queryII(mp1[v],mp1[u],1,lval1,rval1,left1,right1,all1,1);//printf("#2u %d %d %d %d %d\n",lval1,rval1,left1,right1,all1);res=max(res,all1);if(rval1>plval1) res=max(res,right1+pleft1);if(left1==mp1[u]-mp1[v]+1&&rval1>plval1) pleft1=left1+pleft1;else pleft1=left1;res=max(res,pleft1);plval1=lval1;//printf("%d %d %d\n",plval0,pleft1,pleft0);if(plval1<plval0) res=max(res,pleft1+pleft0);}else{queryII(mp1[u],mp1[v],0,lval0,rval0,left0,right0,all0,1);//printf("#2v %d %d %d %d %d\n",lval0,rval0,left0,right0,all0);res=max(res,all0);if(rval0<plval0) res=max(res,right0+pleft0);if(left0==mp1[v]-mp1[u]+1&&rval0<plval0) pleft0=left0+pleft0;else pleft0=left0;res=max(res,pleft0);plval0=lval0;//printf("%d %d %d\n",plval0,pleft1,pleft0);if(plval1<plval0) res=max(res,pleft1+pleft0);}return res;
}int main()
{int t,cas,i,u,v;scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&val[i]);}memset(first,-1,sizeof(first));num=0;for(i=2;i<=n;i++){scanf("%d",&u);addedge(u,i);addedge(i,u);}fa[1]=-1,deep[1]=1;dfsI(1);num=0;dfsII(1,1);build(1,n,1);printf("Case #%d:\n",cas);scanf("%d",&q);while(q--){scanf("%d%d",&u,&v);printf("%d\n",queryI(u,v));}if(cas<t) printf("\n");}return 0;
}/*
100
10
1 2 3 4 5 6 7 8 9 106 2 5 1 5 1 7 10 4
*/
这篇关于The LCIS on the Tree HDU - 4718的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
