OI入门算法详解：含大量优质习题及题解！

文章目录

• 单调队列
• 单调栈
• • • 拓展：区间问题的另一个常见解法——双指针
    • 优先队列
    • 链表
    • 分治
    • ST表

      单调队列

      P2698

      
      （图片来源网络，侵删）

      题目描述，给定一些矩形，有横坐标x，高度h

      求一个最小的窗口，可以使得有一个窗口中的最大高度减最小高度>=d

      输入 d 、 n 每个 x y d、n 每个x y d、n每个xy

      解法：二分答案，判断用一个递增单调队列求滑动窗口最大值，一个递减单调队列求最小值

      启示

      1.答案满足单调性，即本题中窗口变大一定不会使得窗口内最大值-最小值变小，即答案在某个拐点一测check()=0，另一测check()=1，这个拐点就是答案

      2.单调队列滑动窗口不只是可以下标 int x,y; }a[maxn]; int hx=1,tx,hn=1,tn,mx[maxn],mn[maxn],n,d,ans=-1; bool cmp(node x,node y){ return x.x hx=1,tx=0,hn=1,tn=0; for(int i=1;i while(hx scanf("%d%d",&n,&d); for(int i=1;i int mid=(l+r)1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); return 0; } scanf("%d",&n); while(n--){ int op; scanf("%d",&op); if(op==0){ int t;scanf("%d",&t); s1.push(make_pair(t,++cnt)); if(!s2.empty()&&t if(s1.empty()) continue; while(!s2.empty()&&s1.top().second printf("%d\n",s2.empty()?0:s2.top().first); } } return 0; } scanf("%lld%lld",&n,&k); for(int i=1;i if(top){ int l=1,r=top,t=-1; while(l int mid=(l+r)1; if(s[i]-s[sta[mid]]=k) t=sta[mid],l=mid+1; else r=mid-1; } if(t!=-1) ans=min(ans,i-t); } while(top&&s[sta[top]]=s[i]) top--; sta[++top]=i; } printf("%lld",ans); return 0; } scanf("%lld%lld",&n,&k); for(int i=1;i while(head int val,pos; }F[maxn][20]; int que(int l,int r){ int k=log(r-l+1)/log(2); return F[l][k].val scanf("%d",&n); for(int i=1;i F[i][j]=min(F[i][j-1],F[i+(1 while(!s.empty()&&a[i]=a[s.top()]) s.pop(); if(s.empty()) f[i]=0; else f[i]=s.top(); s.push(i); } for(int r=n;r1;r--){ int l=f[r]+1; int t=que(l,r); if(r-t+1=2) ans=max(ans,r-t+1); } printf("%d",ans); return 0; } scanf("%d",&n); for(int i=1;i while(!s.empty()&&a[s.top()] int mid=(l+rr)1; if(mn[mid]=pos) k=mn[mid],rr=mid-1; else l=mid+1; } if(k!=-1) ans=max(ans,r-k+1); s.push(r),mn[++top]=r; } printf("%d",ans); return 0; } scanf("%d%d",&n,&m); for(int i=1;i if(last[a[j]] if(ansj-i+1){ al=i,ar=j,ans=j-i+1; } i++,cnt--; } } printf("%d %d\n",al,ar); return 0; } int x,y,sum; node(int x_,int y_,int sum_){ x=x_,y=y_,sum=sum_; } node(){} }; bool operator return x.sumy.sum; } priority_queue scanf("%d",&n); for(int i=1;i printf("%d ",q.top().sum); node now=q.top(); q.pop(); q.push(node(now.x+1,now.y,a[now.x+1]+b[now.y])); } return 0; }