AcWing 101. 最高的牛（字首和、stl的運用）

題幹：

有 N 頭牛站成一行，被編隊為1、2、3…N，每頭牛的身高都為整數。

當且僅當兩頭牛中間的牛身高都比它們矮時，兩頭牛方可看到對方。

現在，我們隻知道其中最高的牛是第 P 頭，它的身高是 H ，剩餘牛的身高未知。

但是，我們還知道這群牛之中存在着 M 對關系，每對關系都指明了某兩頭牛 A 和 B 可以互相看見。

求每頭牛的身高的最大可能值是多少。

1≤N≤10000

1≤H≤1000000

1≤A,B≤10000

0≤M≤10000

此題中給出的關系對可能存在重複

思路：

因為兩頭牛a、b之間想要互相看到，那麼a、b之間的牛都必須比a、b中的低值至少低1，是以我們假定所有的牛都是最高的，然後每次将a、b之間的牛的高度減一。

但因為n的範圍較大，直接暴力容易逾時，是以運用字首和知識，我們隻需要記錄每個值與最大值的內插補點就行，然後先用d[i]表示從第i頭到最後一頭牛與最高值的內插補點，這樣每次出現a、b，隻需要d[a+1]-1，d[b]+1（到第b頭就不變了，是以要+1），最後 跑一遍d[i]=d[i]+d[i-1]就可以得到真正的內插補點d[i]。

然後考慮重複的關系，用map映射出現次數，用pair整合a、b的關系，實作見代碼

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int inf= 0x3f3f3f3f;
int n,p,h,m,a,b;
int d[10010];
pair<int,int>t;
map<pair<int,int>,int>q;
int main()
{
    scanf("%d%d%d%d",&n,&p,&h,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        if(a>b)  swap(a,b);
        t=make_pair(a,b);
        if(a!=b&&q[t]==0){
            q[t]++;
            d[b]++;
            d[a+1]--;
        }
    }
    for(int i=1;i<=n;i++){
        d[i]=d[i]+d[i-1];
        printf("%d\n",h+d[i]);
    }
    return 0;
}