看心情填坑

http://codeforces.com/problemset/gymProblem/100703/J

为什么CF总喜欢把很简单的东西扯这么复杂。

题意：给定一个n个点，m条边的有向图，每个点存在一个权值t_i，默认t₁=inf，然后从节点1开始，依次发送p个信号，第i个信号存在一个权值g_i，当一个节点收到信号g_i的时候，若t_i>=g_i,t_i-=g_i，若t_i<g_i则这个节点会永久地从图中删去，求每个信号收到的节点数*g_i

我们不要从信号去考虑，从节点去考虑，因为节点的存在一定是有单调性的，即假如第k个信号发出时这个节点存在，那么k-1个信号发出时这个节点也一定存在，然后就可以跑SPFA，最后统计一下v[i]用树状数组维护前缀和算出答案即可。

#include<cstdio>
#include<queue>
using namespace std;
long long tree[200005];
long long head[200005];
long long t[200005],T[200005],v[200005],b[200005],k[200005];
long long n,m,g,cnt,x,y,l,r;
struct edge{
    int to,next;
}e[400005];
queue<int>dl;
long long find(int x){
    int l=0,r=g+1;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(k[mid]<=x)l=mid;
        else r=mid;
    }
    return l;
}
void add(int x,int y){
    cnt++;
    e[cnt].next=head[x];
    e[cnt].to=y;
    head[x]=cnt;
}
long long lowbit(int k){return k&-k;}
void Add(int k,int x){
    while(k<=g){
        tree[k]+=x;
        k+=lowbit(k);
    }
}
int sum(int k){
    int ans=0;
    while(k>0){
        ans+=tree[k];
        k-=lowbit(k);
    }
    return ans;
}
int main(){
    scanf("%d%d%d",&n,&m,&g);
    for(int i=2;i<=n;i++)scanf("%d",&t[i]);
    for(int i=1;i<=g;i++)scanf("%d",&T[i]);
    k[1]=T[1];
    for(int i=2;i<=g;i++)if(k[i-1]>T[i])k[i]=k[i-1];
    else k[i]=T[i];
    for(int i=2;i<=n;i++)t[i]=find(t[i]);
    t[1]=n;
    for(int i=1;i<=n;i++)head[i]=-1,b[i]=true;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    v[1]=g;
    b[1]=false;
    dl.push(1);
    while(!dl.empty()){
        for(int i=head[dl.front()];i>0;i=e[i].next)if(v[dl.front()]>v[e[i].to]){
            if(t[e[i].to]>=v[dl.front()])v[e[i].to]=v[dl.front()];
            else v[e[i].to]=t[e[i].to];
            if(b[e[i].to]){     
                dl.push(e[i].to);
                b[e[i].to]=false;
            }
        }
        b[dl.front()]=true;
        dl.pop();
    }
    for(int i=1;i<=n;i++)if(v[i]>0)Add(v[i],1);
    for(int i=1;i<=g;i++)printf("%I64d ",1LL*(1LL*sum(g)-1LL*sum(i-1))*T[i]);
}