单调栈/单调队列

处理问题

我的理解是： 处理一些相邻大/小值问题

什么意思呢？

比如我记得有一道题，但我忘了题号 形如：

a = 1 2 4 1 2 3 5 8 7 6 b = 0 9 5 4 2 4 3 4 5 1

这样的一个序列，其中每一个a都会向两边进行发射信号，但是只能由第一个比a大的数字接受到，然后获得b的能量，所以我们维护一个单调减的栈就可以了。

具体的：

1. 开始栈是空的，1入栈 [1]
2. 然后2与栈顶比较，发现2比栈顶高，栈顶出栈，4获得栈顶发射的能量。栈空，2入栈. [2]
3. 同理 4>2 ，2出栈4获得2的能量，栈空，4入栈。 [4]
4. 1<4，1获取不到4的能量，1入栈 [4,1]
5. 2>1，2获取1的能量，1出栈，2<4,2获取不到4的能量，2入栈 [4,2] …… 同理反着就可以将能量向左发射。

~就不放代码了，毕竟这个比较简单~

P1901 发射站

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
struct node{
  int v,h;
}a[N];
int n;
int b[N];
deque<node>q;
int ans=0;
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
  {
   cin>>a[i].h>>a[i].v;
   while( q.size() and  a[i].h>q.back().h )
   {
     b[i]+=q.back().v;
     ans=max(ans,b[i]);
     q.pop_back();
   }
   q.push_back(a[i]);
  }
  q.clear();
  for(int i=n;i>=1;i--)
  {
    while( q.size() and a[i].h>q.back().h )
    {
      b[i]+=q.back().v;
      ans=max(ans,b[i]);
      q.pop_back();
    }
    q.push_back(a[i]);
  }
  cout<<ans;
}