题解：P3712 少女与战车

yangzichen1203 · 2026-03-07 20:34:24 · 题解

子树问题等价于区间问题，值域也没什么用。

就是区间加区间 kth。

1

序列分块。

区间加：直接打懒标记，并维护排序后的序列，时间复杂度 O\left(B\log B+\dfrac{n}{B}\right)。

区间 kth：二分答案，问题转换为区间 rank。在散块上暴力比较，整块上二分，时间复杂度 O\left(\left(B+\dfrac{n\log B}{B}\right)\log V\right)。

根号平衡一下，当 B=O(\sqrt{n}\log^{\frac{1}{2}} n) 时，总时间复杂度取到最小值 O(n\sqrt n\log^{\frac{3}{2}}n)。

然后大力卡常一下就过了，就很无语。

2

区间加：发现散块加的部分也是有顺序的，可以直接归并排序，时间复杂度优化到 O\left(B+\dfrac{n}{B}\right)。

区间 kth：我们发现散块部分查询了很多遍，所以可以在二分答案前归并排序，预处理出散块按顺序的排列。每次求 rank 时直接二分即可。时间复杂度优化到 O\left(B+\left(\log B+\dfrac{n\log B}{B}\right)\log V\right)=O\left(B+\dfrac{n\log B\log V}{B}\right)。

根号平衡一下，当 B=O(\sqrt{n}\log n) 时，总时间复杂度优化到 O(n\sqrt n\log n)。

3

唯一能优化的地方就是整块二分了。我们对于所有整块进行分散层叠，优化区间 rank 的多次二分的时间复杂度。可以做到 O\left(B+\left(\dfrac{n}{B}+\log B\right)\log V\right)=O\left(B+\dfrac{n}{B}\log V\right)。

根号平衡一下，当 B=O(\sqrt n\log^{\frac{1}{2}}n)，总时间复杂度取到最小值 O(n\sqrt n\log^{\frac{1}{2}}n)。

4

lxl 说存在严格 O(n\sqrt n) 的区间加区间 kth，但我不会。

:::success[O(n\sqrt n\log n) Code]

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define dFor(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  char gc() {
#if DEBUG  // ??,?????
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }

  void read(int &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') neg = true;
    if (neg)
      for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
      for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
  }

  void read(char *s) {
    char ch = gc();
    for (; isspace(ch); ch = gc());
    for (; !isspace(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }

  void read(char &c) { for (c = gc(); isspace(c); c = gc()); }

  void push(const char &c) {
#if DEBUG  // ??,?????
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }

  void write(long long x) {
    bool neg = false;
    if (x < 0) {
      neg = true;
      push('-');
    }
    static int sta[40];
    int top = 0;
    do {
      sta[top++] = x % 10;
      x /= 10;
    } while (x);
    if (neg)
      while (top) push('0' - sta[--top]);
    else
      while (top) push('0' + sta[--top]);
  }

  void write(long long x, char lastChar) { write(x), push(lastChar); }
} io;
#define MAXN 100005
#define MAXBS 70
#define MAXSZ 1600
int n,m,len,a[MAXN];
namespace Tree{
    int len,fa[MAXN],w[MAXN];
    vector<int> e[MAXN];
    int id[MAXN],sz[MAXN],tot=0;
    void dfs(int u){
        id[u]=++tot;sz[u]=1;
        for(int v:e[u]){
            dfs(v);
            sz[u]+=sz[v];
        }
    }
    void init(){
        For(i,2,n){
            io.read(fa[i]);io.read(w[i]);
            a[i]=a[fa[i]]+w[i];
            e[fa[i]].push_back(i);
        }
        dfs(1);
        static int tmp[MAXN];
        For(i,1,n){
            tmp[id[i]]=a[i];
        }
        For(i,1,n){
            a[i]=tmp[i];
        }
    }
}
namespace Block{
    int sz,bs,L[MAXBS],R[MAXBS],id[MAXN];
    pair<int,int> b[MAXN];
    int add[MAXBS],Min[MAXBS],Max[MAXBS];
    void init(){
        sz=sqrt(n)*log2(n)*0.3;bs=(n+sz-1)/sz;
        cerr<<sz<<' '<<bs<<endl;
        For(i,1,bs){
            L[i]=R[i-1]+1;
            R[i]=min(n,i*sz);
        }
        For(i,1,bs){
            For(j,L[i],R[i]){
                id[j]=i;
            }
        }
        For(i,1,bs){
            For(j,L[i],R[i]){
                b[j]={a[j],j};
            }
            sort(b+L[i],b+R[i]+1);
            Min[i]=b[L[i]].first;
            Max[i]=b[R[i]].first;
        }
    }
    void mo(int l,int r,int k){
        int c=id[l];
        For(i,L[c],R[c]){
            a[i]+=add[c];
            b[i].first+=add[c];
        }
        add[c]=0;
        For(i,l,r){
            a[i]+=k;
        }
        static pair<int,int> va[MAXSZ],vb[MAXSZ];
        int sza=0,szb=0;
        For(i,L[c],R[c]){
            if(b[i].second>=l&&b[i].second<=r){
                b[i].first+=k;
                va[sza++]=b[i];
            }else{
                vb[szb++]=b[i];
            }
        }
        int x=0,y=0,pos=L[c];
        while(x<sza&&y<szb){
            if(va[x]<vb[y]){
                b[pos]=va[x];
                x++;
            }else{
                b[pos]=vb[y];
                y++;
            }
            pos++;
        }
        while(x<sza){
            b[pos]=va[x];
            x++;pos++;
        }
        while(y<szb){
            b[pos]=vb[y];
            y++;pos++;
        }
        Min[c]=b[L[c]].first;
        Max[c]=b[R[c]].first;
    }
    void modify(int l,int r,int k){//O(B+n/B)
        if(id[l]==id[r]){
            mo(l,r,k);
            return ;
        }
        mo(l,R[id[l]],k);
        For(i,id[l]+1,id[r]-1){
            add[i]+=k;
            Min[i]+=k;
            Max[i]+=k;
        }
        mo(L[id[r]],r,k);
    }
    pair<int,int> querycap(int l,int r){
        if(id[l]==id[r]){
            int ansmin=1e9,ansmax=0;
            For(i,l,r){
                ansmin=min(ansmin,a[i]+add[id[l]]);
                ansmax=max(ansmax,a[i]+add[id[l]]);
            }
            return {ansmin,ansmax};
        }
        int ansmin=1e9,ansmax=0;
        For(i,l,R[id[l]]){
            ansmin=min(ansmin,a[i]+add[id[l]]);
            ansmax=max(ansmax,a[i]+add[id[l]]);
        }
        For(i,id[l]+1,id[r]-1){
            ansmin=min(ansmin,Min[i]);
            ansmax=max(ansmax,Max[i]);
        }
        For(i,L[id[r]],r){
            ansmin=min(ansmin,a[i]+add[id[r]]);
            ansmax=max(ansmax,a[i]+add[id[r]]);
        }
        return {ansmin,ansmax};
    }
    int v[MAXSZ*2],szv;
    int rank(int l,int r,int k){
        int sum=lower_bound(v,v+szv,k)-v;
        For(i,id[l]+1,id[r]-1){
            sum+=lower_bound(b+L[i],b+R[i]+1,make_pair(k-add[i],0))-b-L[i];
        }
        return sum+1;
    }
    int query(int l,int r,int k){//O(B+nlogBlogV/B)
        if(r-l+1<k) return -1;
        szv=0;
        if(id[l]==id[r]){
            For(i,L[id[l]],R[id[l]]){
                if(b[i].second>=l&&b[i].second<=r){
                    v[szv++]=b[i].first+add[id[l]];
                }
            }
        }else{
            int x=L[id[l]],y=L[id[r]];
            while(x<=R[id[l]]&&y<=R[id[r]]){
                while(x<=R[id[l]]&&b[x].second<l) x++;
                while(y<=R[id[r]]&&b[y].second>r) y++;
                if(x>R[id[l]]||y>R[id[r]]) break;
                if(b[x].first+add[id[l]]<b[y].first+add[id[r]]){
                    v[szv++]=b[x].first+add[id[l]];
                    x++;
                }else{
                    v[szv++]=b[y].first+add[id[r]];
                    y++;
                }
            }
            while(x<=R[id[l]]){
                while(x<=R[id[l]]&&b[x].second<l) x++;
                if(x>R[id[l]]) break;
                v[szv++]=b[x].first+add[id[l]];
                x++;
            }
            while(y<=R[id[r]]){
                while(y<=R[id[r]]&&b[y].second>r) y++;
                if(y>R[id[r]]) break;
                v[szv++]=b[y].first+add[id[r]];
                y++;
            }
        }
        pair<int,int> cap=querycap(l,r);
        int L=cap.first,R=cap.second;
        while(L<=R){
            int mid=(L+R)/2;
            if(rank(l,r,mid)<=k){
                L=mid+1;
            }else{
                R=mid-1;
            }
        }
        return L-1;
    }
}
int main(){
    freopen("P3712_1.in","r",stdin);
    freopen("AC.out","w",stdout);
    io.read(n);io.read(m);io.read(len);
    Tree::init();
    Block::init();
    while(m--){
        int op,x,k;
        io.read(op);io.read(x);io.read(k);
        if(op==1){
            io.write(Block::query(Tree::id[x],Tree::id[x]+Tree::sz[x]-1,k),'\n');
        }else{
            Block::modify(Tree::id[x],Tree::id[x]+Tree::sz[x]-1,k);
        }
    }
    return 0;
}

:::