題目描述
在幻想鄉，琪露諾是以笨蛋聞名的冰之妖精。

某一天，琪露諾又在玩速凍青蛙，就是用冰把青蛙瞬間凍起來。但是這只青蛙比以往的要聰明許多，在琪露諾來之前就已經跑到了河的對岸。于是琪露諾決定到河岸去追青蛙。

小河可以看作一列格子依次編號為0到N，琪露諾只能從編號小的格子移動到編號大的格子。而且琪露諾按照一種特殊的方式進行移動，當她在格子i時，她只移動到區間[i+l,i+r]中的任意一格。你問為什么她這么移動，這還不簡單，因為她是笨蛋啊。

每一個格子都有一個冰凍指數A[i]，編號為0的格子冰凍指數為0。當琪露諾停留在那一格時就可以得到那一格的冰凍指數A[i]。琪露諾希望能夠在到達對岸時，獲取最大的冰凍指數，這樣她才能狠狠地教訓那只青蛙。

但是由于她實在是太笨了，所以她決定拜托你幫它決定怎樣前進。

開始時，琪露諾在編號0的格子上，只要她下一步的位置編號大于N就算到達對岸。

輸入格式
第1行：3個正整數N, L, R

第2行：N+1個整數，第i個數表示編號為i-1的格子的冰凍指數A[i-1]

輸出格式
一個整數，表示最大冰凍指數。保證不超過2^31-1

輸入輸出樣例
輸入 #1
5 2 3
0 12 3 11 7 -2
輸出 #1
11

說明/提示
對于60%的數據：N <= 10,000

對于100%的數據：N <= 200,000

對于所有數據 -1,000 <= A[i] <= 1,000且1 <= L <= R <= N

解題思路：
由于對于每一次$i$，均是從$arr[i+l]$到$arr[i+r]$中挑選一個最大的值，于是我們就可以用單調隊列維護這個最大值即可。

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
typedef pair<int,int> p;
p arr[200100];
deque<p> q;
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int n,l,r;scanf("%d %d %d",&n,&l,&r);rep(i,0,n) {scanf("%d",&arr[i].second);arr[i].first=i;}arr[n+1].second=0;arr[n+1].first=n+1;q.push_back(arr[n+1]);lep(i,n-l,0) {while(!q.empty()&&arr[i+l].second>=q.back().second) {q.pop_back();}q.push_back(arr[i+l]);if(q.front().first>i+r) {q.pop_front();}arr[i].second=arr[i].second+q.front().second;}printf("%d\n",arr[0].second);return 0;
}