HDU 6047 - Maximum Sequence | 2017 Multi-University Training Contest 2

/*

HDU 6047 - Maximum Sequence [ 单调队列 ]

题意：

	起初给出n个元素的数列 A[N], B[N]

	对于 A[]的第N+K个元素，从B[N]中找出一个元素B[i]，在 A[] 中找到一个数字A[p]满足 B[i] <= p <= N+K-1

	令 A[N+K] = A[p]-p，直到A[]的长度等于2N

	问 A[N+1] + A[N+2] + ... + A[N<<1] 最大是多少

分析：

	将A[]中元素全部减去其下标

	将B[]排序，可分析一定是从小往大选择最优

	每次从可以选择的A[]中选最大的一个，过程用单调队列来实现

编码时长：13分钟

*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const LL MOD = 1e9+7;

const int N = 250004;

int n;

int a[N<<1], b[N];

struct Node {

    int x, id;

}q[N<<1];

int head, tail;

void solve()

{

    for (int i = 1; i <= n; i++) a[i] -= i;

    head = tail = 0;

    for (int i = 1; i <= n; i++)

    {

        while (head < tail && q[tail-1].x < a[i]) tail--;

        q[tail++] = Node{a[i], i};

    }

    for (int i = n+1; i <= n<<1; i++)

    {

        while (head < tail && q[head].id < b[i-n]) head++;

        a[i] = q[head].x-i;

        while (head < tail && q[tail-1].x < a[i]) tail--;

        q[tail++] = Node{a[i], i};

    }

}

int main()

{

    while (~scanf("%d", &n))

    {

        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

        sort(b+1, b+1+n);

        solve();

        LL ans = 0;

        for (int i = n+1; i <= n<<1; i++)

        {

            ans += a[i] + i;

            if (ans > MOD) ans -= MOD;

            if (ans < 0) ans += MOD;

        }

        ans = (ans%MOD + MOD) % MOD;

        printf("%lld\n", ans);

    }

}