[NPSC 2015]上司的薪水

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

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

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

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

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

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

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

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

其實，利用持久化線段樹，我們可以用$O(N\log Q)$的時間和$O(N\log Q)$的記憶體，同時擁有每一個時間點的$Q$棵線段樹

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

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<utility>
using namespace std;
typedef long long LL;
struct Node
{
    Node *ch[2];
    LL sum;
}BUFFER[12000000],*NEW;
Node *NewNode(const LL &_sum)
{
    assert(NEW<BUFFER+12000000);
    NEW->ch[0]=NEW->ch[1]=NULL;
    NEW->sum=_sum;
    return NEW++;
}
Node *Build(const int l,const int r)
{
    Node *ans=NewNode(0LL);
    if(l<r)
    {
        const int mid=(l+r)/2;
        ans->ch[0]=Build(l,mid),ans->ch[1]=Build(mid+1,r);
    }
    return ans;
}
Node *Modify(Node *o,const int l,const int r,const int loc,const LL &val)
{
    Node *ans=NewNode((o->sum)+val);
    if(l<r)
    {
        const int mid=(l+r)/2;
        if(loc<=mid)ans->ch[0]=Modify(o->ch[0],l,mid,loc,val),ans->ch[1]=o->ch[1];
        else ans->ch[0]=o->ch[0],ans->ch[1]=Modify(o->ch[1],mid+1,r,loc,val);
    }
    return ans;
}
LL Query(Node *o,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 o->sum;
    const int mid=(l+r)/2;
    return Query(o->ch[0],l,mid,bl,br)+Query(o->ch[1],mid+1,r,bl,br);
}
int N,Q;
LL K;
pair<int,int>SEG[300000];
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++;
}
Node *TREE[300001];
int ANS[300002];
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();
        NEW=BUFFER;
        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);}
        TREE[0]=Build(0,N-1);
        for(int i=1,u;i<=Q;i++)
        {
            static LL x;
            scanf("%d%lld",&u,&x),u--;
            TREE[i]=Modify(TREE[i-1],0,N-1,SEG[u].second,x);
        }
        for(int i=0;i<=Q+1;i++)ANS[i]=0;
        for(int i=0;i<N;i++)
        {
            int l=0,r=Q+1;
            while(l<r)
            {
                const int mid=(l+r)/2;
                if(Query(TREE[mid],0,N-1,SEG[i].first,SEG[i].second)<K)l=mid+1;
                else r=mid;
            }
            ANS[r]++;
        }
        for(int i=1;i<=Q;i++)ANS[i]+=ANS[i-1];
        for(int i=1;i<=Q;i++)printf("%d\n",ANS[i]);
    }
    return 0;
}