POJ – 3263 差分+前缀和

给出n头牛的身高，和m对关系（a[i]与b[i]可以相互看见。即他们中间的牛都比他们矮）。已知最高的牛为第p头，身高为h，求每头牛的身高最大可能是多少。

只需不断维护相对值的前缀就能得到解

这种思想第一次是在树状数组区间更新那里看到的,由于题目要求是1~n所以直接可以用前缀和维护

注意不能直接-1 +1

/*H E A D*/
int delta[maxn];
map<P,int> vis;
int main(){
    int n,I,h,r,a,b;
    while(~iin(n)){
        I=read();h=read();r=read();
        memset(delta,0,sizeof delta);
        vis.clear();
        rep(i,1,r){
            a=read();b=read();
            if(a>b) swap(a,b);//strict prefix
            if(vis[P(a,b)]) continue;
            vis[P(a,b)]=1;
            delta[a+1]--;delta[b]++;//-1 +1
        }
        rep(i,1,n){
            delta[i]+=delta[i-1];
        }
        rep(i,1,n){
            println(delta[i]+h);
        }
    }
    return 0;
}