BZOJ3831 [Poi2014]Little Bird

2015.01.13 10:12 Tue| 2 visits oi_2015| 2015_刷题日常| Text

Solution

再不刷它就土了系列!!!

最简单的双端队列解决问题 -_-||

Code

#include <bits/stdc++.h>
using namespace std;
#define N 1000005

deque<int> q;
int n, m, f[N], a[N];

inline int read()
{
    int x=0, f=1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int getans(int k)
{
    memset(f, 0x3f, sizeof f);
    q.clear();
    f[1] = 0; q.push_back(1);
    for (int i = 2; i <= n; ++i)
    {
        while (!q.empty() && q.front() < i - k)
            q.pop_front();
        f[i] = f[q.front()] + (a[q.front()] <= a[i]);
        while (!q.empty() && (f[q.back()] == f[i] ?
                                        a[q.back()] < a[i] : f[q.back()] > f[i]))
            q.pop_back();
        q.push_back(i);
    }
    return f[n];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    cin >> m;
    for (int i = 1; i <= m; ++i)
        printf("%d\n",getans(read()));
}