有 stack，有 queue
那理論上，應該要有一個 STL，同時具有 stack 跟 queue 的功能啊？
也就是說，要可以從前面跟後面拿東西、刪東西。
先介紹這個比較厲害的！
它不只可以從前面跟後面拿東西、刪東西，還可以隨時知道第 k 項是什麼！
也就是說，它其實更像是可以從前方插入移除的 vector。
語法
宣告：
加入元素：
1
2
| dq.push_back(1);
dq.push_front(5);
|
刪除元素：
1
2
| dq.pop_back();
dq.pop_front();
|
此外，由於支援隨機存取，因此如 sort、lower_bound 等在 vector 可以用的函式，在 deque 中當然也可以用！
缺點
慢。
雖然各操作仍是 $O(1)$，但大約比 vector 慢 3 倍。
沒事不會用到它，沒事不要用到它。
對了，stack 跟 queue 其實是基於 deque 上的結構，也就是說，當你以為你在用 stack，其實程式幫你宣告的是 deque，即使你並不需要那些 deque 的功能。
因此，stack 跟 queue 跟 deque 一樣慢。
練習
★★★★TIOJ 1618
★★★★TIOJ 1566
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
ll n, k, h[500005], b[500005];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> h[i];
for(int i=1;i<=n;i++) cin >> b[i];
deque<pii> dq;
ll cur = 0, ans = -1e18, ansid = 0;
for(ll i=1;i<=n;i++){
while(!dq.empty() && dq[0].first <= i-k){
cur -= b[dq[0].first];
dq.pop_front();
}
while(!dq.empty() && dq[dq.size()-1].second <= h[i]){
cur -= b[dq[dq.size()-1].first];
dq.pop_back();
}
cur += b[i];
dq.emplace_back(i, h[i]);
if(cur > ans){
ans = cur;
ansid = i;
}
}
cout << ansid << " " << ans << '\n';
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
ll n, m, k, h[10000005];
deque<pii> mx, mn;
vector<pii> ans;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
for(int i=1;i<=n;i++) cin >> h[i];
for(int i=1;i<=n;i++){
while(!mx.empty() && mx[0].first <= i-m) mx.pop_front();
while(!mn.empty() && mn[0].first <= i-m) mn.pop_front();
while(!mx.empty() && mx[mx.size()-1].second <= h[i]) mx.pop_back();
while(!mn.empty() && mn[mn.size()-1].second >= h[i]) mn.pop_back();
mx.emplace_back(i, h[i]);
mn.emplace_back(i, h[i]);
if(mx[0].second - mn[0].second == k){
if(i <= m) ans.emplace_back(1, i);
else ans.emplace_back(i-m+1, i);
}
}
for(int i=n+1;i<n+m;i++){
while(!mx.empty() && mx[0].first <= i-m) mx.pop_front();
while(!mn.empty() && mn[0].first <= i-m) mn.pop_front();
if(mx[0].second - mn[0].second == k){
if(i-m > 0) ans.emplace_back(i-m+1, n);
}
}
cout << ans.size() << '\n';
for(auto i:ans){
cout << i.first << " " << i.second << '\n';
}
}
|