$T1$ 小组队列

思路；纯模拟，队列套队列

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> mp;
struct P{
    deque<int> q;
    int num;
};
deque<P> d;
void solve(int qwe){
    int t;
    cin >> t;
    if(t==0) exit(0);
    for(int i=1;i<=t;i++){
        int n;
        cin >> n;
        for(int j=1;j<=n;j++){
            int x;
            cin >> x;
            mp[x]=i;
        }
    }
    string ml;
    cout << "Scenario #" << qwe << endl;
    while(1){
        cin >> ml;
        if(ml=="ENQUEUE"){
            int x;
            cin >> x;
            int y=mp[x];
            int flag=0;
            for(int i=0;i<d.size();i++){
                if(d[i].num==y){
                    d[i].q.push_back(x);
                    flag=1;
                    break;
                }
            }
            if(!flag){
                deque<int> f;
                f.push_back(x);
                d.push_back(P{f,y});
            }
        }else if(ml=="DEQUEUE"){
            if(d.empty()) continue;
            while(d.front().q.empty()&&d.size()) d.pop_front();
            cout << d.front().q.front() << endl;
            d.front().q.pop_front();
        }else{
            return;
        }
    }
}
signed main(){
    int i=0;
    while(1){
    	d.clear();
        solve(++i);
    }
}

$T2$ 蚯蚓

用三个队列共同维护原数值，[px]那段数值，x-[px]那段数值，其他模拟即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
queue<int> a,b,c;
const int N=1e5+50;
int a1[N];
bool cmp(int a,int b){
	return a>b;
}
signed main(){
    int n,m,q,u,v,t;
    cin >> n >> m >> q >> u >> v >> t;//p=u/v
    int T=0;
    for(int i=1;i<=n;i++){
        int ai;
        cin >> ai;
        a1[i]=ai;
    }
    sort(a1+1,a1+n+1,cmp);
    for(int i=1;i<=n;i++){
        a.push(a1[i]);
    }
    int dq=0;
    for(int ccf=1;ccf<=m;ccf++){
        int A,B,C,x;
        A=B=C=-2e9;
        if(!a.empty()) A=a.front();
        if(!b.empty()) B=b.front();
        if(!c.empty()) C=c.front();
        x=max(A,max(B,C));
        if(x==A){
            a.pop();
        }else if(x==B){
            b.pop();
        }else{
            c.pop();
        }
        x+=dq;
        T++;
        if(T==t) T=0,cout << x << " ";
        b.push(x*u/v-dq-q);
        c.push(x-(x*u/v)-dq-q);
        dq+=q;
    }
    cout << endl;
    int NM=n+m;
    T=0;
    while(NM--){
        int A,B,C,x;
        A=B=C=-2e9;
        if(!a.empty()) A=a.front();
        if(!b.empty()) B=b.front();
        if(!c.empty()) C=c.front();
        x=max(A,max(B,C));
        if(x==A){
            a.pop();
        }else if(x==B){
            b.pop();
        }else{
            c.pop();
        }
        T++;
        if(T==t) T=0,cout << x+m*q << " ";
    }
}

$T3$ 双端队列

思路：先将数组排好序，再分成尽量少的几段，使得每一段都对应原问题中一个合法的双端队列。

代码：

#include <bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define num second
using namespace std;
const int N=2e5+50;
PII a[N];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i].x;
		a[i].num=i;
	}
	sort(a,a+n);
	int ans=1,flag=0;
	for(int i=0,ed=n+1;i<n;){
		int j=i;
		while(j<n&&a[j].x==a[i].x) j++;
		int mn=a[i].num,mx=a[j-1].num;
		if(!flag){
			if(ed>mx) ed=mn;
			else flag=1,ed=mx;
		}else{
			if(ed<mn){
				ed=mx;
			}else{
				flag=0,ed=mn;
				ans++;
			}
		}
		i=j;
	}
	cout << ans << endl;
}

$T4$ 最大子序和

思路：用一个单调队列维护区间信息即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+50;
int a[N];
deque<int> q;
signed main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
    	cin >> a[i];
    	a[i]+=a[i-1];
	}
	int mx=a[1];
	for(int i=1;i<=n;i++){
		if(q.size()){
			if(q.front()<i-m) q.pop_front();
			mx=max(mx,a[i]-a[q.front()]);
		}
		while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
		q.push_back(i);
	}
	cout << mx;
}

$T5$ 滑动窗口

思路：模版题

代码：勉为其难给一下吧

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+50;
int a[N];
deque<int> q;
signed main(){
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        while(q.size()&&i-k+1>q.front()) q.pop_front();
        while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) cout << a[q.front()] << " ";
    }
    cout << endl;
    q.clear();
    for(int i=0;i<n;i++){
        while(q.size()&&i-k+1>q.front()) q.pop_front();
        while(q.size()&&a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) cout << a[q.front()] << " ";
    }
}