ACM模版

描述


题解

像这种问题，很明显是单调栈，不过这里的单调栈有些差异，因为栈本身不是正常的栈，出只能尾出，入则可以首尾入，那么维护单调栈时，我们一样无法只从一个方向进行维护，但是可以肯定的是我们只需要维护一个加强版单调栈就好了。

这里维护一个单调递增栈，当加入操作是从尾部加入时，我们从单调递增栈的栈顶进行添加，不过添加规则是大于栈顶方可添加；当加入操作是从头部加入时，我们从但带哦递增栈的栈底进行添加，不过添加规则是先将单调递增栈内的所有大于这个元素的抛出，然后将这个元素插入。这样的话，很容易便可以明白，我们维护的是一个从栈底到栈顶单调递增的单调栈，当然这里还有一个删除操作，删除时只能从尾部删除，所以我们从实际栈中删除时要考虑他是否也在单调递增栈中，如果在的话一定是在栈顶，所以只消得对比一下栈顶和要删除的元素是否相同，相同的话一并删除，否则只需要删除题中所给栈内的尾部元素，而不用删除单调递增栈中的元素。

至于这里的双向添加，我们需要用到 STL 中的一个容器，叫做那个 deque ，剩下的就没有什么了。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAXN = 1e7 + 10;

ll n, A, B, C, a, b, mod;
ll x[MAXN];
deque<ll> s, s_;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

signed main()
{
    scan_d(n), scan_d(A), scan_d(B), scan_d(C), scan_d(x[0]), scan_d(a), scan_d(b), scan_d(mod);

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        x[i] = (x[i - 1] * a + b) % mod;
        if (x[i] % (A + B + C) < A || s.size() < 2)
        {
            s.push_back(i);
            if (s_.empty() || x[s_.back()] <= x[i])
            {
                s_.push_back(i);
            }
            ans = (ans + x[s_.back()]) % MOD;
        }
        else if (A <= x[i] % (A + B + C) && x[i] % (A + B + C) < A + B)
        {
            s.push_front(i);
            while (!s_.empty() && x[s_.front()] < x[i])
            {
                s_.pop_front();
            }
            s_.push_front(i);
            ans = (ans + x[s_.back()]) % MOD;
        }
        else
        {
            if (s_.back() == s.back())
            {
                s_.pop_back();
            }
            s.pop_back();
            if (!s_.empty())
            {
                ans = (ans + x[s_.back()]) % MOD;
            }
        }
    }

    printf("%lld", ans);

    return 0;
}