[luogu5654]基础函数练习题

答案即区间$[l,r]$的笛卡尔树上，左右子树有一个为空的点到根路径和（定义此为的该点答案）的max，

对求区间笛卡尔树复杂度为$o(n)$，无法通过，因此在全局笛卡尔树中考虑此问题

设$k$为$l$和$r$的lca，那么$i$的答案就是$i$到$k$路径中在$[l,r]$中的部分的和

对于$i$所在子树分类，即将$[l,r]$分为$[l,k)$和$(k,r]$两部分（分别求max），以下以左半部分为例：

考虑$i$到$k$的链，由于$i$在$k$左子树中，因此这条链也时刻在$k$左子树中，即其一定在$k$也就是$r$的左边，因此只需要考虑这个位置大于等于$l$

进一步的，再求$l$和$i$的lca（记为$j$），由于是lca且$l\le i$，因此$l$一定在$j$的左子树中，$i$在$j$的右子树中，因此$i$到$j$的这一部分一定都在$l$的右边，换言之可以枚举lca，直接对右子树内所有点深度取max

还要考虑$j$到$k$的部分，即求这一部分中在$l$右边的数之和，这件事是与$l$无关而仅和$j$本身有关，凡是这条链上其儿子是其右儿子的都不能被计算

（因为这就说明了$k$在其右子树，$l$又在$k$子树内，即$l$在其的右边，反之就说明$l$在左边）

根据上面的性质，具体过程如下——

预处理出以下三个数组：$s_{1}[k]$表示$k$到根路径中所有点的和，$s_{2}[k]$表示其中所有儿子是左儿子的点之和（特别的，$k$都计算入内），$mx[k]$表示$k$子树中满足左右子树有一个为空的点的$s_{1}[k]$的最大值

考虑询问$[l,k)$，暴力枚举$j$，则对于给定的$j$，其对答案的贡献为$mx[rs[j]]-s_{1}[j]+s_{2}[j]-s_{2}[k]+w[k]$（注意$j$一定在$l$的右边，否则不可能是$l$和$i$的lca），贡献是取max

离线，将询问挂在$l$上，然后遍历笛卡尔树，对于点$k$，将$mx[rs[k]]-s_{1}[k]+s_{2}[k]$记在以$k$的深度为下标的线段树上，然后搜索左子树，当搜索右子树时撤销此记录

对于询问，求出$k$（指询问的顶点）的深度+1到$l$的深度这段区间在线段树上的最大值即可（由于$l$的右子树也是可以的，因此先修改再询问）

（右半部分类似，即只考虑其儿子是右儿子的点）

注意要开long long，时间复杂度为$o(n\log_{2}n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 500005

 4 #define ll long long

 5 #define L (k<<1)

 6 #define R (L+1)

 7 #define mid (l+r>>1)

 8 vector<pair<int,int> >vl[N],vr[N];

 9 int n,q,x,y,a[N],w[N],st[N],ls[N],rs[N],s[N],f[N][21];

10 ll s1[N],s2[N],s3[N],mx[N],ans[N],tr[N<<2];

11 int lca(int x,int y){

12     if (s[x]<s[y])swap(x,y);

13     for(int i=20;i>=0;i--)

14         if (s[f[x][i]]>=s[y])x=f[x][i];

15     if (x==y)return x;

16     for(int i=20;i>=0;i--)

17         if (f[x][i]!=f[y][i]){

18             x=f[x][i];

19             y=f[y][i];

20         }

21     return f[x][0];

22 }

23 void dfs(int k,int fa){

24     if (!k)return;

25     s[k]=s[fa]+1;

26     s1[k]=s1[fa]+w[k];

27     s2[k]+=s2[fa]+w[k];

28     s3[k]+=s3[fa]+w[k];

29     f[k][0]=fa;

30     for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1];

31     if (ls[k])s3[ls[k]]=-w[k];

32     dfs(ls[k],k);

33     if (rs[k])s2[rs[k]]=-w[k];

34     dfs(rs[k],k);

35     mx[k]=max(mx[ls[k]],mx[rs[k]]);

36     if ((!ls[k])||(!rs[k]))mx[k]=max(mx[k],s1[k]);

37 }

38 void update(int k,int l,int r,int x,ll y){

39     if (l==r){

40         tr[k]=y;

41         return;

42     }

43     if (x<=mid)update(L,l,mid,x,y);

44     else update(R,mid+1,r,x,y);

45     tr[k]=max(tr[L],tr[R]);

46 }

47 ll query(int k,int l,int r,int x,int y){

48     if ((l>y)||(x>r))return -1e15;

49     if ((x<=l)&&(r<=y))return tr[k];

50     return max(query(L,l,mid,x,y),query(R,mid+1,r,x,y));

51 }

52 void calc_l(int k){

53     if (!k)return;

54     if (!rs[k])update(1,1,n,s[k],s2[k]);

55     else update(1,1,n,s[k],mx[rs[k]]-s1[k]+s2[k]);

56     for(int i=0;i<vl[k].size();i++){

57         x=vl[k][i].first,y=vl[k][i].second;

58         ans[y]=max(ans[y],query(1,1,n,s[x]+1,s[k])-s2[x]+w[x]);

59     }

60     calc_l(ls[k]);

61     update(1,1,n,s[k],-1e15);

62     calc_l(rs[k]);

63 }

64 void calc_r(int k){

65     if (!k)return;

66     if (!ls[k])update(1,1,n,s[k],s3[k]);

67     else update(1,1,n,s[k],mx[ls[k]]-s1[k]+s3[k]);

68     for(int i=0;i<vr[k].size();i++){

69         x=vr[k][i].first,y=vr[k][i].second;

70         ans[y]=max(ans[y],query(1,1,n,s[x]+1,s[k])-s3[x]+w[x]);

71     }

72     calc_r(rs[k]);

73     update(1,1,n,s[k],-1e15);

74     calc_r(ls[k]);

75 }

76 int main(){

77     scanf("%d%d",&n,&q);

78     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

79     for(int i=1;i<=n;i++)scanf("%d",&w[i]);

80     for(int i=1;i<=n;i++){

81         while ((st[0])&&(a[st[st[0]]]<a[i]))ls[i]=st[st[0]--];

82         if (st[0])rs[st[st[0]]]=i;

83         st[++st[0]]=i;

84     }

85     mx[0]=-1e15;

86     dfs(st[1],0);

87     for(int i=1;i<=q;i++){

88         scanf("%d%d",&x,&y);

89         int z=lca(x,y);

90         ans[i]=max(s2[x]-s2[z],s3[y]-s3[z])+w[z];

91         if (x<z)vl[x].push_back(make_pair(z,i));

92         if (z<y)vr[y].push_back(make_pair(z,i));

93     }

94     for(int i=1;i<=n;i++)update(1,1,n,i,-1e15);

95     calc_l(st[1]);

96     calc_r(st[1]);

97     for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);

98 }

巴特西

[luogu5654]基础函数练习题

最新文章

热门文章