[NPSC 2015]上司的薪水

NPSC官方網站好像找不到題目，所以做了題目備份，請參考～

這裡、這裡和這裡提供了另外幾項作法，選個喜歡的去實現吧～

可以觀察到，一個人的薪水是他所有下屬的薪水總和
也就是子樹的總和

因此，我們可以把樹壓平
簡單來說就是把每個節點都給一個編號，讓每個節點的編號$>$以它為根的子樹中所有點的編號
編號$1\sim N$的節點組成了一個序列
這樣任何的子樹都可以用一段區間來表示了，區間右界即是子樹根節點的編號

如果我們用線段樹來維護這個序列的區間和，那麼我們就可以隨時$O(\log N)$得出任一個人目前的薪水是多少了！

可是總不可能每次加薪完就檢查所有$N$個人吧

可以發現，每個人的薪水只會增加，不會減少
所以我們可以二分搜每個人的薪水甚麼時候會$\geq K$
這樣每一時刻有幾個人的薪水$\geq K$就可以很容易的算出來了

可是要判斷某個人在某個時間點的薪水是否$\geq K$時，需要這個時間點的線段樹
總不可能$N$個人讓線段樹重建$N$次吧



可以觀察到，很多人會共用同一個時間點的判斷，那就先將這個時間點的線段樹弄出來，然後大家一次判斷完就好啦～

這就是整體二分的概念

時間複雜度：$O((N+Q)\log Q\log N)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<utility>
using namespace std;
typedef long long LL;
struct SegTree
{
    int N;
    LL SUM[300000*4];
    void Build(const int id,const int l,const int r)
    {
        SUM[id]=0LL;
        if(l<r)
        {
            const int mid=(l+r)/2;
            Build(id*2,l,mid),Build(id*2+1,mid+1,r);
        }
    }
    void Build(const int _N){N=_N;Build(1,0,N-1);}
    void Modify(const int id,const int l,const int r,const int loc,const LL &val)
    {
        SUM[id]+=val;
        if(l<r)
        {
            const int mid=(l+r)/2;
            if(loc<=mid)Modify(id*2,l,mid,loc,val);
            else Modify(id*2+1,mid+1,r,loc,val);
        }
    }
    void Modify(const int loc,const LL &val){Modify(1,0,N-1,loc,val);}
    LL Query(const int id,const int l,const int r,const int bl,const int br)
    {
        if(r<bl||br<l)return 0LL;
        if(bl<=l&&r<=br)return SUM[id];
        const int mid=(l+r)/2;
        return Query(id*2,l,mid,bl,br)+Query(id*2+1,mid+1,r,bl,br);
    }
    LL Query(const int bl,const int br){return Query(1,0,N-1,bl,br);}
}SEG_TREE;
struct QueryType
{
    int u;
    LL x;
};
vector<QueryType>QUERY;
pair<int,int>SEG[300000];//not related to SEG_TREE
vector<int>ET[300000];
void BuildSEG(const int u,int &clock)
{
    SEG[u].first=clock;
    for(const int nxt:ET[u])BuildSEG(nxt,clock);
    SEG[u].second=clock++;
}
int ANS[300001];
LL K;
void Solve(const int l,const int r,const vector<int>&staffs)
{
    if(staffs.empty())return;
    if(l==r){ANS[r]+=staffs.size();return;}
    const int mid=(l+r)/2;
    for(int i=l;i<=mid;i++)
    {
        const QueryType &q=QUERY[i];
        SEG_TREE.Modify(SEG[q.u].second,q.x);
    }
    vector<int>left_staffs,right_staffs;
    for(const int s:staffs)
    {
        if(SEG_TREE.Query(SEG[s].first,SEG[s].second)<K)right_staffs.push_back(s);
        else left_staffs.push_back(s);
    }
    Solve(mid+1,r,right_staffs);
    for(int i=mid;i>=l;i--)
    {
        const QueryType &q=QUERY[i];
        SEG_TREE.Modify(SEG[q.u].second,-q.x);
    }
    Solve(l,mid,left_staffs);
    vector<int>().swap(left_staffs);
    vector<int>().swap(right_staffs);
}
int N,Q;
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
//    freopen("s2.in","r",stdin);
    for(;scanf("%d%d%lld",&N,&Q,&K)==3;)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=1,parent;i<N;i++)scanf("%d",&parent),ET[--parent].push_back(i);
        if(true){int clock=0;BuildSEG(0,clock);assert(clock==N);}
        QUERY.clear();
        for(int i=0;i<Q;i++)
        {
            static QueryType q;
            scanf("%d%lld",&q.u,&q.x),q.u--;
            QUERY.push_back(q);
        }
        vector<int>staffs;
        for(int i=0;i<N;i++)staffs.push_back(i);
        for(int i=0;i<Q;i++)ANS[i]=0;
        SEG_TREE.Build(N);
        Solve(0,Q,staffs);
        for(int i=1;i<Q;i++)ANS[i]+=ANS[i-1];
        for(int i=0;i<Q;i++)printf("%d\n",ANS[i]);
    }
    return 0;
}