前言

已经是第三次遇到原题。

第一次是在

J

O

I

2021

S

p

r

i

n

g

C

a

m

p

\rm JOI2021~Spring~Camp

JOI2021 Spring Camp 里遇到的类似的题（Food Court），我当初就用的启发式合并平衡树做法，但是由于常数不够优，没能通过

2

e

5

\tt2e5

2e5 的测试点。当时就只能用线段树合并做，

O

(

n

log

⁡

n

)

\rm O(n\log n)

O(nlogn) ，但是我不会。

第二次是在打

C

E

O

I

2019

D

a

y

2

\tt CEOI2019~Day2

CEOI2019 Day2 的虚拟赛时，遇到了这一道明显变简单许多（不再是基环树、且

n

≤

1

e

5

\rm n\leq1e5

n≤1e5）的原题，喜出望外，不管

T

1

\tt T1

T1 了，直接把它做了。果然，启发式合并平衡树又可以了。

这次是在 WK 讲题过程中，PPT 跳出了这么一道原题，直接导致提前下课……

题面

和笔者原先这篇博客做法几乎完全一致，这里就不重复了，下面是此题的平衡树做法代码：

#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return f * x;
}
int n,m,i,j,s,o,k;
//---------------------------------------------Treap
struct np{int s[2];np(){s[0]=s[1]=0;}np(int A,int B){s[0]=A;s[1]=B;}};
struct tr{
    int s[2],siz,hp,ky;
    LL nm,mx,lz;
    tr(){s[0]=s[1]=siz=hp=0;ky=0;nm=mx=lz=0;}
}tre[MAXN];
int CNT;
int newnode(int tm,LL nm) {
    int x = ++ CNT; tre[x]=tr();
    tre[x].siz = 1; tre[x].hp = rand() *1145136223ll % 998244353;
    tre[x].ky = tm; tre[x].nm = tre[x].mx = nm; return x;
}
int update(int x) {
    if(!x) return x;
    int ls = tre[x].s[0],rs = tre[x].s[1]; tre[x].siz = tre[ls].siz + tre[rs].siz + 1;
    tre[x].mx = max(tre[x].nm,max(tre[ls].mx,tre[rs].mx) + tre[x].lz);
    tre[0] = tr();return x;
}
void addnm(int x,LL y) {if(!x)return;tre[x].nm+=y;tre[x].lz+=y;tre[x].mx+=y;return ;}
void pushdown(int x) {
    if(!x) return;
    int ls = tre[x].s[0],rs = tre[x].s[1];
    if(tre[x].lz) {
        addnm(ls,tre[x].lz); addnm(rs,tre[x].lz);
        tre[x].lz = 0;
    }return ;
}
np spli(int x,int key) {
    np as(0,0); if(!x) return as;
    pushdown(x);
    int d = (tre[x].ky <= key ? 1:0);
    as = spli(tre[x].s[d],key);
    tre[x].s[d] = as.s[d^1];
    as.s[d^1] = update(x);
    return as;
}
int merg(int p1,int p2) {
    if(!p1 || !p2) return p1+p2;
    pushdown(p1); pushdown(p2);
    if(tre[p1].hp < tre[p2].hp) {
        tre[p1].s[1] = merg(tre[p1].s[1],p2);
        return update(p1);
    }
    tre[p2].s[0] = merg(p1,tre[p2].s[0]);
    return update(p2);
}
int ins(int x,int y) {
    np p = spli(x,tre[y].ky);
    return merg(p.s[0],merg(y,p.s[1]));
}
int st[MAXN],cns;
void distr(int x) {
    if(!x) return ; pushdown(x);
    distr(tre[x].s[0]);st[++ cns]=x;distr(tre[x].s[1]);
    tre[x].s[0]=tre[x].s[1]=0;update(x);return ;
}
void print(int x) {
    if(!x) return ; pushdown(x);
    print(tre[x].s[0]); printf(" (%d,%lld)",tre[x].ky,tre[x].nm);
    print(tre[x].s[1]); return ;
}
//--------------------------------------------------------------
LL adn[MAXN];
int bing(int a,int b) {
    if(tre[a].siz < tre[b].siz) swap(a,b);
    cns = 0; distr(b);LL mxb = 0;
    for(int i = 1;i <= cns;i ++) {
        int y = st[i];
        LL nb = max(mxb,tre[y].mx);
        adn[i] = nb-mxb; mxb = nb;
        np p = spli(a,tre[y].ky);
        addnm(y,tre[p.s[0]].mx);
        a = merg(p.s[0],p.s[1]);
    }
    for(int i = 1;i <= cns;i ++) {
        int y = st[i];
        np p = spli(a,tre[y].ky);
        addnm(p.s[1],adn[i]);
        a = merg(p.s[0],merg(y,p.s[1]));
    }
    return a;
}
int addtp(int a,int y) {
    np p = spli(a,tre[y].ky);
    addnm(y,tre[p.s[0]].mx);
    return merg(p.s[0],merg(y,p.s[1]));
}
vector<int> g[MAXN];
int tm[MAXN],mg[MAXN];
int d[MAXN],rt[MAXN];
void dfs(int x) {
    rt[x] = 0;
    for(int i = 0;i < (int)g[x].size();i ++) {
        int y = g[x][i];
        dfs(y);
        rt[x] = bing(rt[x],rt[y]);
    }
    rt[x] = addtp(rt[x],newnode(tm[x],mg[x]));
//    printf("%d:\n",x);
//    print(rt[x]);ENDL;
    return ;
}
int main() {
    n = read(); m = read(); k = read();
    for(int i = 2;i <= n;i ++) {
        s = read(); g[s].push_back(i);
    }
    for(int i = 1;i <= n;i ++) tm[i] = k,mg[i] = 0;
    LL sm = 0;bool flag2 = 0;
    for(int i = 1;i <= m;i ++) {
        s = read();o = read();k = read();
        tm[s] = o; mg[s] = k; sm += k;
        if((int)g[s].size() > 0) flag2 = 0;
    }
    if(flag2) {
        printf("%lld\n",sm);
        return 0;
    }
    dfs(1);
    printf("%lld\n",tre[rt[1]].mx);
    return 0;
}

在看了别人的 DP 分析后，我发现我就是个大傻·逼

这题的合并操作其实并不是很复杂，如果把每个值都打在数轴上，是可以进行线段树合并的。在加入了自己这个值后，可以先暂时不取前缀最大值，而是在合并线段树的时候取！

线段树合并的复杂度是

O

(

n

log

⁡

n

)

\rm O(n\log n)

O(nlogn) ，少了不少，常数也更优：

H

a

n

d

I

n

D

e

v

i

l

\tt HandInDevil

HandInDevil 的全指针美观代码

// 指针，是美的！—— HandInDevil
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
    T t=0;
    char k;
    bool vis=0;
    do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
    while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
    return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define A pair<int,ll>
int s,m,k,d[100005],w[100005];
vector<int>G[100005];
struct node{
    node *l,*r;
    ll m,i,d;//max min
    node(){l=r=NULL;m=i=d=0;}
}*a[100005];
bool Same(node *x){return !x->l&&!x->r;}
void Lz(node *x){
    if(!x||!x->d)return;
    x->m+=x->d;x->i+=x->d;
    if(x->l)x->l->d+=x->d;
    if(x->r)x->r->d+=x->d;
    x->d=0;
}
node* Merge(node *x,node *y){
    Lz(x);Lz(y);
    if(!x||!y)return x?x:y;
    if(Same(y)){
        x->d+=y->m;
        Lz(x);
        delete[] y;
        return x;
    }if(Same(x))return Merge(y,x);
    x->l=Merge(x->l,y->l);
    x->r=Merge(x->r,y->r);
    x->m=max(x->l->m,x->r->m);
    x->i=min(x->l->i,x->r->i);
    if(x->m==x->i){
        delete x->l;x->l=NULL;
        delete x->r;x->r=NULL;
    }delete[] y;
    return x;
}
ll query(node *x,int w,int l,int r){
    if(!x)return 0;Lz(x);
    if(Same(x))return x->m;
    int mid=l+r>>1;
    if(w<=mid)return query(x->l,w,l,mid);
    return query(x->r,w,mid+1,r);
}void era(node *x){
    if(!x)return;
    era(x->l);era(x->r);
    delete[] x;
}
void Turn(node *&x,int l,int r,ll v,int tl,int tr){
    Lz(x);
    if(x->i>=v)return;
    if(x->m<=v&&l==tl&&r==tr){
        x->m=x->i=v;era(x->l);era(x->r);
        x->l=x->r=NULL;
        return;
    }if(Same(x)){
        x->l=new node;x->r=new node;
        x->l->m=x->r->m=x->l->i=x->r->i=x->m;
    }
    int mid=tl+tr>>1;
    if(r<=mid)Turn(x->l,l,r,v,tl,mid);
    else if(mid<l)Turn(x->r,l,r,v,mid+1,tr);
    else Turn(x->l,l,mid,v,tl,mid),Turn(x->r,mid+1,r,v,mid+1,tr);
    x->m=max(x->l->m,x->r->m);
    x->i=min(x->l->i,x->r->i);
    if(x->m==x->i){
        delete x->l;x->l=NULL;
        delete x->r;x->r=NULL;
    }
}
void pr(node *x,int l=1,int r=k){
    if(!x)return;Lz(x);
    if(Same(x))printf("%d %d %lld\n",l,r,x->m);
    pr(x->l,l,l+r>>1);pr(x->r,(l+r>>1)+1,r);
}
void dfs(int n){
    a[n]=new node;
    for(int i=0;i<G[n].size();++i)
        if(G[n][i]){
            dfs(G[n][i]);
            a[n]=Merge(a[n],a[G[n][i]]);
        }
    if(d[n])Turn(a[n],d[n],k,w[n]+query(a[n],d[n],1,k),1,k);
//    cout<<"::"<<n<<endl;pr(a[n]);
}
int main(){
    s=read,m=read,k=read;
    for(int i=2;i<=s;++i)G[read].push_back(i);
    for(int i=1;i<=m;++i){
        int x=read;
        d[x]=read;w[x]=read;
    }dfs(1);
    cout<<query(a[1],k,1,k);
    return 0;
}