洛谷 P2879 [USACO07JAN]区间统计Tallest Cow

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门

题目大意：

n头牛，其中最高身高为h，给出r对关系(x,y)

表示x能看到y，当且仅当y>=x并且x和y中间的牛都比

他们矮的时候，求每头牛的最高身高.

题解： 贪心+差分

将每头牛一开始都设为最高高度。

每一对关系(x,y)，我们将[x+1,y-1]这个区间的身高变为

min(x,y)-1.这样是不对了。因为要维护[x+1,y-1]这个区间里

各个元素的大小关系，所以要将[x+1,y-1]的元素身高都减1.

一开始我是用线段树做的，后来发现题解用的差分。

没有询问的区间修改，差分做就好了。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 10009

using namespace std;

int n,I,H,R;

int C[N];

struct Q{

    int l,r;

}f[N];

bool cmp(Q a,Q b){

    if(a.l==b.l)return a.r<b.r;

    return a.l<b.l;

}

int main(){

    scanf("%d%d%d%d",&n,&I,&H,&R);

    for(int i=;i<=R;i++){

        scanf("%d%d",&f[i].l,&f[i].r);

        if(f[i].l>f[i].r)swap(f[i].l,f[i].r);//忘记交换了

    }

    sort(f+,f+R+,cmp);

    for(int i=;i<=R;i++){

        if(f[i].l==f[i-].l&&f[i].r==f[i-].r)continue;

        C[f[i].l+]++;C[f[i].r]--;

    }

    for(int i=;i<=n;i++){

        C[i]+=C[i-];

        printf("%d\n",H-C[i]);

    }

    return ;

}