因为给出的每一对牛需要相互看见
所以在本例中所有区间都不存在区间A交区间B等于区间C的情况(此时C是不等于A,B的一个区间)
第一种情况:例如给出的三个区间(1,2),(2,4),(4,5)
他们三个之间互不干扰只要确定每一个区间内的所有节点取值就可以了 。
第二种情况:如(2,5),(2,6),(2,7)
如果最高的牛点是2,且h=5
对于区间(2,5)那么按照这个顺序对点给出长度就会有(5,4,4,5)
对区间(2,6)给出高度得到(5,4,4,4,5)
(2,7)给出(5,4,4,4,4,4,5)
这个时候与区间(2,5)就矛盾了
因为当区间具有包含关系的时候,更新大区间内所有点的值时会改变小区间的值。
所以要先更新大区间再更新小区间,让他符合所有的区间限制。
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 5010 , M = 10010;
int n,p,hp,m;
int h[N];
struct len {
int l, r;
bool operator < (const len &x) const { // 需要加 const 限定符
if (l < x.l) return true;
else if (l == x.l) return r > x.r;
else return false;
}
} L[M];
int main()
{
cin>>n>>p>>hp>>m;
for(int i = 1 ; i <= n ; i++) h[i] = hp;
for(int i = 0 ; i < m ; i++){
int x,y;
cin>>x>>y ;
int l = min(x,y) , r = max(x,y);
L[i] = {l,r} ;
}
sort(L,L+m) ;
for(int i = 0 ; i < m ; i++){
int l = L[i].l , r = L[i].r ;
if(r-1==l) continue;
else {
int hl = h[l] , hr = h[r] ;
int temp = min(hl,hr) ;
for(int j = l+1 ; j < r ; j++){
if(h[j]>=temp)
h[j] = temp-1;
}
}
}
for(int i = 1 ;i <= n ; i++)
cout << h[i] <<endl;
}