ACM模版

描述

题解

这个题的解法真是奇思妙想，一开始只是知道单调栈搞不定，至于为什么，因为话题这里写得不是单调栈啊……当然也不是特别理解为什么要用链表，看了题解后恍然大悟。

对于这种题，尽管用的数据结构变了，但是不变的是逐个求贡献，那么这个题我们需要根据什么求贡献呢？我们可以求出对于每一个值的位置 now 的相关四个数，分别是位于他前边的两个大于他的数 l1、l2 以及位于他后边的两个大于他的数 r1,r2 。具体的位置关系是： l2∼l1∼now∼r1∼r2 ，这样，贡献就容易求了，因为存在两种合法贡献，设左右端点分别为 L、R ：
1、 L∈[l2+1,l1],R∈[now,r1−1]
2、 L∈[l1+1,now],R∈[r1,r2−1]
这样，根据乘法原理我们就能够轻易求出来每个值的贡献了。

剩下的就是优化了，我们可以采用桶排进行优化，然后维护一个链表，从小到大枚举数，为了保证每次都能 O(1) 求出来每个数的 l1,l2,r1,r2 ，我们需要枚举一个就删除一个，这样每次枚举一个数，这个数都是链表中最小的。这部分看代码不难理解，over！

代码

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

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

int n, A, B, p;
int a[MAXN];
int b[MAXN];
int cnt[MAXN];
int net[MAXN];
int pre[MAXN];
int l1, r1, l2, r2;

void del(int now)
{
    net[pre[now]] = net[now];
    pre[net[now]] = pre[now];
}

int main()
{
    cin >> n >> a[0] >> A >> B >> p;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = (1LL * A * a[i - 1] + B) % p;
        cnt[a[i]]++;
    }
    for (int i = 1; i < p; ++i)
    {
        cnt[i] += cnt[i - 1];
    }
    // 桶排后，b 指向元素在 a 中的位置，b 是排好序的
    for (int i = n; i >= 1; --i)
    {
        b[cnt[a[i]]--] = i;
    }
    // 仿真链表
    for (int i = 1; i <= n; ++i)
    {
        net[i] = i + 1;
        pre[i] = i - 1;
    }

    int now;
    ll ans = 0;
    pre[0] = 0;
    net[n + 1] = n + 1;
    for (int i = 1; i <= n; ++i)
    {
        now = b[i];
        l1 = pre[now];
        r1 = net[now];
        l2 = pre[l1];
        r2 = net[r1];
        // 乘法原理求每个数的贡献
        ans = ans + 1LL * a[l1] * a[now] % MOD * (l1 - l2) % MOD * (r1 - now) % MOD;
        if (ans >= MOD)
        {
            ans -= MOD;
        }
        ans = ans + 1LL * a[r1] * a[now] % MOD * (r2 - r1) % MOD * (now - l1) % MOD;
        if (ans >= MOD)
        {
            ans -= MOD;
        }
        del(now);
    }

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

    return 0;
}