题解：P3712 少女与战车

· · 题解

前言

纯由乃打扑克啊，会了那道题这道题就差不多了。对就是这个入重编号完了之后修改的时候用的还是原编号调试两个小时。

解题过程

观察到这题在对 x 与他的祖先的路径的权值加 k 时相当于将 x 及其子树内所有节点的深度增加 k。那么我们把树按 dfs 序跑下来之后，由于子树在 dfs 序上是连续的，所以就变成了区间加区间 k 小模板。

会的可以直接做了，不过这是模板，所以还是讲一下做法。我们先按块长为 B 分块，对于每块，维护一个排序后的数组。在修改时，散块直接重构，整块打标记便可。在查询时，我们二分答案，通过二分最终可能的答案，然后在进行查询排名便可。查询排名的话，散块直接枚举 \leq k 的数的个数。对于整块由于我们有了排序后的数组，所以直接在这个数组上二分便可。

上述过程时间复杂度大概是 O(nB\log B+n\log B\log V) 的，块长调到900稳过。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,len,a[100005],b[100005],c[100005],t,siz1,l[405],r[405],p[100005],siz[100005],id[100005],cnt,f[100005],tag[100005]; 
vector<int>g[100005];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void dfs(const int x,const int fa){
    c[x]+=c[fa];
    f[x]=fa;
    id[x]=++cnt;
    a[cnt]=c[x];
    b[cnt]=c[x];
    siz[x]=1;
    for(int i=0;i<g[x].size();++i){
        if(g[x][i]==fa)continue;
        dfs(g[x][i],x);
        siz[x]+=siz[g[x][i]];
    }
}
inline void modify(const int x,const int y,const int k){
    if(p[x]==p[y]){
        for(int i=x;i<=y;++i)a[i]+=k;
        for(int i=l[p[x]];i<=r[p[y]];++i)b[i]=a[i];
        sort(b+l[p[x]],b+r[p[y]]+1);
    }
    else{
        for(int i=x;i<=r[p[x]];++i)a[i]+=k;
        for(int i=l[p[x]];i<=r[p[x]];++i)b[i]=a[i];
        sort(b+l[p[x]],b+r[p[x]]+1);
        for(int i=p[x]+1;i<=p[y]-1;++i)tag[i]+=k;
        for(int i=l[p[y]];i<=y;++i)a[i]+=k;
        for(int i=l[p[y]];i<=r[p[y]];++i)b[i]=a[i];
        sort(b+l[p[y]],b+r[p[y]]+1);
    }
}
inline int getmin(const int x,const int y){
    int ans=INT_MAX;
    if(p[x]==p[y])for(int i=x;i<=y;++i)ans=min(ans,a[i]+tag[p[x]]);
    else{
        for(int i=x;i<=r[p[x]];++i)ans=min(ans,a[i]+tag[p[x]]);
        for(int i=p[x]+1;i<=p[y]-1;++i)ans=min(ans,b[l[i]]+tag[i]);
        for(int i=l[p[y]];i<=y;++i)ans=min(ans,a[i]+tag[p[y]]);
    }
    return ans;
}
inline int getmax(const int x,const int y){
    int ans=-INT_MAX;
    if(p[x]==p[y])for(int i=x;i<=y;++i)ans=max(ans,a[i]+tag[p[x]]);
    else{
        for(int i=x;i<=r[p[x]];++i)ans=max(ans,a[i]+tag[p[x]]);
        for(int i=p[x]+1;i<=p[y]-1;++i)ans=max(ans,b[r[i]]+tag[i]);
        for(int i=l[p[y]];i<=y;++i)ans=max(ans,a[i]+tag[p[y]]);
    }
    return ans;
}
inline int getrank(const int x,const int y,const int k){
    int cnt=0;
    if(p[x]==p[y]){
        for(int i=x;i<=y;++i)if(a[i]+tag[p[x]]<=k)cnt++;
    }
    else{
        for(int i=x;i<=r[p[x]];++i)if(a[i]+tag[p[x]]<=k)cnt++;
        for(int i=l[p[y]];i<=y;++i)if(a[i]+tag[p[y]]<=k)cnt++;
        for(int i=p[x]+1;i<=p[y]-1;++i){
            if(b[l[i]]+tag[i]>k)continue;
            if(b[r[i]]+tag[i]<=k){
                cnt+=r[i]-l[i]+1;
                continue;
            }
            int l1=l[i],r1=r[i],mid;
            while(l1<=r1){
                mid=(l1+r1)>>1;
                if(b[mid]+tag[i]<=k)l1=mid+1;
                else r1=mid-1;
            }
            cnt+=r1-l[i]+1;
        }
    }
    return cnt;
}
inline int query(const int x,const int y,const int k){
    if(k<1||k>y-x+1)return -1;
    int l1=getmin(x,y),r1=getmax(x,y),mid;
    while(l1<=r1){
        mid=(l1+r1)>>1;
        if(getrank(x,y,mid)<k)l1=mid+1;
        else r1=mid-1;
    }
    return l1;
}
signed main(){
//  freopen("P3712.in","r",stdin);
//  freopen("P3712.out","w",stdout);
    n=read(),m=read(),len=read();
    for(int i=2;i<=n;++i){
        int u=read();
        g[u].push_back(i);
        g[i].push_back(u);
        c[i]=read();
    }
    dfs(1,0);
    siz1=sqrt(n*__lg(n));
    siz1=max(1,siz1);
    t=n/siz1;
    for(int i=1;i<=t;++i){
        l[i]=(i-1)*siz1+1;
        r[i]=i*siz1;
    }
    if(r[t]!=n){
        t++;
        l[t]=r[t-1]+1;
        r[t]=n;
    }
    for(int i=1;i<=t;++i){
        sort(b+l[i],b+r[i]+1);
        for(int j=l[i];j<=r[i];++j){
            p[j]=i;
        }
    }
    while(m--){
        int op=read(),x=read(),k=read();
        if(op==1)cout<<query(id[x],id[x]+siz[x]-1,k)<<'\n';
        else modify(id[x],id[x]+siz[x]-1,k);
    }
    return 0;
}