单调队列和单调栈问题优化思路：
栈/队列里面有没有元素是没有用的，有的话想办法删掉，使队列保持单调性
然后再在单调的队列里面查找某一特定值

#include<iostream>
using namespace std;

const int N = 1e6+10;
int a[N],q[N];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)    scanf("%d", &a[i]);
   // for(int i=0;i<n;i++)    printf("%d ", a[i]);
    int hh = 0, tt = -1;//初始化队列
    for(int i=0; i<n; i++){
        if(hh <= tt && i-k+1 > q[hh]) hh++;//保证队列包含窗口里的所有元素
        while(hh<=tt && a[q[tt]] >= a[i]) tt--;//出队
        q[++tt] = i;//入队

        if(i>=k-1)  printf("%d ", a[q[hh]]);//输出队头元素
    }
    puts("");
    hh = 0, tt = -1;//初始化队列
    for(int i=0; i<n; i++){
        if(hh <= tt && i-k+1 > q[hh]) hh++;//保证队列包含窗口里的所有元素
        while(hh<=tt && a[q[tt]] <= a[i]) tt--;//出队
        q[++tt] = i;//入队

        if(i>=k-1)  printf("%d ", a[q[hh]]);//输出队头元素
    }

    return 0;
}

#include<iostream>
using namespace std;
//根据题目的特点，排除掉一些不可能作为输出的数
//单调栈
const int N = 1E5+10;
int stk[N],tt = 0;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(tt && stk[tt]>=x) tt--;//维护栈里面的严格单调
        if(tt)
            cout<<stk[tt]<<" ";
        else cout<<-1 <<" ";
        stk[++tt] = x;
    }
    return 0;
}

#include<iostream>
#include<string>
using namespace std;

const int N = 1E5+10;
int qu[N],hh=0,tt=-1;// 设置头指针和尾指针

int main(){
    int m;
    cin>>m;
    while(m--){
        string str;
        cin>>str;
        if(str == "push"){
            int x;
            cin>>x;
            qu[++tt] = x;
        }
        else if(str == "pop")
            hh++;
        else if(str == "empty"){
            if(hh<=tt)//tt初始设为-1
                cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        else cout<<qu[hh]<<endl;
    }
    return 0;
}

中缀表达式求值：画出中序表达式的树，可以递归来求解
叶子节点都是数，非叶子节点都是运算符
记住模板——hashmap来存优先级（main里面不涉及对运算符的处理，方便运算符的扩充）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<unordered_map>
using namespace std;

stack<int> nums;
stack<char> op;
void eval(){//具体计算
    auto b = nums.top(); nums.pop();
    auto a = nums.top(); nums.pop();
    auto c = op.top(); op.pop();
    int x;
    if(c == '+')
        x = a + b;//注意a,b的顺序
    else if(c == '-')
        x = a - b;
    else if(c == '*')
        x = a * b;
    else if (c =='/')
        x = a / b;
    nums.push(x);
}
int main(){
    unordered_map<char,int> pr{{'+',1}, {'-',1}, {'*',2}, {'/',2 }};//符号的优先级
    string str;
    cin>>str;
    for(int i=0; i<str.size(); i++){
        auto c = str[i];
        if(isdigit(c)){ //处理数字
            int x = 0, j = i;
            while(j<str.size() && isdigit(str[j]))
                x = x*10 + str[j++] - '0';
            i = j-1;
            nums.push(x);
        }
        else if(c == '(') op.push(c);//左括号进，可以理解为一种标记
        else if(c == ')'){
            while(op.top() != '(') eval();
            op.pop();//左括号出
        }
        else{//普通运算符
            while(op.size() && pr[op.top()] >= pr[c])   eval(); 
            op.push(c);
        }
    }
    while(op.size()) eval();//计算剩下的
    cout<<nums.top()<<endl;
    return 0;
}

#include<iostream>
#include<string>
using namespace std;

const int N = 1e5+10;
int stk[N],tt;//栈，栈顶指针
void push(int x){
    stk[++tt]=x;
}
void pop(){
    tt--;
}
int query(){
    return stk[tt];
}
bool empty(){
    if(!(tt>0))
        return true;
    else return false;
}

int main(){
    int m;
    string op;
    cin>>m;
    while(m--){
        cin>>op;
        if(op=="push"){
            int x;
            cin>>x;
            push(x);
        }
        else if(op=="pop")
            pop();
        else if(op=="empty"){
            if(empty())
                cout<<"YES"<<endl;
            else    cout<<"NO"<<endl;
        }
        else
            cout<<query()<<endl;
    }
    return 0 ;
}

#include<iostream>
#include<string>
using namespace std;

const int N = 1E5+10;
int e[N],l[N],r[N],idx;//数组模拟实现双链表

void Init(){
    //0是第一个节点，1是最后一个结点（可以理解为指针？节点√）
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
void insert(int k, int a){//在k右边插入一个结点
    e[idx] = a;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void remove(int k){//删除一个结点
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    Init();
    int m;
    cin>>m;
    string op;
    while(m--){
        cin>>op;
        if(op=="L"){
            int a;
            cin>>a;
            insert(0,a);
        }
        else if(op=="R"){
            int a;
            cin>>a;
            insert(l[1],a);
        }
        else if(op=="D"){
            int k;
            cin>>k;
            remove(k+1);
        }
        else if(op=="IL"){
            int k,a;
            cin>>k>>a;
            insert(l[k+1],a);
        }
        else if(op=="IR"){
            int k,a;
            cin>>k>>a;
            insert(k+1,a);
        }
    }

    for(int i=r[0]; i!=1;i = r[i])
        cout<<e[i]<<" ";
    return 0;
}

#include<iostream>

using namespace std;

//idx:现在用到了哪个节点
const int N = 1e5+10;
int head, e[N], ne[N], idx;
//初始化
void Init(){
    head = -1;//表示NULL
    idx = 0;
}
//在链表头插入一个结点
void insert_head(int a){
    e[idx] = a;
    ne[idx] = head;
    head = idx++;
}
//在k结点后面插入一个结点
void insert(int k,int a){
    e[idx] = a;
    ne[idx] = ne[k];
    ne[k] = idx++;
}
//移除k结点之后的节点
void remove(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    int m;
    cin>>m;
    char op;
    Init();
    while(m--){
        cin>>op;
        if(op == 'H'){
           int a;
           cin>>a;
           insert_head(a);
        }
        else if(op =='D'){
            int k;
            cin>>k;
            if(!k) head = ne[head];//特判
            else remove(k-1);
        }
        else{
            int k,a;
            cin>>k>>a;
            insert(k-1,a);
        }
    }
    int tmp = head;
    while(tmp != -1){
        cout<<e[tmp]<<" ";
        tmp = ne[tmp];
    }
    return 0;
}

//合并区间
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
vector<PII>segs;
void merge(vector<PII> &segs){
    vector<PII> res;
    int st = -2e9,ed = -2e9;//正确处理第一个区间
    for(int i=0;i<segs.size();i++){
        if(segs[i].first>ed){
            if(st != -2e9)  res.push_back({st,ed});
            st = segs[i].first; 
            ed = segs[i].second;
        }
        else ed = max(ed,segs[i].second);
    }
    if(st != -2e9) res.push_back({st,ed});//最后一个区间放进去
    segs = res;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    //按左端点排序
    sort(segs.begin(),segs.end());
    //合并区间
    merge(segs);
    cout<<segs.size()<<endl;
    return 0;
}

//离散化可能用到的下标

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 3e5+10;
int a[N],s[N];
vector<int> alls;
vector<PII> add, query;

int Find(int x){//找到离散化之后小数组的下标(有序的离散化)
    int l = 0, r = alls.size()-1;
    while(l<r){
        int mid = l+r>>1;
        if(alls[mid]>=x) r = mid;
        else l = mid+1;
    }
    return r+1;
}

int main(){
    int n,m;
    cin>>n>>m;
    //读取添加信息
    for(int i=0; i<n; i++){
        int x,c;
        cin>>x>>c;
        alls.push_back(x);
        add.push_back({x,c});
    }
    //读取查询信息
    for(int i=0; i<m; i++){
        int l,r;
        cin>>l>>r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l,r});
    }
    //去重
    sort(alls.begin(), alls.end());//有序离散化
    alls.erase(unique(alls.begin(),alls.end()), alls.end());

    //插入
    for(auto item : add){
        int i = Find(item.first);
        a[i] += item.second;
    }
    //前缀和
    for(int i=1; i<=alls.size();i++)    s[i] = s[i-1] + a[i];
    //查询
    for(auto item : query){
        int l = Find(item.first);
        int r = Find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }

    return 0;
}

核心:指针移动满足单调特性就可以使用双指针算法

模板：
for(int i=0,j=0; i<n; i++){ while(某种条件) j++; //具体题目具体处理 }
类别1：
对于一个序列，用两个指针维护一个区间
类别2：
对于两个序列，维护某种次序，例如归并排序中的归并两个有序序列的操作