【题意】n头牛，其中最高h。给定r组关系a和b，要求满足h[b]>=h[a]且a、b之间都小于min(h[a],h[b])，求第i头牛可能的最高高度。

【算法】差分

【题解】容易发现r组关系只能包含或不相交。

先假设所有牛是最高高度。

对于一组关系(a,b)显然只需要让区间[a+1,b-1]整体-1就好了。使用差分维护。

特别判断a=b和a=b+1和多区间LR一样的情况。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=10010;int a[maxn],n,lll,h,m;struct cyc{
    int l,r;}b[maxn];bool cmp(cyc a,cyc b){
    return a.l
          
           
            b[i].r)swap(b[i].l,b[i].r); } sort(b+1,b+m+1,cmp);int tot=1; for(int i=2;i<=m;i++)if(b[i].l!=b[i-1].l||b[i].r!=b[i-1].r)b[++tot]=(cyc){b[i].l,b[i].r}; m=tot; for(int i=1;i<=m;i++)if(b[i].l