基准时间限制：1 秒 空间限制：262144 KB 分值: 80 难度：5级算法题
小A和小B在玩一个游戏。
他们拥有一个数列。
小A在该数列中选择出最大的那个数，然后移出该数列。
小B在剩下的数列中选择出最大的那个数，并乘上小A的那个值，作为他的答案。
那么现在问题来了。
他们现在想换一种玩法，把该数列长度大于等于2的区间（即n*(n-1)/2个区间）单独作为一个数列拿出来，然后做一次上述的游戏，然后计算出小B所有的答案，考虑到输出那么多数比较困难，因此他们想知道所有答案和对 1e9+7取模后的值。
样例解释：
该数列为2，0，1，2
对于1-2的区间答案为0
对于1-3的区间答案为2
对于1-4的区间答案为4
对于2-3的区间答案为0
对于2-4的区间答案为2
对于3-4的区间答案为2
Input
第一行五个数n，a0，a，b，p(1<=n,a0,a,b,p<=10000000)。
该数列的构造方法为，a[i]=(a[i-1]*a+b)%p。该数列的下标为1~n。
Output
1行，表示答案。
Input示例
4 1 1 1 3
Output示例
10
题解：
设当前为now
设now之前第一个比他大的数的位置为L1，L1之前第一个比他大的数的位置为L2
设now之后第一个比他大的数的位置为R1，R1之后第一个比他大的数的位置为R2
那么对于now，其作为次大值存在的区间有：
1、左端点在[L2+1，L1]之间，右端点在[now,R1-1]之间
2、左端点在[L1+1，now]之间，右端点在[R1,R2-1]之间。
因为此题数据范围n在1~1e7，最大值p范围在1~1e7，所以考虑用桶排序优化合适。
然后维护一个链表，从小到大枚举数，枚举完就删除，保证每次枚举的数是链表中最小的。这样就可以控制复杂度在O（N）啦。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7+;
const int MOD = 1e9+;
int a[N], b[N];//b[i]=j 表示a[j]排序后在i位置
int vis[N];
int pre[N], nex[N];
void del(int now) {//删除now节点
nex[pre[now]] = nex[now];
pre[nex[now]] = pre[now];
}
int main() {
int n, aa, bb, p, i, j;
ll ans = ;
scanf("%d%d%d%d%d", &n, &a[], &aa, &bb, &p);
for(i = ; i <= n; ++i) a[i] = (1ll * a[i-] * aa + bb) % p;
//桶排序
for(i = ; i <= n; ++i) vis[a[i]]++;
for(i = ; i < p; ++i) vis[i] += vis[i-];
for(i = n; i >= ; --i) b[vis[a[i]]--] = i;
//链表
pre[] = ; nex[n+] = n+;
for(i = ; i <= n; ++i) {
pre[i] = i - ;
nex[i] = i + ;
}
for(i = ; i <= n; ++i) {
int now = b[i];
int l1 = pre[now];
int l2 = pre[l1];
int r1 = nex[now];
int r2 = nex[r1];
ans = (ans + (1ll*a[now]*a[l1]%MOD*(l1-l2)%MOD*(r1-now)%MOD)) % MOD;
ans = (ans + (1ll*a[now]*a[r1]%MOD*(now-l1)%MOD*(r2-r1)%MOD)) % MOD;
del(now);
}
printf("%lld\n", ans);
return ;
}