OJ 中的目录——题解

题目大意：
在一棵树中选择K条不重复的垂直的长度在[L,R]$[L,R]$之间的树链，树链的价值定义为点权的加和，求最大总价值
N≤500000$N\le 500000$

显然，我们可以枚举每一条符合条件的树链，取前K大的进行选择——极端O(N∗N)$O(N\ast N)$

那么看这题之前，先考虑一个较简单的情形：
在一个数组中，找一个第K大的满足长度为[L,R]$[L,R]$的子序列
N≤500000$N\le 500000$

有点困难。。求最大的就很简单了——
构造前缀和，枚举个终点i$i$，在[i−R,i−L]$[i-R,i-L]$中找出最小值，最后刷最优解S[i]−Min$S[i]-Min$：RMQ就可以完美搞定了

我们假设Min=S[t]$Min=S[t]$，则t$t$将区间[i−R,i−L]$[i-R,i-L]$划分成两部分，且显然以i$i$为终点的次优解Min一定在区间[i−R,t−1]或[t+1,i−L]$[i-R,t-1]或[t+1,i-L]$中——

这个问题显然与刚才的问题相同
那么，我们就定义一个三元组(i,L,R)$(i,L,R)$，表示从i$i$往左推L−−R$L--R$个单位，即S[i]−Min[i−R][i−L]$S[i]-Min[i-R][i-L]$
PS:L,R是否包括该元素自己定义，如上为包含的
每次在堆中取个最大的出来，将区间拆分后再放入堆中，处理K次，最后一次的即为答案
效率O(3∗N∗log+N∗log预处理)$O(3\ast N\ast log+N\ast log预处理)$

#pragma GCC optimize(6)
#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int maxn=(1e5)+5,Log=21;
int n,k,L,R,len;LL S[maxn];

template<typename T>
T Min(T a,T b){return a<b?a:b;}

struct ST{
    int x;LL val;
    bool operator <(const ST b)const{return val<b.val;}
}f[maxn][Log],wk;
void make(){
    for(int j=1,tj=2;tj<=n;tj=1<<++j)
      for(int i=0,ti=tj>>1;i+tj-1<=n;i++) f[i][j]=Min(f[i][j-1],f[i+ti][j-1]);
}
void ask(int x,int l,int r){
    l=x-l,r=x-r;int p=log2(l-r+1);
    wk=Min(f[r][p],f[l-(1<<p)+1][p]);
}

struct ff{
    int x,l,r,it;LL val;
    bool operator <(const ff b)const{return val<b.val;}
}hep[maxn*3],ans;
void put(ff x){hep[++len]=x,push_heap(hep+1,hep+1+len);}
ff get(){pop_heap(hep+1,hep+1+len);return hep[len--];}


char gt(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
    int ret=0;bool f=0;char ch=gt();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gt();
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=gt();
    return f?-ret:ret;
}

int main(){
    n=read(),k=read(),L=read(),R=read();
    for(int i=1;i<=n;i++) f[i][0]=(ST){i,S[i]=S[i-1]+read()};
    make();
    for(int i=L;i<=n;i++) ask(i,L,Min(i,R)),put(((ff){i,L,Min(i,R),wk.x+1,S[i]-wk.val}));
    while(k--){
        ans=get();
        if(ans.l<=ans.x-ans.it) ask(ans.x,ans.l,ans.x-ans.it),put(((ff){ans.x,ans.l,ans.x-ans.it,wk.x+1,S[ans.x]-wk.val}));
        if(ans.x-ans.it+2<=ans.r) ask(ans.x,ans.x-ans.it+2,ans.r),put(((ff){ans.x,ans.x-ans.it+2,ans.r,wk.x+1,S[ans.x]-wk.val}));
    }
    printf("%lld\n",ans.val);
    return 0;
}

再回归正题——这题不就是将这个模型做到树上吗？
预处理即为树上RMQ——倍增LCA的同时顺便带出来就OK了
然后代码神似。。
PS:仍然那句话，是否包括自身——下面代码中val[x][i]$val[x][i]$表示节点x$x$向上推了2j$2^j$个单位（不包括自身）加上自身的价值的最小值（有点拗口？多读几遍就懂了O(∩_∩)O！）

#pragma GCC optimize(6)
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=(5e5)+5,Log=21;const LL INF=(LL)1<<60;
int n,m,rot,L,R,len,dep[maxn],down[maxn],up[maxn][Log],pow[maxn];LL p[maxn],ans;

template<typename T>
T Min(T a,T b){return a<b?a:b;}

int tot,son[maxn],nxt[maxn],lnk[maxn];
void add_e(int x,int y){son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot;}

char gt(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
    int ret=0;bool f=0;char ch=gt();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gt();
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=gt();
    return f?-ret:ret;
}

struct ff{
    int x,it,l,r;LL va;
    bool operator <(const ff b)const{return va<b.va;}
}hep[maxn*3];
void put(ff x){hep[++len]=x,push_heap(hep+1,hep+1+len);}
ff get(){pop_heap(hep+1,hep+1+len);return hep[len--];}

struct ST{
    LL x;int id;
    bool operator <(const ST b)const{return x<b.x;}
    void clear(){x=INF,id=0;}
}val[maxn][Log],now;
ST getdata(int x,int l,int r){
    int lst=x;
    now.clear();int tol=dep[x]-l,tor=dep[x]-r;
    while(dep[x]>tol) x=up[x][pow[dep[x]-tol]-1];
    while(dep[x]>tor) now=Min(now,val[x][pow[dep[x]-tor]-1]),x=up[x][pow[dep[x]-tor]-1];
    if(l==r) now=Min(now,((ST){p[x],x}));
    now.id=down[now.id];
}

void DFS(int x,int fa){
    dep[x]=dep[fa]+1,val[x][0]=Min(((ST){(p[x]+=p[fa]),x}),((ST){p[fa],fa})),up[x][0]=fa,down[fa]=x;
    for(int i=1;(1<<i)<=dep[x];i++) up[x][i]=up[up[x][i-1]][i-1],val[x][i]=Min(val[x][i-1],val[up[x][i-1]][i-1]);
    if(dep[x]>=L) getdata(x,Min(L,dep[x]),Min(R,dep[x])),put(((ff){x,now.id,Min(L,dep[x]),Min(R,dep[x]),p[x]-now.x}));
    for(int j=lnk[x];j;j=nxt[j]) DFS(son[j],x);
}

int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        if(x) add_e(x,i);else rot=i;
    }
    for(int i=1;i<=n;i++) p[i]=read();
    m=read(),L=read(),R=read();
    for(int i=1;i<=maxn-5;i++) pow[i]=pow[i-1]+((1<<pow[i-1])==i);
    dep[rot]=1,DFS(rot,0);
    while(m--){
        ff K=get();ans+=K.va;
        if(K.l<=dep[K.x]-dep[K.it]) getdata(K.x,K.l,dep[K.x]-dep[K.it]),put(((ff){K.x,now.id,K.l,dep[K.x]-dep[K.it],p[K.x]-now.x}));
        if(dep[K.x]-dep[K.it]+2<=K.r) getdata(K.x,dep[K.x]-dep[K.it]+2,K.r),put(((ff){K.x,now.id,dep[K.x]-dep[K.it]+2,K.r,p[K.x]-now.x}));
    }
    printf("%lld\n",ans);
    return 0;
}