CF A city day

求一个点使得它在i-x到i+y区间内最小

双端队列做法

求i-1 到 i-x 区间内的最小值  类似于 滑动窗口 与i进行比较

//
#include<bits/stdc++.h>
using namespace std;
deque < int > Q;
#define maxnn 200000
int a[maxnn];
int mark1[maxnn],mark2[maxnn];
int main()
{
    int n,x,y;
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    Q.push_back(1);
    mark1[1]=1;
    for(int i=2;i<=n;i++)
    {
        mark1[i]=1;
        while(Q.size()&&Q.front()<i-x) Q.pop_front();
        if(Q.size()&&a[Q.front()]<a[i]) mark1[i]=0;
        while(Q.size()&&a[Q.back()]>a[i]) Q.pop_back();
        Q.push_back(i); 
    }
    Q.clear();
    Q.push_back(n);
    mark2[n]=1;
    for(int i=n-1;i>=1;i--)
    {
        mark2[i]=1;
        while(Q.size()&&Q.front()>i+y) Q.pop_front();
        if(Q.size()&&a[Q.front()]<a[i]) mark2[i]=0;
        while(Q.size()&&a[Q.back()]>a[i]) Q.pop_back();
        Q.push_back(i); 
    }
        for(int i=1;i<=n;i++)
        {
            if(mark1[i]&mark2[i])
            {
            cout<<i;
            return 0;
            }
        }
    
    
    
}