题意：

n头牛，如果某头牛左边距离D以内有高度至少是它的两倍的牛，右边也有，则此牛会感觉到不舒服。问多少牛会不舒服。n≤50000

题解：

用单调队列维护距离D以内的区间最大值，判断是否至少是当前牛的两倍，再倒回去做一遍即可。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 100010 6 using namespace std; 7  8 inline int read(){ 9     char ch=getchar(); int f=1,x=0;10     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();12     return f*x;13 }14 struct nd{
   int x,h;}; nd nds[maxn];15 bool cmp(nd a,nd b){
   return a.x
        
         d)l++; if(l<=r&&q2[l]>=(nds[i].h<<1))unc[i]=1;21         while(l<=r&&q2[r]
         
          =1;i--){25         while(l<=r&&q1[l]-nds[i].x>d)l++; if(l<=r&&q2[l]>=(nds[i].h<<1)&&unc[i])ans++;26         while(l<=r&&q2[r]
         
        
       
      
     

 

20160812