(POI) XXI OI Round II - day 2 Task Little Bird

https://szkopul.edu.pl/problemset/problem/xfpVU8vFP2RzZ0hrqWq9kTZM/site/?key=statement

只能拜中國大神了<(_ _)>我這份code是看提示之後才AC的><。

#include <iostream>
#include <cstdio>
#include <utility>
#include <queue>
using namespace std;

const int N = 1000006;

#define F first
#define S second

typedef pair<int,int> pii;
typedef pair<pii,int> piii;

int a[N];
int dp[N];

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
    }
    int q;
    scanf("%d",&q);
    while (q--)
    {
        int k;
        scanf("%d",&k);
        deque<piii> dq;
        dp[1] = 0;
        dq.push_back(make_pair( make_pair(dp[1],-a[1]),1 ));
        #define SZ(x) ((int)(x).size())
        for (int i=2;n>=i;i++)
        {
            while (SZ(dq) &&dq[0].S == i-k-1) dq.pop_front();
            piii p = dq[0];
            dp[i] = (p.F.F + (-p.F.S > a[i]?0:1));
            piii now = make_pair( make_pair(dp[i],-a[i]),i );
            while (SZ(dq) && dq.back() > now)
            {
                dq.pop_back();
            }
            dq.push_back(now);
        }
        printf("%d\n",dp[n]);
    }
}