【POJ 3263】 Tallest Cow

【题目链接】

http://poj.org/problem?id=3263

【算法】

若A和B两头牛可以互相看见，那么说明中间的牛的高度都至少比它们少1，因此，我们可以引入一个差分数组c

对于每组关系，我们将c[a+1]减一，c[b]加一

最后，每头牛的最高高度就是 h + c的前缀和

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 100010

int i,a,b,n,p,h,m;

map< pair<int,int>,bool > mp;

int d[MAXN];

int main()

{

        scanf("%d%d%d%d",&n,&p,&h,&m);

        for (i = ; i <= m; i++)

        {

                scanf("%d%d",&a,&b);

                if (a > b) swap(a,b);

                if (mp[make_pair(a,b)]) continue;

                d[a+]--; d[b]++;

                mp[make_pair(a,b)] = true;

        }

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

        {

                d[i] += d[i-];

                printf("%d\n",h+d[i]);

        }

        return ;

}