題目連接配接:http://acm.hdu.edu.cn/showproblem.php?pid=4718
題意:給你一棵樹,每個節點有一個值,然後任給樹上的兩點,問這兩點的最長連續遞增區間是多少
題解:先樹鍊剖分,然後結合線段樹的區間合并來搞,注意的是要記錄遞增和遞減兩個狀态,因為線段樹的區間都是從根到子節點,如果詢問從子節點到子節點,那麼就是一增一減
1 #include<cstdio>
2 #include<algorithm>
3 #define F(i,a,b) for(int i=a;i<=b;i++)
4 #define root 1,n,1
5 #define ls l,m,rt<<1
6 #define rs m+1,r,rt<<1|1
7 using namespace std;
8 const int N=1e5+7;
9 int t,x,y,n,ic=1,q,cnt,g[N],ed,nxt[N],v[N],a[N];
10 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
11 //樹鍊剖分----------------------------
12 int dep[N],sz[N],fa[N],hs[N],tid[N],top[N],idx,cot[N];
13 void dfs1(int u,int pre){
14 dep[u]=dep[pre]+1,sz[u]=1,fa[u]=pre,hs[u]=0;
15 for(int i=g[u];~i;i=nxt[i]){
16 dfs1(v[i],u),sz[u]+=sz[v[i]];
17 if(sz[v[i]]>sz[hs[u]])hs[u]=v[i];
18 }
19 }
20 void dfs2(int u,int tp){
21 top[u]=tp,tid[u]=++idx,cot[tid[u]]=a[u];
22 if(hs[u])dfs2(hs[u],tp);
23 for(int i=g[u];~i;i=nxt[i])if(v[i]!=hs[u])dfs2(v[i],v[i]);
24 }
25 //線段樹-------------------------------
26 int Rn[N<<3],Ln[N<<3],len[N<<3],ml[N<<3],Rl[N<<3];
27 int Ll[N<<3],dml[N<<3],dRl[N<<3],dLl[N<<3];
28
29 inline void up(int rt,int li,int ri){
30 Ln[rt]=Ln[li],Rn[rt]=Rn[ri];
31 Ll[rt]=Ll[li],Rl[rt]=Rl[ri];
32 dLl[rt]=dLl[li],dRl[rt]=dRl[ri];
33 ml[rt]=max(ml[li],ml[ri]);
34 dml[rt]=max(dml[li],dml[ri]);
35 if(Rn[li]<Ln[ri]){//左右區間可以合并
36 ml[rt]=max(ml[rt],Rl[li]+Ll[ri]);
37 if(Rl[li]==len[li])Ll[rt]=Ll[li]+Ll[ri];
38 if(Rl[ri]==len[ri])Rl[rt]=Rl[li]+Rl[ri];
39 }
40 if(Rn[li]>Ln[ri]){
41 dml[rt]=max(dml[rt],dRl[li]+dLl[ri]);
42 if(dRl[li]==len[li])dLl[rt]=dLl[li]+dLl[ri];
43 if(dRl[ri]==len[ri])dRl[rt]=dRl[li]+dRl[ri];
44 }
45 }
46
47 void build(int l,int r,int rt){
48 len[rt]=r-l+1;
49 if(l==r){
50 Ln[rt]=Rn[rt]=cot[l],ml[rt]=Ll[rt]=Rl[rt]=1;
51 dml[rt]=dLl[rt]=dRl[rt]=1;
52 return;
53 }
54 int m=(l+r)>>1;
55 build(ls),build(rs),up(rt,rt<<1,rt<<1|1);
56 }
57 //将兩個區間合并
58 inline void adt(int li,int ri,int rt){len[rt]=len[li]+len[ri],up(rt,li,ri);}
59
60 int anson(int l,int r){
61 int ans=max(dml[l],ml[r]);
62 if(Ln[l]<Ln[r])return max(ans,dLl[l]+Ll[r]);
63 return ans;
64 }
65
66 int query(int L,int R,int l,int r,int rt){
67 if(L==l&&R==r)return rt;
68 int m=(l+r)>>1;
69 if(m>=R)return query(L,R,ls);
70 else if(m<L)return query(L,R,rs);
71 else{
72 int lss=query(L,m,ls),rss=query(m+1,R,rs);
73 adt(lss,rss,++cnt);
74 return cnt;
75 }
76 }
77
78 int lca(int x,int y){
79 if(x==y)return 1;
80 cnt=N<<2;
81 int xp=-1,yp=-1,op;
82 while(top[x]!=top[y]){
83 if(dep[top[x]]>dep[top[y]]){
84 op=query(tid[top[x]],tid[x],root),x=fa[top[x]];
85 if(xp==-1)xp=op;
86 else adt(op,xp,++cnt),xp=cnt;
87 }else{
88 op=query(tid[top[y]],tid[y],root),y=fa[top[y]];
89 if(yp==-1)yp=op;
90 else adt(op,yp,++cnt),yp=cnt;
91 }
92 }
93 if(dep[x]>=dep[y]){
94 op=query(tid[y],tid[x],root);
95 if(xp==-1)xp=op;
96 else adt(op,xp,++cnt),xp=cnt;
97 }else{
98 op=query(tid[x],tid[y],root);
99 if(yp==-1)yp=op;
100 else adt(op,yp,++cnt),yp=cnt;
101 }
102 if(xp==-1)return ml[yp];
103 if(yp==-1)return dml[xp];
104 return anson(xp,yp);
105 }
106
107 int main(){
108 scanf("%d",&t);
109 while(t--){
110 scanf("%d",&n);
111 F(i,0,N-1)g[i]=-1;ed=0;
112 F(i,1,n)scanf("%d",a+i);
113 F(i,2,n)scanf("%d",&x),adg(x,i);
114 dfs1(1,0),idx=0,dfs2(1,1),build(root);
115 scanf("%d",&q);
116 printf("Case #%d:\n",ic++);
117 while(q--)scanf("%d%d",&x,&y),printf("%d\n",lca(x,y));
118 if(t)puts("");
119 }
120 }
View Code
轉載于:https://www.cnblogs.com/bin-gege/p/5696107.html