2016年2月23日 星期二

[NPSC 2015]上司的薪水

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

這裡這裡這裡提供了另外幾項作法,選個喜歡的去實現吧~

可以觀察到,薪水$\geq K$的人的分佈會從根慢慢往下「擴散」並「分岔」

把這個過程倒回來,就變成了薪水$<K$的人慢慢往上「蔓延」並在交叉點「合併」,不會往回跑

假如我們能快速找出每次修改會影響到蔓延體的哪個頂端,並快速算出這個蔓延體頂端的薪水,就能判斷要不要繼續往上蔓延了

可以的!
可以利用並查集維護每個點沿著蔓延體往上會走到哪裡
利用懶惰標記可以在蔓延上去時把懶惰標記往上丟,並直接算出該節點的值

每蔓延一格,就把答案減一
請記得答案是倒著算出來的

時間複雜度:$O(Q\alpha(N))$ (實際上,我的並查集沒有特別優化到$O(\alpha(N))$,複雜度為$O(\log N)$)

code:
#include<cstdio>
#include<cassert>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
int N,Q,PARENT[300000];
vector<int>ET[300000],TOPU;
LL K,COST[300001],TAG[300001];
int ANS[300000];
pair<int,LL>QUERY[300000];
int DJ[300001];
int Find(const int a){return DJ[a]==a?a:(DJ[a]=Find(DJ[a]));}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
//    freopen("s1.in","r",stdin);
    while(scanf("%d%d%lld",&N,&Q,&K)==3)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=1,v;i<N;i++)scanf("%d",&v),ET[PARENT[i]=--v].push_back(i);
        PARENT[0]=N;
        for(int i=0;i<N;i++)COST[i]=TAG[i]=0LL;
        for(int i=0;i<Q;i++)
        {
            auto &q=QUERY[i];
            scanf("%d%lld",&q.first,&q.second),COST[--q.first]+=q.second;
        }
        if(true)
        {
            TOPU.clear();
            queue<int>q;q.push(0);
            while(!q.empty())
            {
                const int u=q.front();q.pop();
                TOPU.push_back(u);
                for(const int nxt:ET[u])q.push(nxt);
            }
            assert((int)TOPU.size()==N);
        }
        for(int i=N-1;i>=0;i--)
        {
            const int u=TOPU[i];
            for(const int nxt:ET[u])COST[u]+=COST[nxt];
        }
        for(int i=0;i<=N;i++)DJ[i]=i;
        int ans=N;
        for(int i=N-1;i>=0;i--)
        {
            const int u=TOPU[i];
            if(COST[u]<K)DJ[u]=PARENT[u],ans--;
        }
        for(int i=Q-1;i>=0;i--)
        {
            ANS[i]=ans;
            const auto &q=QUERY[i];
            int u=Find(q.first);
            TAG[u]+=q.second;
            COST[u]-=q.second;
            while(u!=N&&COST[u]<K)
            {
                const int nxt=Find(PARENT[u]);
                TAG[nxt]+=TAG[u];
                COST[nxt]-=TAG[u];
                u=DJ[u]=nxt,ans--;
            }
        }
        for(int i=0;i<Q;i++)printf("%d\n",ANS[i]);
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原