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

目录：

---

题目：

传送门

---

分析：

我们有一个简单而高效的做法，就是建一个D数组，对于每对牛(A，B)$(A，B)$，令D[A+1]−1$D[A+1]-1$，D[B]+1$D[B]+1$。其含义是：“身高减小1”的影响从A+1$A+1$开始，持续到B−1$B-1$，在B结束。最后，用数组C计算D的前缀和，输出数组C的值+最高的身高即可。

---

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define LL long long
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
map<pair<int,int>,bool> e;
int d[10001],c[10001];
int main()
{
    int a,b;
    int n=read(),p=read(),h=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        a=read();b=read();
        if(a>b) swap(a,b);
        if(e[make_pair(a,b)]) continue;
        d[a+1]--;d[b]++;
        e[make_pair(a,b)]=true;
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+d[i];
        printf("%d\n",h+c[i]);
    }
    return 0;
}